AdministriviaAdministrivia• Nachos guide and Lab #1 are on the web.http://www.cs.duke.edu/~chase/cps210• Form project teams of 2-3.• Lab #1 due February 5.• Synchronization problem set is up: due January 29.• Synchronization hour exam on January 29.• Readings page is up.• Read Tanenbaum ch 2-3 and Birrell for Thursday’s class.Threads and ConcurrencyThreads and ConcurrencyThreadsThreadsA thread is a schedulable stream of control.defined by CPU register values (PC, SP)suspend: save register values in memoryresume: restore registers from memoryMultiple threads can execute independently:They can run in parallel on multiple CPUs...- physical concurrency…or arbitrarily interleaved on a single CPU.- logical concurrencyEach thread must have its own stack.A Peek Inside a Running ProgramA Peek Inside a Running Program0highcode libraryyour dataheapregistersCPUR0RnPC“memory”xxyour programcommon runtimestackaddress space(virtual or physical)SPyyTwo Threads Sharing a CPUTwo Threads Sharing a CPUrealityconceptcontext switchA Program With Two ThreadsA Program With Two Threads0highcode librarydataregistersCPUR0RnPC“memory”xxprogramcommon runtimestackaddress spaceSPyystackrunningthread“on deck” and ready to runThread Context SwitchThread Context Switch0highcode librarydataregistersCPUR0RnPC“memory”xxprogramcommon runtimestackaddress spaceSPyystack1. save registers2. load registersswitch inswitch outThread States and TransitionsThread States and TransitionsrunningreadyblockedScheduler::RunScheduler::ReadyToRun(“wakeup”)Thread::Sleep(voluntary)Thread::Yield(voluntary or involuntary)Blocking in Blocking in SleepSleep• An executing thread may request some resource or action that causes it to block or sleep awaiting some event.passage of a specific amount of time (a pause request)completion of I/O to a slow device (e.g., keyboard or disk)release of some needed resource (e.g., memory)In Nachos, threads block by calling Thread::Sleep.• A sleeping thread cannot run until the event occurs.• The blocked thread is awakened when the event occurs.E.g., Wakeup or Nachos Scheduler::ReadyToRun(Thread* t)• In an OS, threads or processes may sleep while executing in the kernel to handle a system call or fault.Why Threads Are ImportantWhy Threads Are Important1. There are lots of good reasons to use threads.“easy” coding of multiple activities in an applicatione.g., servers with multiple independent clientsparallel programming to reduce execution time2. Threads are great for experimenting with concurrency. context switches and interleaved executionsrace conditions and synchronizationcan be supported in a library (Nachos) without help from OS3. We will use threads to implement processes in Nachos.(Think of a thread as a process running within the kernel.)ConcurrencyConcurrencyWorking with multiple threads (or processes) introduces concurrency: several things are happening “at once”.How can I know the order in which operations will occur?• physical concurrencyOn a multiprocessor, thread executions may be arbitrarily interleaved at the granularity of individual instructions.• logical concurrencyOn a uniprocessor, thread executions may be interleaved as the system switches from one thread to another.context switch (suspend/resume)Warning: concurrency can cause your programs to behave unpredictably, e.g., crash and burn.CPU Scheduling 101CPU Scheduling 101The CPU scheduler makes a sequence of “moves” that determines the interleaving of threads.• Programs use synchronization to prevent “bad moves”.• …but otherwise scheduling choices appear (to the program) to be nondeterministic.The scheduler’s moves are dictated by a scheduling policy.Wakeup orReadyToRunGetNextToRun()SWITCH()readyListblockedthreadsinterrupt current threador wait for it to block/yield/terminateContext Switches: Voluntary and InvoluntaryContext Switches: Voluntary and InvoluntaryOn a uniprocessor, the set of possible execution schedules depends on when context switches can occur.• Voluntary: one thread explicitly yields the CPU to another.E.g., a Nachos thread can suspend itself with Thread::Yield.It may also block to wait for some event with Thread::Sleep.• Involuntary: the system scheduler suspends an active thread, and switches control to a different thread.Thread scheduler tries to share CPU fairly by timeslicing.Suspend/resume at periodic intervals (e.g., nachos -rs)Involuntary context switches can happen “any time”.The Dark Side of ConcurrencyThe Dark Side of ConcurrencyWith interleaved executions, the order in which processes execute at runtime is nondeterministic.depends on the exact order and timing of process arrivalsdepends on exact timing of asynchronous devices (disk, clock)depends on scheduling policiesSome schedule interleavings may lead to incorrect behavior.Open the bay doors before you release the bomb.Two people can’t wash dishes in the same sink at the same time.The system must provide a way to coordinate concurrent activities to avoid incorrect interleavings.Example: A Concurrent Color StackExample: A Concurrent Color StackInitColorStack() {push(blue);push(purple);}PushColor() {if (s[top] == purple) {ASSERT(s[top-1] == blue);push(blue);} else {ASSERT(s[top] == blue);ASSERT(s[top-1] == purple);push(purple);}}Interleaving the Color Stack #1Interleaving the Color Stack #1PushColor() {if (s[top] == purple) {ASSERT(s[top-1] == blue);push(blue);} else {ASSERT(s[top] == blue);ASSERT(s[top-1] == purple);push(purple);}}ThreadBody() {while(1)PushColor();}Interleaving the Color Stack #2Interleaving the Color Stack #2if (s[top] == purple) {ASSERT(s[top-1] == blue);push(blue);} else {ASSERT(s[top] == blue);ASSERT(s[top-1] == purple);push(purple);}Interleaving the Color Stack #3Interleaving the Color Stack #3if (s[top] == purple) {ASSERT(s[top-1] == blue);push(blue);} else {ASSERT(s[top] == blue);ASSERT(s[top-1] == purple);push(purple);}Consider a yield here on blue’s first call to PushColor().XInterleaving the Color Stack #4Interleaving the Color Stack #4if (s[top] == purple) {ASSERT(s[top-1] == blue);push(blue);} else {ASSERT(s[top] == blue);ASSERT(s[top-1] == purple);push(purple);}Consider yield here on blue’s first call toPushColor().XThreads vs. ProcessesThreads vs. Processes1. The process is a kernel abstraction for an independent executing program.includes at least one “thread of control”also includes a private address space (VAS)-