From Processes to ThreadsProcesses and ThreadsProcess abstraction combines two conceptsConcurrencyEach process is a sequential execution stream of instructionsProtectionEach process defines an address spaceAddress space identifies all addresses that can be touched by the programThreadsKey idea: separate the concepts of concurrency from protectionA thread represents a sequential execution stream of instructionsA process defines the address space that may be shared by multiple threadsThe Case for ThreadsConsider the following code fragmentfor(k = 0; k < n; k++)! a[k] = b[k] * c[k] + d[k] * e[k];Is there a missed opportunity here? On a Uni-processor? On a Multi-processor?The Case for ThreadsConsider a Web server! get network message from client! get URL data from disk! compose response! send responseHow well does this web server perform?Introducing ThreadsA thread represents an abstract entity that executes a sequence of instructionsIt has its own set of CPU registers It has its own stackThreads are lightweightThere is no thread-specific heap or data segment (unlike process)Therefore, context switching is much cheaper than for a processExamples:OS-supported: Sun’s LWP, POSIX’s threadsLanguage-supported: Modula-3, JavaProgrammer’s Viewmain()! some code! tid = CreateThread(fn1, arg0, arg1, …);! some more codefn1(int arg0, int arg1, …)! some codeAfter CreateThread is called, execution in parent thread continues in main function, and, in parallel, execution in child thread starts at fn1 How Can it Help?Consider the following code fragmentfor(k = 0; k < n; k++)! a[k] = b[k] * c[k] + d[k] * e[k];Rewrite this code fragment as:CreateThread(fn, 0, n/2);CreateThread(fn, n/2, n);fn(l, m)! for(k = l; k < m; k++)! ! a[k] = b[k] * c[k] + d[k] * e[k];What did we gain?How Can it Help?Consider a Web server Create a number of threads, and for each thread doget network message from clientget URL data from diskcompose responsesend responseWhat did we gain?Threads vs. ProcessesThreadsNo data segment or heapMultiple can coexist in a processShare code, data, heap and I/0Have own stack and registers, but no isolation from other threads in the same processInexpensive to createInexpensive context switchingProcessesHave data/code/heap and other segmentsInclude at least one threadHave own address space, isolated from other processes’Expensive to createExpensive context switchingImplementing ThreadsProcesses define address space; threads share address spaceProcess Control Block (PCB) contains process-specific information Owner, PID, heap pointer, priority, active thread, and pointers to thread informationThread Control Block (TCB) contains thread-specific informationStack pointer, PC, thread state (running, …), register values, a pointer to PCB, …CodeInitialized dataHeapDLL’smapped segmentsProcess’s address spaceStack – thread1PCSPStateRegisters…TCB for Thread1Stack – thread2PCSPStateRegisters…TCB for Thread2Implementing Threads (Cont’d.)CreateThread(pointer_to_procedure, arg0, …) {! // allocate a new TCB and stack ! TCB tcb = new TCB(); Stack stack = new Stack(); ! // initialize TCB and stack with initial register values and address of first instruction! tcb.pc = Stub;! tcb.stack = stack;! tcb.arg0reg = pointer_to_procedure;! tcb.arg1reg = arg0; ! …! // Tell the dispatcher about the newly created thread! ReadyQ.add(tcb);}Stub(proc, arg0, arg1, …) { (*proc)(arg0, arg1, …); DeleteCurrentThread();}Threads Life CycleReadyStartRunningWaitingDoneThreads (just like processes) go through a sequence of start, ready, running, waiting, and done statesBasic operationSwitch to kernel initiated bySystem call (e.g., IO, yield CPU, etc.)ExceptionInterrupt (e.g., timer interrupt)Dispatching Kernel ThreadsThread is runningSwitch to kernelSave thread state (TCB)Choose new thread to runLoad state of the chosen thread (from TCB)…User-level ThreadsMotivationThreads are a useful programming abstractionImplement thread creation/manipulation using procedure calls to a user-level library rather than system callsUser-level threads!User-level library implementations for!CreateThread(), DestroyThread(), Yield(), …User-level library performs same actions of corresponding system callsMain difference with kernel threads: thread management is under the control of user-level libraryPros and Cons of User-level ThreadsProsNo context for switching between threadsFlexible schedulingApplication specificProcess specificThreads voluntarily give up CPU–easy to reason about!ConsOS is unaware of user-level threadsThread blocked for I/O blocks entire processOS schedules processes independent of number of threads within a processKernel Threads vs. User-level ThreadsKernel threads:Known to OSSwitching between them within same process is inexpensive (though not quite as for user-level threads)The values of registers, PC, and stack pointers are changedMemory management information does not changeKernel uses process scheduling algorithms to manage threadsUser-level threads:OS does not know about user-level threadsOS is only aware of the process containing threadsOS schedules processes, not threadsProgrammer uses a threads library to manage threads (create, delete, synchronize and schedule)Concurrency is great …int a = 1, b = 2;main() {! CreateThread(fn1, 4);! CreateThread(fn2, 5);}fn1(int arg1) {! if(a) b++; }fn2(int arg1) {! a = arg1;}What are the value of a and bat the end of execution?…but can be problematicint a = 1, b = 2;main() {! CreateThread(fn1, 4);! CreateThread(fn2, 5);}fn1(int arg1) {! if(a) b++; }fn2(int arg1) {! a = 0;}What are the values of a & bat the end of execution?Some More ExamplesWhat are the possible values of x in these cases?Thread1: x = 1; Thread2: x = 2;Initially y = 10;Thread1: x = y + 1; Thread2: y = y * 2;Initially x = 0;Thread1: x = x + 1; Thread2: x = x + 2;This is because …Order of process/thread execution is non-deterministicA system may contain multiple processors and cooperating threads/processes can execute simultaneouslyThread/process execution can be interleaved because of time-slicingOperations are often not atomicAn atomic operation is one that executes to completion without any interruption or failure---it is “all or nothing”Goal: Ensure correctness under ALL possible interleavingChallengeEnumerating all cases is not possible!Need to define synchronization constructs and programming style for developing concurrent