1 6 July 2015 Charles Reiss https://cs162.eecs.berkeley.edu/CS162: Operating Systems and Systems Programming Lecture 9: Concurrency (Finish) / Address Translation 6 July 2015 Charles Reiss https://cs162.eecs.berkeley.edu/

2 Recall: Multithreaded ProcessesThread(s) + Shared Address Space Multiple stacks in one address space

3 Recall: High-Level SyncSemaphores – integers with restricted interface P() / down: Wait until non-zero then decrement V() / up: Increment and wake sleeping task Monitors: Lock + Condition Variables Shared state determines when to wait Condition variables to wait "within critical section" on shared state changing Wait(), Signal(), Broadcast()

4 Thread Correctness ProblemsMany famous bugs from synchronization bug: Therac-25 – Radiation therapy machine had race condition causing overdose and death Space shuttle launch aborted because of timing bug Really hard to find synchronization bugs Can't test Nondeterminstic errors Some tools, but very underdeveloped "Too much" synchronization – deadlock

5 Avoiding Threads/SynchronizationMultiple processes Use files? Still synchronization Non-preemptive threads Event-based programming

6 Avoiding Threads/SynchronizationMultiple processes Use files? Still have synchronization Non-preemptive threads Event-based programming Can't use multiple cores

7 Avoiding Threads/SynchronizationMultiple processes Use files? Still synchronization Non-preemptive threads Event-based programming

8 Recall: Threading ModelsOption A: User-level library, one kernel thread (1:N) Early Java, ... Library does thread context switch Kernel time slices between processes, e.g. on I/O Option B: User-level library, multiple kernel threads (M:N) Solaris <9, FreeBSD <7, … Kernel still time slices on I/O Option C: Scheduler activations, kernel thread/CPU (M:N + upcalls) NetBSD < 5, Windows (option), … Option D: Kernel thread per user thread (1:1) Linux, OS X, Windows (default), FreeBSD >= 7, Solaris >= 7, NetBSD >= 5

9 Threads with explicit switchingOur problems come from arbitrary interleavings Let's only context switch when program tells us to Example: In a web server, when reading/writing from the network No need for special synchronization functions

10 Problems with explicit switchingWhat if too long between switches? What if a thread enters an infinite loop? What if a thread blocks on IO without triggering context switching?

11 Alternatives to ThreadsMultiple processes Use files? Still synchronization Non-preemptive threads Event-based programming

15 Logistics Homework 0 grades out – please check themTell us by next week if there's something wrong Project 1 Design Reviews (today) Project 1 Checkpoint 1 – Tommorrow 11:59PM Homework 1 Due Wednesday 11:59PM

16 Break

17 Virtualizing ResourcesRun multiple processes/thread Multiplex CPUs: scheduling/threads – just finished Multiplex memory (today) via address translation Multiplex devices (like disk) – later

18 Virtualizing ResourcesRun multiple processes/thread Multiplex CPUs: scheduling/threads – just finished Multiplex memory (today) via address translation Multiplex devices (like disk) – later

19 Recall: Multithreaded ProcessesThread(s) + Shared Address Space Multiple stacks in one address space

20 Memory Multiplexing GoalsProtection Private memory of other processes/OS remains private Even from malicious processes Controlled overlap Want processes, OS to be able to use shared memory to communicate Or to save space Uniform view of memory No need to change addresses in a program to run two copies of it No need to change a program to let it use more memory

21 Address Translation Translation Program addresses are virtualKernel-controlled mapping from virtual to physical Implemented by hardware Preferred mechanism for memory multiplexing

22 Living Without Translation

27 Recall: Generating ExecutablesSteps: Compile ("gcc") Link/Load ("ld") Execute (dynamic linker) Addresses chosen at all of these steps Want to avoid work at runtime...

28 Relocatable LibrariesDynamic libraries – final linking postponed Code compiled with only relative addresses MIPS: can't use jal Table of pointers to library routines Statically linked stubs Initial entries in table Locate dynamic library routine Replace entry in table

29 Recall: UniprogrammingNo translation and no protection Application can access any physical address Application always at same location (owns machine) Reality of dedicated machine

38 B&B: Internal FragmentationTraditional MIPS memory layout: Big hole where stack/dynamic data grows Allocate 2GB to every process? Would like to have unallocated space

45 Recall: Base and Bound ProblemsExternal fragmentation: free space between allocations is not all together expensive moving Internal fragmentation unused gaps within allocated chunks can't fix without relocating program No sharing – waste space with extra copies Which of these problems does segmentation solve?

49 Swapping Problem: Not all processes fit in memoryBreaks the illusion of dedicated machine Extreme context switch: when process is not running, move it to disk

52 Swapping: Discussion Disks are slowSSDs are faster, but not that much faster For modern systems, swapping performance is usually unacceptable Why do we talk about it? Big motivation for paging Program loading uses this mechanism (load from disk on fault)

53 A better solution: pagingEliminate external fragmentation with fixed sized chunks Called pages All holes are multiples of a page size All allocations are whole pages Minimize internal fragmentation by making pages small Typical size: 4096 bytes

56 Address Translation: OverheadBase and Bound Two registers Segmentation One segment table entry per segment Registers for segment table? Paging Extra memory access for every memory access 4K pages → 1M entries for 32-bit address space!

57 Summary: Event-driven programmingKey idea: loop calling function to "get next event" Need to break up "straight" threaded code into many chunks If chunks block – trouble If chunks take too long – trouble But: No synchronization – correctness easier Maybe less overhead (no extra stacks)

58 Summary: Address Translation GoalsProtection programs can only access physical memory they are allowed to Controlled Sharing programs can share memory to communicate or to save resources Uniform view programs have the same virtual addresses every time Avoid fragmentation allow efficient allocation/deallocation

59 Summary: Base and BoundAddress translation with two special registers: Base – added to every virtual address Bound – checked against every virtual address Protection Controlled sharing Uniform view (???) Not if program is resized Avoid fragmentation

60 Summary: SegmentationAddress translation with segment table Each entry has base, bound Segment number (index into table) extracted from address (or elsewhere) Protection Controlled sharing but limited number of segments to share Uniform view Avoid fragmentation

61 Summary: Paging Address translation with page tableEach entry has small, fixed size Page frame number (index into table) extracted from address (or elsewhere) Protection Controlled sharing Uniform view Avoid fragmentation