Project03 Adding Lottery and Stride Scheduling to xv6

Deliverables due Wed Apr 23 by 6:25pm in your project03 GitHub repo

• A copy of xv6 with your implementations of lottery scheduling and stride scheduling
• Your source code should conform to xv6 formatting conventions.
• Your Project03 repo should not have any extraneous files or build artifacts
• You will demo you solution in Lab Section on Wed Apr 23.

Overview

Proportional share scheduling is an alternative to round robin scheduling which is the default scheduler in xv6. Two popular forms of proportional are lottery scheduling and stride scheduling. We will implement simple versions of both.

Implementation Approaches

Your goal is to modify the xv6 kernel to support lottery scheduling and stride scheduling as described below. You will need to add two new system calls also detailed below to change the scheduler mode and to set a ticket/share value for a specific process. You will only be modifying or adding to the kernel. You have a few options to get this work done:

1. Read this spec, copy schedtest.c to your user directory and implement the system calls and modifications to the kernel directly.
2. If you get stuck on how to get started, use the Roo Code CS Tutor Role (AI Coding) to get help, but not a complete solution.
3. If you are still stuck, I would do the following. Point Roo Code to schedtest.c in your repo and then ask it to implement lottery scheduling, but not stride scheduling. Then try to implement stride scheduling yourself.
4. If you are still having trouble, you can have Roo Code generate solutions to both lottery scheduling and stride scheduling. Make sure that you look closely at the solutions and make sure to ask Roo Code to explain them to you as you are still responsible for understanding the code you submit and on the final exam.

Lottery Scheduling

Lottery scheduling is a probabilistic scheduling algorithm used in operating systems to manage the execution of processes. In this approach, each process is assigned a certain number of “lottery tickets,” which represent its share of the CPU. When the scheduler needs to select the next process to run, it conducts a random lottery draw where each ticket has an equal chance of being selected. The process holding the winning ticket gets scheduled to run. The more tickets a process has, the higher its probability of being chosen, allowing for flexible and fine-grained control over resource allocation.

One of the key advantages of lottery scheduling is its simplicity and fairness. It naturally supports proportional-share scheduling, where processes can be allocated CPU time relative to their importance or priority by adjusting their ticket count. Additionally, it is easy to implement and extend—for instance, tickets can be transferred between processes or inherited by child processes in a fork. However, because of its randomness, lottery scheduling does not provide strict guarantees about short-term scheduling behavior, which may be a limitation for real-time systems or latency-sensitive applications.

https://www.usenix.org/legacy/publications/library/proceedings/osdi/full_papers/waldspurger.pdf

Stride Scheduling

Stride scheduling is a deterministic proportional-share CPU scheduling algorithm used in operating systems. Each process is assigned a “stride,” which is inversely proportional to the number of tickets (or shares) it holds: the more tickets a process has, the smaller its stride. The scheduler maintains a “pass value” for each process, initially set to zero. At each scheduling decision, the process with the lowest pass value is chosen to run, and its pass value is incremented by its stride. This approach ensures that processes with more tickets (i.e., higher priority or share) are scheduled more frequently than those with fewer.

Compared to lottery scheduling, stride scheduling offers more predictable and repeatable behavior since it avoids randomness. It provides strong fairness guarantees over time, as each process gets CPU time proportional to its assigned shares, and deviations from this ideal behavior are bounded. This makes stride scheduling particularly well-suited for systems that require deterministic scheduling, such as those with soft real-time requirements. However, it is slightly more complex to implement than lottery scheduling and requires careful handling of large stride values and potential overflow in pass counters.

https://www.waldspurger.org/carl/papers/stride-mit-tm528.pdf

Stride Scheduling Visualization

This diagram illustrates how stride scheduling works with two processes having different weights:

• Process A: 20 tickets (20% of CPU) → stride = 10,000,000 / 20 = 500,000
• Process B: 80 tickets (80% of CPU) → stride = 10,000,000 / 80 = 125,000

