Controlling Complexity in System Design

Multi-programming in THE Landon Cox Landon Cox February 3, 2016 February 3, 2016

THE (First SOSP 67) SIGOPS Hall of Fame summary SIGOPS Hall of Fame summary The first paper to suggest that an operating system be built in a structured way. That structure was a series of layers, each a virtual machine that introduced abstractions built using the functionality of lower layers. The paper stimulated a great deal of subsequent work in building operating systems as structured systems.

Across systems categories Many common, important problems Many common, important problems Fault tolerance Coordination of concurrent activities Geo. separated but linked data Large-scale data sets Protection from mistakes and attacks Interactions with many people All of these problems lead to All of these problems lead to complexity complexity

Complexity How do we control complexity? How do we control complexity? Build abstractions that hide unimportant details Establish conventional interfaces Enable composition of simple, well-defined components None of these ideas a specific to computer systems None of these ideas a specific to computer systems These are just principles of good engineering Civil engineering, urban planning, mechanical engineering, aviation and space flight, electrical engineering, ecology and political science

Dealing with complexity How do you impose order on complex programs? How do you impose order on complex programs? Break functionality into modules Goal is to decouple unrelated functions Narrow the set of interactions between modules Hope to make whole system easier to reason about H How do we specify interactions between code modules? ow do we specify interactions between code modules? Procedure calls int foo(char *buf) Why do procedure calls reduce complexity? Why do procedure calls reduce complexity? They make interface between modules explicit They hide implementation details

