1Outline for Today• Objectives: – To define the process and thread abstractions.– To briefly introduce mechanismsfor implementing processes (threads).– To introduce the critical section problem.– To learn how to reason about the correctness of concurrent programs.• Administrative details: – Groups are listed on the web site, linked off main page under Communications.2The Basics of Processes• Processes are the OS-provided abstraction of multiple tasks (including user programs) executing concurrently.• One instance of a program (which is only a passive set of bits) executing(implying an execution context –register state, memory resources, etc.)• OS schedules processes to share CPU.3Why Use Processes?• To capture naturally concurrent activities within the structure of the programmed system.• To gain speedup by overlapping activities or exploiting parallel hardware.– From DMA to multiprocessorsP P P PMemory4Separation of Policy and Mechanism• “Why and What” vs. “How”• Objectives and strategies vs. data structures, hardware and software implementation issues.• Process abstraction vs. Process machineryCan you think of examples?5Process Abstraction• Unit of scheduling• One (or more*) sequential threads of control – program counter, register values, call stack• Unit of resource allocation – address space (code and data), open files– sometimes called tasks or jobs• Operations on processes: fork (clone-style creation), wait (parent on child), exit (self-termination), signal, kill.Process-related System Calls in Unix.6Threads and Processes• Decouple the resource allocation aspect from the control aspect• Thread abstraction - defines a single sequential instruction stream (PC, stack, register values)• Process - the resource context serving as a “container” for one or more threads (shared address space)• Kernel threads - unit of scheduling (kernel-supported thread operations −> still slow)7Threads and ProcessesAddress Space Address SpaceThread Thread Thread8An ExampleAddress SpaceThread ThreadEditing thread:Responding toyour typing in your docAutosavethread: periodicallywrites your docfile to diskdocDoc formatting process9User-Level Threads• To avoid the performance penalty of kernel-supported threads, implement at user level and manage by a run-time system – Contained “within” a single kernel entity (process)– Invisible to OS (OS schedules their container, not being aware of the threads themselves or their states). Poor scheduling decisions possible.• User-level thread operations can be 100x faster than kernel thread operations, but need better integration / cooperation with OS.10Process Mechanisms• PCB data structure in kernel memory represents a process (allocated on process creation, deallocated on termination).• PCBs reside on various state queues (including a different queue for each “cause” of waiting) reflecting the process’s state. • As a process executes, the OS moves its PCB from queue to queue (e.g. from the “waiting on I/O” queue to the “ready to run” queue).11Context Switching• When a process is running, its program counter, register values, stack pointer, etc. are contained in the hardware registers of the CPU. The process has direct control of the CPU hardware for now.• When a process is not the one currently running, its current register values are saved in a process descriptor data structure (PCB - process control block)• Context switching involves moving state between CPU and various processes’ PCBs by the OS.12Process State TransitionsReadyCreateProcessRunningBlockedDoneWakeup(due to interrupt)sleep (due tooutstanding requestof syscall)scheduledsuspendedwhile anotherprocess scheduled13Interleaved SchedulesUni-processor implementationlogical concept /multiprocessorimplementationcontext switch14PCBs & Queuesprocess stateprocess identifierPCStack Pointer (SP)general purpose regowner useridopen filesscheduling parametersmemory mgt stuffqueueptrs...other stuff...process stateprocess identifierPCStack Pointer (SP)general purpose regowner useridopen filesscheduling parametersmemory mgt stuffqueueptrs...other stuff...process stateprocess identifierPCStack Pointer (SP)general purpose regowner useridopen filesscheduling parametersmemory mgt stuffqueueptrs...other stuff...head ptrtail ptrhead ptrtail ptrReady Queue Wait on Disk Read15The Trouble with Concurrency in Threads...Thread0 Thread1Data: xwhile(i<10){x=x+1;i++;}0while(j<10){x=x+1;j++;}00i jWhat is the value of x when both threadsleave this while loop?16Nondeterminism• What unit of work can be performed without interruption? Indivisible or atomic operations.• Interleavings - possible execution sequences of operations drawn from all threads.• Race condition - final results depend on ordering and may not be “correct”.while (i<10) {x=x+1; i++;}load value of x into regyield( )add 1 to regyield ( )store reg value at xyield ( )17Reasoning about Interleavings• On a uniprocessor, the possible execution sequences depend on when context switches can occur– Voluntary context switch -the process or thread explicitly yields the CPU (blocking on a system call it makes, invoking a Yield operation).– Interrupts or exceptions occurring - an asynchronous handler activated that disrupts the execution flow.– Preemptive scheduling - a timer interrupt may cause an involuntary context switch at any point in the code.• On multiprocessors, the ordering of operations on shared memory locations is the important factor.18Critical Sections• If a sequence of non-atomic operations must be executed as if it were atomic in order to be correct, then we need to provide a way to constrain the possible interleavings in this critical section of our code. – Critical sections are code sequences that contribute to “bad” race conditions.– Synchronization needed around such critical sections.• Mutual Exclusion - goal is to ensure that critical sections execute atomically w.r.t. related critical sections in other threads or processes.– How?19The Critical Section ProblemEach process follows this template:while (1){ ...other stuff... //processes in here shouldn’t stop othersenter_region( );critical sectionexit_region( );}The problem is to define enter_region and exit_region to ensure mutual exclusion with some degree of fairness.20Implementation Options for Mutual Exclusion• Disable Interrupts• Busywaiting solutions -