---
# System prepended metadata

title: CS 111 Class Notes 2022/02/08

---

# 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.