Dealing with complexity P(a){ } C(){ y=P(x); } Via what data structure do C and P communicate? Via what data structure do C and P communicate? They communicate via a shared, in-memory stack What is on the stack? What is on the stack? Stack: regs, args, RA, P's vars, maybe args ... C: push regs, push args, push PC+1, jmp P: push vars, ..., pop vars, mov xx -> R0, pop PC The call contract The call contract P returns P returns to where C said P restores stack pointer P doesn't modify stack (or C's other memory) P doesn't wedge machine (e.g., use up all heap memory) jmp P P, pop args, pop regs, ... R0

Dealing with complexity P(a){ } C(){ y=P(x); } Is the call contract enforced? Is the call contract enforced? At a low level none of it is enforced P can violate all terms of the contract Violations due to bugs and attacks What about P s functionality (what it does)? What about P s functionality (what it does)? E Enforced? No. E.g., no guarantee that sqrt() returns the right answer Would like a specification (spec spec) that P is correct Can we enforce either the spec or contract? Can we enforce either the spec or contract? We cannot enforce a procedure s spec (i.e., that it is correct) Can only apply testing testing to convince ourselves that code adheres to spec We can enforce the call contract (= enforced modularity nforced? enforced modularity)

Dealing with complexity P(a){ } C(){ y=P(x); } Why can we enforce the call contract? Why can we enforce the call contract? Purely mechanical interaction Programmer s intention is clear No semantic gap to cross Ways that call contracts are enforced? Ways that call contracts are enforced? Put P and C in different processes (RPC) Trusted compiler/runtime transitions between C, P (Java) Hardware regulates transitions (kernel, user process)

Dealing with complexity P(a){ } C(){ y=P(x); } Functions are programming language constructs Functions are programming language constructs Can you think of a PL construct that shatters modularity? Can you think of a PL construct that shatters modularity? goto Inspired famous rant by Dijkstra in CACM in 1968 Go To Statement Considered Harmful "The unbridled use of the goto statement has as an immediate consequence that it becomes terribly hard to find a meaningful set of coordinates in which to describe the process progress. ... The goto statement as it stands is just too primitive, it is too much an invitation to make a mess of one's program. Several months earlier Structure of THE multi Several months earlier Structure of THE multi- -programming programming s system ystem

THE-multiprogramming system An operating system is a very complex program An operating system is a very complex program Has to manage other processes Has to handle interrupts Has to handle I/O devices Has to handle synchronization primitives How THE handles all of this complexity How THE handles all of this complexity Breaks functionality into stacked layers Higher layers depend on lower layers

THE-multiprogramming system What is a layer? What is a layer? A layer is a set of related procedure calls or functionality Represents a level in a hierarchy How do layers differ from procedure calls How do layers differ from procedure calls w w/in a program? Code can only call within layer and into layers below Can build a layer without worrying about what happens above Why is this additional structure appealing? Why is this additional structure appealing? Further limits how modules interact Reduces dependencies between modules Hopefully reduces complexity and bugs Do not have to worry about code in Layer 1 calling into Layer 4 /in a program?

THE-multiprogramming system Batch system Batch system Users submit programs OS decides what to run 5 user processes at a time Multi Multi- -tasking tasking Manage multiple programs concurrently Need to switch between programs

Multi-programming Want more Want more than 1 process in phys memory than 1 process in phys memory Processes can have same virtual addrs Cannot share physical addrs Addresses must be translated Addresses must be translated Programs cannot manipulate phys addrs anymore Statically: occurs before execution Dynamically: occurs during execution Protection Protection becomes harder becomes harder

Static address translation Want two processes in memory Want two processes in memory With address independence Without translating on-the-fly Using static translation How to do this? How to do this?

Static address translation Adjust loads/stores when put in memory Adjust loads/stores when put in memory This is called a linker-loader Programming Programming Assume memory starts at 0 fffff (high memory) . OS kernel 80000 . 3ffff . . User process 2 . 20000 1ffff . . User process 1 . 00000 (low memory) load $1, $base + offset Linker Linker- -loader Adds 0x20000 to offsets for P2 Similar to linking phase of compile Similar to linking phase of compile loader

User programs Layer 4 I/O devices Layer 3 Layer 2 Console Layer 1 Pager Layer 0 Scheduler

Layer 0 Primary responsibilities of Layer 0 Primary responsibilities of Layer 0 Ensure efficient, fair allocation of processor (government) Hide number of processors (abstraction layer) How did the scheduler ensure fair allocation? How did the scheduler ensure fair allocation? Handled all transitions between processes Some were voluntary transitions (synchronization calls) Some were involuntary transitions (timer interrupts) Could Layer 0 code be swapped out? Could Layer 0 code be swapped out? No, timer-interrupt handler always has to be in memory

Layer 1 Primary responsibilities of Layer 1 Primary responsibilities of Layer 1 Ensure efficient, fair allocation of memory (government) Hide drum addresses (abstraction layer) What were a segment, core page, and drum page? What were a segment, core page, and drum page? Segment = coarse-grained unit of data, visible to program Core page = in-memory container for a segment Drum page = on-disk container for a segment

Layer 1 H How were processes isolated? ow were processes isolated? No hardware support for virtual memory Relied on language and compiler Programs written in Algol used private segment identifiers Like the static address translation discussed last time Could Layer 1 code be swapped out? Could Layer 1 code be swapped out? No, memory manager always has to be in memory Otherwise have a serious bootstrapping problem

Layer 1 H How did paging work without hardware support? ow did paging work without hardware support? Similar to way compiler handles procedure calls Compiler needed to know which segments to be accessed Compiler could insert calls into layer 1 to page-in segments Was any of this enforced? Was any of this enforced? No, just like procedure-call contract is not enforced At the lowest-level, could easily corrupt other processes Bugs and attacks could crash the whole system

Coordination of processes A society of harmonious sequential processes A society of harmonious sequential processes Each layer implemented as a process Each layer implemented as a process To move between layers, need way to transition safely What primitives provided safe switching? What primitives provided safe switching? Semaphores: Up (V) and Down (P) Down (may) block the calling process Up (may) allow another process to be scheduled

Semaphores First defined by First defined by Dijkstra Two operations: up and down Two operations: up and down Dijkstra for THE for THE // aka V ( verhogen ) up () { // begin atomic value++ // end atomic } // aka P ( proberen ) down () { do { // begin atomic if (value > 0) { value-- break } // end atomic } while (1) } What is going on here? What is going on here? Can value ever be < 0? Can value ever be < 0?

More semaphores Key state of a semaphore is its Key state of a semaphore is its value Initial value determines semaphore s behavior Value cannot be accessed outside semaphore (i.e., there is no semaphore.getValue() call) Semaphores can be both synchronization types Semaphores can be both synchronization types Mutual exclusion (like locks) Ordering constraints (like monitors) value

Semaphore mutual exclusion Ensure that 1 (or < N) thread is in critical section Ensure that 1 (or < N) thread is in critical section s.down (); // critical section s.up (); How How do we make a semaphore act like a lock? do we make a semaphore act like a lock? Set initial value to 1 (or N) Like lock/unlock, but more general (could allow 2 threads in critical section if initial value = 2) Lock is equivalent to a binary semaphore

Semaphore ordering constraints Thread A waits for B before proceeding Thread A waits for B before proceeding // Thread A s.down (); // continue // Thread B // do task s.up (); How to make a semaphore behave like a monitor? How to make a semaphore behave like a monitor? Set initial value of semaphore to 0 A is guaranteed to wait for B to finish A is guaranteed to wait for B to finish Doesn t matter if A or B run first Like a CV in which condition is Like a CV in which condition is sem.value==0 Can think of as a prefab condition variable

Prod.-cons. with semaphores Same before Same before- -after constraints after constraints If buffer empty, consumer waits for producer If buffer full, producer waits for consumer Semaphore assignments Semaphore assignments mutex (binary semaphore) fullBuffers (counts number of full slots) emptyBuffers (counts number of empty slots)

Prod.-cons. with semaphores Initial semaphore values? Initial semaphore values? Mutual exclusion sem mutex (?) Machine is initially empty sem fullBuffers (?) sem emptyBuffers (?)

Prod.-cons. with semaphores Initial semaphore Initial semaphore values? Mutual exclusion sem mutex (1) Machine is initially empty sem fullBuffers (0) sem emptyBuffers (MaxSodas) values?

Prod.-cons. with semaphores Semaphore mutex(1),fullBuffers(0),emptyBuffers(MaxSodas) consumer () { down (fullBuffers) producer () { down (emptyBuffers) down (mutex) down (mutex) take soda out put soda in up (mutex) up (mutex) up (emptyBuffers) } Use one semaphore for Use one semaphore for fullBuffers Remember semaphores are like prefab CVs. Remember semaphores are like prefab CVs. up (fullBuffers) } fullBuffers and and emptyBuffers emptyBuffers? ?

Prod.-cons. with semaphores Semaphore mutex(1),fullBuffers(0),emptyBuffers(MaxSodas) consumer () { down (mutex) producer () { down (mutex) 2 2 1 1 down (fullBuffers) down (emptyBuffers) take soda out put soda in up (emptyBuffers) up (fullBuffers) up (mutex) } up (mutex) } Does the order of the down calls matter? Does the order of the down calls matter? Yes. Can cause deadlock. Yes. Can cause deadlock.

Prod.-cons. with semaphores Semaphore mutex(1),fullBuffers(0),emptyBuffers(MaxSodas) consumer () { down (fullBuffers) producer () { down (emptyBuffers) down (mutex) down (mutex) take soda out put soda in up (emptyBuffers) up (fullBuffers) up (mutex) } up (mutex) } Does the order of the up calls matter? Does the order of the up calls matter? Not for correctness (possible efficiency issues). Not for correctness (possible efficiency issues).

Prod.-cons. with semaphores Semaphore mutex(1),fullBuffers(0),emptyBuffers(MaxSodas) consumer () { down (fullBuffers) producer () { down (emptyBuffers) down (mutex) down (mutex) take soda out put soda in up (mutex) up (mutex) up (emptyBuffers) } up (fullBuffers) } What about multiple consumers and/or producers? What about multiple consumers and/or producers? Doesn t matter; solution stands. Doesn t matter; solution stands.

Prod.-cons. with semaphores Semaphore mtx(1),fullBuffers(1),emptyBuffers(MaxSodas-1) consumer () { down (fullBuffers) producer () { down (emptyBuffers) down (mutex) down (mutex) take soda out put soda in up (mutex) up (mutex) up (emptyBuffers) } up (fullBuffers) } What if 1 full buffer and multiple consumers call down? What if 1 full buffer and multiple consumers call down? Only one will see semaphore at 1, rest see at 0. Only one will see semaphore at 1, rest see at 0.

Monitors vs. semaphores Monitors Monitors Separate Separate mutual exclusion and ordering Semaphores Semaphores Provide both with same mechanism Semaphores are more elegant Semaphores are more elegant Single mechanism Can be harder to program

Monitors vs. semaphores // Monitors lock (mutex) // Semaphores down (semaphore) while (condition) { wait (CV, mutex) } unlock (mutex) Where are the conditions in both? Where are the conditions in both? Which is more flexible? Which is more flexible? Why do monitors need a lock, but not semaphores? Why do monitors need a lock, but not semaphores?

Monitors vs. semaphores // Monitors lock (mutex) // Semaphores down (semaphore) while (condition) { wait (CV, mutex) } unlock (mutex) When are semaphores appropriate? When are semaphores appropriate? When shared integer maps naturally to problem at hand (i.e., when the condition involves a count of one one thing)

Classic synchronization problem Each barber/stylist is a thread Each customer is a thread Sofa capacity = 4 Sofa capacity = 4 Standing room Standing room Customer room capacity = 9 Customer room capacity = 9 Only 9 customers in room at a time. Only 9 customers in room at a time.

Stylist(int id) { Customer () { } Break up into groups of 2 or 3 Break up into groups of 2 or 3 Try to come up with a solution Try to come up with a solution We ll talk about it in 10 minutes We ll talk about it in 10 minutes }

Salon with semaphores Customer () { room.down () // enter room sofa.down () // sit on sofa chair.down () // sit on chair sofa.up () customer.up () cut.down () // leave chair chair.up () // leave room room.up () } Semaphore room = 9, sofa = 4, chair = 3, customer = 0, cut = 0; Stylist () { while (1) { customer.down() // cut hair cut.up () } } Is anything weird here? Is anything weird here?

Customer () { lock.acquire (); while (numInRoom == 9) roomCV.wait (lock); numInRoom++; Enter room Enter room lock; roomCV; numInRoom=0; sofaCV; numOnSofa=0; chairCV; freeChairs[3]; customerCVs[3]; cutCVs[3]; while (numOnSofa == 4) sofaCV.wait (lock); numOnSofa++; Sit on sofa Sit on sofa while (findFreeChair () == NONE) chairCV.wait (lock); stylist = findFreeChair (); freeChairs[stylist] = 1; numOnSofa--; sofaCV.signal (lock); customerCVs[stylist].signal (lock); cutCVs[stylist].wait (lock); freeChairs[stylist] = 0; chairCV.signal (lock); numInRoom--; roomCV.signal (lock); lock.release (); } Sit in chair Sit in chair Wake up Wake up stylist Wait for cut to finish Wait for cut to finish stylist Leave the shop Leave the shop

Customer () { lock.acquire (); while (numInRoom == 9) roomCV.wait (lock); numInRoom++; Stylist(int id) { lock.acquire (); while (1) { while (!freeChairs[id]) customerCVs[id].wait (lock); cutHair (); cutCVs[id].signal (); } lock.release (); } while (numOnSofa == 4) sofaCV.wait (lock); numOnSofa++; while (findFreeChair () == NONE) chairCV.wait (lock); stylist = findFreeChair (); freeChairs[stylist] = 1; numOnSofa--; sofaCV.signal (lock); customerCVs[stylist].signal (lock); cutCVs[stylist].wait (lock); freeChairs[stylist] = 0; chairCV.signal (lock); numInRoom--; roomCV.signal (lock); lock.release (); }

Next time More history More history Multics Almost every important idea in OS can be found somewhere in Multics. So complicated and hard to use, it inspired UNIX Questions? Questions?