flowchart TD
    subgraph "Initial State"
        A0["Process A<br>pass = 0<br>stride = 500,000"]
        B0["Process B<br>pass = 0<br>stride = 125,000"]
    end

    subgraph "Round 1"
        A1["Process A<br>pass = 500,000<br>stride = 500,000"]
        B1["Process B<br>pass = 0<br>stride = 125,000"]
        note1["A selected (tie broken)<br>A.pass += A.stride"]
    end

    subgraph "Round 2"
        A2["Process A<br>pass = 500,000<br>stride = 500,000"]
        B2["Process B<br>pass = 125,000<br>stride = 125,000"]
        note2["B selected<br>B.pass += B.stride"]
    end

    subgraph "Round 3"
        A3["Process A<br>pass = 500,000<br>stride = 500,000"]
        B3["Process B<br>pass = 250,000<br>stride = 125,000"]
        note3["B selected<br>B.pass += B.stride"]
    end

    subgraph "Round 4"
        A4["Process A<br>pass = 500,000<br>stride = 500,000"]
        B4["Process B<br>pass = 375,000<br>stride = 125,000"]
        note4["B selected<br>B.pass += B.stride"]
    end

    subgraph "Round 5"
        A5["Process A<br>pass = 500,000<br>stride = 500,000"]
        B5["Process B<br>pass = 500,000<br>stride = 125,000"]
        note5["B selected<br>B.pass += B.stride"]
    end

    subgraph "Round 6"
        A6["Process A<br>pass = 1,000,000<br>stride = 500,000"]
        B6["Process B<br>pass = 500,000<br>stride = 125,000"]
        note6["A selected (tie broken)<br>A.pass += A.stride"]
    end

    subgraph "Round 7"
        A7["Process A<br>pass = 1,000,000<br>stride = 500,000"]
        B7["Process B<br>pass = 625,000<br>stride = 125,000"]
        note7["B selected<br>B.pass += B.stride"]
    end

    subgraph "Round 8"
        A8["Process A<br>pass = 1,000,000<br>stride = 500,000"]
        B8["Process B<br>pass = 750,000<br>stride = 125,000"]
        note8["B selected<br>B.pass += B.stride"]
    end

    subgraph "Round 9"
        A9["Process A<br>pass = 1,000,000<br>stride = 500,000"]
        B9["Process B<br>pass = 875,000<br>stride = 125,000"]
        note9["B selected<br>B.pass += B.stride"]
    end

    subgraph "Round 10"
        A10["Process A<br>pass = 1,000,000<br>stride = 500,000"]
        B10["Process B<br>pass = 1,000,000<br>stride = 125,000"]
        note10["B selected<br>B.pass += B.stride"]
    end

    A0 --> A1 --> A2 --> A3 --> A4 --> A5 --> A6 --> A7 --> A8 --> A9 --> A10
    B0 --> B1 --> B2 --> B3 --> B4 --> B5 --> B6 --> B7 --> B8 --> B9 --> B10

Explanation

1. Initial State: Both processes start with pass = 0, but have different stride values based on their tickets.
2. Round 1: With equal pass values, A is selected (tie-breaking by process list order). A’s pass increases by its stride (500,000).
3. Round 2: B’s pass (0) < A’s pass (500,000), so B runs next. B’s pass increases to 125,000.
4. Round 3: B’s pass (125,000) < A’s pass (500,000), so B runs again. B’s pass increases to 250,000.
5. Round 4: B’s pass (250,000) < A’s pass (500,000), so B runs again. B’s pass increases to 375,000.
6. Round 5: B’s pass (375,000) < A’s pass (500,000), so B runs again. B’s pass increases to 500,000.
7. Round 6: With equal pass values (500,000), A is selected (tie-breaking). A’s pass increases to 1,000,000.
8. Round 7: B’s pass (500,000) < A’s pass (1,000,000), so B runs. B’s pass increases to 625,000.
9. Round 8: B’s pass (625,000) < A’s pass (1,000,000), so B runs again. B’s pass increases to 750,000.
10. Round 9: B’s pass (750,000) < A’s pass (1,000,000), so B runs again. B’s pass increases to 875,000.
11. Round 10: B’s pass (875,000) < A’s pass (1,000,000), so B runs again. B’s pass increases to 1,000,000.

