IntrotoOS CUCS MosséProcesses and Threads• What is a process? What is a thread? What types?• A program has one or more locus of execution. Eachexecution is called a thread of execution. The set ofthreads comprise a process.• Not an object or executable files: must be executing• Each thread contains:–aninstruction pointer (IP), a register with next instruction.–astack for temporary data (eg, return addresses, parameters)–adata area for data declared globally and statically• A process/thread is active, while a program is not.IntrotoOS CUCS MosséHow to run a program• The executable code is loaded onto memory (where?)• Space is allocated to variables (what types of vars?)• A stack is allocated to the process (for what?)• Registers are updated (which registers?)• Control (of execution) goes to the process (how?)• Process runs one instruction at a time, in a cycle:– fetch the instruction from memory– decode the instruction– update the IP– execute the instructionIntrotoOS CUCS MosséProcesses and Threads (revisited)• Address space: memory reserved for a process• A heavyweight process has a single locus of executionper address space, a single IP, a single PCB• A Process Control Block (PCB) contains informationpertaining to the process itself– state (running, ready, etc)– registers and flags (stack pointer, IP, etc)– resource information (memory/CPU usage, open files, etc)– process ID– security and protection information– accounting info (who to bill, limits, similar to resource info)IntrotoOS CUCS MosséProcesses and Threads (cont)• Thread (lightweight process)ofaprocesssharesomeresources (e.g., memory, open files, etc)• Threads have their own stack, IP, local address space• With only a single process in memory, easy to manage• For example, if a process requests IO (eg, read fromkeyboard), it just stays in the memory waiting• Several threads or processes complicate things; whenIO is requested, why make other processes wait?• Context switching takes place… take a waiting thread“out of the CPU” and put a thread that is ready in CPUIntrotoOS CUCS MosséState Diagram• Create: PCB and other resources are setup• End: resources held are returned to the OS (freed)• Context switching: saves HW context; updates PCB• States are typically implemented as queues, lists, setsendreadyblockedrunningcreatedispatchQuantumexpiredIOcompletedIOrequestedprocesscompletedprocessinitializedIntrotoOS CUCS MosséThese two states check for sufficientresources in the systemComplete State DiagramprocessstartedendreadyblockedrunningcreateIOcompletedIOrequestedprocesscompletedadmissioncontrolsuspendedprocesssubmittedtemporarysuspensionprocessreturnsdispatchQuantumexpiredIntrotoOS CUCS MosséMultiple Threads and Processes• Several problems with multitasking:– fairness in usage of CPU– fairness in usage of other resources– coordinated input and output– lack of progress (deadlocks and livelocks)– synchronization: access to the same data item by severalprocesses/threads (typical example, deposits into account)IntrotoOS CUCS MosséSynchronization Example• At time t=6 T2 requests the withdrawal of $200 (andgets preempted); at t=8 T1 requests the deposit of$200; t=9, T1 reads balance ($300); at t=10, T2 adds$200, at t=11, T1 writes new balance; at t=12, T2resumes and reads balance; at t=13, T2 subtracts $200;at t=14, T2 writes new balance• What if order was changed: 6, 8, 9, 12, 13, 14, 10, 11?• Other combinations?6 7 8 9 10 1112131415...T2req T1req T1r T1c T1w T2r T2c T2wIntrotoOS CUCS MosséMore on Synchronization• Semaphores and primitives serve to achieve mutualexclusion and synchronized access to resources• Clearly, there is more delays associated with attemp-ting to access a resource protected by semaphores• Non-preemptive scheduling solves that problem• As an aside:– Which scheduling mechanism is more efficient? Preemptiveor non-preemptive?– Within each type of scheduling (pr or non-pr), one canchoose which policy he/she wants to useIntrotoOS CUCS MosséUsing Semaphores• When threads use semaphores, they are attempting toreserve a resource for usage. Only the threads thatsucceed are allowed in the CS.• If there is a thread in the CS already, other requestingthreads are blocked, waiting on an event• When the thread exits the CS, the OS unblocks thewaiting thread, typically during the V(s) sys_call• The now unblocked thread becomes ready• The OS may decide to invoke the scheduler… or notIntrotoOS CUCS MosséTypes of Synchronization• There are 2 basic types of sync:P1::P(s1)…V(s1)P2::P(s1)…V(s1)P2::P(s2)…V(s1)P1::P(s1)…V(s2)MUTEXBARRIER SYNCIntrotoOS CUCS MosséDeadlocks• When a program is written carelessly, it may cause a…• DEADLOCK!!!• Each process will waitfor the other processindefinitely• How can we deal withthese abnormalities?• Avoidance, prevention, or detection and resolution• Which one is more efficient?P1::P(s1)P(s2)…V(s2)V(s1)P2::P(s2)P(s1)…V(s1)V(s2)IntrotoOS CUCS MosséDining Philosophers• There were some hungry philosophers, and some angryphilosophers (not the same, not Rastas)• Each needed two forks, each shared both his/her forks• Possible deadlock situation! HOW?• Is it possible to have a (literally) starvation situation?• What is the best solution?– Round-robin? FIFO? How good are FIFO and RR?• Important: what is the metric to judge a solution by?– Least overhead? Minimum starvation?– How to evaluate