|

Dynamic Stride Scheduler with Dynamic Ticket Modification

CS537: Operating Systems

Taught by Prof. Louis Oliphant

Project Goals

Implement a dynamic stride scheduler in xv6 with dynamic ticket modification so CPU share tracks ticket allocation while adapting to sleeping/waking processes and runtime changes.

  • Implement and reason about stride scheduling.
  • Modify xv6 scheduler and process state.
  • Add and validate scheduler-facing system calls.

Scheduling Model

Per-Process Fields

  • tickets: defaults to 8 and can be changed via syscall.
  • stride = STRIDE1 / tickets, with STRIDE1 = 1 << 10.
  • pass: starts at 0 and increments by stride each time the process is scheduled.
  • remain: stores offset versus global pass when leaving/rejoining scheduling queue.

Scheduler selection rule: choose runnable process with the smallest pass.

Global Fields for Dynamic Participation

  • global_tickets: sum of tickets over runnable processes.
  • global_stride = STRIDE1 / global_tickets.
  • global_pass: incremented each tick by current global_stride.

On process creation, initialize pass from global_pass. Recompute global values when processes enter/leave runnable set.

The handout emphasizes that global_pass should use STRIDE1 / global_tickets, not an arithmetic mean of process strides.

Dynamic Ticket Modification Rule

When tickets change from tickets to tickets', recompute stride' normally and rescale the remaining stride fraction so scheduling progress remains consistent across the old/new stride values.

Implementation Tasks

Use xv6's modular scheduler setup via SCHED_MACRO and support both RR and STRIDE builds from flags. For this project, STRIDE is implemented for a single CPU, and one timeslice equals one tick.

Task 1

Add fields to proc, track process runtime ticks, and maintain global/pass/remain state transitions correctly.

Task 2

Pick the runnable process with minimum pass. Tie-breakers:

  1. Lower total runtime ticks first.
  2. If still tied, lower PID first.

Task 3

Add syscall:

int settickets(int n);
  • Maximum tickets: 1 << 5.
  • Minimum valid tickets: 1.
  • If n < 1, reset tickets to default 8.

Task 4

Add syscall:

int getpinfo(struct pstat*);

Add this definition in pstat.h:

struct pstat {
  int inuse[NPROC];
  int tickets[NPROC];
  int pid[NPROC];
  int pass[NPROC];
  int remain[NPROC];
  int stride[NPROC];
  int rtime[NPROC];
};

Task 5 (RR vs STRIDE Experiment)

Run the included workload program in both schedulers and collect CSV output.

# RR (default)
make qemu-nox
workload &
cat rr_process_stats.csv

# STRIDE build
make qemu-nox SCHEDULER=STRIDE
workload &
cat stride_process_stats.csv
  • Run workload with & so the long-running job stays in the background.
  • Wait until output prints Done Measuring before collecting CSV files.
  • Copy resulting CSV files to your lab machine for submission packaging.

Include both rr_process_stats.csv and stride_process_stats.csv in the project directory.

Task 6 (Analysis)

Compare observed runtime behavior between RR and STRIDE, discuss proportional fairness advantages, and explain dynamic participation patterns using your CSV results. Add this analysis to README.md.

Submission Checklist

Expected directory output of ls p4:

README.md
solution/
tests/
rr_process_stats.csv
stride_process_stats.csv
partners.txt
slipdays.txt # optional

Further Reading

License

Distributed under the MIT License. SeeLICENSE.txt for more information.