Chapter_02_Slides Processes and Threads.pdf

Modern Operating Systems Fourth Edition Chapter 2 Processes and Threads Concepts & models, Scheduling, Synchronization Copyright © 2014 Pearson Education, Inc. All Rights Reserved Outline • • • • • Concept of “Process” and “thread” Threads & Multithreaded systems Thread models Scheduling Synchr...

Modern Operating Systems Fourth Edition Chapter 2 Processes and Threads Concepts & models, Scheduling, Synchronization Copyright © 2014 Pearson Education, Inc. All Rights Reserved Outline • • • • • Concept of “Process” and “thread” Threads & Multithreaded systems Thread models Scheduling Synchronization 2 Process Concept • An operating system executes a variety of programs: – Batch system – jobs – Time-shared systems – user programs or tasks • Short definition: A process is a “program in execution.” – A program is the code sitting in a file in this terminology. 3 Process Concept • Multiple parts – The program code, also called text section – Current activity including program counter register and processor registers – Stack containing temporary data • Function parameters, return addresses, local variables – Data section containing global variables – Heap containing memory dynamically allocated during run time (through new and malloc()). 4 Process in Memory Address space of a process (typically virtual) 5 Process Concept • An operating system involves asynchronous, and sometimes parallel/concurrent, activities. • The notion of a software process is used in operating systems to express the management and control of such activities. • A process is the key concept underlying modern operating system design. 6 Process Concept • The concept of process simplifies the user’s view of the computation model: – process execution uses a sequential model of computation, making the programming simpler. – Long definition: A process is an abstraction for a sequence of operations that implement a computation. – Multiple processes are executed concurrently with CPU (or CPU’s) multiplexing among them. 7 Processes The Process Model with one CPU a) Multiprogramming of four programs on a single CPU b) Conceptual model of 4 independent, concurrent, sequential processes c) Only one program active at any instant on a single CPU 8 Process States • As a process executes, it changes process state (status). • The list of possible process states: – new: The process is being created. (transient state) – running: Instructions are being executed on the CPU. – blocked (waiting): The process is waiting for some event to occur (e.g., I/O request to complete) – It cannot do anything even if given the CPU. – ready: The process is ready to run and is waiting to be assigned to the CPU. – Terminated (dead): The process has finished execution. (transient state) 9 Diagram of Process State Transitions Steady state • Possible process states during their lifetime: • running • Blocked/waiting • ready • Transitions between states shown 10 Process Creation Principal events that cause process creation (new process): 1. System initialization 2. Execution of a process creation system 3. User request to create a new process 4. Initiation of a batch job 11 Process Creation • Processes are created and deleted dynamically. • Process Creation: Process which creates another process is called parent process. • Created process is called child process. • Parent process creates children processes, which, in turn create other processes, forming a tree of processes. 12 Process Creation • UNIX examples (for historical reasons) – Fork() system call creates a new process ➔ clone of the parent process. – Execve() system call used after a fork to replace the process’ memory space with a new program ➔ overwrites the cloned parent process. • On Win32, the combination of these two is done by a single system call – CreateProcess() 13 UNIX Example more on fork() int prntpid; int chldpid; if ((chldpid = fork()) == -1 ) { perror(can't create a new process); exit(1); } else if (chldpid == 0) { /* child executes */ printf(“chld: chldpid=%d, prntpid=%d \n”, getpid(), getppid()); exit(0); } else { /* parent process executes */ printf(“prnt: chldpid=%d, prntpid=%d\n”, chldpid,getpid()); exit(0); } 14 Process Creation • Execution possibilities (different OS’s implement differently): – the parent continues to execute concurrently with the child; or – parent waits until child has terminated. • Address space possibilities: – child process is duplicate of the parent process; or – child process has a program loaded into it during creation. 15 Process Hierarchies In many OS’s processes exist in a hierarchy: • Parent creates a child process, child processes can create their own child processes, etc. • Forms a hierarchy – UNIX calls this a “process group” or process tree. 16 Process Tree on a UNIX System 17 Process Termination Conditions which terminate processes 1. Normal exit (voluntary) 2. Error exit (voluntary) 3. Fatal error (involuntary) 4. Killed by another process (involuntary) 18 Process Termination • Process executes last statement and asks the operating system to execute system call (exit). – Output data from child to parent (via wait). – Process’ resources are deallocated by operating system. 19 Process Termination • Parent may terminate execution of children processes (abort or kill). – Child has exceeded allocated resources. – Task assigned to child is no longer required. – Parent is exiting. • Operating system does not allow child to continue if its parent terminates. • Cascading termination. 20 Implementation of Processes • Through process table or process control block (PCB) – Similar structures for threads (i.e., thread table) 21 Process table information • What is included in the process table? – Information about the state of computation necessary for process management (e.g., the value of the PC, processor register contents, etc). – Information about memory management (e.g., page tables and other memory related information) – Information about file management (e.g., open file descriptors, etc). 22 Implementation of Processes • Fields of a process table entry 23 Revisit multiplexing CPU • One CPU is shared between multiple processes over time (multiplexed). • This is accomplished via “context switch” 24 Context Switch • The act of switching CPU from one process to another is called Context Switch. • Context Switch must do: – save PCB state of the old (switched out) process; – load PCB state of the new (switched in) process, which might include changing the current register set, advanced memory management techniques moving data from one memory segment to another; 25 Context switch 26 Context Switch • Context Switch represents a pure overhead because the system does not do any useful work during switching (Context switching time 1-1000 microseconds). • Context switch highly depends on hardware support. • Context switch can become a bottleneck. 28 Threads • The term comes from thread of execution. • A process has one thread by default. 29 Threads in one Task (process) • Processes do not share resources very well – shared variables/memory – open files • Context switching of processes can be very expensive. • THREADS (belonging to the same process) share some of the resources and, thus, have lower context switching overhead: – Shared information need not be saved and restored. 30 Threads The Thread Model • (a) Three processes each with one thread • (b) One process with three threads 31 Example: Vanilla web server done by creating a child process. for (;;){ sd = accept(sock,…) switch(fork()) { Port 80 case –1: panic(); http req break; case 0: handle_http_request(); exit(0); default: close(sd); } } http reply 32 Example: Vanilla web server • Creating a new process for every http request would work, but would have a big overhead. • Same thing could be accomplished by creating a thread to process the http request instead of creating a process. • It would be more efficient. • Example of this given further ahead. 33 Benefits of threads • Responsiveness — because of low overhead of context switching • Resource Sharing — Unlike processes, threads share a common address space. • Economy — because of resource sharing. • Utilization of Multiprocessor Architectures — easier to map multiple threads to multiple CPU’s with shared memory. 34 Threads within one process • A thread shares with its peer threads its – code section, – data section and – OS resources such as • open files and • signals belonging to the process. • A traditional process has one thread – sometimes called a heavyweight process. 35 Single and Multithreaded Processes shared not shared 36 The Thread Model Items shared by all threads in a process Items private to each thread 37 The Thread Model • Each thread has its own stack because it can have a different execution history with different function calls, etc. 38 Thread Usage Thread 2: reformat Thread 3: save Thread1: input • • A word processor with three threads: input, reformat, and save. Each can be implemented and thought of as a simple sequential computation. 39 Other Thread Usage examples • Graphics applications: Augmented Reality Thread 1 Video capture and analysis Position and orientation tracking Mix the graphics & video Mixed Video and Graphics Thread 2 Graphics Rendering Thread 3 40 Operations on threads Similar to process operations: • Thread creation int thread_id = spawn(); (or fork()) • Thread blocking block(); • Thread unblocking unblock(int thread_id); • Thread termination finish(); 43 Thread states • Threads go through states similar to processes: ready, blocked, running, terminated • Unlike processes, threads are considered cooperating, therefore, there is no protection among threads. spawn() ready unblock() running blocked finish() block() 45 Threads • In a multiple threaded process, while one server thread is blocked and waiting, a second thread in the same task can run. – Cooperation of multiple threads in same job confers higher throughput and improved performance. – Applications that require sharing a common buffer (i.e., producer-consumer) benefit from thread utilization. 46 Threads • Extensive sharing makes CPU switching among peer threads and creation of thread inexpensive compared to heavyweight processes. • Thread context switch still requires a register set switch, but no memory management related work! ➔ Less overhead; more efficient. 47 Thread models • Types of thread implementations: – Kernel-supported threads (Mach and OS/2). – User-level threads; supported above the kernel, via a set of library calls at the user level (Project Andrew from CMU). – Hybrid approach implements both user-level and kernel-supported threads (Solaris 2). 48 User Threads • Thread management done by user-level threads library • Kernel does not know about threads (only processes) • Examples - POSIX Pthreads - Mach C-threads - Solaris threads 49 User Threads A user-level threads package 50 User Threads • Reduces context switch times by eliminating kernel overhead • No need to involve the kernel ➔ context switch done in the user space • Flexibility: Allows user scheduling of processes • Need new primitives for processes to coordinate user with system example: may need synchronization primitives 51 User-level Threads • User-level threads are implemented – in user space – using user-level libraries, not system calls. • i.e., they don’t go through the kernel. – threads do not depend on calls to OS and do not cause interrupts or traps to the kernel. – User-level threads require a stack and a program counter. 52 Disadvantages of User-level Threads • If kernel is single threaded, then any userlevel thread can block the entire task executing a single system call. – For example an I/O request must involve the kernel. To the kernel this will look like an I/O request from one user process. ➔ process is blocked ➔ all threads in this process will be blocked. • No concurrency for I/O operations 54 Kernel Threads • Supported by the Kernel • Many examples from real OS’s – – – – – Windows Solaris Tru64 UNIX BeOS Linux 55 Kernel Threads • A threads package managed by the kernel 56 Kernel (system) threads • Done by going to the kernel to do context switching • OS does the scheduling of threads • Lightweight threads – switch between threads but not between memories (i.e., heavyweight processes) • Allows user programs to continue after starting I/O and/or making blocking system calls. 57 Kernel (system) threads • User cannot explicitly schedule threads. • The user can control some of the scheduling by passing parameters to the kernel (e.g., indicating priorities, etc. that will affect the scheduling). • Allows parallel processing – Kernel knows about possibly multiple CPU’s. – Kernel can share the ready queue between the CPU’s. 58 Kernel threads • Disadvantages – Less control over scheduling than user-level threads – Heavier than user threads (system calls to kernel are involved → inherently more expensive) – Cannot change the thread model. 59 Hybrid Implementations • Multiplexing user-level threads onto kernel- level threads 60 Multithreading Models • Many-to-One • One-to-One • Many-to-Many 61 Many-to-One • Many user-level threads mapped to single kernel thread. • Used on systems that do not support kernel threads. 62 Many-to-One Model 63 One-to-One • Each user-level thread maps to kernel thread. • Examples – Windows 95/98/NT/2000 – OS/2 64 One-to-one Model 65 Many-to-Many Model • Allows many user level threads to be mapped to many kernel threads. • Allows the operating system to create a sufficient number of kernel threads. • Solaris 2 • Windows NT/2000 with the ThreadFiber package 66 Many-to-Many Model 67 Threading Issues • Semantics of fork() and exec() system calls. – when a process is spawned, do we create clones of all the threads in the parent process? • Global variables – If each thread is to have a global variable, how is this handled? (ex: errno; see next slide) – Similarly issues with malloc(). • Signal handling – which thread should catch the signals. – Especially important in user-threads. Kernel doesn’t know about multiple threads. 68 Making Single-Threaded Code Multithreaded • Conflicts between threads over the use of a global variable • If one thread causes and error and gets suspended, next thread will think an error occurred in it. 69 Making Single-Threaded Code Multithreaded One possible solution: • Threads can have private global variables. • Complicates the threads implementation. 70 Processes and Thread Scheduling 71 Contents • • • • • Scheduling objectives Scheduling levels Batch systems Interactive systems Real-time systems 72 Process Scheduling Objectives • Objective of multiprogramming: maximal CPU utilization (always have a process running); • Objective of time-sharing: switch CPU among processes frequently enough so that users can interact with a program which it is running; 73 Scheduling Objectives • • • • Enforcement of fairness Enforcement of priorities Make best use of equipment Give preference to resources holding key resources • Give preference to processes exhibiting good behavior • Degrade gracefully under heavy loads 74 Performance Terms • Fairness • CPU and resource utilization -- keep resources as busy as possible • Throughput -- # of processes that complete execution in unit time • Turnaround time -- amount of time to execute a particular process from the time it entered the system 75 Performance Terms • Waiting time -- amount of time process has been waiting in ready queue • Response time -- amount of time from when a request was first submitted until first response is produced 76 Performance Criteria • • • • • Max CPU utilization Max throughput Min turnaround time Min waiting time Min response time 77 Program behavior characteristics • CPU–I/O Burst Cycle – Process execution consists of a alternating cycles of CPU execution and I/O wait during their lifetime. 78 CPU/IO cycles • Some processes have long CPU bursts between I/O requests – a CPU-bound process • And some have short CPU bursts – an I/O bound process 79 Histogram of CPU Burst Times Most programs have CPU burst length in this range 80 Scheduling Algorithm Goals 81 Scheduling Levels • High level scheduling (admission scheduling) (Typically in batch systems.) • Intermediate level scheduling (memory scheduling) (tries to balance system load) • Low level scheduling (CPU scheduling) 82 Scheduling in Batch Systems Three level scheduling 84 High Level Scheduling • Also called long term scheduling or admission scheduling. (Typically in batch systems.) • Which jobs should be allowed to enter the system and compete for the – CPU and other resources. • This scheduler selects jobs from the input queue • The goal is to select a “good” mix of CPU-bound and I/O-bound jobs so that the system is wellutilized. • Alternate selection criteria: select short jobs for admission with higher priority. 85 Intermediate Scheduling • Also called medium term scheduling or memory scheduling • Scheduling for jobs admitted to the system. – Temporarily suspend, or – Resume to smooth fluctuations in system load – e.g., too many processes and not enough memory ➔ swap some processes out to disk (hence the name “memory scheduling”) 86 Low-level Scheduling • Also called CPU scheduling, short term scheduling or dispatching • Assigning a CPU to a ready process – Many algorithms we will see will concentrate on this. 87 CPU Scheduler • CPU scheduler selects one of the processes from the ready queue and allocates CPU to one of them; • Ready queue: FIFO queue, tree queue, or unordered linked list, or priority queue; • Elements in the ready queue are PCBs (Process Control Block) of processes 88 Kinds of Scheduling • Non-preemptive scheduling • Preemptive scheduling 89 Non-preemptive Scheduling • Once the CPU is allocated to a process, the process keeps the CPU until 1. the process exits (i.e., finishes), or 2. it blocks (i.e., it switches to the wait state) • Does not require any special hardware (e.g., Timer) unlike preemptive scheduling 90 Preemptive Scheduling • A process can involuntarily relinquish its CPU because a higher priority process is becoming ready to run • Interrupt request due to – Timer, or – Device event: Key stroke 91 Preemptive Scheduling Issues • Preemptive scheduling has problems of interference between processes through shared data in an inconsistent state • Mechanisms required to coordinate access to shared data (synchronization) • Possible starvation 92 Dispatcher • Dispatcher gives control of the CPU to the process, scheduled by the short-term scheduler. Its functions: 1. switching context, 2. switching to user mode, 3. jumping to the proper location in the user program • • Dispatcher must be fast Dispatch latency = time to stop process and start another one 93 Scheduling in batch systems • Mostly mainframe computers doing data processing. • Can have batch processes on interactive systems also (e.g., using cron or at on Unix) – But they have to optimize their scheduling more for interactive environment. 94 First Come First Serve (FCFS) • Policy: process that requests the CPU FIRST is allocated the CPU FIRST • FCFS is Non-preemptive scheduling • Implementation: FIFO queues – Process entering the ready queue is inserted to the tail of the queue – The process selected from the ready queue is taken from the head of the queue 95 First Come First Serve (FCFS) • Performance metric: average waiting time • Given parameters: – Burst time (in ms), – Arrival time and – Order • Visualization of schedules - use Gantt charts • Metric: average waiting time 96 FCFS Scheduling Example: • Process Burst Time P1 24 P2 3 P3 3 Suppose that the processes arrive at time=0 in the order: P1, P2, P3 The Gantt Chart for the schedule is: P1 0 • • P2 24 P3 27 30 Waiting time for P1 = 0; P2 = 24; P3 = 27 Average waiting time: (0 + 24 + 27)/3 = 17 97 FCFS Scheduling Suppose that the processes arrive at time=0 in the order P2 , P3 , P1 . • The Gantt chart for the schedule is: P2 0 • • • • P3 3 P1 6 30 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 98 Convoy effect in FCFS n jobs in system … n-1 I/O bound jobs 1 CPU bound job • Remember FCFS is non-preemptive • • • – I/O bound jobs pass quickly through the ready queue and suspend themselves waiting for I/O – CPU bound job arrives at head of queue and executes until burst is complete – I/O bound jobs rejoin ready queue and wait for CPU bound job to complete I/O devices idle until CPU bound job completes  underutilized I/O devices When CPU bound job completes, other processes rush to wait on I/O again CPU becomes idle  underutilized CPU 99 FCFS Performance • Result: convoy effect, low CPU and I/O device utilization – CPU bound process holds CPU while I/O bound processes wait in the ready queue ➔ during this I/O devices are idle. – When I/O bound processes get hold of CPU, their CPU bursts are short ➔ during this time CPU is idle. 100 Shortest-Job-First (SJF) Scheduling • Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time. • Normally, we don’t know ahead of time the job lengths. • Used mostly as a benchmark (baseline for comparing other methods). 101 Shortest-Job-First (SJF) Scheduling • Two versions: – nonpreemptive – once CPU given to the process it cannot be preempted until it completes its CPU burst. – Preemptive – if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. This scheme is also known as the Shortest-Remaining-Time-First (SRTF). • SJF is optimal – gives minimum average waiting time for a given set of processes. 102 Example of Non-Preemptive SJF Process Arrival Time P1 0.0 P2 2.0 P3 4.0 P4 5.0 • SJF (non-preemptive) P1 0 3 P3 7 Burst Time 7 4 1 4 P2 8 0 wait time 6 wait time 3 wait time 7 wait time P4 12 16 Arrives at 2, has to wait until 8 • Average waiting time = (0 + 6 + 3 + 7)/4 = 4 103 Example of Preemptive SJF (SRTF) Process P1 P2 P3 P4 • SJF (preemptive) P1 0 Arrival Time 0.0 2.0 4.0 5.0 P2 2 P3 4 P2 5 Burst Time 7 4 1 4 P4 7 P1 11 16 • Average waiting time = (9 + 1 + 0 +2)/4 = 3 104 SJF - Preemptive Vs. Non-preemptive Process (Arrival Order): P1 P2 P3 P4 Burst Time 8 4 9 5 Arrival Time: 0 1 2 3 0 Preempt P1 1 P2 5 P4 10 P1 17 P3 26 Average WT := ((10-1) + (1-1) +(17-2) + (5-3))/4 = 6.5 ms Non 0 8 12 17 26 P1 P2 P4 P3 Preempt Average WT := (0 + (8-1) + (12-3) +(17-2))/4 = 7.75 ms 105 Determining Length of Next CPU Burst One possibility: guess the CPU burst based on history • Can only estimate the length. • Can be done by using the length of previous CPU bursts, using exponential averaging. 1. 𝑡𝑛 = actual length of 𝑛𝑡ℎ CPU burst 2. 𝜏𝑛+1 = predicted value for the next CPU burst 3. 𝛼, 0 ≤ 𝛼 ≤ 1 4. Define: 𝜏𝑛+1 = 𝛼𝑡𝑛 + 1 − 𝛼 𝜏𝑛 . 106 Examples of Exponential Averaging •  =0 – n+1 = n – Recent history does not count. •  =1 – n+1 = tn – Only the actual last CPU burst counts. 107 Predicting the Length of a SJF Job • Predicted value n+1 = tn + (1- ) n • Expanding the equation, we get n+1 = tn + (1- )  tn-1+…+ (1- )j  tn-j +…+(1- )n+1 0 • 0    both  and 1 -  are less than or equal to 1. Each term adds less to current value • For  = 0.5 recent history and past history are equally weighted • Version of SJF with preemption is called shortest remaining time first 108 Exponential Average 109 Priority Scheduling • Can be used both in batch as well as interactive systems. • Each job is assigned a priority • FIFO within each priority level Higher priority Queue for priority n Queue for priority n-1 … Queue for priority 1 Lower priority Queue for priority 0 110 Priority Scheduling Figure 2-43. A scheduling algorithm with four priority classes. Copyright © 2014 Pearson Education, Inc. All Rights Reserved Priority Scheduling • Select highest priority job over lower ones • Starvation possible. • Priority may be based on: – Cost to user – Importance of user – Aging (we’ll talk more about this) – Percentage of CPU time used in last X hours 112 Priority Scheduling - Example Process (Arrival Order) Burst Time Arrival Time Priority 0 P2 1 P5 6 P1 P1 10 0 3 P2 1 0 1 16 P3 2 0 3 P3 P4 1 0 4 18 P5 5 0 2 P4 19 Average WT := (0+1 + 6 + 16 + 18)/5 = 8.2 ms P1 and P3 have same priority ➔ FCFS Low number means high priority 113 Priority Scheduling - Comparison 0 10 P1 P2 11 P3 13 P4 Average WT := (0+10 + 11 + 13 + 14)/5 = 9.6 ms 0 P2 1 P4 2 P3 4 P5 14 P5 19 FCFS 9 P1 19 Average WT := (0+1 + 2 + 4 + 9)/5 = 3.2 ms SJF No preemption 114 Priority Scheduling • Low priority processes may end up waiting forever ➔ Indefinite postponement or starvation a problem. • Solution? Aging… – As the process ages, increase its priority over time. – Eventually, it has highest priority and gets scheduled. 115 Round Robin (RR) • Used in interactive systems. • Goal: minimize response time. • Each process gets a small unit of CPU time (time quantum or time slice), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue. C B A D CPU Blockage or completion preemption 116 Round Robin (RR) • If there are 𝑛 processes in the ready queue and the time quantum is 𝑞, then each process gets 1/𝑛 of the CPU time in chunks of at most 𝑞 time units at once. • No process waits more than (𝑛 − 1)𝑞 time units. • Short CPU burst processes get their chance and exit the queue quickly when they are done. (interactive tasks such as typing a character) • Long CPU burst processes turnaround time usually becomes longer. 117 Example: RR with Time Quantum q = 20 Process P1 P2 P3 P4 • The Gantt chart is: P1 0 P2 20 37 P3 Burst Time 53 17 68 24 P4 57 P1 77 P3 97 117 P4 P1 P3 P3 121 134 154 162 • Typically, higher average turnaround than SJF, but better response. 118 Round Robin (RR) • Performance – q large  FIFO – q small  q must be large with respect to context switch, otherwise overhead is too high. 119 How a Smaller Time Quantum Increases Context Switches 120 Turnaround Time Varies With The Time Quantum 121 Discussion • Processes change behavior – E.g., foreground vs. background • How can we adapt scheduling? – Have multiple queues 122 Multilevel Queue • Ready queue is partitioned into separate queues: foreground (interactive) background (batch) • Each queue has its own scheduling algorithm, foreground – RR background – FCFS • Processes stay in the queue they enter • Scheduling must be done between the queues. – 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 123 Multilevel Queue Scheduling 124 Multilevel Feedback Queue • A process can move (up and down) between the various queues; aging can be implemented this way. • Multilevel-feedback-queue scheduler defined by the following parameters: – – – – – number of queues scheduling algorithms for each queue method used to determine when to upgrade a process method used to determine when to demote a process method used to determine which queue a process will enter when that process needs service 125 Multi-level Feedback Queues • Each queue represents jobs with similar CPU usage. • Requirement to assign to each queue permanently is relaxed. ➔ processes can migrate to other queues. • Processes using too much CPU move to lower priority queues. • Processes that age move to higher priority queues. High priority,interactive jobs Low priority jobs 127 Multi-level Feedback Queues • Example: 𝑞𝑢𝑒𝑢𝑒𝑖 has time-slice 𝑡 × 2𝑖 • If job in 𝑞𝑢𝑒𝑢𝑒𝑖 doesn't block by end of time-slice it is moved to 𝑞𝑢𝑒𝑢𝑒𝑖+1 • Lowest priority queue is FIFO • Starvation: aging may move process to higher priority queue 128 Lottery Scheduling • Each process/thread given a lottery ticket. • When scheduler wants to decide who to schedule, pick one ticket at random. – The process holding that ticket number gets the CPU for a fixed amount of time (e.g., 20ms). 129 Lottery Scheduling • If everyone gets the same number of tickets, then everyone has fair share. – 5 processes, each holding 1 ticket: each has a 20% chance of getting scheduled. • One can increase the odds of a thread getting scheduled (e.g., because it is high priority) by giving more tickets to higher priority processes. – 1 process holds 2 tickets, and 4 processes hold 1 ticket each, then • Process holding 2 tickets has 2/6=33% chance of getting scheduled. • Other 4 processes each have 1/6=16.7% chance of getting scheduled. • Also, newly arriving thread after given a ticket, immediately has a chance of getting scheduled. 130 Fair share scheduling • Instead of fair share of CPU time for each process/thread, it tries to allocate fair share of time for each user. • Works out better if there are imbalances in the number of processes/user. • Example: User A has processes A, B, C and user B has one process D, • Allocate 50% CPU time per user. A possible schedule would be: – A, D, B, D, C, D, A, D, … • instead of – A, B, C, D, A, B, C, D, … – in which case, user A would have gotten 75% of the CPU time. 131 Multiple-processor Scheduling • Homogeneous processors permit load sharing • To keep all CPUs busy, have one ready queue accessed by each CPU • Self-scheduled -- each CPU dispatches a job from the ready queue – Critical section problems in accessing common queue: shared data structure maintenance problems and synchronization). • Master-slave -- one CPU schedules the other CPUs. extension of M/S results in ➔Asymmetric scheduling • Asymmetric -- one CPU runs the kernel and the others the user applications – System call interface: send a message to kernel CPU. 132 Modeling Multiprogramming • Suppose a process spends 𝑝 fraction of its time waiting for I/O to complete. • With n processes in memory, all 𝑛 of them waiting for I/O is 𝑝𝑛 . – If all n processes are waiting for I/O simultaneously, then CPU would be idle. Therefore, the probability that CPU would be idle with n processes is 𝑝𝑛 . – And the probability that the CPU will be doing useful computation at any given moment would be 1 − 𝑝𝑛 . • Thus, CPU utilization = 1 − 𝑝𝑛 . 136 Modeling Multiprogramming 80% Typical I/O wait times for interactive processes. Need to have at least 10 processes in memory for 90% CPU utilization Degree of multiprogramming • CPU utilization as a function of number of processes in memory 137 Discussion • In all the previous scheduling schemes, the scheduler is completely unaware of the wall clock time? How do we schedule to meet real-time situations then? – Use real-time scheduling. 138 Real-time Scheduling • Lots of solutions possible. • These depend on type of applications. • Different types of real-time scheduling – Hard real-time: produce output (or complete processing) within set time bounds. • Examples: flight control systems, etc. – Soft real-time: try to do things as fast as possible, at interactive rates. • Examples: interactive systems, video compression, etc. 139 Real-time Scheduling • Periodic schedulers – Tasks repeat at periodic rates. • Demand-driven schedulers – Interrupt-driven • Deadline schedulers – Deadlines by which tasks need to be completed. 140 Latency in Dispatching Goal: keep Dispatch latency small 142 Dispatch Latency • Problem: keep dispatch latency small. OS may enforce process to wait either for a system call to complete or for an I/O block to take place – This adds to dispatch latency 143 Dispatch Latency • Solution: need preemptable system calls • Insert preemption points (can be placed at safe location where kernel structures are not modified) • Make the kernel preemptable (all kernel structures must be protected through the use of various synchronization mechanisms) Example: Solaris2 144 Priority Inversion and Inheritance • Problem: – A higher priority process needs to read or modify kernel data – The data is being accessed by another, lower priority process • E.g., lower priority process has a lock – The result is that the higher priority process waits! ➔ thus, priority inversion. 145 Priority Inversion and Inheritance • Solution: priority inheritance • Goal is to have the lower priority processes do their task and get out of the way ASAP. – All processes accessing a resource needed by a high-priority process inherit high-priority until finished with the resource – When complete, their priority reverses to its natural value 146 Periodic Scheduler j h units with period 44 i units with period 22 j units with period 11 i h jobs 44 0 h1 i1 j1 0 j1 i1 h1 Periods and levels i2 j2 11 j2 i1 h1 j3 22 j3 i2 h1 j4 33 j4 i2 h1 44 Gant chart 147 Scheduling in Real-Time Systems • Question: What are the conditions under which periodic processes can be scheduled? Schedulable real-time system • Given – m periodic events – event i occurs within period 𝑃𝑖 and requires 𝐶𝑖 seconds of processing • Then the load can only be handled if 𝑚 𝐶𝑖 ෍ ≤1 𝑃𝑖 𝑖=1 148 Deadline Scheduling Process priority determined by process deadline Process A 2 1 Process B 1 Both streams scheduled according 1 to their deadlines 2 1 3 3 2 3 4 4 2 5 4 3 6 5 6 149 Deadline Scheduling • Result by Liu and Layland (1973): if any schedule will work, earliest deadline first will schedule tasks • Citation: “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,” C. L. Liu and James W. Layland, Journal of the ACM (JACM), v. 20, no. 1, pp. 46-61, 1973. 150 Process and Thread Synchronization 151 Interprocess Communication Race Conditions • Two processes want to access shared memory at same time 152 Cooperating Processes • Cooperating processes may be communicating with each other via shared variables or resources. • The actual execution of the instructions of a thread may become interleaved with other instructions of other threads due to preemptive scheduling. • In a multiprocessor system, the concurrent threads may actually each execute on an independent processor. 153 High level language code • Shared variable x Thread 1 Thread 2 x++ x++ • Concurrent threads, operating on shared variable x. • At high level language: we want increments to be atomic operations • When both threads are done – we expect x to be incremented by 2 regardless of order in which increment is performed. 154 Low level translated code • x++ could be implemented as register1  x register1  register1 + 1 x  register1 • It takes 3 low level instructions to accomplish the increment. • If the increment is not done atomically, computations can end up wrong. 155 interleaved Strictly sequential Interference and Shared Variables Process 1 Register R Process 2 Register R M Load M into R 1 Noop 0 1 Add 1 to R 2 Noop 0 1 Store R in M 2 Noop 0 2 Noop 2 Load M into R 2 2 Noop 2 Add 1 to R 3 2 Noop 2 Store R in M 3 3 Process 1 Register R Process 2 Register R M Load M into R 1 Noop 0 1 Noop 1 Load M into R 1 1 Add 1 to R 2 Noop 1 1 Store R in M 2 Noop 1 2 Noop 2 Add 1 to R 2 2 Noop 2 Store R in M 2 2 156 Producer-Consumer Problem • Concurrent execution that requires cooperation among processes needs mechanisms to allow: – communication with each other and synchronization of their actions. • Producer-Consumer problem is a paradigm for cooperating processes (and an example you will come across often). 157 Producer-Consumer Problem • For concurrent processing we need a buffer of items that can be filled by the producer and emptied by the consumer. • Communication occurs through shared memory. • buffer is the shared data between the two processes/threads. 158 Producer-Consumer Problem • Buffer can be of finite size or infinite size. • Unbounded-buffer producer-consumer problem places no practical limits on buffer size, The consumer may wait for a new item (when buffer is empty), but producer never waits (there is always space in the buffer). • Bounded-buffer producer-consumer problem assumes fixed buffer size. The consumer must wait for a new item when buffer is empty and the producer must wait when the buffer is full. 159 Background • A solution to shared-memory producerconsumer problem is not simple. – Let us create a variable counter, initialized to 0 and incremented when a new item is added and decremented when an item is consumed. – Let us create two pointers into buffer in and out where the produced item is put and from which consumed item is taken, respectively. 160 Bounded-Buffer • Shared data #define BUFFER_SIZE N typedef struct { . . ./* whatever information is produced/consumed */ } item; item buffer[BUFFER_SIZE]; int in = 0; /* pointer to where next item produced goes */ int out = 0; /* pointer from which next item is consumed */ int counter = 0; /* number of items in the buffer */ /* counter == 0 means buffer is empty counter == BUFFER_SIZE means buffer is full */ 161 Bounded-Buffer • Producer process item nextProduced; This is called a “busy wait” or “spinlock” while (TRUE) { while (counter == BUFFER_SIZE) {}; /* do nothing; buffer is full */ buffer[in] = nextProduced; C.S. in = (in + 1) % BUFFER_SIZE; /* wrap around */ counter++; } there’s our shared variable: counter 162 Bounded-Buffer • Consumer process item nextConsumed; while (TRUE) { while (counter == 0) {}; /* do nothing; buffer is empty */ nextConsumed = buffer[out]; C.S. out = (out + 1) % BUFFER_SIZE; counter--; } there’s our shared variable: counter 163 Bounded Buffer • counter is shared variable between producer and consumer ➔ both of them modify it. • counter counts the number of full buffer locations • The statements counter++; counter--; must be performed atomically. • Atomic operation means an operation that completes in its entirety without interruption (or if interrupted other processes/threads cannot operate on the shared variable). 164 Bounded Buffer • The statement “counter++” may be implemented in machine language as: register1 = counter register1 = register1 + 1 counter = register1 • The statement “counter--” may be implemented as: register2 = counter register2 = register2 – 1 counter = register2 165 Bounded Buffer • If both the producer and consumer attempt to update the buffer concurrently, the assembly language statements may get interleaved. • Similar situation to previous example. • Interleaving depends upon how the producer and consumer processes are scheduled. 166 Bounded Buffer • Consider this execution interleaving with “counter = 5” initially: S0: producer execute register1 = counter S1: producer execute register1 = register1 + 1 S2: consumer execute register2 = counter S3: consumer execute register2 = register2 – 1 S4: producer execute counter = register1 S5: consumer execute counter = register2 {register1 = 5} {register1 = 6} {register2 = 5} {register2 = 4} {counter = 6 } {counter = 4} • The correct result should be count = 5 after one atomic increment and one atomic decrement. – But we end up with counter = 4 instead. 167 Race Condition • Race condition: The situation where several processes access – and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes last. • To prevent race conditions, concurrent processes must be synchronized. 168 Synchronization approaches • Two main approaches – Software based solution: If processor does not provide synchronization primitives guaranteed to be atomic. ➔ Rely on memory write being atomic. – Hardware based solution: processor provides synchronization instructions guaranteed to be atomic. 169 Critical Section Problem • Consider system of n processes {p0, p1, … pn-1} • Each process has a critical section segment of code – Process may be changing common variables, updating table, writing file, etc. – When one process in critical section, no other may be in its critical section • Critical section problem is to design a protocol to solve this • Each process must ask permission to enter critical section in entry section, may follow critical section with exit section, then remainder section Critical Section Problems • General structure of a C.S. process is: do { This could be ENTER CRITICAL SECTION a very complex operation: critical section e.g., updating a LEAVE CRITICAL SECTION database. remainder section any other computation } while (TRUE); • Processes may share some common variables to synchronize their actions. 171 Critical Section Problem • Problem – How to ensure Mutual Exclusion in critical section? • That’s when one process is executing in its critical section, no other process is allowed to execute in its critical section? That is, how to synchronize? 172 Critical Sections Only one process at a time in respective critical section. Mutual exclusion using critical regions 173 Mutual exclusion • Assumption: In normal situations (i.e., computation at the machine instruction level), the Read/Write cycle on a bus (at the HW level) provides the mutual exclusion. – When doing write, the bus will prevent any other CPU from accessing memory (bus arbitration unit). – This assumption is used for the solution to critical section problem as we will see. 174 Properties of a Correct Solution to Critical-Section Problem 1. Mutual Exclusion. If process 𝑃𝑖 is executing in its critical section, then no other processes can be executing in their corresponding critical sections. 2. Progress. If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely. – Only processes that are not executing in the “remainder sections” (I.e., doing other work) can participate in deciding who gets into critical sections. 175 Properties of a Correct Solution to Critical-Section Problem 3. Bounded Waiting. A bound must exist 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 that request is granted. ❑ Guarantee that a process will enter C.S. within a bounded amount of time. ❑ Assume that each process executes at a nonzero speed. ❑ No assumption concerning relative speed of the processes. 176 Initial Attempts to Solve Problem Start with software solutions to synchronizing only two processes, P0 and P1 History of attempts to solve the problem • Approach 1: Turn Mutual Exclusion • Approach 2: Other Flag Mutual Exclusion • Approach 3: Two Flag Mutual Exclusion • Approach 4: Two Flag and Turn Mutual Exclusion (aka Peterson’s solution) • In all examples to follow for these approaches, we have two processes: P0 and P1. 177 Approach 1: Turn Mutual Exclusion • Shared variables: – int turn; initially turn = 0 – turn = i  Pi can enter its critical section • Process Pi do { while (turn != i) {/* no-op */}; // busy wait critical section turn = j; remainder section } while (true); • Satisfies mutual exclusion, but not progress – P0 and P1 take turns. If speed difference between two processes is large, this causes unnecessary waiting. 178 Approach 2: Other Flag Mutual Exclusion • Shared variables – boolean flag[2]; initially flag [0] = flag [1] = false. – flag[i] = true  Pi ready to enter its critical section • • Process Pi do { while (flag[j]) {/* noop */}; flag[i] = true; critical section flag [i] = false; remainder section } while (true); Does not satisfy mutual exclusion. // busy wait – Initially both flags can be false, and both processes will proceed into their critical regions. By the time a process sets flag to true it would be too late. 179 Approach 3: Two Flag Mutual Exclusion • Shared variables – – • • • boolean flag[2]; initially flag [0] = flag [1] = false. flag[i] = true  Pi ready to enter its critical section Same as other flag M.E., but flag set before entering the busy wait while loop. Process Pi do { flag[i] = true; while (flag[j]) {/* no-op */}; // busy wait critical section flag [i] = false; remainder section } while (true); Satisfies mutual exclusion, but not progress requirement. – Can block indefinitely: They can both set the flags to true before the loop and wait on each other indefinitely. 180 Approach 4: Combine turn and two flag approaches (Peterson’s solution) • Combined shared variables of algorithms 1 and 3. • Process Pi do { flag [i]= true; turn = j; while (flag[j] and turn == j) {/* no-op */}; // busy wait critical section flag [i] = false; remainder section } while (true); • Meets all three requirements; solves the critical-section problem for two processes. • In case there is a race condition (both set the flag = true at the same time), turn breaks the tie. 181 Bounded Buffer Producer-Consumer Solution using Petersen’s solution • Producer process item nextProduced; int turn; // initialize to 0 Boolean flag[2]; // initialize to false #define producer 0 #define consumer 1 while (TRUE) { while (counter == BUFFER_SIZE); /* do nothing; buffer is full */ flag [producer]= true; // The 3 statements in blue turn = consumer; // are ENTER CRITICAL SECTION while (flag[consumer] and turn == consumer); // busy wait buffer[in] = nextProduced; in = (in + 1) % BUFFER_SIZE; /* wrap around */ counter++; // this is the critical section flag [producer] = false; // exit critical section } 182 Bounded Buffer Producer-Consumer Solution using Petersen’s solution • Consumer process item nextConsumed; int turn; Boolean flag[2]; #define producer 0 #define consumer 1 while (TRUE) { while (counter == 0); /* do nothing; buffer is full */ flag [consumer]= true; // The 3 statements in blue turn = producer; // are ENTER CRITICAL SECTION while (flag[producer] and turn == producer); // busy wait nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; /* wrap around */ counter--; // this is the critical section flag [consumer] = false; // exit critical section } 183 n-process synchronization • There is a solution called “baker’s algorithm” • We won’t go into details. • The solution relies on each process getting “tickets” as in a bakery and using this “ticket number” to order who accesses critical section in what order, but still oneat-a-time. 184 Hardware Solutions • The earlier mutual exclusion examples depend on the memory hardware having an atomic write. If multiple reads and writes could occur to the same memory location at the same time, they would not work. • Processors with caches but no cache coherency cannot use the solutions provided. 185 Hardware Solutions • In general, it is IMPOSSIBLE to build mutual exclusion without a primitive that provides some form of mutual exclusion at the hardware level. 186 Synchronization Hardware • Thus, many systems provide hardware support for implementing the critical section code. • All solutions we will see are based on idea of locking – Protecting critical regions via locks • Uniprocessors – could disable interrupts – Currently running code would execute without preemption – Generally too inefficient on multiprocessor systems • Operating systems using this not broadly scalable Solution to Critical-section Problem Using Locks • General structure of the critical section will look as follows: do { acquire lock critical section release lock remainder section } while (TRUE); Hardware Solutions • Modern machines provide special atomic hardware instructions • Atomic = non-interruptible • Two solutions (and their related derivatives) are popular: – Either test memory word and set value • Test-and-set (e.g., Motorola 68000 TAS instruction) – Or swap contents of two memory words • Swap (e.g., Pentium XCHG instruction) – In general, not trivial to implement in multi-processor architectures. ➔ Beyond the scope of this class. 189 Test-and-Set • Hardware provides a test-and-set instruction that is guaranteed by hardware to be atomic and has the following semantics: Example Machine instruction Semantics (meaning) in C syntax TAS in 68000 boolean test_and_set (boolean *target) {// all done atomically boolean rv = *target; *target = TRUE; return rv: } 1. Executed atomically 2. Returns the original value of passed parameter 3. Set the new value of passed parameter to “TRUE”. 190 Solution using test_and_set() • Shared Boolean variable lock, initialized to FALSE • Solution: do { while (test_and_set(&lock)) // spinlock ; /* do nothing */ // trying to acquire lock /* critical section */ lock = false; // release lock /* remainder section */ } while (true); Swap • An alternative instruction is swap, provided by hardware that works atomically in hardware. Example Machine instruction Semantics (meaning) in C syntax XCHG in Pentium void swap(byte *x, *y); // All done atomically { byte temp = *x; *x = *y; *y = temp } 192 Variations on the theme compare_and_swap Instruction Definition: int compare_and_swap(int *value, int expected, int new_value) { int temp = *value; if (*value == expected) *value = new_value; return temp; } 1. Executed atomically 2. Returns the original value of passed parameter “value” 3. Set the variable “value” the value of the passed parameter “new_value” but only if “value” ==“expected”. That is, the swap takes place only under this condition. Solution using compare_and_swap • Shared integer “lock” initialized to 0; • Solution: do { while (compare_and_swap(&lock, 0, 1) != 0) ; /* do nothing */ /* critical section */ lock = 0; // release lock /* remainder section */ } while (true); Mutex Locks • Previous solutions are complicated and generally inaccessible to application programmers • OS designers build software tools to solve critical section problem • Simplest is mutex lock • Protect a critical section by first acquire() a lock then release() the lock • Boolean variable indicating if lock is available or not • Calls to acquire() and release() must be atomic • Usually implemented on top of hardware atomic instructions Usage of hardware primitives • Example implementation • Example: “lock” C++ class using test-andset. – Provides mutual exclusion. 196 A Lock Class that uses TestAndSet Lock class declaration: class Lock { byte state; // internal state var public: Lock(); void acquire(); void release(); int isFree(); }; 197 A Lock Class that uses TestAndSet Example usage of Lock class: Lock a; a.acquire(); // acquire the lock // Do Critical Section using lock a a.release(); // release the lock 198 Lock Class Implementation using TestAndSet() inline Lock::Lock() { state = 0; } inline void Lock::acquire() { while (test_and_set(state));/* spin-lock */ } inline void Lock::release() { state = 0; } inline int Lock::isFree() { return (state == 0); } This test is atomic! 199 Busy wait disadvantages • Previous solutions to synchronization problems we saw (e.g., bounded-buffer producer-consumer problem) used “busy-wait” to implement the waiting on a condition: while loop waiting on some condition to change. • This is wasteful, because the while loop needs to execute on the CPU and, therefore, wastes precious processor cycles, doing nothing useful. – There are cases where busy-wait is better: if the wait is expected to be short – Tradeoff in this case: overhead of context-switch going through kernel vs. wasting CPU cycles. 200 Alternatives to busy waiting • One possible solution: sleep() and wakeup() system calls. • Process/thread executing sleep() would be suspended and be put in “blocked” state until some other process/thread wakes it up. • wakeup(pid) call wakes up process/thread with pid: meaning it is put in ready state and put in the ready queue to be scheduled for the CPU. • Problem: it can cause race conditions. 201 Sleep and Wakeup • Producer-consumer problem with fatal race condition: because of unconstrained access to count. 202 Race condition 1. 2. Buffer is empty. Consumer has loaded count into a register getting ready to test against 0 At that moment, scheduler decides to stop running consumer and schedules producer to run on the CPU. Producer inserts an item into buffer, increments count, tests against 1, and issues wakeup(consumer). When consumer is scheduled to run on CPU again, it is not logically asleep yet. 3. 4. 5. • • 6. It continues with the previous value of count (=0). Consumer tests this value against 0 and issues a sleep() command. But the wakeup call issued by the producer is lost! 203 Solution: Semaphores • Invented by Dijkstra in 1965, they are meant to keep track of the wakeup’s and sleeps so they don’t get lost. • Various versions: – Original: P() and V() operations (from the initials of the dutch words for test/Proberen and signal/Verhogen) – down() and up() (in Tanenbaum textbook) – wait() and signal() (in Silberschatz textbook) 204 Semaphore • Goal is to make it easier to program synchronization (SW synchronization primitive). – Want to have the same effect from a SW view as the acquire and release. • A semaphore count represents the number of abstract resources. • The P (wait or down) operation is used to acquire a resource and decrements count. – If a P operation is performed on a count that is 0, then the process must wait for a V or release of a resource. • The V (signal or up) operation is used to release a resource and increments count. • P and V occur atomically: i.e. indivisibly. 205 Busy Wait Semaphore Class Uses test_and_set primitive class Semaphore { Lock mutex; // Mutual exclusion. int count; // Resource count. public: Semaphore(int num); // constructor void P(); // wait void V(); // signal }; static inline Semaphore::Semaphore(int num) { count = num; } 206 Busy Wait Semaphore P() Defn void Semaphore::P() { while (count == 0) {/* busy-wait */}; mutex.acquire(); // M.E. lock acquire count is no longer= 0 count--; so I can decrement Mutex protects the mutex.release(); updating of count. } •For semaphores to work, the modification of the semaphore variable, count must be done atomically. •In this implementation, this is accomplished through the use of lock, which uses the hardware provided atomic operation test-and-set. 207 Busy Wait Semaphore V() Defn void Semaphore::V() { mutex.acquire(); count++; mutex.release(); } 208 Two Types of Semaphores • Counting semaphore – integer value can range over an unrestricted domain. • Binary semaphore – integer value can range only between 0 and 1; can be simpler to implement. These are also called mutexes (because they are used mostly to implement mutual exclusion). 209 Busy Wait Semaphore Issues • Busy waits waste CPU cycles. • Instead of a busy wait, we can implement a blocking semaphore. • Instead of going into a busy wait loop, the semaphore blocks (yields) so another process/thread can be scheduled to use the CPU. 210 Busy Wait Semaphore Issues • The queue/block/resume implementation of Semaphore has less of a busy wait problem. – The processes/threads can be put on a queue for the semaphore! – When a release operation occurs, look at the queue to see who gets semaphore. – A mutex is used to make sure that two processes don’t change count at the same time. – Two possible ways to implement: 1. If P() decrements before it suspends ➔ count can be < 0. 2. P() suspends when count == 0, then decrements when woken up ➔ count can never go negative. – For negative counts ➔ value gives number of processes/threads in the queue. 211 Busy Wait Semaphore Issues – If process is to be blocked, enqueue (in the semaphore queue) PCB of process/thread and call scheduler to run a different process. • Thread in Nachos project 1 instead of process. • Yield() in Nachos will do this. – Comment: An interrupt while mutex is held will result in a long delay. So, turn off interrupts during critical section. 212 Blocking semaphore Class Semaphore { int count; // semaphore value ProcessList queue; // queue/list of // process PCB’s for // this semaphore lock mutex; Public: Semaphore(int num); void P(); void V(); }; 213 Blocking semaphore Void Semaphore::P() { lock.acquire(); // for mutual exclusion count--; // decremented before suspend In uniprocessor if (count < 0) { system lock.acquire() // put process on semaphore queue would just turn off queue.append(this); // this=current interrupts; no need for Spinlock. // process lock.release(); block(); // suspend/block current process // or equivalently sleep() } else } lock.release(); 214 Blocking Semaphore Void Semaphore::V() { lock.acquire(); // for mutual exclusion count++; if (count <= 0) { // wake up some process waiting P = queue.remove() ReadyQueue.append(P) } Move the process at the lock.release(); head of L to ReadyQueue } 215 Semaphores class in nachos (java version) Let’s see how semaphores are implemented in Nachos. (some details deleted) This version does not allow semaphore count to go negative. class Semaphore { public String name; private int value; private List queue; // useful for debugging // semaphore value, always >= 0 // threads waiting in P() for the value to be > 0 // constructor public Semaphore(String debugName, int initialValue) { name = debugName; value = initialValue; queue = new List(); } // methods in the next couple of slides 216 Implementation P() // Checking the value and decrementing (i.e., the entire P() operation) // must be done atomically, so we need to disable interrupts // before checking the value. public void P() { int oldLevel = Interrupt.setLevel(Interrupt.IntOff); // disable interrupts while (value == 0) { // semaphore not available queue.append(NachosThread.thisThread()); // so go to sleep NachosThread.thisThread().sleep(); // Thread::Sleep() assumes interrupts are off // next scheduled thread is responsible for enabling interrupts } // here we don’t need lock or mutex because we have d