After these 10 rounds:

• Process A ran 2 times (20%)
• Process B ran 8 times (80%)

This aligns perfectly with the assigned weights of 20% and 80%, demonstrating how stride scheduling maintains proportional CPU allocation over time.

Table View of Pass Values

Over a longer period, the CPU allocation approaches the ideal 20%/80% distribution.

Stride Scheduling Example with 3 Processes:

• Process A: 10 tickets (10% of CPU) → stride = 10,000,000 / 10 = 1,000,000
• Process B: 40 tickets (40% of CPU) → stride = 10,000,000 / 40 = 250,000
• Process C: 50 tickets (50% of CPU) → stride = 10,000,000 / 50 = 200,000

System Call Specifications for xv6 Proportional Share Scheduling

This document provides specifications for the system calls required to implement and control lottery and stride scheduling in xv6.

System Calls Overview

Two new system calls must be implemented:

1. setscheduler - Change the global scheduling algorithm
2. setprocshare - Set a process’s proportional CPU share (tickets)

Detailed Specifications

int setscheduler(int sched_mode)

Purpose:
Changes the scheduling algorithm used by the xv6 kernel.

Parameters:

• sched_mode: The scheduling mode to set
  • 0: Standard round-robin scheduling (default)
  • 1: Lottery scheduling
  • 2: Stride scheduling

Return Value:

• 0 on success
• -1 on failure

Error Conditions:

• Returns -1 if the specified sched_mode is invalid (not 0, 1, or 2)

Behavior:

• When switching to lottery or stride scheduling (modes 1 or 2), all runnable processes should initially have equal shares (tickets) unless explicitly set otherwise.
• When switching from standard to lottery or stride scheduling, the scheduler should perform any necessary initialization for the selected scheduling algorithm.
• When switching to stride scheduling (mode 2), all processes should have their pass values reset to 0 to ensure fair scheduling starts.
• This system call can only be executed by a process with appropriate privileges (e.g., init or shell).

Implementation Requirements:

• A global variable sched_mode must be maintained in the kernel to track the current scheduling mode.
• The scheduler function in proc.c must check this variable to determine which scheduling algorithm to use.
• Thread safety must be ensured when changing the scheduling mode.

int setprocshare(int pid, int tickets)

Purpose:
Sets the number of tickets (proportional CPU share) for a specific process. This affects how frequently the process is scheduled under lottery and stride scheduling.

Parameters:

• pid: The process ID of the target process
• tickets: The number of tickets to assign to the process (1-100)
  • This value represents the relative weight for CPU allocation
  • Higher values give the process a larger share of CPU time

Return Value:

• 0 on success
• -1 on failure

Error Conditions:

• Returns -1 if the specified pid does not exist or is invalid
• Returns -1 if the tickets value is less than 1 (processes must have at least 1 ticket)
• Returns -1 if the current scheduling mode is standard (mode 0), as tickets are only relevant in lottery and stride scheduling

Behavior:

• For lottery scheduling: Updates the process’s ticket count, affecting its probability of selection
• For stride scheduling: Updates both the process’s ticket count and recalculates its stride value using the formula stride = STRIDE_MAX / tickets
• Does not affect the process’s current pass value in stride scheduling
• The change takes effect the next time the scheduler runs

Implementation Requirements:

• The process control block (struct proc in proc.h) must be extended to include:
  • int tickets - Number of tickets for lottery/stride scheduling
  • uint stride - The stride value (for stride scheduling)
  • uint pass - The pass value (for stride scheduling)
• The implementation must ensure that processes always have at least 1 ticket.
• For stride scheduling, a large constant (STRIDE_MAX) should be defined to calculate stride values and avoid potential integer division issues.
• Thread safety must be ensured by acquiring the appropriate locks before modifying a process’s ticket count.

