Are your Go Routines Treated Unfairly?

This project investigates fairness in the Go runtime scheduler and proposes modifications to improve scheduling for long-running goroutines. Our modifications introduce alternative scheduling policies to address starvation issues in Go’s concurrency model.

📌 Overview

The Go runtime scheduler is responsible for efficiently distributing goroutines across logical processors. However, we observed that long-running goroutines can suffer from starvation when preempted and placed back into the global run queue. This project presents scheduling enhancements to mitigate unfair scheduling and improve overall performance. We highlighted the two key problems in long running go routines:

• Long running go routines once preempted are kept back in the global runqueue, which then have to wait for one of the local queue to be empty to be pulled back into the logical processor’s local queue. This in a way is causing a starvation on long running go routines that execute for multiple time slices.
• Additionally when most of the processors preempt the long running go routines at once, they have to contend for the global run queue lock.

🚀 Modifications to the Go Runtime

We propose three key modifications to Go’s scheduling mechanism:

1️⃣ Cyclic Swapping of Go Routines

• Instead of placing preempted goroutines in the global run queue, they are passed to the next logical processor’s local queue.
• This reduces contention for the global queue and ensures preempted goroutines resume execution without waiting for an empty local queue.

2️⃣ Phase Splitting of Processors

• Logical processors are divided into two groups:
  • One group processes short-running goroutines.
  • The other processes long-running goroutines.
• Short-running goroutines transition into the long-running group upon preemption, ensuring a balanced workload distribution.

3️⃣ Phase Splitting with Differential Preemption

• Introduces a variable time slice:
  • Short-running processors maintain a standard 10ms time slice.
  • Long-running processors have an extended time slice (20ms).

• This reduces excessive preemption for long-running tasks, improving overall execution efficiency.

  

🔍 Experimental Setup

• We categorized workloads into short-running and long-running goroutines based on execution duration.
• We analyzed scheduler traces using the Go trace tool to observe scheduling patterns.
• Three workloads were tested:
  • Simple loops
  • Fibonacci computation
  • Matrix multiplication

Loop Short Running Go Routines

Loop Long Running Go Routines

📊 Findings

• The default Go scheduler can cause long-running goroutines to starve when short-running goroutines dominate the local queues.
• Our modified scheduler significantly reduces average wait times and improves fairness for long-running workloads.
• We identified additional Go runtime tuning parameters such as schedtick, timeslice, and work stealing batch size that can further refine performance.

Average Scheduler Wait Times per Go Routine in (s)

Global & Local Runqueue Sizes in normal operation

Global & Local Runqueue Sizes in phase splitting runtime scheduler

🔧 How to Build & Run

1. Clone the Go source code:

   ```sh git clone https://github.com/golang/go.git

2. Install the Go compiler from go.dev.

3. Replace the following files with our modified versions:

• src/runtime/runtime2.go

• src/runtime/proc.go

cp path/to/modified/runtime2.go go/src/runtime/
cp path/to/modified/proc.go go/src/runtime/

1. Set up the custom Go runtime:

export GOROOT=/path/to/custom/go
export PATH=$GOROOT/bin:$PATH

1. Run your Go programs using:

go run your_program.go

Yup this works like magic, no need to manually build the whole sourcefile using ./make.bash from the src directory.

📎 Additional Resources

• 📄 Project Report

• 🎥 Demo Video

Contributors

• Sai Vamsi Alisetti
• Abhishek Kumar