Skip to main content Link Menu Expand (external link) Document Search Copy Copied

Project 03 Practice Problems with Solutions

These practice problems are designed to help you understand the concepts and implementation details of proportional share scheduling in xv6.

Lottery Scheduling

Easy Problems

  1. Concept Understanding

    Problem: Explain the basic concept of lottery scheduling. How does a lottery scheduler decide which process to run next?

    Solution: Lottery scheduling is a probabilistic scheduling algorithm where each process is assigned a certain number of “lottery tickets” that represent its share of CPU time. When the scheduler needs to select the next process to run, it:

    1. Counts the total number of tickets held by all runnable processes
    2. Generates a random number between 0 and the total ticket count
    3. Traverses the list of processes, adding up tickets until it exceeds the random number
    4. The process that puts the sum over the random number is selected to run

    Lottery scheduling provides proportional share scheduling in a probabilistic way - processes with more tickets have a higher probability of being selected. It’s simple to implement but doesn’t guarantee precise CPU allocation in the short term.

  2. Lottery Algorithm Implementation

    Problem: In lottery scheduling, what key data structure or value must be maintained for each process, and how is the “winning process” selected?

    Solution: Each process must have a field to store its ticket count. In the xv6 implementation, this is the tickets field added to the struct proc:

    struct proc {
  // ... existing fields
  int tickets;  // Number of tickets for lottery scheduling
};

    The winning process is selected by:

    1. Summing the total tickets of all runnable processes
    2. Generating a random number within that range (e.g., using a simple linear congruential generator)
    3. Traversing the process list, accumulating tickets until exceeding the random number

    In code, this looks like:

    // Calculate total tickets of all runnable processes
int total_tickets = 0;
for(p = proc; p < &proc[NPROC]; p++) {
  if(p->state == RUNNABLE)
    total_tickets += p->tickets;
}
   
// Choose a random winner
int winner = rand() % total_tickets;
   
// Find the winning process
int counter = 0;
for(p = proc; p < &proc[NPROC]; p++) {
  if(p->state == RUNNABLE) {
    counter += p->tickets;
    if(counter > winner) {
      // This process wins - run it
      // ...
      break;
    }
  }
}

Moderate Problems

  1. Ticket Allocation Analysis

    Problem: Consider a system with three processes A, B, and C with 20, 30, and 50 tickets respectively. If the lottery scheduler makes 100 scheduling decisions:

    • What is the expected number of times each process will be selected?
    • What code would you need to modify in xv6 to implement this ticketing system?

    Solution:

    With ticket allocations of 20, 30, and 50, the total is 100 tickets.

    Expected selections in 100 decisions:

    • Process A (20 tickets): 20% of selections = 20 times
    • Process B (30 tickets): 30% of selections = 30 times
    • Process C (50 tickets): 50% of selections = 50 times

    Code modifications for xv6:

    1. Add a tickets field to the struct proc in proc.h:
      struct proc {
  // ... existing fields
  int tickets;  // Number of lottery tickets
};
    2. Initialize this field in allocproc() in proc.c:
      static struct proc*
allocproc(void)
{
  // ... existing code
  p->tickets = 1;  // Default is 1 ticket
  // ... rest of function
}
    3. Implement the setprocshare() system call to set ticket values: ```c int setproctickets(int pid, int tickets) { struct proc *p;

    if(tickets <= 0) return -1;

    for(p = proc; p < &proc[NPROC]; p++) { acquire(&p->lock); if(p->pid == pid) { p->tickets = tickets; release(&p->lock); return 0; } release(&p->lock); } return -1; // Process not found } ```

    1. Use setprocshare() to set the tickets for each process (20, 30, 50).

  2. System Call Requirements

    Problem: The project requires implementing the setprocshare(int pid, int tickets) system call. Explain:

    • What changes need to be made to the process control block (struct proc) to support this system call?
    • What validation checks should be performed in the implementation of this system call?
    • What happens when a process forks - should the child inherit the parent’s ticket count?

    Solution:

    Changes to process control block:

    struct proc {
  // ... existing fields
  int tickets;  // Number of tickets for lottery scheduling
};

    Validation checks in the system call:

    1. Check if the PID exists
    2. Ensure the ticket count is valid (greater than zero)
    3. Verify that lottery scheduling is currently active (sched_mode == 1)
    int
sys_setprocshare(void)
{
  int pid, tickets;
     
  // Get arguments
  argint(0, &pid);
  argint(1, &tickets);
     
  // Validate tickets
  if(tickets <= 0)
    return -1;
       
  // Make sure we're in lottery or stride scheduling mode
  if(sched_mode == 0)
    return -1;
       
  // Set the tickets
  return setproctickets(pid, tickets);
}

    Process fork behavior:

    Yes, the child should inherit the parent’s ticket count during fork. This maintains the relative priorities across fork operations and is implemented in the fork() function:

    int