Scheduler Implementation Behavior

The xv6 scheduler in proc.c should be modified to check the global sched_mode variable and use the appropriate scheduling algorithm:

• Mode 0 (Standard): Use the existing round-robin scheduler
• Mode 1 (Lottery):
  1. Sum tickets of all runnable processes
  2. Choose a random number within that range
  3. Select the process owning the winning ticket
• Mode 2 (Stride):
  1. Find the runnable process with the minimum pass value
  2. Run that process
  3. Increment its pass value by its stride value

Both lottery and stride scheduling should maintain the property that processes receive CPU time proportional to their ticket allocations.

Scheduler Test

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

// Function to do CPU-intensive work and count iterations
void
busywork(int *counter, int duration)
{
  int start = uptime();

  // Work until duration ticks have passed
  while(uptime() - start < duration)
    // Do some computation to burn CPU cycles
    for(int i = 0; i < 100000; i++)
      (*counter)++;
}

int
main(int argc, char *argv[])
{
  int pid1, pid2;
  int counter1 = 0, counter2 = 0;
  int status;
  int duration = 50;  // Default test duration in timer ticks

  if(argc > 1){
    duration = atoi(argv[1]);
    if(duration <= 0)duration = 50;
  }

  printf("Proportional Share Scheduling Test\n");
  printf("==================================\n");

  // First test with standard scheduler
  printf("Running with standard scheduler for %d ticks...\n", duration);

  pid1 = fork();
  if(pid1 < 0){
    printf("Fork failed\n");
    exit(1);
  }

  if(pid1 == 0){
    // Child process 1
    sname("proc-std-1");
    counter1 = 0;
    busywork(&counter1, duration);
    printf("Process 1 (standard): %d iterations\n", counter1);
    exit(0);
  }

  pid2 = fork();
  if(pid2 < 0){
    printf("Fork failed\n");
    kill(pid1);
    exit(1);
  }

  if(pid2 == 0){
    // Child process 2
    sname("proc-std-2");
    counter2 = 0;
    busywork(&counter2, duration);
    printf("Process 2 (standard): %d iterations\n", counter2);
    exit(0);
  }

  // Wait for processes to complete
  wait(&status);
  wait(&status);

  // Switch to lottery scheduler
  printf("\nSwitching to lottery scheduler...\n");
  if(setscheduler(1) < 0){
    printf("Failed to set scheduler mode\n");
    exit(1);
  }

  printf("Running with 10:90 share ratio for %d ticks...\n", duration);

  // Create first child process (10% share)
  pid1 = fork();
  if(pid1 < 0){
    printf("Fork failed\n");
    exit(1);
  }

  if(pid1 == 0){
    // Child process 1 (10% share)
    sname("proc-10pct");
    counter1 = 0;
    busywork(&counter1, duration);
    printf("Process 1 (10%%): %d iterations\n", counter1);
    exit(0);
  }

  // Create second child process (90% share)
  pid2 = fork();
  if(pid2 < 0){
    printf("Fork failed\n");
    kill(pid1);
    exit(1);
  }

  if(pid2 == 0){
    // Child process 2 (90% share)
    sname("proc-90pct");
    counter2 = 0;
    busywork(&counter2, duration);
    printf("Process 2 (90%%): %d iterations\n", counter2);
    exit(0);
  }

  // Set process shares
  if(setprocshare(pid1, 10) < 0)    // 10% of CPU
    printf("Failed to set share for process 1\n");

  if(setprocshare(pid2, 90) < 0)    // 90% of CPU
    printf("Failed to set share for process 2\n");

  // Wait for processes to complete
  wait(&status);
  wait(&status);

  // Calculate and display the ratio
  printf("\nExpected ratio (process2:process1) is approximately 9:1\n");

  // Switch to stride scheduler
  printf("\nSwitching to stride scheduler...\n");
  if(setscheduler(2) < 0){
    printf("Failed to set stride scheduler mode\n");
    exit(1);
  }

  printf("Running with 10:90 share ratio for %d ticks using stride scheduling...\n", duration);

  // Create first child process (10% share)
  pid1 = fork();
  if(pid1 < 0){
    printf("Fork failed\n");
    exit(1);
  }

  if(pid1 == 0){
    // Child process 1 (10% share)
    sname("stride-10pct");
    counter1 = 0;
    busywork(&counter1, duration);
    printf("Process 1 (stride 10%%): %d iterations\n", counter1);
    exit(0);
  }

  // Create second child process (90% share)
  pid2 = fork();
  if(pid2 < 0){
    printf("Fork failed\n");
    kill(pid1);
    exit(1);
  }

  if(pid2 == 0){
    // Child process 2 (90% share)
    sname("stride-90pct");
    counter2 = 0;
    busywork(&counter2, duration);
    printf("Process 2 (stride 90%%): %d iterations\n", counter2);
    exit(0);
  }

  // Set process shares
  if(setprocshare(pid1, 10) < 0)    // 10% of CPU
    printf("Failed to set share for process 1\n");

  if(setprocshare(pid2, 90) < 0)    // 90% of CPU
    printf("Failed to set share for process 2\n");

  // Wait for processes to complete
  wait(&status);
  wait(&status);

  // Calculate and display the ratio
  printf("\nExpected ratio (process2:process1) is approximately 9:1\n");
  printf("Stride scheduling should provide more deterministic results than lottery scheduling\n");

  // Switch back to standard scheduler
  if(setscheduler(0) < 0)
    printf("Failed to revert scheduler mode\n");
  printf("Switched back to standard scheduler\n");

  printf("\nTest completed\n");
  return 0;
}

