Project 03 Practice Problems

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

Lottery Scheduling

Concept Understanding
Explain the basic concept of lottery scheduling. How does a lottery scheduler decide which process to run next?
Lottery Algorithm Implementation
In lottery scheduling, what key data structure or value must be maintained for each process, and how is the “winning process” selected?

Ticket Allocation Analysis
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?
System Call Requirements
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?

Full Implementation Analysis
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.

Concept Understanding
Explain the basic concept of stride scheduling. How does it differ from lottery scheduling?
Stride Calculation
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?

Pass Value Analysis
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?
Implementation Strategies
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?

Comprehensive Stride Implementation
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?