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

Meeting Summary: CS 326 Lecture/Lab Spring 2025

Date: April 17, 2025, 02:47 PM Pacific Time (US and Canada)
Meeting ID: 813 3845 7711

Quick Recap

Greg discussed the project specification for implementing lottery and stride scheduling in the xv6 operating system. The key points include:

  • Project Specification Highlights:
    • Multiple implementation approaches (from direct implementation to leveraging AI coding assistants).
    • Emphasis on the importance of understanding the scheduling algorithms.
    • An introduction to Virtual Time Round Robin as an extension possibility.
    • Discussion on how the scheduler handles ticket assignment.
    • Overview of proportional share scheduling and methods to hold a lottery in the scheduler.
  • Concepts Covered:
    • Lottery Scheduling: Uses a random process to pick a winning ticket among runnable processes.
    • Stride Scheduling: Uses a deterministic algorithm based on each process’s pass and stride values, where progress is inversely proportional to the share value.

Next Steps

Students are expected to modify the xv6 kernel to implement the scheduling algorithms. The next steps include:

  • Kernel File Modifications:
    Modify the following files:
    • syscall.h
    • syscall.c
    • sysproc.c
    • proc.c
    • proc.h
  • Process Structure Updates:
    In proc.h, add the following new fields to the proc struct:
    • tickets – number of lottery tickets.
    • pass – cumulative pass value for stride scheduling.
    • stride – stride value used for scheduling decisions.

    Example xv6 C code:

    // In proc.h
struct proc {
    // Existing fields...
    int tickets;    // Number of lottery tickets assigned
    int pass;       // Cumulative pass value for stride scheduling
    int stride;     // Stride value for scheduling
    // Other fields...
};
  • System Call Implementations:
    Implement the following system calls:
    • set_scheduler
    • set_proc_share
  • Scheduler Enhancements:
    • Extend the existing scheduler to support different scheduling algorithms based on the mode.
    • Initialize new process structure fields with reasonable default values in alloc_proc.
    • Calculate stride values by dividing a maximum ticket value (e.g., 10 million) by the number of tickets assigned.
  • Demonstration and Submission:
    • Demo the working implementation to the TAs during the lab section on Wednesday.
    • Submit the project under the “project 1 corrections” label (visible only to instructors and TAs).

Detailed Summary

Xv6 Lottery and Stride Scheduling

Greg provided a detailed overview of the project specification for implementing both lottery and stride scheduling in xv6. Key points include:

  • Scheduling Modes:
    The specification now includes system call descriptions and high-level algorithms for each scheduling mode.

  • Implementation Options:
    Options range from a straightforward direct implementation to using AI coding tools, though understanding of the underlying algorithms is emphasized.

  • Optional Extra Credit:
    An option to create a generalized test program was mentioned for extra credit.

Proportional Share Scheduling in Process Management

Key details of proportional share scheduling include:

  • Concept Overview:
    • Processes are assigned shares, and the scheduler ensures they run at rates proportional to these share values.
    • A test scenario was discussed where two processes with 10% and 90% shares run for 50 ticks.
    • The scheduler’s goal is to maximize progress within the smallest time window while maintaining the defined proportions.
  • Ticket Handling:
    • The total number of tickets is calculated by summing the tickets of all runnable processes.

Lottery System Ticket Assignment Process

The lottery mechanism involves:

  • Ticket Assignment:
    • Tickets are assigned to processes.
    • A random number is generated to determine the winning ticket.
    • The winning ticket is identified by comparing the random number with the cumulative ticket counts for each process.

  • Example xv6 Code Snippet for Lottery Scheduling:

    /*
 * Lottery scheduling in xv6
 */
int total_tickets = 0;
struct proc *p;
for (p = ptable.proc; p < &ptable.proc[NPROC]; p++) {
    if (p->state == RUNNABLE) {
        total_tickets += p->tickets;
    }
}
  
int winning_ticket = random() % total_tickets;
int ticket_sum = 0;
for (p = ptable.proc; p < &ptable.proc[NPROC]; p++) {
    if (p->state == RUNNABLE) {
        ticket_sum += p->tickets;
        if (ticket_sum > winning_ticket) {
            // Process 'p' is selected to run
            break;
        }
    }
}

  • Mermaid Diagram – Lottery Scheduling Process:

    flowchart TD
    A[Calculate Total Tickets] --> B[Generate Random Winning Ticket]
    B --> C[Loop through Processes]
    C --> D[Accumulate Ticket Counts]
    D --> E[Determine the Winning Process]

Lottery Process in Scheduler

The process within the scheduler involves:

  • Algorithm Details:
    • The scheduler first loops through the process table to compute the total tickets.
    • A second loop is performed to pick the winning process by maintaining a running sum of ticket counts.
    • Special care is needed when scaling up to a larger number of processes or ticket values.

Consistent Ticket Assignment and Stride Scheduling

Consistency in ticket assignment is crucial to:

  • Scheduling Integrity:
    • Ensure that processes are scheduled in a consistent order.
    • Guarantee that the proportional relationships among process shares are maintained.
  • Stride Scheduling Parameters:
    • Each process uses a pass value (to track progress) and a stride value (to determine the rate of progress).

Stride Scheduling Algorithm Explained

The deterministic stride scheduling algorithm operates as follows:

  • Algorithm Overview:
    • The scheduler selects the process with the smallest pass value.
    • After running the selected process, its pass value is increased by its stride.

  • Example xv6 Code Snippet for Stride Scheduling:

    /*
 * Stride scheduling in xv6
 */
struct proc *selected = NULL;
int min_pass = INT_MAX;
for (p = ptable.proc; p < &ptable.proc[NPROC]; p++) {
    if (p->state == RUNNABLE && p->pass < min_pass) {
        min_pass = p->pass;
        selected = p;
    }
}
  
if (selected != NULL) {
    // Run the selected process and update its pass value
    selected->pass += selected->stride;
}

  • Mermaid Diagram – Stride Scheduling Process:

    flowchart TD
    A[Initialize Process Stride and Pass Values] --> B[Select Process with Smallest Pass Value]
    B --> C[Execute Selected Process]
    C --> D[Increment Process's Pass by its Stride]
    D --> B

Linux Scheduler Improvements and Allocation

Greg discussed the current flaws in the Linux Scheduler and suggested potential improvements:

  • Extensibility:
    • Extend the scheduler to support multiple scheduling algorithms such as lottery scheduling and stride scheduling.
  • Process Allocation:
    • Emphasize the importance of setting initial values (including the new fields) during process allocation in alloc_proc.
  • Future Topics:
    • A deep dive into virtual memory is scheduled for the upcoming Tuesday session.

This meeting summary provides a clear roadmap for students to enhance the xv6 scheduler by implementing both lottery and stride scheduling algorithms while emphasizing the importance of a thorough understanding of these concepts.