fork(void)
{
  // ... existing code
     
  // Copy process state to child
  np->tickets = p->tickets;  // Child inherits parent's ticket count
     
  // ... rest of function
}

Hard Problem

  1. Full Implementation Analysis

    Problem: When implementing lottery scheduling in xv6, several considerations must be addressed:

    • How would you modify the scheduler function in proc.c to implement lottery scheduling?
    • What issues might arise if the total number of tickets becomes very large?
    • How would you handle the case when a process with tickets terminates?
    • What synchronization challenges exist when updating ticket counts and selecting the winning process?
    • Describe a test case that would verify your lottery scheduler is working correctly.

    Solution:

    Scheduler function modification:

    void
scheduler(void)
{
  struct proc *p;
  struct cpu *c = mycpu();
     
  c->proc = 0;
  for(;;) {
    intr_on();
       
    if(sched_mode == 1) {  // Lottery scheduling
      // Count total tickets
      int total_tickets = 0;
      for(p = proc; p < &proc[NPROC]; p++) {
        acquire(&p->lock);
        if(p->state == RUNNABLE)
          total_tickets += p->tickets;
        release(&p->lock);
      }
         
      if(total_tickets == 0) {
        // No runnable processes with tickets
        asm volatile("wfi");
        continue;
      }
         
      // Select winning ticket
      int winner = rand() % total_tickets;
         
      // Find process with winning ticket
      int counter = 0;
      for(p = proc; p < &proc[NPROC]; p++) {
        acquire(&p->lock);
        if(p->state == RUNNABLE) {
          counter += p->tickets;
          if(counter > winner) {
            // Run this process
            p->state = RUNNING;
            c->proc = p;
            swtch(&c->context, &p->context);
            c->proc = 0;
            release(&p->lock);
            break;
          }
        }
        release(&p->lock);
      }
    } else {
      // Original scheduler code for round-robin
    }
  }
}

    Issues with large ticket counts:

    1. Integer overflow in total_tickets calculation
    2. Poor distribution if random number generator has low-order bit bias
    3. Performance impact due to large random number calculations

    Solution: Use unsigned integers for ticket counts and implement a better random number generator if needed. Consider capping the total ticket count and scaling proportionally.

    Process termination:

    No special handling is needed when a process terminates. The process table entry will be marked as UNUSED, and the scheduler naturally excludes it from the lottery. The total ticket count is recalculated on each scheduler invocation.

    Synchronization challenges:

    1. The process table must be locked during ticket counting and process selection
    2. Each process lock must be acquired when checking its state or modifying its tickets
    3. Potential race condition when setting tickets via system call while scheduler is running

    Solution: Follow xv6’s locking protocol - acquire the process lock before checking its state or updating tickets, and release it afterward. The scheduler only considers a process’s tickets when its lock is held.

    Test case:

    A good test case would create multiple processes with different ticket allocations and measure their CPU usage:

    // Create two CPU-bound processes with 10:90 ticket ratio
pid1 = fork();
if(pid1 == 0) {
  // Child process 1 - do CPU-intensive work
  while(1) counter1++;
}
   
pid2 = fork();
if(pid2 == 0) {
  // Child process 2 - do CPU-intensive work
  while(1) counter2++;
}
   
// Set ticket counts
setprocshare(pid1, 10);  // 10% of CPU
setprocshare(pid2, 90);  // 90% of CPU
   
// Let them run for a while, then measure counters
sleep(1000);
kill(pid1);
kill(pid2);
   
// The ratio counter2/counter1 should be approximately 9:1

Stride Scheduling

Easy Problems

  1. Concept Understanding

    Problem: Explain the basic concept of stride scheduling. How does it differ from lottery scheduling?

    Solution: Stride scheduling is a deterministic proportional-share scheduling algorithm where:

    1. Each process is assigned a “stride” value that is inversely proportional to its ticket count: stride = STRIDE_MAX / tickets
    2. Each process has a “pass” value that starts at 0 and increases by its stride each time it runs
    3. The scheduler always selects the runnable process with the lowest pass value
    4. After running, the selected process’s pass value is incremented by its stride

    Key differences from lottery scheduling:

    • Deterministic: The same sequence of scheduling decisions will occur every time
    • Fairer in the short term: Guarantees proportional CPU time allocation even over small intervals
    • More predictable: No random element means more consistent behavior
    • Slightly more complex: Requires maintaining pass values and finding the minimum

  2. Stride Calculation

    Problem: Given three processes with 10, 30, and 60 tickets respectively:

    • Calculate the stride values for each process using a stride constant of 10,000.
    • Which process would be selected to run first in a stride scheduler? Why?

    Solution:

    Stride calculation: stride = STRIDE_MAX / tickets

    With STRIDE_MAX = 10,000:

    • Process A (10 tickets): stride = 10,000 / 10 = 1,000
    • Process B (30 tickets): stride = 10,000 / 30 = 333
    • Process C (60 tickets): stride = 10,000 / 60 = 167

    Assuming all processes start with pass = 0, there would be a tie for the first selection. In this case, the scheduler typically selects the first process it encounters in the process table. After this first selection, the chosen process’s pass value would be incremented by its stride.

    If process A runs first, its pass becomes 1,000. Then process B would run (pass = 0), followed by C (pass = 0). After that, the pass values would be:

    • A: 1,000
    • B: 333
    • C: 167

    The process with the lowest pass (C with 167) would run next.

