THREADS

UNIT - 2 : 

UNIT - 2

Threads : 

Operating Systems 2 Threads Overview Multithreading Models Threading Issues

Single vs. Multithreaded Processes : 

Operating Systems 3 Single vs. Multithreaded Processes Process: everything we’ve seen up to now Thread: like a process, only shares memory, global variables, files, PID with other threads within the same process

Should you use threads or processes? : 

Operating Systems 4 Should you use threads or processes? Why use threads instead of processes? Faster context switch (why?) Easier to share data Uses less memory and resources Thread creation faster than process creation (30x faster in Solaris) Less things to set-up Why use processes instead of threads? Different code Running on different machines Different owners Little communication Sharing memory can lead to obscure bugs

User-level threads : 

Operating Systems 5 User-level threads Threads can be provided at the user or kernel level User level: kernel knows nothing about threads Implemented in a library by somebody without touching the kernel User library handles Thread creation Thread deletion Thread scheduling Benefits: Faster creation and scheduling (why?) Drawbacks: One thread blocking during I/O blocks all threads in process (even ready-to-run threads)

User-level threads (cont’d) : 

Operating Systems 6 User-level threads (cont’d) Three primary thread libraries: POSIX Pthreads Win32 threads Java threads

Kernel-level threads : 

Operating Systems 7 Kernel-level threads Kernel knows about threads Kernel handles thread creation, deletion, scheduling Benefits: Kernel can schedule another thread if current one does blocking I/O Kernel can schedule multiple threads on different CPUs on SMP multiprocessor Drawbacks: Slower to schedule, create, delete than user-level Most modern OSes support kernel-level threads Windows XP/2000 Solaris Linux Tru64 UNIX Mac OS X

Multithreading Models : 

Operating Systems 8 Multithreading Models How to map kernel-level threads to user-level threads? Many-to-One One-to-One Many-to-Many

Many-to-One Model : 

Operating Systems 9 Many-to-One Model

Many-to-One : 

Operating Systems 10 Many-to-One Many user-level threads mapped to single kernel thread Examples: Solaris Green Threads GNU Portable Threads Any disadvantages? All block when one blocks All run on 1 CPU

One-to-one Model : 

Operating Systems 11 One-to-one Model

One-to-One : 

Operating Systems 12 One-to-One Each user-level thread maps to a kernel thread Examples: Windows NT/XP/2000 Linux Solaris 9 and later Any disadvantages? Overhead for creating threads Many operating systems limit number of threads

Many-to-Many Model : 

Operating Systems 13 Many-to-Many Model

Many-to-Many Model : 

Operating Systems 14 Many-to-Many Model Allows many user level threads to be mapped to smaller or equal number of kernel threads Allows the flexibility of choosing the number of kernel threads allocated to a process “Best of both worlds” Solaris prior to version 9

Two-level Model : 

Operating Systems 15 Two-level Model

Two-level Model : 

Operating Systems 16 Two-level Model Similar to many-to-many, but allows a user thread to be bound to kernel thread Examples IRIX HP-UX Tru64 UNIX Solaris 8 and earlier

Threading Issues : 

Operating Systems 17 Threading Issues Semantics of fork() and exec() system calls Thread cancellation Signal handling Thread pools Thread-specific data

Semantics of fork() and exec() : 

Operating Systems 18 Semantics of fork() and exec() Does fork() duplicate only the calling thread or all threads? Some UNIX systems have two versions of fork() exec() usually replaces all threads with new program fork1() fork2()

Thread Cancellation : 

Operating Systems 19 Thread Cancellation Terminating a thread before it has finished E.g., two cooperating threads, one discovers an error Two general approaches: Asynchronous cancellation terminates the target thread immediately Deferred cancellation allows the target thread to periodically check if it should be cancelled Why is this an issue? What if a thread is in the middle of Allocating resources Performing I/O Updating a shared data structure

Thread Cancellation (cont’d) : 

Operating Systems 20 Thread Cancellation (cont’d) Essentially, deferred cancellation = “target, please cancel yourself” Occurs when target checks for cancellation signal Allows cancellation at “safe” points Called cancellation points in Pthreads

Signal Handling : 

Operating Systems 21 Signal Handling Signals are used in UNIX to notify a process that a particular event has occurred A signal handler is used to process signals Signal is generated by a particular event Signal is delivered to a process Signal is handled (or ignored/blocked) Options: Deliver the signal to the thread to which the signal applies Applicable with synchronous signals e.g., illegal memory access Deliver the signal to every thread in the process Deliver the signal to certain threads in the process Assign a specific threat to receive all signals for the process