Scheduler Test Output

$ schedtest
Proportional Share Scheduling Test
==================================
Running with standard scheduler for 50 ticks...
Process 1 (standard): 658200000 iterations
Process 2 (standard): 690000000 iterations

Switching to lottery scheduler...
Running with 10:90 share ratio for 50 ticks...
Process 2 (90%): 1207800000 iterations
Process 1 (10%): 126400000 iterations

Expected ratio (process2:process1) is approximately 9:1

Switching to stride scheduler...
Running with 10:90 share ratio for 50 ticks using stride scheduling...
Process 1 (stride 10%): 120100000 iterations
Process 2 (stride 90%): 1215500000 iterations

Expected ratio (process2:process1) is approximately 9:1
Stride scheduling should provide more deterministic results than lottery scheduling
Switched back to standard scheduler

Test completed
$ 

Optional Work (10 point extra credit for each of these)

If you want to extend this work further, here are some options:

1. Add a more general version schedtest.c that can take command line arguments that will construct a test case scenario with different processes and weights:

$ schedtest2 50 A 10 B 40 C 50

This will run three processes with different ticket/share values for 50 ticks

1. Add Virtual Time Round Robin Scheduling (VTRR).

Virtual Time Round Robin (VTRR) is a deterministic proportional-share CPU scheduling algorithm designed to combine the fairness of weighted scheduling with the simplicity and responsiveness of round-robin execution. In VTRR, each process is assigned a weight (or share), and a virtual time value that represents the amount of CPU time it has effectively consumed. This virtual time increases when the process runs, based on the inverse of its weight—processes with higher weights accumulate virtual time more slowly, allowing them to be scheduled more frequently.

The scheduler maintains a round-robin queue of runnable processes and selects the process with the lowest virtual time to run next. If multiple processes have the same or similar virtual time, VTRR cycles through them in round-robin order, ensuring low overhead and smooth execution. Over time, this approach ensures that each process receives CPU time proportional to its assigned weight, while also offering predictable short-term scheduling behavior. VTRR is particularly well-suited for systems that require both fairness and interactivity, such as desktop environments or multimedia applications.

https://www.usenix.org/legacy/event/usenix01/full_papers/nieh/nieh.pdf

You must add a VTRR test to schedtest.c.