# CS 111 Class Notes 2022/02/08 ## Stride Scheduling While random is pretty close, stride scheduling attempts to get a more accurate distribution. 1. Fairness - proportionate share scheduling 1. "Soft" priority (not technical name) - no starvation, everything gets to run but higher priority gets more time 1. Deterministic Compare to priority scheduler: * Downside: Starvation * Upside: Turnaround time for high priority tasks minimized What does it do that the lottery scheduler doesn't? * Lottery scheduler is statistically correct in the long run, but stride scheduling is deterministic. How does a stride scheduler work? 1. Compute the stride $$stride_i = C/tickets_i$$ where C is a large constant 1. Each time the process is run, $$pass_i = pass_i + stride_i$$ 1. When switching to a new process, select the one with the lowest pass value If same number of tickets, go round robin. Pros & Cons: * \[CON\] Global state: stride scheduling is more complex. If a new process comes in, it doesn't keep running until its pass catches up * \[PRO\] Guarantees proportionality on small timescales (b/c deterministic) ## Measuring Systems 4 Questions: 1. **What** is being measured? 1. What **metrics** to measure? * Response time, throughput, etc. 1. What **workload** to measure? * Exact process workload is going to affect the resulting schedule and therefore metrics. * Compute cluster may be different from a laptop * Benchmarks(?) 1. **How** to measure? * Simulation, Modeling, Real implementation ## Virtual memory ### Address Spaces Address space is the memory allocated to a process * Includes code, stack, heap, etc. Two problems: 1. Process address space does not start at 0x00000000 (process relocation) 2. We don't want processes to access eachother's address spaces (process isolation) Dynamic Relocation vs. Static Relocation * Dynamic relocation uses two registers (base and bounds) that map where the available memory starts and ends, does adjustments at runtime * Static allocates memory at execution time (loading the program) and fixes it permanently (does translation by adding offset to all addresses in the code) * Dynamic solves both relocation and isolation, because it has memory bounds which should contain all memory for a process. * Static does not solve isolation. #### Pros & Cons: **Dynamic** * \[PRO\] Solves process isolation with bounds check (SEGFAULT) * \[PRO\] If you want/ need more memory, you can expand into it OR can move the entire address space * \[CON\] Expensive overhead * \[CON\] Relies upon hardware support **Static** * \[PRO\] Very little overhead after startup * \[PRO\] No h/w support needed * \[CON\] Hard to relocate * \[CON\] Does not address process isolation ### Assumptions Virtual memory requires three assumptions * Address space is smaller than the total amount of phys memory * Address space is contiguous * Address space is the same size We've now relaxed the second two, and will relax the first one soon.