Thread Pools : 

Operating Systems 22 Thread Pools Motivating example: a web server running on an SMP machine To handle each connection: Create a new process to handle it too slow, inefficient Create a new thread to handle it Option 2 better but still has some problems: Some overhead for thread creation/deletion Thread will only be used for this connection Unbounded number of threads might crash web server Better solution: use a thread pool of (usually) fixed size

Thread Pools (cont’d) : 

Operating Systems 23 Thread Pools (cont’d) Threads in pool sit idle Request comes in: Wake up a thread in pool Assign it the request When it completes, return it to pool If no threads in pool available, wait Advantages: Usually slightly faster to wake up an existing thread than create a new one Allows the number of threads in the application to be limited by the size of the pool More sophisticated systems dynamically adjust pool size

Thread-specific Data : 

Operating Systems 24 Thread-specific Data Allows each thread to have its own copy of data Useful for implementing protection For example, user connects to bank’s database server Server process responds, has access to all accounts Multiple people may be accessing their accounts at the same time Thread assigned to manipulate or view user’s bank account Using thread-specific data limits (unintentional or erroneous) access by other threads

CPU Scheduling : 

Operating Systems 25 CPU Scheduling Basic Concepts Scheduling Criteria Scheduling Algorithms Multiple-Processor Scheduling Real-Time Scheduling

Basic Concepts : 

Operating Systems 26 Basic Concepts Maximum CPU utilization obtained with multiprogramming CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait CPU burst distribution

Alternating Sequence of CPU And I/O Bursts : 

Operating Systems 27 Alternating Sequence of CPU And I/O Bursts

Histogram of CPU-burst Times : 

Operating Systems 28 Histogram of CPU-burst Times

CPU Scheduler : 

Operating Systems 29 CPU Scheduler Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them CPU scheduling decisions may take place when a process: 1. Switches from running to waiting state 2. Switches from running to ready state 3. Switches from waiting to ready 4. Terminates Scheduling under 1 and 4 is nonpreemptive All other scheduling is preemptive

Dispatcher : 

Operating Systems 30 Dispatcher Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves: switching context switching to user mode jumping to the proper location in the user program to restart that program Dispatch latency – time it takes for the dispatcher to stop one process and start another running

Scheduling Criteria : 

Operating Systems 31 Scheduling Criteria CPU utilization – keep the CPU as busy as possible Throughput – # of processes that complete their execution per time unit Turnaround time – amount of time to execute a particular process Waiting time – amount of time a process has been waiting in the ready queue Response time – amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)

Optimization Criteria : 

Operating Systems 32 Optimization Criteria Max CPU utilization Max throughput Min turnaround time Min waiting time Min response time

First-Come, First-Served (FCFS) Scheduling : 

Operating Systems 33 First-Come, First-Served (FCFS) Scheduling 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

FCFS Scheduling (Cont.) : 

Operating Systems 34 FCFS Scheduling (Cont.) 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 (SJR) Scheduling : 

Operating Systems 35 Shortest-Job-First (SJR) Scheduling Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time Two schemes: nonpreemptive – once CPU given to the process it cannot be preempted until 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 know as the Shortest-Remaining-Time-First (SRTF) SJF is optimal – gives minimum average waiting time for a given set of processes

Example of Non-Preemptive SJF : 

Operating Systems 36 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 Example of Non-Preemptive SJF

Example of Preemptive SJF : 

Operating Systems 37 Example of Preemptive SJF Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (preemptive) Average waiting time = (9 + 1 + 0 +2)/4 = 3

Determining Length of Next CPU Burst : 

Operating Systems 38 Determining Length of Next CPU Burst Can only estimate the length Can be done by using the length of previous CPU bursts, using exponential averaging

Prediction of the Length of the Next CPU Burst : 

Operating Systems 39 Prediction of the Length of the Next CPU Burst

Examples of Exponential Averaging : 

Operating Systems 40 Examples of Exponential Averaging ? =0 ?n+1 = ?n Recent history does not count ? =1 ?n+1 = ? tn Only the actual last CPU burst counts If we expand the formula, we get: ?n+1 = ? tn+(1 - ?)? tn -1 + … +(1 - ? )j ? tn -j + … +(1 - ? )n +1 ?0 Since both ? and (1 - ?) are less than or equal to 1, each successive term has less weight than its predecessor

Priority Scheduling : 

Operating Systems 41 Priority Scheduling A priority number (integer) is associated with each process The CPU is allocated to the process with the highest priority (smallest integer ? highest priority) Preemptive nonpreemptive SJF is a priority scheduling where priority is the predicted next CPU burst time Problem ? Starvation – low priority processes may never execute Solution ? Aging – as time progresses increase the priority of the process

