AdministriviaThreads and ConcurrencyThreadsA Peek Inside a Running ProgramTwo Threads Sharing a CPUA Program With Two ThreadsThread Context SwitchThread States and TransitionsBlocking in SleepWhy Threads Are ImportantConcurrencyCPU Scheduling 101Context Switches: Voluntary and InvoluntaryThe Dark Side of ConcurrencyExample: A Concurrent Color StackInterleaving the Color Stack #1Interleaving the Color Stack #2Interleaving the Color Stack #3Interleaving the Color Stack #4Threads vs. ProcessesKernel-Supported ThreadsUser-level ThreadsA Nachos ThreadA Nachos Context SwitchRace Conditions DefinedAvoiding Races #1Critical Sections in the Color StackAvoiding Races #2Synchronization 101Digression: Sleep and Yield in NachosResource Trajectory GraphsRelativity of Critical SectionsQuestions about Nachos Context SwitchesDebugging with ThreadsAdministriviaAdministrivia• 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 Program0CPUhighheapregistersR0RnPCxxSPyycommon runtimeyour programcode libraryaddress space(virtual or physical)your datastack“memory”Two Threads Sharing a CPUTwo Threads Sharing a CPUrealityconceptcontext switchA Program With Two ThreadsA Program With Two Threads0highregistersR0RnPC“memory”xxstackSPyystack“on deck” and ready to runaddress spacecommon runtimeprogramcode libraryrunningthreaddataCPUThread Context SwitchThread Context Switch0highcode librarydata“memory”stackystackregistersR0RnPCxSPyswitch inswitch outaddress spacecommon runtimexprogram1. save registersCPU2. load registersThread States and TransitionsThread States and TransitionsScheduler::RunThread::Yield(voluntary or involuntary)runningThread::Sleep(voluntary)blocked readyScheduler::ReadyToRun(“wakeup”)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.readyListinterrupt current threador wait for it to block/yield/terminateblockedthreadsWakeup orReadyToRunGetNextToRun()SWITCH()Context 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] ==