Threads and ConcurrencyA First Look at Some Key ConceptsThreadsTwo Threads Sharing a CPUA Peek Inside a Running ProgramA Program With Two ThreadsThread Context SwitchContext Switches: Voluntary and InvoluntaryA Nachos ThreadWhy Threads Are ImportantConcurrencyThe Dark Side of ConcurrencyExample: A Concurrent Color StackInterleaving the Color Stack #1Interleaving the Color Stack #2Interleaving the Color Stack #3Interleaving the Color Stack #4Race Conditions DefinedThreads vs. ProcessesUser-level ThreadsKernel-Supported ThreadsThreads and ConcurrencyThreads and ConcurrencyA First Look at Some Key ConceptsA First Look at Some Key ConceptskernelThe software component that controls the hardware directly, and implements the core privileged OS functions.Modern hardware has features that allow the OS kernel to protect itself from untrusted user code.threadAn executing stream of instructions and its CPU register context.virtual address spaceAn execution context for thread(s) that provides an independent name space for addressing some or all of physical memory.processAn execution of a program, consisting of a virtual address space, one or more threads, and some OS kernel state.ThreadsThreadsA 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.Two Threads Sharing a CPUTwo Threads Sharing a CPUrealityconceptcontext switchA Peek Inside a Running ProgramA Peek Inside a Running Program0highcode libraryyour dataheapregistersCPUR0RnPC“memory”xxyour programcommon runtimestackaddress space(virtual or physical)SPyyA 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 outContext 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”.A Nachos ThreadA Nachos ThreadThread* tmachine statename/status, etc.“fencepost”0xdeadbeefStacklowhighstack topunused regionthread objectorthread control blockint stack[StackSize]t = new Thread(name);t->Fork(MyFunc, arg);currentThread->Sleep();currentThread->Yield();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.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 to PushColor().XRace Conditions DefinedRace Conditions Defined1. Every data structure defines invariant conditions.defines the space of possible legal states of the structuredefines what it means for the structure to be “well-formed”2. Operations depend on and preserve the invariants.The invariant must hold when the operation begins.The operation may temporarily violate the invariant.The operation restores the invariant before it