Round Robin (RR) : 

Operating Systems 42 Round Robin (RR) Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end 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. Performance q large ? FIFO q small ? q must be large with respect to context switch, otherwise overhead is too high

Example of RR with Time Quantum = 20 : 

Operating Systems 43 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

Time Quantum and Context Switch Time : 

Operating Systems 44 Time Quantum and Context Switch Time

Turnaround Time Varies With The Time Quantum : 

Operating Systems 45 Turnaround Time Varies With The Time Quantum

Multilevel Queue : 

Operating Systems 46 Multilevel Queue Ready queue is partitioned into separate queues:foreground (interactive)background (batch) Each queue has its own scheduling algorithm foreground – RR background – FCFS 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

Multilevel Queue Scheduling : 

Operating Systems 47 Multilevel Queue Scheduling

Multilevel Feedback Queue : 

Operating Systems 48 Multilevel Feedback Queue A process can move 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

Example of Multilevel Feedback Queue : 

Operating Systems 49 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 : 

Operating Systems 50 Multilevel Feedback Queues

Multiple-Processor Scheduling : 

Operating Systems 51 Multiple-Processor Scheduling CPU scheduling more complex when multiple CPUs are available Homogeneous processors within a multiprocessor Load sharing Asymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharing

Real-Time Scheduling : 

Operating Systems 52 Real-Time Scheduling Hard real-time systems – required to complete a critical task within a guaranteed amount of time Soft real-time computing – requires that critical processes receive priority over less fortunate ones

Process Synchronization : 

Operating Systems 53 Process Synchronization Background The Critical-Section Problem Peterson’s Solution Synchronization Hardware Semaphores Classic Problems of Synchronization Monitors

Background : 

Operating Systems 54 Background Concurrent access to shared data may result in data inconsistency (e.g., due to race conditions) 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. Incremented by producer after producing a new buffer Decremented by consumer after consuming a buffer

Producer : 

