CS 345 Operating Systems
Learn about mutual exclusion concepts such as the comma operator, semaphores, and mutexes in operating systems. Understand how semaphores and mutexes help synchronize access to shared resources in concurrent systems. Explore the uses and benefits of semaphores for synchronization, resource allocation, and mutual exclusion
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Welcome to CS 345 Operating Systems Mutual Exclusion (12)
Tip #12: Comma Operator 2 Mutual Exclusion (12) The comma operator isn't widely used. It can certainly be abused, but it can also be very useful. for (int i=0; i<10; i++, doSomethingElse()) { /* whatever */ } int j = (printf("Assigning variable j\n"), getValueFromSomewhere()); printf("%d", j); Each statement is evaluated, but the value of the expression will be that of the last statement evaluated.
Semaphores 3 Mutual Exclusion (12) A semaphore is a protected variable whose value is accessed and altered by the operations signal (produce) and wait (consume). A semaphore is used for controlling access to a common resource in a concurrent system, such as multi-threading. The value of a semaphore is the number of available resources and may be used to synchronize various task activities. A useful way to think of a semaphore is as a record of how many units of a particular resource are available, coupled with operations to safely consume those units, and, if necessary, wait until a unit of the resource becomes available.
Mutexes 4 Mutual Exclusion (12) A mutex is locking mechanism used to synchronize access to a resource (such as code). Only one task can acquire the mutex. It means there is ownership associated with mutex, and only the owner can release the lock (mutex). A mutex is designed to protect critical data so that only one thread can access it at the same time, such as a section of code or access to a variable.
Semaphores 5 Mutual Exclusion (12) What is a semaphore? A semaphore is an autonomous synchronous abstract data type used for controlling access by multiple processes, to a common resource in a concurrent system. How are semaphores produced? Semaphores are produced by SEM_SIGNAL. How are semaphores consumed? Semaphores are consumed by SEM_WAIT and SEM_TRYLOCK. What are the major uses of semaphores? Synchronization Resource allocation Mutual Exclusion
Semaphores 6 Mutual Exclusion (12) What does it mean to be autonomous? Disable interrupts (only works on uni-processor) Software solutions (Decker) Hardware: test-and-set, exchange What does it mean to be synchronous? What are the different types of semaphores? Binary semaphore 1 resource, 2 states 0 = nothing produced, maybe tasks in queue 1 = something produced, no tasks in queue Counting semaphore 1 resource, multiple copies 0 = nothing produced, nothing in queue -n = nothing produced, n tasks queued +n = n items produced, no tasks in queue semWait(Semaphore s) { while(TestAndSet(&lock)); s.value--; if (s.value < 0) { add process to s.queue *lock = FALSE; block; } else *lock = FALSE; }
SEM_SIGNAL - Producer 7 Mutual Exclusion (12) void semSignalBinary(Semaphore* semaphore) { semaphore->state = 1; tid = deQ(semaphore->queue, -1); if (tid < 0) return; semaphore->state = 0; tcb[tid].state = S_READY; enQ(rq, tid, tcb[tid].priority); return; } // end semSignalBinary // signal binary semaphore // produce binary semaphore // dequeue blocked task // if empty, return // blocked task consumes semaphore // ready task for execution // move task to ready queue Produce Consume void semSignalCounting(Semaphore* semaphore) // signal counting semaphore { if (++semaphore->state > 0) return; tid = deQ(semaphore->queue, -1); tcb[tid].state = S_READY; enQ(rq, tid, tcb[tid].priority); return; } // end semSignalCounting Produce & Consume // return if nothing in queue // dequeue task // ready task for execution // move task to ready queue
SEM_WAIT - Consumer 8 Mutual Exclusion (12) void semWaitBinary(Semaphore* semaphore) { if (semaphore->state == 0) { tcb[curTask].state = S_BLOCKED; enQ(semaphore->queue, deQ(rq, curTask)); // move from ready to blocked queue swapTask(); } semaphore->state = 0; return; } // end semWaitBinary // wait binary semaphore // signaled? // n, change task state to blocked // reschedule the tasks // consume semaphore // return w/no block Consume void semWaitCounting(Semaphore* semaphore) { semaphore->state--; if (semaphore->state < 0) { tcb[curTask].state = S_BLOCKED; enQ(semaphore->queue, deQ(rq, curTask)); // move from ready to blocked queue swapTask(); } return; } // end semWaitCounting // wait counting semaphore // consume // change task state to blocked // reschedule the tasks // return w/semaphore
Step 3: 5-State Scheduling 9 Mutual Exclusion (12) Add priority queue to semaphore struct: typedef struct semaphore { struct semaphore* semLink; char* name; int state; int type; int taskNum; PQueue q; } Semaphore; // semaphore // link to next semaphore // semaphore name (malloc) // state (count) // type (binary/counting) // tid of creator // blocked queue Malloc semaphore queue in createSemaphore: semaphore->q = (int*)malloc((MAX_TASKS + 1) * sizeof(int)); semaphore->q[0] = 0; // init queue semWait: deQueue current task from ready queue and enQueue in semaphore block queue. semSignal: deQueue task from semaphore block queue and enQueue in ready queue.
5-State Scheduler 10 Mutual Exclusion (12) #define SWAP swapTask(); #define SEM_WAIT(s) semWait(s); #define SEM_SIGNAL(s) semSignal(s); #define SEM_TRYLOCK(s) semTryLock(s); dispatch() Ready Queue New Running Exit createTask() killTask() swapTask() Blocked Queues
Task Scheduling 11 Mutual Exclusion (12) Scheduler / Dispatcher Executing Ready Priority Queue SWAP SEM_SIGNAL SEM_WAIT Semaphore Priority Queue SEM_SIGNAL SEM_WAIT Semaphore Priority Queue SEM_SIGNAL SEM_WAIT Semaphore Priority Queue
Step 4a: Counting Semaphore 12 Mutual Exclusion (12) Add counting functionality to semaphores os345semaphores.c: semSignal, semWait, semTryLock Replace goto temp; Add a 10 second timer (tics10sec) counting semaphore to the polling routine (os345interrupts.c). #include <time.h> header. Call the C function time(time_t *timer). semSignal the tics10sec semaphore every 10 seconds. Create a reentrant high priority timing task that blocks (SEM_WAIT) on the 10 second timer semaphore (tics10sec). when activated, outputs a message with the current task number and time and then blocks again.
Task Control Block (tcb) 13 Mutual Exclusion (12) State = { NEW, READY, RUNNING, BLOCKED, EXIT } Priority = { LOW, MED, HIGH, VERY_HIGH, HIGHEST } // task control block typedef struct { char* name; int (*task)(int,char**); int state; int priority; int argc; char** argv; int signal; // task signals (P1) // void (*sigContHandler)(void); void (*sigIntHandler)(void); // void (*sigKillHandler)(void); // void (*sigTermHandler)(void); // void (*sigTstpHandler)(void); TID parent; int RPT; int cdir; Semaphore *event; void* stack; jmp_buf context; } TCB; // task control block // task name // task address // task state (P2) // task priority (P2) // task argument count (P1) // task argument pointers (P1) // task mySIGCONT handler // task mySIGINT handler // task mySIGKILL handler // task mySIGTERM handler // task mySIGTSTP handler // task parent // task root page table (P4) // task directory (P6) // blocked task semaphore (P2) // task stack (P1) // task context pointer (P1) Pending semaphore when blocked.
Step 4: List Tasks 14 Mutual Exclusion (12) Modify the list tasks command to Display all tasks in all system queues in execution/priority order List task name, if the task is ready, paused, executing, or blocked, and the task priority. If the task is blocked, list the reason for the block. Use the project2 command to schedule timer tasks 1 through 9, two signal tasks and two ImAlive tasks. Round Robin: tics10sec task outputs current time every 10 seconds in round robin order. Blocking: The low priority ImAlive tasks will periodically say hello. Prememption: The high priority Signal tasks respond immediately when signaled. # 0 Task Name CLI w/pseudo-input interrupts TenSeconds sTask1 sTask2 ImAlive ImAlive Priority 5 10 20 20 1 1 Time slice 1 1 1 1 1 1 Blocking Semaphore inBufferReady 1-9 10 11 12 13 tics10sec sTask10 sTask11 None None
Bounded Buffer Solution 15 Mutual Exclusion (12) Shared semaphore: empty = n, full = 0, mutex = 1; repeat produce an item in nextp repeat wait(full); wait(mutex); wait(empty); wait(mutex); remove an item from buffer place it in nextc add nextp to the buffer signal(mutex); signal(empty); signal(mutex); signal(full); consume the item in nextc until false until false
Readers and Writers Problem 16 Mutual Exclusion (12) Data object is shared (file, memory, registers) many processes that only read data (readers) many processes that only write data (writers) Conditions needing to be satisfied: many can read at the same time (patron of library) only one writer at a time (librarian) no one allowed to read while someone is writing Different from producer/consumer (general case with mutual exclusion of critical section) possible for more efficient solution if only writers write and readers read. Solutions result in reader or writer priority
Shared Data 17 Mutual Exclusion (12) What are some characteristics of shared data objects (files, data bases, critical code)? Many processes only need mutual exclusion of critical sections (producer/consumer, mutexes) many processes only read data (readers) many processes only write data (writers) What conditions / advantages / problems arise when there is concurrent reading and writing? many can read at the same time (patrons of library) only one writer at a time (librarians) no one allowed to read while someone is writing possible for more efficient solution than producer / consumer if only writers write and readers read. Who should have priority, readers or writers?
Readers/Writers 18 Mutual Exclusion (12) Semaphore rmutex=1, wmutex = 1; integer readcount = 0; Only one writer at a time The first reader makes sure no one can write while(true) { wait(wmutex); <write to the data object> signal(wmutex); }; while(true) { wait(rmutex); readcount++; if (readcount == 1) wait(wmutex); signal(rmutex); <read the data> wait(rmutex); readcount--; if (readcount == 0) signal(wmutex); signal(rmutex); }; Writer Who has priority Reader or Writer? (writers subject to starvation!) Readers have priority! Last one out allows writing again Reader More than one reader at a time
Writers/Readers 19 Mutual Exclusion (12) Semaphore outerQ, rsem, rmutex, wmutex, wsem = 1; while(true) { wait(outerQ); wait(rsem); wait(rmutex); readcnt++ if (readcnt == 1) wait(wsem); signal(rmutex); signal(rsem); signal(outerQ); while(true) { wait(wmutex); writecnt++; if (writecnt == 1) wait(rsem); signal(wmutex); wait(wsem); Additional readers queue here allowing writers to jump ahead of the readers 6 Once a writer wants to write no new readers allowed 3 WRITE Disable writers 1 Wait here until all readers done, as well as multiple writers 4 signal(wsem); wait(wmutex); writecnt--; if (writecnt == 0) signal(rsem); signal(wmutex); }; READ wait(rmutex); readcnt--; if(readcnt == 0) signal(wsem); signal(rmutex); }; 5 Last reader out allows writers 2 Last writer out allows readers
Barbershop Problem 20 Mutual Exclusion (12) 3 barbers, each with a barber chair Haircuts vary in time Barber chairs Sofa can hold 4 customers Cashier Entrance Maximum of 20 in shop Customers arrive randomly Customers wait outside if necessary Exit Standing room area Sofa When a chair is empty: Customer sitting longest on sofa is served Customer standing the longest sits down After haircut, customer pays cashier at cash register Barbers have to cut hair and cashier Customer waits for receipt Upon exit, new customer allowed in shop
Fair Barbershop 21 Mutual Exclusion (12) procedure barber; var b_cust: integer begin repeat // get customer wait( cust_ready ); wait( mutex2 ); dequeue1( b_cust ); signal( mutex2 ); wait( coord ); // cut hair signal( coord ); signal( finished[b_cust] ); wait( leave_b_chair ); signal( barber_chair ); forever end; procedure customer; var custnr: integer; begin wait ( max_capacity ); // enter_shop wait( mutex1 ); count := count + 1; custnr := count; signal( mutex1 ); wait( sofa ); // sit on sofa wait( barber_chair ); // get up from sofa signal( sofa ); // sit in barber chair wait( mutex2 ); enqueue1( custnr ); signal( cust_ready ); signal( mutex2 ); wait( finished[custnr] ); // leave barber chair signal( leave_b_chair ); // pay signal( payment ); wait( receipt ); // exit shop signal( max_capacity ); end; Barber chairs Cashier Entrance Exit Standing room area Sofa max_capacity: semaphore (:=20); sofa: semaphore (:=4); barber_chair, coord: semaphore (:=3); mutex1, mutex2: semaphore (:=1); cust_ready, leave_b_chair: semaphore (:=0) payment, receipt: semaphore (:=0) finished: array [1..50] of semaphore (:=0); count: integer; procedure cashier; begin repeat wait( payment ); wait( coord ); // accept payment signal( coord ); signal( receipt ); forever end;
Lab 03: Jurassic Park 22 Mutual Exclusion (12) When the touring car is filled with visitors and a driver is obtained, the car enters Jurassic Park and runs a guided tour through the park. Visitors try to enter the Jurassic Park at random times. (Only a set number of visitors may be in the park at any one time OSHA requirements!) Upon being allowed in the park, a visitor must get in line to purchase a ticket. When the tour car pulls into the unloading station, the visitors exit the tour car. and the driver goes to sleep awaiting new duties. The tour car pulls forward to be loaded again. After visiting the museum, the visitor gets in the tour car line to wait until permitted to board a tour car. (As a visitor boards a tour car, he returns his ticket.) After successfully obtaining a ticket from a driver, the visitor gets in the museum line and visits the museum. (A limited number of visitors are allowed in the museum as well as the gift shop.) After the visitors exit a tour car, they get into the gift shop line until they can visit the gift shop. After visiting the gift shop, the visitors exit the park.
Jurassic Park 23 Mutual Exclusion (12) procedure car; var carID: integer begin repeat // fill 3 car seats for (NUM_SEATS) { wait ( fillSeat[carID] ); signal ( need_visitor ); wait ( visitor_ready ); save_Visitor( visitorID ); signal ( seatFilled[carID] ); } pass_to_park( carDone ); signal ( carReady ); // enjoy ride wait ( carDone ); signal ( each visitorID ); forever end; max_capacity: semaphore (:=20); parkMutex, requestTicketMutex: semaphore (:=1); needTicket, waitTicket: semaphore (:=0) procedure visitor; var visitor_id: integer; begin wait ( max_capacity ); // enter_park wait ( parkMutex ); numOutsidePark--; numInPark-++; signal ( parkMutex ); // get a ticket wait ( requestTicketMutex ); signal ( needTicket ); signal ( wakeupDriver ); wait ( takeTicket ); signal ( requestTicketMutex ); procedure driver; var carID: integer begin repeat wait ( wakeupDriver ); if ( trylock ( need_ticket ) ) { signal (takeTicket); } else { signal ( driver_ready ); wait ( ride_over ); { forever end; pass_to_car ( visitor_id ); wait ( ride_over ); // give back ticket // visit gift shop // exit park signal ( max_capacity ); end; // visit museum // get in car line // wait for a seat wait ( need_visitor ); signal ( visitor_ready );
Message Passing 24 Mutual Exclusion (12) Shared memory is useful in a threaded environment Single atomic variables (semaphores, modes) Memory mapping (data structures, messages) Test-and-set (atomic instructions) Fast do not require data movement (reference) Inter-process communication (IPC) used by processes for processes inside the same computer for processes in a distributed system Message passing used by distributed systems (networks) send(destination, message) post(destination, message) receive(source, message)
Synchronization 25 Mutual Exclusion (12) For the sender: it is more natural not to be blocked can send several messages to multiple destinations sender usually expects acknowledgment of message receipt (in case receiver fails) PostMessage() is asynchronous returns immediately SendMessage() is synchronous block until message delivered and processed For the receiver: it is more natural to be blocked after issuing ReceiveMessage() the receiver usually needs the info before proceeding but could be blocked indefinitely if sender process fails before sending reply
Addressing 26 Mutual Exclusion (12) Direct addressing: when a specific process identifier is used for source/destination But what if late binding (ie., a print server)? Indirect addressing (more convenient): messages are sent to a shared mailbox (queue of messages) senders place messages in the mailbox, receivers pick them up A mailbox facilitates message deliveries A mailbox can be private one sender/receiver pair A mailbox can be shared among several senders and receivers OS may then allow the use of message types (for selection) A mailbox port associates one receiver with multiple senders used for client/server application: the receiver is the server
Port/Mailbox Ownership 27 Mutual Exclusion (12) A port is usually owned and created by the receiving process The port is destroyed when the receiver terminates The OS creates a mailbox on behalf of a process (which becomes the owner) The mailbox is destroyed at the owner s request or when the owner terminates
Monitors 28 Mutual Exclusion (12) A programming-language construct that provides equivalent functionality to that of semaphores ME threads that wait (block) for true conditions. Thread-safe class (wrapped by mutual exclusive conditions) Concurrent Pascal, Pascal-Plus, Modula, Java A monitor is a software module containing: one or more procedures, an initialization sequence, and local data variables Mutex (lock) object and condition variables Condition variable: Container of threads that are waiting on a certain condition. Threads temporarily give up exclusive access in order to wait for some condition to be met. Local variables accessible only by monitor s procedures A process enters the monitor by invoking one of its procedures Only one process can be in the monitor at any one time
Monitor for the P/C problem 29 Mutual Exclusion (12) Monitor boundedbuffer: buffer: array[0..k-1] of items; nextin:=0, nextout:=0, count:=0: integer; notfull, notempty: condition; Make threading system release all locks; sleep until condition is met. Produce(v): if (count = k) cwait(notfull); buffer[nextin] := v; nextin := nextin+1 mod k; count++; csignal(notempty); Signal a consumer thread or all consumer threads that are blocked waiting for non-empty buffer. Consume(v): if (count = 0) cwait(notempty); v := buffer[nextout]; nextout := nextout+1 mod k; count--; csignal(notfull);
Conclusion 30 Mutual Exclusion (12) Semaphores are a powerful tool for enforcing mutual exclusion and to coordinate processes. When wait(S) and signal(S) are scattered among several processes Difficult to understand their effects. Difficult to test. Monitors make classes thread-safe and mutual exclusion more controllable. Usage must be correct in all the processes (everyone has to play by the rules). One bad (or malicious) process can fail the entire collection of processes
