CS537

Brief CPU Virtualization Mechanism => Limited Direct Execution Policy => Scheduling Q) How to build a scheduling policy? Memory Virtualization Scheduling Metric #1: Turnaround Time ($T_{completes} - T_{arrives}$) “Run to completion” FIFO (FCFS) Bad (Short jobs stuck behind long jobs) SJF Process does not all arrive at $T_0$ STCF (Shortest Time to Completion First) “Generalized” SJF Metric #2: Response Time: ($T_{firstruns} - T_{arrives}$) Round Robin ABCABC….ABC (Switch frequently) Time Slice (Quantum): Multiple of how often Timer goes off “Real” Scheduler Don’t know job length (How to learn?...

Brief MMU Base/bounds (Dynamic relocation) 2 Registers OS role: When process is created: allocate (contiguous) memory for address space Keep track of Process List: $P_A$ base 2048 and bound Free List: which parts of physical memory are free When process runs: Before it run, set base and bounds on MMU then, run process When Context switch: $P_A$ running -> Timer interrupt -> Want to run $P_B$ -> need to set base/bounds for $P_B$ When Process wants to grow its address space: System call: ask OS for more memory OS: Update its free list change the bounds register to new new size Pros/Cons Pros: Fast SImple Cons: Inflexible Doesn’t support large “sparse” virtual address space Segmentation (Generalization of Base/Bounds) For each segment: keep <base, bounds> Pro: “Very large” virtual address space now possible Cons: External fragmentation => memory is hard to manage Paging

Brief Virtual Address technique Base/Bounds Segmentation Paging Problems with Segmentation: external fragmentation: free space becomes full of small used spots and free spots intermixed not fully flexible Internal fragmentation e.g. “sparse” heap (data in top and bottom of heap, even though middle part is unused must keep in memory) New Approach: Paging divide virtual address space into small(4KB), fixed-sized units call pages similarly, divide physical memory into 4Kb page frames Free space management: easy (e....

Brief Page Table  Per Process large => in memory Upon every memory reference: address translation What does the hardware need to know? location of page table (Page Table Base Register[PTBR] in MMU) Points to start of page table of currently running process Privileged Paging: Too Slow To do translation: Fetch Page Table Entry Extra memory reference Solution: Hardware (Translation Lookaside Buffer [TLB]) in CPU hardware that holds some number of “popular” translation Method: When Virtual address -> TLB, If VPN is in the TLB, “hit” use PFN in TLB, form physical addr, perform mem access If not, “miss”....