Moderate Problems

  1. Pass Value Analysis

    Problem: For processes A, B, and C with stride values of 1000, 500, and 250 respectively:

    • Draw a table showing the first 5 scheduling decisions in stride scheduling.
    • Include the pass values before and after each selection.
    • Which process receives the most CPU time? Why?

    Solution:

    Initial state: All processes have pass = 0

    RoundA pass (before)B pass (before)C pass (before)SelectedA pass (after)B pass (after)C pass (after)
    1000A100000
    2100000B10005000
    310005000C1000500250
    41000500250C1000500500
    51000500500B10001000500

    Process C receives the most CPU time in these first 5 decisions (runs twice), followed by A and B (run once each).

    Over a longer period, the CPU allocation would reflect the inverse of the stride values. The stride values (1000, 500, 250) correspond to relative ticket values of (1, 2, 4). Therefore, the expected CPU time allocation would be:

    • Process A: 1/7 ≈ 14.3%
    • Process B: 2/7 ≈ 28.6%
    • Process C: 4/7 ≈ 57.1%

    Process C receives the most CPU time because it has the smallest stride value, which corresponds to the largest number of tickets/highest priority.

  2. Implementation Strategies

    Problem: When implementing stride scheduling in xv6:

    • What potential problems might occur with the pass value over time?
    • How would you handle new processes entering the system?
    • What data structures would you modify or add to support stride scheduling?

    Solution:

    Potential pass value problems:

    1. Overflow: Pass values continuously increase and could eventually overflow. Solution: Either use a large integer type or periodically reset all pass values (subtracting the minimum pass value from all processes).

    2. Process starvation after sleep: If a process sleeps for a long time, its pass value remains unchanged while others increase, giving it an unfair advantage when it wakes up. Solution: Adjust the pass value of a newly awakened process to be at least the minimum pass of all runnable processes.

    Handling new processes:

    New processes should start with a pass value equal to the minimum pass value of all runnable processes. This prevents new processes from dominating CPU time upon creation.

    static struct proc*
allocproc(void)
{
  // ... existing code
     
  if(sched_mode == 2) { // Stride scheduling
    p->stride = STRIDE_MAX / p->tickets;
       
    // Initialize pass value to minimum pass value
    p->pass = 0;
    struct proc *tp;
    int found_runnable = 0;
       
    for(tp = proc; tp < &proc[NPROC]; tp++) {
      if(tp != p && tp->state == RUNNABLE) {
        if(!found_runnable || tp->pass < p->pass) {
          p->pass = tp->pass;
          found_runnable = 1;
        }
      }
    }
  }
     
  // ... rest of function
}

    Data structure modifications:

    1. Add fields to the process structure:
      struct proc {
  // ... existing fields
  int tickets;    // Process's weight/tickets
  uint stride;    // Stride value (STRIDE_MAX / tickets)
  uint pass;      // Current pass value
};
    2. Define a large stride constant:
      #define STRIDE_MAX 10000000  // Large value to avoid rounding errors
    3. Add a global variable to track the current scheduling mode:
      int sched_mode = 0;  // 0=RR, 1=lottery, 2=stride

Hard Problem

  1. Comprehensive Stride Implementation

    Problem: Design a complete implementation of stride scheduling for xv6:

    • What variables and fields need to be added to the process structure?
    • How would you select the process with the minimum pass value efficiently?
    • What happens during context switches and process creation/termination?
    • How would you handle the potential for pass value overflow?
    • How would you compare the fairness of your implementation to the standard xv6 scheduler?

    Solution:

    Process structure additions:

    struct proc {
  // ... existing fields
  int tickets;    // Proportional share weight
  uint stride;    // Stride value (STRIDE_MAX / tickets)
  uint pass;      // Current pass counter
};
    
// Global stride scheduling constant
#define STRIDE_MAX 10000000
    
