Topic 2 - Concurrency (1) PDF

Topic 2: Concurrency Distributed Network Architectures & Operating System’s Overview Distributed Network Architectures & Operating Systems Operating Systems architec...

Topic 2: Concurrency Distributed Network Architectures & Operating System’s Overview Distributed Network Architectures & Operating Systems Operating Systems architectures Process life cycle Process execution Scheduling Threads Process synchronisation Mutual exclusion and Critical sections Semaphores Producer-Consumer Dining philosophers problem 2 Directed Study Distributed Network Architectures & Operating Systems Directed study (activities will be released on a weekly basis) 1. Read chapter 2 (Processes and Threads) from Modern Operating Systems book. 2. Read the "Minix 3 - A highly reliable, self-repairing operating system" paper. 3. Read paper "Real-Time-Operating Systems" 4. Read paper "Integrating Flexible Support for Security Policies into the Linux Operating System." 5. Read paper "Survey and performance evaluation of real-time operating systems (RTOS) for small microcontrollers" 6. Start looking at and follow the C programming tutorials at W3 3 Schools / Tutorialspoint (links in the activities section)  (Windows) Operating Systems: Architecture Distributed Network Architectures & Operating 4 Systems  (Linux) Operating Systems Structure Distributed Network Architectures & Operating 5 Systems Operating Systems Structure (Minix) Distributed Network Architectures & Operating Systems MINIX 3 is structured in four layers. Only processes in the bottom layer may use privileged (kernel mode) instructions. 6 Areas of the Kernel covered in this topic Concurrency Distributed Network Architectures & Operating Systems Processes & threads Process life cycle Process execution Scheduling Other considerations: Inter process communication & sharing Critical Sections Semaphores Buffers 7  Programs and Processes A program is the code written by a Distributed Network Architectures & Operating Systems programmer A process (job, task) is basically a program in execution – a particular instance of the program Data are stored values used for computations by the process Several instances of the same program may be launched (sharing the same code) Each process uses its address space (a 8 list of memory locations which the process can read and write): Process Life Cycle – Process Creation A process can be created in one of Distributed Network Architectures & Operating Systems two ways: The program is executed by a user (e.g. via a double-click using a GUI or by typing in a command using a console to “trigger” the processor to load executable file with program code to memory) Through spawning/forking by another process The process that creates a new process is called the parent while the created process is 9 called the child The child can also spawn a new process forming a tree of processes Process Life Cycle - Process Table and Process Control Block When a new process is created it is given a unique process Distributed Network Architectures & Operating Systems identification number (PID) which is stored in a process table by the OS A Process Control Block (PCB) is also created, holding all the information about the process 10 Process Life Cycle – Process Descriptors Process descriptor fields – examples in MINIX Distributed Network Architectures & Operating Systems 11  Process Life Cycle – State Queues At any time, a process is in one and Distributed Network Architectures & Operating Systems only one state At any time, at most one process is in the RUNNING state There may be queue of processes in the READY state There may be several queues of processes in the BLOCKED state Each queue represents one resource for which processes in that queue are waiting 12 Process Life Cycle – Three State Model Distributed Network Architectures & Operating Systems A process, once initiated, can be in one of three main states (stored in PCB): READY: ready to run but waiting for the CPU RUNNING: actually running on the CPU BLOCKED: waiting for resource to become available 13 (e.g. due to an I/O operation which needs to complete)  Process Life Cycle – Process Termination Voluntary termination: Distributed Network Architectures & Operating Systems Normal exit: process has done its work Error exit: process itself handles and “catches” an error (e.g. try-catch code to check if variable not defined) Involuntary termination: Fatal error: error detected by OS protected mode (e.g. exception error due to reference to non-existent memory or division by zero) Killed by another process: a process that executes a system call that causes OS to kill another process 14 Process Execution - Fetch-Execute Cycle The processor in general terms executes a process as follows: Distributed Network Architectures & Operating Systems Start Proces s Fetch Instructio n Execute Instructio n Termina te Process 15 Process Execution Distributed Network Architectures & Operating Systems The Fetch-Execute Cycle However, what if a process blocks the processor because it is waiting for an event to occur? (e.g. a printer to finish its job) Or what if a high-priority process is supposed to execute ASAP? The processor simply cannot wait for the current process to terminate! 16  Process Execution - Interrupts Distributed Network Architectures & Operating Systems An interrupt is a signal sent to the processor indicating that an event caused by hardware or software needs immediate attention. For example: When an I/O event occurs, process execution is suspended The processor can then switch execution to another process When I/O completes, an interrupt will occur, which diverts execution to the interrupt handling routine The suspended program may 17 restart, if conditions are met  Process Execution - Interrupts Distributed Network Architectures & Operating Systems An interrupt is a signal sent to the processor indicating that an event caused by hardware or software needs immediate attention: I/O interrupt: caused by I/O devices to signal completion or error Timer interrupt: caused by a processor timer used to alert the OS at specific instants Program interrupt: caused by error conditions within user program or fatal errors Interrupts enable OS’s to oversee several programs and I/O events 18 simultaneously Process Execution – Updated Fetch-Execute Cycle Distributed Network Architectures & Operating Systems Start Proces s Termina Fetch Instructio te n Process Execute Termina Instructio te n Process No Interrup t? Yes Handle 19 Interrupt  Concurrency A (single-core) processor can only execute a single Distributed Network Architectures & Operating Systems instruction at a time The processor continues executing a process until: The process issues an I/O request by a system call An interrupt occurs The moment a user process execution is suspended (i.e. the process is blocked), the OS takes over and starts handling the I/O request or launches the interrupt handler Once the OS takes control, it can then switch the processor to executing another process This allows a processor to run several processes concurrently (although only a single instruction of a specific process is executing at any given time) This interleaved execution is called multitasking – it does not 20 require parallel execution  Process Scheduling – The Scheduler After an I/O system call or interrupt handling, Distributed Network Architectures & Operating Systems control is passed to the scheduler to decide which job to execute. The scheduler works as follows: Check if the current process is still the most suitable to run? If so, return control to it. Otherwise: Save the state of the current process in the process table Retrieve the state of the most suitable process Transfer control to the newly selected process, at the point indicated by the restored program counter This action of storing the state of the current process and activating another process is called context switch 21 a context switch Context switching must be minimized to reduce overheads Process Scheduling - Scheduling Scheduling is the act of determining the optimal sequence and Distributed Network Architectures & Operating Systems timing of assigning execution to processes Different scheduling criteria: CPU utilisation: keep the CPU as busy as possible Efficiency: maximise system throughput Fairness: be fair to all users This means different policies and algorithms for scheduling 22 Process Scheduling – Scheduling Policies and Algorithms 2 scheduling policies Distributed Network Architectures & Operating Systems Non-preemptive: allow processes to run until complete or encountering an I/O wait Preemptive: allow processes to be interrupted and replaced by other processes (generally through timer interrupts) Number of scheduling algorithms Non-preemptive: first come, first serve/first in, first out (FCFS/FIFO), shortest job first (SJF) Preemptive: shortest remaining time (SRT); highest response ratio next (HRRN); round robin (RR); multi-level feedback queues (MFQ) 23 We will also revisit scheduling when it comes to distributed systems next term. Process Scheduling – Scheduling Algorithms – Case Study Distributed Network Architectures & Operating Systems Time that it takes for Instant at which process process to finish if in is first created continuous execution waiting time = the sum of the time spent in the ready queue during the 24 life of the process (time blocked, waiting for I/O, is not part of the waiting time) Non-Preemptive Scheduling – First Come, First Served / First in, first out (FCFS/FIFO) Distributed Network Architectures & Operating Systems Assigns processor to the process that is ready first Favours long jobs To be fair, the ratio between waiting time/run time should be about the same for each process. 25 Non-Premptive Scheduling – Shortest Job First (SJF) Distributed Network Architectures & Operating Systems Selects job with shortest estimated run time Favours short jobs Similar ratio but long jobs may be starved by arriving of short jobs Exercise: What would be the temporal diagram in this case? 26 Premptive Scheduling – Shortest Remaining Time (SRT) Distributed Network Architectures & Operating Systems Pre-emptive version of SJF - selects job with shortest estimated remaining time During the run of a process, if a new job arrives whose run-time is shorter than the remaining run-time of current process, it will be pre- empted to allow the new job to start Favours short jobs – long jobs may be starved Needs to measure elapsed run-time – increased system overhead Exercise: What would be the temporal diagram in this case? 27 Preemptive Scheduling – Highest Response Ratio Next (HRRN) Distributed Network Architectures & Operating Systems Derived from SJF to reduce its bias against long jobs and avoid starvation Each job is assigned a priority Based on memory, time and/or any other resource requirement [(waiting time + run time) / run time] Job with the highest priority goes first Priorities may change when a new job comes in Exercise: Lets say that processes are assigned a letter in reverse order of priority (E = greatest priority; A = lowest priority) What would be the temporal diagram in this 28 case? Preemptive Scheduling – Round Robin Assigns processor to each process in turn with a fixed time quantum, Distributed Network Architectures & Operating Systems typically 10-20ms (modern processor clock frequencies > 2GHz, which implies clock periods of 5.0⋅10-7ms) If a process runs over its quantum (timeout) it is interrupted, and returned to the back of the queue Heavy overhead due to continuous context switches READY QUEUE DISPATCH CPU TIMEOUT 29 We will revisit this when looking at distributed systems next term. Process Scheduling – Round Robin Assigns processor to each process in turn with a fixed time quantum, Distributed Network Architectures & Operating Systems typically 10-20ms (modern processor clock frequencies > 2GHz, which implies clock periods of 5.0⋅10-7ms) If a process runs over its quantum (timeout) it is interrupted, and returned to the back of the queue Heavy overhead due to continuous context switches 30  Process Scheduling – Multi-Level Queues Basically, it is not another Distributed Network Architectures & Operating Systems scheduling algorithm Consists of several independent queues Makes use of other existing scheduling algorithms Priorities are assigned to each queue Useful to maintain common processes I/O jobs in one queue and CPU jobs in another one. Jobs can also move from one queue to another as their priority changes In fact the scheduler of MINIX 3 31 uses multi-level queues (16 queues) Distributed Systems and Scheduling In topic 9, we will look at scheduling in distributed systems. Distributed Network Architectures & Operating Systems In distributed computing, this becomes more of a routing problem and ensuring there are no over / under loaded nodes within the system. There are a number of methods: Round robin Priority based (weighted round robin) Sender / receiver initiated Least connection/Least Loaded Min-max Max-min Opportunistic load balancing Equally spread current execution Throttled load balancing 32 Ant colony optimisation We will discuss these next term in topic 9. Threads A thread is an independent path/sequence of execution within a Distributed Network Architectures & Operating Systems process By default, a process is run by means of a “single execution thread” However, different parts of the same process could be parallelised to make the system more efficient or usable – multi-threading Multi-threading provides a way of improving application performance Time Thread 33 Single-threaded process Multi-threaded process Threads vs Processes A thread is similar to a process Distributed Network Architectures & Operating Systems Both have a single sequential flow of control with start and end At any time a thread has a single point of execution A thread has its own execution context and stack (history) & program counter – thread control block (TCB) Each thread follows its own 3-state model (running, blocked, ready) Context switching also happens for threads A thread can spawn another thread PCB share co e d In fact, a thread is often called a lightweight process fil at d es d a amon g regs. regs. regs. threa stack stack stack TC ds TC TC B B B 34 multi-threaded process Threads vs Processes However, a thread differs from a process Distributed Network Architectures & Operating Systems A thread cannot exist on its own – it exists within a process Usually created and/or controlled by a process Threads can share process properties, including memory and open files Inexpensive creation and context switching Do not need separate address space PCB share co e d fil at d es d a amon g regs. regs. regs. threa stack stack stack TC ds TC TC B B B 35 multi-threaded process Threads vs Processes Distributed Network Architectures & Operating Systems Multiple threads running is analogous to processes running concurrently The difference is that threads share an address space whereas processes share resources (memory, disk, printers etc.) Process properties are shared between threads 36 Thread properties are local and private to each thread Threads – Concurrent Vs Sequential Programming Distributed Network Architectures & Operating Systems What is sequential programming? Traditional activity of constructing a program using a sequential computer language (e.g. C, Python, etc) Programming methodology assumes that statements are executed in order (i.e. sequence) The program is assumed to execute on a single-CPU system Single thread of control We will revisit how we have to think 37 about programming distributed systems next term.  Threads – Concurrent Vs Sequential Programming Distributed Network Architectures & Operating Systems What is concurrent programming? The activity of constructing a program taking advantage of concurrency allowed by the use of multiple threads Multiple threads of control allow processes to perform multiple computations in parallel and to control parallelism multitasking simultaneous external activities The program may run both on: a multi-CPU system (true parallelism) a single-CPU system (multitasking)... Needs language support but also OS support Old-school OS’s were generally single-threaded, but 38 modern OS’s This can besupport scaled multithreading up to include systems made out of 100’s / 1000’s nodes – even more issues to consider for these type of systems - we will Sequential Execution – Order and Precedence Only one possible sequence of execution Distributed Network Architectures & Operating Systems A sequential program gives the system strict instructions on the order of executing the statements in the program. For instance, the simple program below with three statements P; Q; R; tells the system to execute the statement in the order P => Q => R i.e. P must precede Q, and Q must precede R 39 Sequential Execution – Order and Precedence – High-Level (High-level language) example: Distributed Network Architectures & Operating Systems x = 1; (P) y = x+1; (Q) x = y+2; (R) The final values of x and y depend on the order of executing the statements For DS’s, order is extremely important – What would happen if “y=x+1” came first? Will discuss order dependency next term but 40 this has implications for dependencies between iterations, synchronisation etc.  Sequential Execution – Order and Precedence – System-Level Distributed Network Architectures & Operating Systems Each statement may be compiled into several machine instructions as follows: 1. P is treated as a single machine instruction: P1: store 1 at the address of x 2. Q is broken into 3 machine instructions: Q1: load the value x into a CPU register Q2: increment the value in this register by 1 Q3: store the value in this register at the address of y 3. Similarly, R is broken into 3 machine instructions: R1: load the value of y into a CPU register R2: increment the value in this register by 2 41 R3: store the result at the address of x  Sequential Execution – The Nature of Sequential Execution Distributed Network Architectures & Operating Systems The execution sequence at the program level P => Q => R Implies the execution sequence at the system level P1 => Q1 => Q2 => Q3 => R1 => R2 => R3 Single-threaded computation, no overlap in the execution of the statements – total ordering Deterministic: same input always results in same output User specifies a strict sequence of steps to achieve desired goal However, this does not apply in many practical 42 applications, for which a sequence of steps is not really needed Concurrent Execution - Interleaving In a single-CPU system, the execution of threads in a Distributed Network Architectures & Operating Systems concurrent program is interleaved in an unpredictable order The operations within each thread are strictly ordered but the interleaving of operations is not Example: a concurrent program spawns threads t1 and t2: t1 has three statements A, B, C t2 has two statements S and T main; run t1; t2; end t1; t2; begin A; B; begin S; T; 43 C; end end Concurrent Execution - Interleaving In this example, there are 10 possible Distributed Network Architectures & Operating Systems main interleaving's yielding 10 possible different execution sequences (begin t1, begin t2) A run of the program corresponds to an interleaving sequence (A, S) Each interleaving sequence determines a unique sequence of executing the (B, S) (A, T) statements Repeated runs with the same input will (C, S) (B, T) (A, end) probably trace different interleaving's (end, S) (C, T) (B, end) (end, T) (C, end) 44 (end, end) exit  Concurrent Execution - Interleaving Given a concurrent program with threads t1 Distributed Network Architectures & Operating Systems main and t2 t1; begin s1; … ; sm; (begin t1, begin t2) end; (A, S) t2; begin p1; …; pn; (B, S) (A, T) end; (C, S) (B, T) (A, end) The number of t2; begin t1, interleaving's = This number grows end; extremely quickly with n (end, S) (C, T) (B, end) and m! (end, T) (C, end) Exercise: compute the number of 45 interleaving's for m=4, (end, end) n=5 exit Concurrent Execution – Thread Interference In general: Distributed Network Architectures & Operating Systems Non-deterministic: same input generally means different output due to ordering Example: main; Imagine a high-level program that c=0; spawns two threads t1 and t2 that run t1; t2; manipulate the same variable print c; As before, the increment/decrement end instructions are broken down into several machine instructions t1; t2; begin c+ begin c--; +; end end 46 Concurrent Execution – Thread Interference In general: Distributed Network Architectures & Operating Systems Non-deterministic: same input generally means different output due to ordering Example: Therefore, one interleaving possibility is as main; follows: c=0; 1. Thread t1: Retrieve c run t1; t2; 2. Thread t2: Retrieve c print c; 3. Thread t1: Increment retrieved value; result is 1 end 4. Thread t2: Decrement retrieved value; result is - 1 t1; t2; 5. Thread t1: Store result in c; c is now 1 begin c+ begin c--; 6. Thread t2: Store result in c; c is now -1 +; end Thread t1's result is lost, overwritten by thread end t2 47 Solution: we will look at this a bit later  User and Kernel Threads – User Threads Created and managed by a user level Distributed Network Architectures & Operating Systems library typically without the knowledge of the kernel Fast to create and manage Portable to any OS If one thread is blocked, then all of them are blocked E.g. In the case of a word processor a thread that handles the printing event would block all other threads! Multi-threaded applications cannot take advantage of parallel execution 48 User and Kernel Threads – Kernel Threads Directly managed/supported by the Distributed Network Architectures & Operating Systems kernel Slower to create and manage Specific to the OS If one thread is blocked; another one is scheduled Can take advantage of parallel execution on multiple CPUs 49 Multi-threading models – Multi- thread mapping The kernel is generally not aware of user threads in a process Distributed Network Architectures & Operating Systems A thread library must map user threads to kernel threads Different mappings exist: Many-to-one User One-to-one Many-to-many process n process m ? Kernel 50 Multi-threading models – Many-to- one mapping All user threads from each Distributed Network Architectures & Operating Systems process map to one kernel thread Pros User Portable: few system dependencies Cons No parallel execution of threads All threads in a process are blocked when one waits for I/O interrupt Kernel 51  Multi-threading models – One-to- One mapping Distributed Network Architectures & Operating Systems Each user thread maps to a single kernel thread Pros User Concurrency: when one blocks, others can still run Better multi-CPU performance Cons Slow: management overhead because kernel is involved for every single user thread Restricted: typically there is a limit on the Kernel number of threads 52 Creating user threads requires the corresponding kernel support  Multi-threading models – Many-to- Many mapping Distributed Network Architectures & Operating Systems Many user threads multiplex to many kernel threads (in equal or smaller number) User Pros Can take advantage of multiple CPUs Flexible: no restrictions on the number of threads When blocking system call the kernel can schedule another thread Cons Complex: implementation difficulties Kernel 53  Inter-Process synchronisation – solution to interleaving interference Distributed Network Architectures & Operating Systems main Threads in the system behave in two ways: Competing: Two or more processes compete for the same computing resource, or access to a particular memory cell (begin t1, begin t2) etc. Cooperating: Two or more processes may need to (A, S) communicate causing information to be passed from one to another. (B, S) (A, T) Important example: the OS itself, within which (C, S) (B, T) (A, end) threads are both cooperating and competing Solution: use inter-process synchronisation (end, S) (C, T) (B, end) to allow threads/processes to share resources! (end, T) (C, end) 54 (end, end) exit  Inter-Process synchronisation – Critical Section and Mutual Exclusion Distributed Network Architectures & Operating Systems The critical section is code in a process that involves sensitive operations on a shared resource The competition for resources in a critical section is called a race condition To avoid race conditions, critical sections of the threads should not be allowed to interleave! Guaranteeing that only one thread is allowed to enter the critical section at a time is called ensuring mutual exclusion Mutual exclusion is a major design issue in OS’s 55 This is also a big problem in distributed systems – we will look at how we deal with this next term. Race Conditions Example 1 – racing for memory access (e.g. register, Distributed Network Architectures & Operating Systems RAM) Example from earlier! main; c=0; run t1; t2; print c; end t1; t2; begin c+ begin c--; +; end end 56  Race Conditions Example 2 – racing for Distributed Network Architectures & Operating Systems peripherals Access to printer spooler directory 1. Next available printer job slot is 7 2. Process A and B access it simultaneously 3. Process A reads 7 and timer interrupt occurs to switch to process B before process A stores anything 57 4. Process B reads 7 also and stores its job and increment values 5. Process A switches back and stores its job at 7 Mutual exclusion on critical sections Ensure mutual exclusion Distributed Network Architectures & Operating Systems No two processes may be simultaneously inside their critical regions No assumptions may be made about speeds or the number of threads No process running outside its critical region may block other processes A thread that is not in the critical section cannot prevent other threads from entering the critical section No process should have to wait forever to enter its critical region 58  Shared resources - semaphores With shared resources, we have a problem that only one thing at a time can have exclusive access to Distributed Network Architectures & Operating Systems the underlying resource. Semaphores provide a way to guard a resource (originally inspired from railroad) System tool used for the design of correct synchronisation protocols – introduced by Edsger Dijkstra in 1960s Convenient to write entry/exit protocols by single atomic (i.e. indivisible) statements To protect track (ensuring only 1 train Single at a time rail can track pass we have to introduce (only one train semaphores at a at either end) This can be time) Train A now signalled scaled up to that semaphore says it ensuring Train can A signals traverse track semaphores that it is distributed now on the track. mutual exclusion in distributed systems for Train B can go on to protecting shared track as it is safe. Has 59 Train A now arrives and wants resources – we to access the track. It has to B hasto Train tell semaphoreTrain now it is B has to check to will look at this passed, hasusing the track see if semaphore says check semaphore to see if it to tell again in Topic 9. can – It can’t as another train (B) is using the track sosemaphores it has that track it is safe  sections Mutual exclusion on critical Distributed Network Architectures & Operating Systems 60 Shared resources - Semaphores Semaphore S is an integer that takes only non- Distributed Network Architectures & Operating Systems negative values Only two indivisible operations on S are allowed: Non-critical section Wait(S) Critical section Signal(S) wait (S) { signal (S) { if (S > 0) S--; S++; } } Allows the processor being switched from a blocked process/thread to another process/thread 61 (context switch) Critical Sections and semaphores need to be scaled up to allow the protection of shared resources in a distributed system– we will look at Semaphores in Distributed Systems Protecting resources is very important in distributed systems Distributed Network Architectures & Operating Systems We will learn more about these in Topic 9: Central Server Algorithm Ring-Based Algorithm Multicast and Logical Clocks 62 The Producer-Consumer Problem Problem description: a producer repeatedly produces items Distributed Network Architectures & Operating Systems and places them into a buffer and a consumer consumes the items one-by-one by taking them from the buffer Requirements: Assume first-in, first-out (FIFO) buffer The producer may produce a new item at any time only when the buffer is not full The consumer may consume an item only when the buffer is not empty Terminates when all items produced are eventually consumed 63 The Producer-Consumer Problem Naive solution – keep track of the number of items in the buffer: Distributed Network Architectures & Operating Systems Producer Class Consumer Class But interleaving might lead to a race condition, which in turn LOOP { LOOP { canProduce lead toitem a deadlock! i if(itemCount == 0) { if(itemCount == N) { sleep(consumer); sleep(producer); } } Remove item j; Put item i; itemCount--; itemCount++; if(itemCount == N - 1){ if(itemCount == 1){ wakeup(producer); wakeup(consumer); } } Consume item j; } } 64 Deadlocks A deadlock occurs when two or more threads wait for each Distributed Network Architectures & Operating Systems other to finish Four conditions must hold simultaneously in order for a deadlock to occur: 1. Mutual exclusion: a resource can be assigned to at most one process at a time 2. Hold and wait: processes holding resources are permitted to request and wait for additional resources 3. No preemption: resources previously locked cannot be forcefully unlocked by another process; they must be released by the holding process 4. Circular wait: there must be a chain of processes such that each 65 member of the chain is waiting for a resource held by the next member of the chain Deadlocks – Circular Wait Distributed Network Architectures & Operating Systems E awaits A A A awaits B E B D awaits E B awaits C D C awaits D C 66  The Producer-Consumer Problem - deadlocks Naive solution – keep track of the number of items in the buffer: Distributed Network Architectures & Operating Systems Possible deadlock: A consumer read itemCount = 0. So it needs to call sleep(consumer). But just before calling sleep(consumer) the consumer is interrupted (timer interrupt) and the producer is resumed The producer adds an item in the buffer, so itemCount = 1. Now producer tries to wakeup(consumer) but it is already in “wakeup” mode. So the call is missed. When the consumer resumes it will call sleep(consumer) and get trapped in “sleep” mode. The producer will continue adding items in the buffer and finally call 67 sleep(producer). Both processes wait for a wakeup call from each other => deadlock!  The Producer-Consumer Problem – Using semaphores Solving the problem using semaphores (1) Distributed Network Architectures & Operating Systems ItemsReady = 0 SpacesLeft = N //size of buffer Producer Class Consumer Class LOOP { LOOP { Produce item i Wait(ItemsReady) Wait(SpacesLeft) //decrement //decrement Get item i Deadlock free? Put item i Signal(SpacesLeft) Signal(ItemsReady) //increment Any unforeseen //increment Consume item i + 68 If semaphores are used correctly then N = SpacesLeft problems? } ItemsReady } The Producer-Consumer Problem The solution works well only when there is a single producer and Distributed Network Architectures & Operating Systems consumer… What about when we have multiple producers/consumers? Produc Consum er er Produc Consum er Buffer er Race condition! Produc Consum 69 er er  (Multiple) Producers-Consumers Problem Distributed Network Architectures & Operating Systems Produc Consum er er Produc Consum er Buffer er Produc Consum er er It is possible that two producers are adding items to the same slot or consumers removing items from the same slot (printer spooler example!) Consider this interleaving: Two producers access the SpacesLeft at the same time; corresponds to decrementing the semaphore. The first producer gets the next empty slot in the buffer At the same time the second producer get the same empty slot in the buffer Both producers write into the same slot; so one item is lost! 70 So how do we ensure mutual exclusion when multiple users are involved? (Multiple) Producers-Consumers Problem Solving the problem using semaphores (2) Distributed Network Architectures & Operating Systems For multiple producers and consumers we introduce an additional semaphore for mutual exclusion (called mutex or binary semaphore) It is a semaphore with ownership that can be released only by its owner Producer Class Consumer Class LOOP { LOOP { Produce item i Wait(ItemsReady) Wait(SpacesLeft) Wait(BusyBuffer) // Wait(BusyBuffer) //mutex mutex Put item i Get item i Signal(BusyBuffer) Signal(BusyBuffer) Signal(ItemsReady) Signal(SpacesLeft) } Consume item i } 71 BusyBuffer has ownership, meaning that it can be only increased/decreased by the same process. Initially is set to  (Multiple) Producers-Consumers Problem Solving the problem using semaphores (2) Distributed Network Architectures & Operating Systems For multiple producers and consumers we introduce an additional semaphore for mutual exclusion (called mutex or binary semaphore) It is a semaphore with ownership that can be released only by its owner Producer Class Consumer Class LOOP { LOOP { Produce item i Wait(BusyBuffer) //mutex Wait(SpacesLeft) What happens in this case? Wait(ItemsReady) Wait(BusyBuffer) //mutex Get item i Put item i Signal(BusyBuffer) Signal(BusyBuffer) Signal(SpacesLeft) Signal(ItemsReady) Consume item i } } 72 We will revisit at this again when looking at Note that the order in which semaphores aredistributed systems as we need to consider incremented/decremented is essential! messaging, shared message queues and shared The Dining Philosophers Problem Distributed Network Architectures & Operating Systems Problem description: Five philosophers are seated around a circular table eating and thinking. Each one has a plate of spaghetti that can eat with forks. Requirements: The life of a philosopher consists of eating and thinking Between each pair of plates is one fork Each philosopher needs two forks to eat the spaghetti 73 No two philosophers may hold the same fork simultaneously The Dining Philosophers Problem Solving the problem using semaphores (1) Distributed Network Architectures & Operating Systems Each philosopher is a different thread with a unique ID One semaphore per fork / chopstick Identify left and right fork / chopsticks using the ID of the philosopher: left = chopstick[i] right = chopstick[((i-1)+N)%N] 74 The Dining Philosophers Problem Solving the problem using semaphores (1) Distributed Network Architectures & Operating Systems Philosopher Class (int i) i is the id of the philosopher LOOP { think(); wait(chopstick[left]); //take left wait(chopstick[right]); //take right eat(); signal(chopstick[left]); //release left signal(chopstick[right]); //release right 75 } No chopstick is ever held by two philosophers… …but does it actually work, or are there still any underlying problems? The Dining Philosophers Problem Solving the problem using semaphores (1) Distributed Network Architectures & Operating Systems Suppose that all five philosophers want to eat at the same time, so they all take their left chopsticks: Phil 0 takes chopstick[left] Phil 1 takes chopstick[left] Phil 2 takes chopstick[left] Phil 3 takes chopstick[left] Phil 4 takes chopstick[left] Circular wait - deadlock! 76 The Dining Philosophers Problem Solving the problem using semaphores (2) Distributed Network Architectures & Operating Systems Philosopher Class (int i) LOOP { think(); wait(busy); //mutex wait(chopstick[left]); //take left wait(chopstick[right]); //take right eat(); signal(chopstick[left]); //release left signal(chopstick[right]); //release right signal(busy); //release mutex } Deadlock free! 77 However, there are ways to achieve maximum parallelism – see Modern operating systems – Andrew S. Tanenbaum pp. 167 – 170 Summary Operating systems architectures Distributed Network Architectures & Operating Systems Process life cycle Process execution Concurrency Process scheduling Threads Sequential execution Concurrent execution Synchronisation and Mutual Exclusion Critical Sections Definition of a Semaphore Synchronisation and mutual exclusion in classical inter-process communication problems: 78 Producer-Consumer problem Dining Philosophers problem References & Directed Study Distributed Network Architectures & Operating Systems References “Modern Operating Systems”, Andrew Tanenbaum, 2015 Next Topic Memory Management Directed study 1. Read chapter 2 (Processes and Threads) from Modern Operating Systems book. 2. Read the "Minix 3 - A highly reliable, self-repairing operating system" paper. 3. Read paper "Real-Time-Operating Systems" 4. Read paper "Integrating Flexible Support for Security Policies into the Linux Operating System." 5. Read paper "Survey and performance evaluation of real-time operating systems (RTOS) for small microcontrollers" 6. Start looking at and follow the C programming tutorials at W3 Schools / 79 Tutorialspoint (links in the activities section)