Operating System Concepts PDF

Overview  A thread is a flow of control within a process  A multithreaded process contains several different flows of control within the same address space  A traditional (heavyweight) process has one thread of control  A thread / lightweight process (LWP) = a unit of CPU utilization ...

Overview  A thread is a flow of control within a process  A multithreaded process contains several different flows of control within the same address space  A traditional (heavyweight) process has one thread of control  A thread / lightweight process (LWP) = a unit of CPU utilization  It comprises a thread ID, program counter, register set, & stack  It shares with other threads belonging to the same process its code section, data section, and other OS resources  If a process has multiple threads of control, it can perform more than one task at a time  Look at fig 4.1 p.153 TB  User-level threads are threads that are visible to a programmer and are unknown to the kernel  OS kernel supports and manages kernel-level threads Motivation  It is more efficient to have multithreading than many processes  RPC servers are typically multithreaded  When a server receives a message, it services it with a separate thread  This lets the server service several concurrent requests Benefits  Responsiveness:  A program can continue running even if part of it is busy  Resource sharing:  Threads share the memory and resources of their process  Economy:  Allocating memory and resources for processes is costly (time)  Scalability:  Utilization of multiprocessor architectures  Each thread runs on a separate CPU, increasing concurrency / parallelism Multicore Programming  p.156 - 157 TB  Provides a mechanism for more efficient use of multiple cores and improved concurrency  On a system with multiple cores the processes run concurrently since the system can assign a separate thread to each core  Five areas that present challenges in programming multicore systems:  Dividing activities:  Areas of applications to be divided into different tasks  Balance:  Tasks must perform equal work of equal value, else CPU time is wasted  Data splitting:  Data accessed and manipulated must be divided to run on separate cores  Data dependency:  If data between cores depends on each other, execution must be synchronized  Testing and debugging:  More difficult to test and debug than single-threaded execution Multithreading Models User threads (Many-to-One) Kernel threads (One-to-One) Implemented by a thread library at the user Supported directly by the OS level The library provides support for thread The kernel performs thread creation, scheduling, and creation, scheduling, and management with no management in kernel space support from the OS kernel Faster to create & manage because the kernel Slower to create & manage than user threads because is unaware of user threads and doesn't thread management is done by the OS intervene Disadvantage: Since the kernel is managing the threads, if a thread performs a blocking system call, the kernel can schedule If the kernel is single- threaded, then any user- another thread in the application for execution. level thread performing a blocking system call will cause the entire process to block, even if In a multiprocessor environment, the kernel can other threads are available to run within the schedule threads on different processors. application Many-to-One Model  Many user-level threads are mapped to one kernel thread  Thread management is done in user space, so it is efficient  The entire process will block if a thread makes a blocking call  Multiple threads can’t run in parallel on multiprocessors One-to-One Model  Each user thread is mapped to a kernel thread  More concurrency than the many-to-one model because another thread can run when a thread makes a blocking system call  Multiple threads can run in parallel on multiprocessors  Disadvantage: creating a user thread requires creating the corresponding kernel thread (This overhead burdens performance) Many-to-Many Model  Many user-level threads are multiplexed to a smaller / equal number of kernel threads  Developers can create as many user threads as necessary  The kernel threads can run in parallel on a multiprocessor  When a thread performs a blocking system call, the kernel can schedule another thread for execution  A variation on the Many-to-Many Model is the two level-model:  Similar to M:M, except that it allows a user thread to be bound to kernel thread Thread Libraries  Thread libraries provide the application programmer with an API for creating and managing threads  Three main thread libraries in use today:  POSIX Pthreads  Win32 threads  Java threads Pthreads  A POSIX standard (IEEE 1003.1c) API for thread creation and synchronization  API specifies behavior of the thread library, implementation is up to development of the library  Common in UNIX operating systems (Solaris, Linux, Mac OS X) Win32 Threads Java Threads  Java threads are managed by the JVM  Java threads may be created by: 1. Implementing the Runnable interface  Sample program:  Java thread states: Threading Issues  Here we discuss issues to consider with multithreaded programs The fork() and exec() System Calls  fork() system call: used to create a separate, duplicate process  Some versions of fork() duplicate all threads  If exec() won't be called afterwards  Other versions duplicate only the thread that invoked fork()  If exec() is called immediately after forking  exec() system call: the parameter used will replace the process  All threads will also be replaced Cancellation  Thread cancellation is the task of terminating a thread before it has completed.  Target thread = the thread that is to be canceled  Cancellation of target threads occur in two different scenarios: Asynchronous cancellation Deferred cancellation One thread immediately terminates the target The target thread can periodically check if it should thread terminate Canceling a thread may not free a necessary Cancellation occurs only when the target thread system- wide resource checks if it should be canceled. (Cancellation points)  Deferred cancellation in Java  Interrupting a thread  Deferred cancellation in Java  Checking interruption status Signal Handling  A signal is used in UNIX to notify a process that a particular event has occurred  All signals follow this pattern:  A signal is generated by the occurrence of a certain event  A generated signal is delivered to a process  Once delivered, the signal must be handled  A signal handler is used to process signals  Signal is generated by particular event  Signal is delivered to a process  Signal is handled  Delivering signals in multithreaded programs, the options are:  Deliver the signal to the thread to which the signal applies  Deliver the signal to every thread in the process  Deliver the signal to certain threads in the process  Assign a specific thread to receive all signals for the process  Synchronous signals are delivered to the same process that performed the operation causing the signal (E.g. / by 0)  Asynchronous signals are generated by an event external to a running process (E.g. user terminating a process with )  Every signal must be handled by one of two possible handlers:  A default signal handler  Run by the kernel when handling the signal  A user-defined signal handler  Overrides the default signal handler Single-threaded programs Multithreaded programs Straightforward signal handling Complicated signal handling Signals are always delivered to a process Which thread should the signal be delivered to?  The method for delivering a signal depends on the signal type:  Synchronous signals need to be delivered to the thread that generated the signal, not to other threads in the process  It is not clear what to do with asynchronous signals  st Signals need to be handled only once, so they're usually delivered to the 1 thread not blocking them Thread Pools  The idea is to create a number of threads at process startup and place them into a pool, where they sit and wait for work  When a server receives a request, it awakens a thread from this pool  If one is available the request is passed to it for service   Once the service is completed, the thread returns to the pool and wait for more work  Benefits of thread pools:  It is faster to service a request with an existing thread  A thread pool limits the number of threads that exist  Potential problems with a multithreaded server:  It takes time to create a thread before servicing a request  Unlimited threads could exhaust system resources (CPU time)  Thread pools are a solution to these problems:  At process startup, several threads are created and placed into a pool, where they sit and wait for work  When a server receives a request, it awakens a thread from this pool, passing it the request to service  When the thread finishes its service it returns to the pool Thread-Specific Data  Threads belonging to a process share the data of the process  Sometimes, each thread might need its own copy of certain data  E.g. Transactions in different threads may each be assigned a unique identifier  Thread-specific data in Java Scheduler Activations  Both M:M and Two-level models require communication to maintain the appropriate number of kernel threads allocated to the application  Scheduler activations provide upcalls - a communication mechanism from the kernel to the thread library  This communication allows an application to maintain the correct number kernel threads Operating-System Examples  Windows XP threads  Implements the one-to-one mapping  Each thread contains 1. A thread id 2. Register set 3. Separate user and kernel stacks 4. Private data storage area  The register set, stacks, and private storage area are known as the context of the threads  Linux threads  Linux refers to them as tasks rather than threads  Thread creation is done through clone() system call  clone() allows a child task to share the address space of the parent task (process) Summary Chapter 5: Process (CPU) Scheduling  Here we look at basic CPU-scheduling concepts and present several CPU-scheduling algorithms.  We also consider the problem of selecting an algorithm for a particular system.  Objectives:  To introduce CPU scheduling, which is the basis for multi-programmed operating systems.  To describe various CPU-scheduling algorithms.  To discuss evaluation criteria for selecting a CPU-scheduling algorithm for a particular system.  The terms process scheduling and thread scheduling are often used interchangeably Basic Concepts  CPU scheduling is the task of selecting a waiting process from the ready queue and allocating the CPU to it  The CPU is allocated to the selected process by the dispatcher  In a uni-processor system, only one process may run at a time; any other process must wait until the CPU is rescheduled  The objective of multiprogramming is to have some process running at all times, in order to maximize CPU utilization  CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait  CPU burst distribution CPU-I/O Burst Cycle  Process execution comprises a cycle of CPU execution & I/O wait  Process execution begins with a CPU burst, followed by an I/O burst, then another CPU burst, etc…  Finally, a CPU burst ends with a request to terminate execution Histogram of CPU-burst times:  An I/O-bound program typically has many short CPU bursts  A CPU-bound program might have a few long CPU bursts  These are important points to keep in mind for the selection of an appropriate CPU-scheduling algorithm CPU Scheduler  Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them  The short-term scheduler selects a process in the ready queue when the CPU becomes idle  The ready queue could be a FIFO / priority queue, tree, list…  The records in the queues are generally process control blocks (PCBs) of the processes Preemptive Scheduling  Circumstances under which CPU scheduling decisions take place:  When a process switches from the running state to the waiting state (E.g. I/O request) (1)  When a process switches from the running state to the ready state (E.g. when an interrupt occurs) (2)  When a process switches from the waiting state to the ready state (E.g. completion of I/O) (3)   When a process terminates (4)  Non-preemptive/cooperative scheduling  Processes are allowed to run to completion  When scheduling takes place under circumstances 1 & 4  There is no choice in terms of scheduling  Preemptive scheduling  Processes that are runnable may be temporarily suspended  There is a scheduling choice in circumstances 2 & 3  Problem: if one process is busy updating data and it is preempted for the second process to run, if the second process reads that data, it could be inconsistent Dispatcher  A component involved in the CPU scheduling function  The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler  This function involves:  Switching context  Switching user mode  Jumping to the proper location in the user program to restart that program  The dispatcher should be as fast as possible, given that it is invoked during every process switch  Dispatch latency = the time it takes for the dispatcher to stop one process and start another running Scheduling Criteria  Different CPU-scheduling algorithms have different properties and the choice of a particular algorithm may favor one class of process over another  Criteria to compare CPU-scheduling algorithms:  CPU utilization  CPU utilization should range from 40% - 90%  Throughput  The number of processes completed per time unit  Turnaround time  The time interval from process submission to completion  Formula: Time of completion – Time of submission  Formula: CPU burst time + Waiting time (includes I/O)  Waiting time  The sum of the periods spent waiting in the ready queue  Formula: Turnaround time – CPU burst time  Response time  The amount of time it takes to start responding, but not the time it takes to output that response  We want to maximize CPU utilization, and minimize turnaround, waiting & response time Scheduling Algorithms  CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to be allocated the CPU  There are many different CPU-scheduling algorithms. Here we describe several of them. First-Come, First-Served (FCFS) Scheduling  st The process that requests the CPU first is allocated the CPU 1  The PCB of a process is linked onto the tail of the ready queue  When the CPU is free, it gets the process at the queue’s head  The average waiting time is generally not minimal  Convoy effect = when processes wait for a big one to get off  Non-preemptive (a process keeps the CPU until it releases it)  Not good for time-sharing systems, where each user needs to get a share of the CPU at regular intervals  Example: Process Burst Time P1 24 P2 3 P3 3  Suppose that the processes arrive in the order: P1, P2, P3  The Gantt Chart for the schedule is:  Waiting time for P1 = 0; P2 = 24; P3 = 27  Average waiting time: (0 + 24 + 27)/3 = 17  Suppose that the processes arrive in the order P2, P3, P1  The Gantt chart for the schedule is:  Waiting time for P1 = 6;P2 = 0; P3 = 3  Average waiting time: (6 + 0 + 3)/3 = 3  Much better than previous case  Convoy effect short process behind long process Shortest-Job-First (SJF) Scheduling  The CPU is assigned the process with the shortest next CPU burst  If two processes have the same length, FCFS scheduling is used  The difficulty is knowing the length of the next CPU request  For long-term scheduling in a batch system, we can use the process time limit specified by the user, as the ‘length’  SJF can't be implemented at the level of short-term scheduling, because there is no way to know the length of the next CPU burst  We can, however, try to predict the length of the next CPU burst  The SJF algorithm may be either preemptive or non-preemptive  Preemptive SJF algorithm:  If the new process has a shorter next CPU burst than what is left of the executing process, that process is preempted  aka Shortest-Remaining-Time-First (SRTF) scheduling  Non-preemptive SJF algorithm:  The current process is allowed to finish its CPU burst  SJF has the minimum average waiting time for a set of processes  Example: Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4  SJF (non-preemptive)  Average waiting time = (0 + 6 + 3 + 7)/4 = 4  SJF (preemptive)  Average waiting time = (9 + 1 + 0 +2)/4 = 3  Determining the length of the next CPU burst:  Can only estimate the length  Can be done by using the length of previous CPU bursts, using exponential averaging  Formula on p.191 top   Examples of exponential averaging: Priority Scheduling  Each process gets a priority (Highest priority = executed first) Preemptive priority scheduling  The CPU is preempted if the priority of the newly arrived process is higher than the priority of the current one Non-preemptive priority scheduling  The new process is put at the head of the ready queue  Equal-priority processes are scheduled in FCFS order  Internally-defined priorities  Use some measurable quantity to compute the priority  E.g. time limits, memory requirements, no. of open files…  Externally-defined priorities  Set by criteria that are external to the OS  E.g. the importance of a process, political factors…  Problem:  Indefinite blocking (starvation), where low-priority processes are left waiting indefinitely for the CPU  Solution:  Aging (a technique of gradually increasing the priority of processes that wait in the system for a long time) Round-Robin Scheduling  Designed especially for time-sharing systems  Like FCFS scheduling, but with preemption  A time quantum / time slice is defined (generally 10 – 100 ms)  The ready queue is treated as a circular queue  The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum  The ready queue is kept as a FIFO queue of processes  The CPU scheduler  st picks the 1 process from the ready queue  sets a timer to interrupt after 1 time quantum, and  dispatches the process  One of two things will then happen:  The process may have a CPU burst of less than 1 time quantum, and will release the CPU voluntarily  If the process has a CPU burst longer than 1 time quantum, the timer will go off and cause an interrupt to the OS. The process will then be put at the tail of the ready queue  If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units  RR Performance depends heavily on the size of the time quantum  q large ⇒ FIFO  q small ⇒ q must be large with respect to context switch, otherwise overhead is too high  We want the time quantum to be large with respect to the context-switch time  Example of RR with time Quantum = 20: Process Burst Time P1 53 P2 17 P3 68 P4 24  The Gantt chart is:  Typically, higher average turnaround than SJF, but better response  In software we need to consider the effect of context switching on the performance of RR scheduling  The larger the time quantum for a specific process time, the less time is spend on context switching   The smaller the time quantum, more overhead is added for the purpose of context-switching  Example: (This is on a per case situation)  Turnaround time also depends on the size of the time quantum: Multilevel Queue Scheduling  For when processes can easily be classified into separate groups  E.g. a common division is made between foreground (interactive) and background (batch) processes  The ready queue is partitioned into several separate queues  The processes are permanently assigned to one queue, based on a property like memory size, process priority, process type…  Each queue has its own scheduling algorithm  There must also be scheduling among the queues, which is commonly implemented as fixed-priority preemptive scheduling  Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation.  Time slice -each queue gets a certain amount of CPU time which it can schedule amongst its processes; i.e., 80% to foreground in RR  20% to background in FCFS Multilevel Feedback Queue Scheduling  Processes may move between queues  Processes with different CPU-burst characteristics are separated  If a process uses too much CPU time, it will be moved to a lower-priority queue  If a process waits too long in a lower-priority queue, it may be moved to a higher-priority queue (Aging prevents starvation)  In general, a multilevel feedback queue scheduler is defined by the following parameters:  The number of queues  The scheduling algorithm for each queue  The method used to determine when to upgrade a process to a higher priority queue  The method used to determine when to demote a process to a lower-priority queue  The method used to determine which queue a process will enter when that process needs service  This is the most general, but complex scheme  Example of Multilevel Feedback Queue:  Three queues:  Q0 - RR with time quantum 8 milliseconds  Q1 - RR time quantum 16 milliseconds  Q2 - FCFS  Scheduling  A new job enters queue Q0 which is served FCFS  When it gains CPU, job receives 8 milliseconds  If it does not finish in 8 milliseconds, job is moved to queue Q1  At Q1 job is again served FCFS and receives 16 additional milliseconds  If it still does not complete, it is preempted and moved to queue Q2  Multilevel feedback queues: Thread Scheduling  p.199 TB  On operating systems that support them, it is kernel-level threads - not processes - that are being scheduled by the operating system  Local Scheduling  How the threads library decides which thread to put onto an available LWP  Global Scheduling  How the kernel decides which kernel thread to run next Contention Scope  Process-Contention scope:  On systems implementing the many-to-one and many-to-many models, the thread library schedules user-level threads to run on an available LWP  System-Contention scope:  The process of deciding which kernel thread to schedule on the CPU Pthread Scheduling Sample of thread creation with Pthreads: Multiple-Processor Scheduling  CPU scheduling more complex when multiple CPUs are available  Homogeneous processors within a multiprocessor  Typically each processor maintains its own private queue of processes (or threads) all of which are available to run  Load sharing  Asymmetric multiprocessing  Only one processor accesses the system data structures, alleviating the need for data sharing Approaches to Multiple-Processor Scheduling  We assume homogeneous processors (identical in functionality) and uniform memory access (UMA)  If several identical processors are available, then load sharing can occur, with a common ready queue  Processes in the queue are scheduled to any available processor  One of two scheduling approaches may be used:  Each processor is self-scheduling, and selects a process from the common ready queue to execute  One processor is appointed as scheduler for the other processors, creating a master-slave structure  Some systems carry the master-slave structure further by having all scheduling decisions, I/O processing, and other system activities handled by one single processor – the master server  This asymmetric multiprocessing is simpler than symmetric multiprocessing (SMP), because only one processor accesses the system data structures, alleviating the need for data sharing  It isn't as efficient, because I/O processes may bottleneck on the one CPU that is performing all of the operations  st Typically, asymmetric multiprocessing is implemented 1 within an OS, and then upgraded to symmetric as the system evolves Processor Affinity  Processor affinity:  Migration of processes to another processor is avoided because of the cost of invalidating the process and repopulating the processor cache  Soft affinity:  When an OS try to keep a process on one processor because of policy, but cannot guarantee it will happen  Hard affinity:  When an OS have the ability to allow a process to specify that it is not to migrate to other processors Load Balancing  Load balancing attempts to keep the workload evenly distributed across all processors in an SMP system  Two migration approaches:  Push migration  A specific task checks the load on each processor and if it finds an imbalance it evenly distributes the load to less-busy processors  Pull migration  A idle processor pulls a waiting task from a busy processor Multicore Processors  Complicated scheduling issue Virtualization and Scheduling Operating System Examples Algorithm Evaluation  p.213 TB  Deterministic modeling:  Takes a particular predetermined workload and defines the performance of each algorithm for that workload  Queuing models  Implementation Deterministic Modeling  A method that takes a particular predetermined workload and defines the performance of each algorithm for that workload  Simple; fast; exact numbers, so algorithms can be compared  However, it requires exact numbers for input, and its answers apply to only those cases  The main uses of deterministic modeling are in describing scheduling algorithms and providing examples  Good if you're running the same programs over and over again  Over many examples, deterministic modeling may indicate trends  In general, deterministic modeling is too specific, and requires too much exact knowledge to be useful Queuing Models  You can determine the distribution of CPU and I/O bursts  A formula describes the probability of a particular CPU burst  The computer system is described as a network of servers  Each server has a queue of waiting processes  Knowing arrival & service rates, we can compute utilization, average queue length, wait time… (= queuing- network analysis)  Limitations of queuing analysis:  The algorithms that can be handled are limited  The math of complicated algorithms can be hard to work with  It is necessary to make assumptions that may not be accurate  As a result, the computed results might not be accurate Simulations  Involve programming a model of the computer system  Software data structures represent the major system components  The simulator has a variable representing a clock  As this variable’s value is increased, the simulator modifies the system state to reflect the activities of the devices, the process, and the scheduler  As the simulation executes, statistics that indicate algorithm performance are gathered and printed  A random-number generator is programmed to generate processes, CPU-burst times… according to probability distributions  The distributions may be defined mathematically or empirically  If the distribution is to be defined empirically, measurements of the actual system under study are taken  The results are used to define the actual distribution of events in the real system, and this distribution can then be used to drive the simulation  Trace tapes can be used to record the sequence of actual events  Disadvantages:  Simulations can be costly, requiring hours of computer time  Traced tapes can require large amounts of storage space  The design, coding, and debugging of the simulator can be a major task Implementation  The only completely accurate way to evaluate a scheduling algorithm is to code it, put it in the OS, and see how it works  The major difficulty is the cost of this approach  The environment in which the algorithm is used will change Summary PART THREE: PROCESS COORDINATION Chapter 6: Synchronization  Co-operating process = one that can affect / be affected by other processes.  Co-operating processes may either directly share a logical address space (i.e. code & data) , or share data through files or messages through threads (ch4).  Concurrent access to shared data can result in inconsistencies  Objectives: 1. To introduce the critical-section problem, whose solutions can be used to ensure the consistency of shared data 2. To present both software and hardware solutions of the critical- section problem 3. To introduce the concept of an atomic transaction and describe mechanisms to ensure atomicity Background  Concurrent access to shared data may result in data inconsistency  Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes  Suppose that we wanted to provide a solution to the consumer-producer problem that fills all the buffers. We can do so by having an integer count that keeps track of the number of full buffers. Initially, count is set to 0. It is incremented by the producer after it produces a new buffer and is decremented by the consumer after it consumes a buffer  Producer:  Consumer:  Race condition:  When the outcome of the execution depends on the particular order in which data access takes place  Example:  count++ could be implemented as register1 = count  register1 = register1 + 1 count = register1  count-- could be implemented as register2 = count register2 = register2 -1 count = register2  Consider this execution interleaving with "count = 5" initially: S0: producer execute register1 = count{register1 = 5} S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = count{register2 = 5} S3: consumer execute register2 = register2 -1{register2 = 4} S4: producer execute count = register1{count = 6 } S5: consumer execute count = register2{count = 4} The Critical-Section Problem  Critical section = a segment of code in which a process may be changing common variables, updating a table, writing a file, etc  Entry section  Requests permission to enter the critical section  Critical section  Mutually exclusive in time (no other process can execute in its critical section)  Exit section  Follows the critical section  Remainder section  A solution to the critical-section problem must satisfy:  Mutual exclusion  Only one process can be in its critical section  Progress  Only processes that are not in their remainder section can enter their critical section, and the selection of a process cannot be postponed indefinitely  Bounded waiting  There must be a bound on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before the request is granted  Structure of a typical process: Peterson's Solution  This is an example of a software solution that can be used to prevent race conditions  Two process solution  Assume that the LOAD and STORE instructions are atomic; that is, cannot be interrupted.  The two processes share two variables:  int turn;  Boolean flag  The variable turn indicates whose turn it is to enter the critical section.  The flag array is used to indicate if a process is ready to enter the critical section  flag[i] = true implies that process Pi is ready!  Algorithm for process Pi:  To prove that this solution is correct we show that:  Mutual exclusion is preserved  The progress requirement is satisfied  The bounded-waiting requirement is met Synchronization Hardware  Hardware can also be used to solve the critical-section problem  If in a uni-processor environment interrupts were disabled, no unexpected modifications would be made to shared variables  Disabling interrupts in a multi-processor environment isn't feasible, so many machines provide special hardware instructions  Instead, we can generally state that any solution to the critical-section problem requires a simple tool, a lock  Race conditions are prevented by requiring that critical regions be protected by locks  Modern machines provide special atomic hardware instructions  Atomic = non-interruptible  Either test memory word and set value  Or swap contents of two memory words  These instructions allow us either to test & modify the content of a word, or to swap the contents of two words, atomically  TestAndSet boolean TestAndSet( boolean *target ) { boolean rv = *target; *target = true; return rv; }  NB characteristic: this instruction is executed atomically, so if two TestAndSet instructions are executed simultaneously (on different CPUs), they will be executed sequentially  TestAndSet with mutual exclusion do{ while( TestAndSet( &lock ) ) ; // critical section lock = false; // remainder section } while( true);  lock is initialized to false  Swap void swap( boolean *a, boolean *b ) { boolean temp = *a; *a = *b; *b = temp;  }  Swap with mutual-exclusion do{ key = true; while(key == true ) swap(& lock, &key ); // critical section lock = false; // remainder section } while(true);  lock is initialized to false  Bounded-waiting mutual exclusion with TestAndSet do{ waiting[i] = true; key = true; while( waiting[i] && key } key = TestAndSet( &lock ); waiting[i] = false; // critical section j = (i+1)%n; while(( j!=i ) && !waiting[j] ) j = (j+1)%n; if( j==i ) lock = false; else waiting[j] = false; // remainder section } while( true);  Common data structures are boolean waiting[n]; boolean lock;  Data structures initialized to false  To prove that the mutual-exclusion requirements is met:  note that Pi can enter its critical section only if either waiting[i] == false or key == false  key can become false only if the TestAndSet() is executed  first process to execute TestAndSet() will find key == false, all others must wait   waiting[i] can become false only if another process leaves its critical section  only one waiting[i] is set to false  To prove the Progress requirement is met:  The mutual exclusion arguments apply, since they let a process that is waiting to enter its critical section proceed  To prove the Bounded waiting requirement is met:  When a process leaves its critical section, it scans the waiting array in the cyclic ordering (i+1, i+2…, n-1, 0…, i-1) and designates the first process in this ordering that is in the entry section (waiting[j] == true) as the next one to enter the critical section Semaphores  Semaphore = a synchronization tool used to control access to shared variables so that only one process may at any point in time change the value of the shared variable  A semaphore S is an integer variable that is accessed only through two standard atomic operations: wait and signal wait(s){ while(s