Operating Systems 55 Producer while (true) { /* produce an item and put in nextProduced */ while (count == BUFFER_SIZE) ; // do nothing buffer [in] = nextProduced; in = (in + 1) % BUFFER_SIZE; count++; }

Consumer : 

Operating Systems 56 Consumer while (true) { while (count == 0) ; // do nothing nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; count--; /* consume the item in nextConsumed }

Race Condition : 

Operating Systems 57 Race Condition 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: T0: producer execute register1 := count {register1 = 5}T1: producer execute register1 := register1 + 1 {register1 = 6} T2: consumer execute register2 := count {register2 = 5} T3: consumer execute register2 := register2 - 1 {register2 = 4} T4: producer execute count := register1 {count = 6} T5: consumer execute count := register2 {count = 4}

Process States : 

Operating Systems 58 Process States Thinking – Executing independent actions Hungry – Requesting access to shared resources Eating – Executing within a critical section of code Exiting – Relinquishing shared resources

Solution to Critical-Section Problem : 

Operating Systems 59 Solution to Critical-Section Problem 1. Mutual Exclusion – No two processes eat simultaneously Progress - If no process eats forever, and some process is hungry, then some (potententially different) hungry process eventually eats. 3. Bounded Waiting - A bound exists on the number of times that other processes are allowed to eat after a process P becomes hungry and before process P eats. Assume that each process executes at a nonzero speed No assumption concerning relative speed of the N processes

Peterson’s Solution : 

Operating Systems 60 Peterson’s Solution Two process solution Assume that the LOAD and STORE instructions are atomic The two processes share two variables: int turn; Boolean flag[2] Initially: flag[0]=flag[1]= false 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 : 

Operating Systems 61 Algorithm for Process Pi while (true) { flag[i] = TRUE; turn = j; while ( flag[j] && turn == j); CRITICAL SECTION flag[i] = FALSE; REMAINDER SECTION }

Synchronization Hardware : 

Operating Systems 62 Synchronization Hardware Many systems provide hardware support for critical sections Uniprocessors – could disable interrupts Current running code would execute without preemption Generally too inefficient on multiprocessor systems Operating systems using this not broadly scalable Modern machines provide special atomic hardware instructions Atomic = non-interruptable Either test memory word and set value Or swap contents of two memory words

TestAndSet Instruction : 

Operating Systems 63 TestAndSet Instruction Definition: (rv is “return value”) boolean TestAndSet (boolean *target) { boolean rv = *target; *target = TRUE; return rv: }

Solution using TestAndSet : 

Operating Systems 64 Solution using TestAndSet Shared boolean variable lock, initialized to false. Solution: while (true) { while (TestAndSet (&lock )) ; /* do nothing // critical section lock := FALSE; // remainder section }

Swap Instruction : 

Operating Systems 65 Swap Instruction Definition: Just exchange the values of variables a and b void Swap (boolean *a, boolean *b) { boolean temp = *a; *a = *b; *b = temp: }

Solution using Swap : 

Operating Systems 66 Solution using Swap Shared Boolean variable lock initialized to FALSE; Each process has a local Boolean variable key. Solution: while (true) { key = TRUE; while ( key == TRUE) Swap (&lock, &key ); // critical section lock = FALSE; // remainder section }

Semaphores in the Real World : 

Operating Systems 67 Semaphores in the Real World Semaphores were a mechanism for optical telegraphy Used to send information using visual signals Information encoded in the position (value) of flags Public domain images sourced from Wikipedia article “Semaphore”

Semaphore : 

Operating Systems 68 Semaphore Synchronization tool that does not require busy waiting (spinlocks) Invented by The Man – Edsger Dijkstra (“Eddie D”) A semaphore S is a protected integer-valued variable Two standard operations modify semaphore: wait() – Originally called P(), from Dutch proberen “to test” signal() – Originally called V(), from Dutch verhogen “to increment” Busy-waiting implementation of these indivisible (atomic) operations: wait (S) { while (S <= 0); // empty loop body (no-op) S--;} signal (S) { S++; }

Semaphore as General Synchronization Tool : 

Operating Systems 69 Semaphore as General Synchronization Tool Counting semaphore Integer value can range over an unrestricted domain Useful for k-exclusion scenarios of replicated resources Binary semaphore Integer value ranges only between 0 and 1 Can be simpler to implement Also known as mutex locks Provides mutual exclusion Semaphore S; // initialized to 1 wait (S); Critical Section signal (S);

Semaphore Implementation : 

Operating Systems 70 Semaphore Implementation Must guarantee that no two processes can execute wait () and signal () on the same semaphore at the same time Thus, semaphore implementation is a critical section problem where the wait and signal code are placed in critical sections Could now have busy waiting in critical section implementation But implementation code is short Little busy waiting if critical section rarely occupied Note that applications may spend lots of time in critical sections and therefore this is not a good general solution.

Semaphore Implementation without busy waiting : 

Operating Systems 71 Semaphore Implementation without busy waiting With each semaphore there is an associated waiting queue. Each entry in a waiting queue has two data items: Value (of type integer) Pointer to next record in the list Two operations: block – place the process invoking the wait operation on the appropriate waiting queue. wakeup – remove one of processes in the waiting queue and place it in the ready queue.

Semaphore Implementation with no Busy waiting (Cont.) : 

Operating Systems 72 Semaphore Implementation with no Busy waiting (Cont.) Implementation of wait: Wait (S){ value--; if (value < 0) { add this process to waiting queue block(); } } Implementation of signal: Signal (S){ value++; if (value <= 0) { remove a process P from the waiting queue wakeup(P); } }

Deadlock and Starvation : 

Operating Systems 73 Deadlock and Starvation Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes Let S and Q be two semaphores initialized to 1 P0 P1 wait (S); wait (Q); wait (Q); wait (S); . . . . . . signal (S); signal (Q); signal (Q); signal (S); Starvation – indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended.

Classical Problems of Synchronization : 

Operating Systems 74 Classical Problems of Synchronization Bounded-Buffer Problem Readers and Writers Problem Dining-Philosophers Problem

Bounded-Buffer Problem : 

Operating Systems 75 Bounded-Buffer Problem Example of a producer-consumer problem N buffers, each can hold one item Semaphore mutex initialized to the value 1 Semaphore full initialized to the value 0 Semaphore empty initialized to the value N.

Bounded Buffer Problem (Cont.) : 

Operating Systems 76 Bounded Buffer Problem (Cont.) The structure of the producer process: while (true) { // produce an item wait (empty); // initially empty = N wait (mutex); // intiallly mutex = 1 // add the item to the buffer signal (mutex); // currently mutex = 0 signal (full); // initially full = 0 }

Bounded Buffer Problem (Cont.) : 

Operating Systems 77 Bounded Buffer Problem (Cont.) The structure of the consumer process while (true) { wait (full); // initially full = 0 wait (mutex); // intiallly mutex = 1 // remove an item from buffer signal (mutex); // currently mutex = 0 signal (empty); // initially empty = N // consume the removed item }

Readers-Writers Problem : 

Operating Systems 78 Readers-Writers Problem A data set is shared among a number of concurrent processes Readers – only read the data set; do not perform any updates Writers – can both read and write. Problem Allow multiple readers to read at the same time. Only one writer can access the shared data at the same time. Shared Data Semaphore mutex initialized to 1. Semaphore wrt initialized to 1. Integer readcount initialized to 0.

Readers-Writers Problem (Cont.) : 

Operating Systems 79 Readers-Writers Problem (Cont.) The structure of a writer process while (true) { wait (wrt) ; // writing is performed signal (wrt) ; }

Readers-Writers Problem (Cont.) : 

Operating Systems 80 Readers-Writers Problem (Cont.) The structure of a reader process while (true) { wait (mutex) ; readcount ++ ; if (readcount == 1) wait (wrt) ; signal (mutex) // reading is performed wait (mutex) ; readcount - - ; if (readcount == 0) signal (wrt) ; signal (mutex) ; }

Dining-Philosophers Problem : 

Operating Systems 81 Dining-Philosophers Problem Shared data Bowl of rice (data set) Semaphore chopstick [5] initialized to 1

Dining-Philosophers Problem (Cont.) : 

Operating Systems 82 Dining-Philosophers Problem (Cont.) The structure of Philosopher i: While (true) { wait ( chopstick[i] ); wait ( chopstick[ (i + 1) % 5] ); // eat signal ( chopstick[i] ); signal ( chopstick[ (i + 1) % 5] ); // think }

Problems with Semaphores : 

Operating Systems 83 Problems with Semaphores Correct use of semaphore operations: signal (mutex) …. wait (mutex) Can violate mutual exclusion wait (mutex) … wait (mutex) Can lead to deadlock! Omitting of wait (mutex) or signal (mutex)

Monitors : 

Operating Systems 84 Monitors A higher-level abstraction that provides a convenient and effective mechanism for process synchronization Key Idea: Only one process may be active within the monitor at a time monitor monitor-name { // shared variable declarations procedure P1 (…) { …. } … procedure Pn (…) {……} Initialization code ( ….) { … } … } }

Schematic view of a Monitor : 

Operating Systems 85 Schematic view of a Monitor

Condition Variables : 

Operating Systems 86 Condition Variables condition x, y; Two operations on a condition variable: x.wait () – process invoking the operation is suspended. x.signal () – resumes one of the processes (if any) that invoked x.wait ()

Monitor with Condition Variables : 

Operating Systems 87 Monitor with Condition Variables

Solution to Dining Philosophers : 

Operating Systems 88 Solution to Dining Philosophers monitor DP { enum { THINKING; HUNGRY, EATING) state [5] ; condition self [5]; void pickup (int i) { state[i] = HUNGRY; test(i); if (state[i] != EATING) self [i].wait; } void test (int i) { if ( (state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING) ) { state[i] = EATING ; self[i].signal () ; } }

Solution to Dining Philosophers (cont) : 

Operating Systems 89 Solution to Dining Philosophers (cont) void putdown (int i) { state[i] = THINKING; // test left and right neighbors test((i + 4) % 5); test((i + 1) % 5); } initialization_code() { for (int i = 0; i < 5; i++) state[i] = THINKING; } }

Solution to Dining Philosophers (cont) : 

Operating Systems 90 Solution to Dining Philosophers (cont) Each philosopher I invokes the operations pickup() and putdown() in the following sequence: dp.pickup (i) EAT dp.putdown (i)

Monitor Implementation Using Semaphores : 

Operating Systems 91 Monitor Implementation Using Semaphores Variables semaphore mutex; // (initially = 1) semaphore next; // (initially = 0) int next-count = 0; // Number of processes suspended Each procedure P will be replaced by wait(mutex); … body of procedure P; … if (next-count > 0) // Yield to a waiting process. signal(next) else // Nobody waiting? Then exit. signal(mutex); Mutual exclusion within a monitor is ensured.

Monitor Implementation : 

Operating Systems 92 Monitor Implementation For each condition variable x, we have: semaphore x-sem; // (initially = 0) int x-count = 0; // Number of processes waiting on cond x The operation x.wait can be implemented as: x-count++; if (next-count > 0) signal(next); // Yield to a waiting process. else signal(mutex); // Nobody waiting? Release mutex. wait(x-sem); x-count--;

Monitor Implementation : 

Operating Systems 93 Monitor Implementation The operation x.signal can be implemented as: if (x-count > 0) { next-count++; signal(x-sem); wait(next); next-count--; } Note: Signal is idempotent if x-count == 0.

Thank you : 

Thank you