// Global scheduler mode
int sched_mode = 0;  // 0=RR, 1=lottery, 2=stride

    Efficient minimum pass selection:

    A linear search is sufficient for xv6 with its limited number of processes (NPROC is typically small):

    // In scheduler()
struct proc *min_proc = 0;
uint min_pass = ~0;  // Start with maximum uint value
    
for(p = proc; p < &proc[NPROC]; p++) {
  acquire(&p->lock);
  if(p->state == RUNNABLE) {
    if(p->pass < min_pass) {
      // Release previous minimum process's lock if we found one
      if(min_proc != 0)
        release(&min_proc->lock);
            
      min_proc = p;
      min_pass = p->pass;
      // Keep lock held - we'll use this process
      continue;
    }
  }
  release(&p->lock);
}
    
if(min_proc) {
  // Run min_proc
  min_proc->pass += min_proc->stride;
  // ... run the process
  release(&min_proc->lock);
}

    For a larger system, a min-heap or other priority queue could be used.

    Context switches, creation, and termination:

    1. Context switches: Just before giving up the CPU, update the process’s pass value:
      // No specific code needed - the scheduler already increments the pass value
// before switching to the process
    2. Process creation (fork): The child should inherit the parent’s tickets and recalculate stride, but get a fresh pass value: ```c int fork(void) { // … existing code

    // Copy scheduler-related state np->tickets = p->tickets;

    if(sched_mode == 2) { // Stride scheduling np->stride = STRIDE_MAX / np->tickets;

    // Set pass to minimum of all runnable processes
np->pass = 0;
struct proc *tp;
int found_runnable = 0;
    
for(tp = proc; tp < &proc[NPROC]; tp++) {
  if(tp->state == RUNNABLE) {
    if(!found_runnable || tp->pass < np->pass) {
      np->pass = tp->pass;
      found_runnable = 1;
    }
  }
}   }

    // … rest of function }

        
3. **Process termination**: No special handling needed - the process simply won't be considered for scheduling anymore.
    
**Handling pass value overflow:**
    
Periodically reset all pass values by subtracting the minimum pass value from all processes:
    
```c
void
reset_pass_values(void)
{
  struct proc *p;
  uint min_pass = ~0;
      
  // Find minimum pass value among all processes
  for(p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if(p->state != UNUSED && p->pass < min_pass)
      min_pass = p->pass;
    release(&p->lock);
  }
      
  // Subtract minimum from all processes
  for(p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if(p->state != UNUSED)
      p->pass -= min_pass;
    release(&p->lock);
  }
}

    Call this function when switching to stride scheduling or when a potential overflow is detected:

    // In scheduler(), check for potential overflow
if(min_proc && min_proc->pass > (0xFFFFFFFF - min_proc->stride))
  reset_pass_values();

    Comparing fairness to standard xv6:

    To evaluate fairness, implement a test program that:

    1. Creates multiple processes with different ticket allocations
    2. Has each process perform an identical CPU-intensive workload
    3. Measures the number of iterations completed by each process
    4. Compares the actual ratio of iterations to the expected ratio
    // Example test program (schedtest.c)
void busywork(int *counter, int duration) {
  int start = uptime();
  while(uptime() - start < duration)
    for(int i = 0; i < 100000; i++)
      (*counter)++;
}
    
int main() {
  // Test with standard scheduler
  int pid1 = fork();
  if(pid1 == 0) {
    int counter = 0;
    busywork(&counter, 100);
    printf("Process 1 (standard): %d iterations\n", counter);
    exit(0);
  }
      
  int pid2 = fork();
  if(pid2 == 0) {
    int counter = 0;
    busywork(&counter, 100);
    printf("Process 2 (standard): %d iterations\n", counter);
    exit(0);
  }
      
  wait(0);
  wait(0);
      
  // Switch to stride scheduler
  setscheduler(2);
      
  // Test with 20:80 ratio
  pid1 = fork();
  if(pid1 == 0) {
    int counter = 0;
    busywork(&counter, 100);
    printf("Process 1 (stride 20%%): %d iterations\n", counter);
    exit(0);
  }
      
  pid2 = fork();
  if(pid2 == 0) {
    int counter = 0;
    busywork(&counter, 100);
    printf("Process 2 (stride 80%%): %d iterations\n", counter);
    exit(0);
  }
      
  setprocshare(pid1, 20);
  setprocshare(pid2, 80);
      
  wait(0);
  wait(0);
      
  printf("Stride scheduling should be fairer than round-robin\n");
  return 0;
}

    If the stride scheduler is working correctly, the ratio of iterations should closely match the 20:80 ticket ratio, while the standard scheduler would likely show a more even distribution.