Understanding Producer-Consumer Problem and Semaphores
This content delves into the intricacies of mutual exclusion solutions for producer-consumer problems, focusing on software and hardware solutions. It discusses avoiding busy waiting using sleep and wakeup functions, along with examples and illustrations. The aim is to enhance understanding of semaphores and critical region management in concurrent programming.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lecture 13: Producer-Consumer and Semaphores 1
Review: Mutual Exclusion Solutions Software solution Disabling interrupts Strict alternation Peterson s solution Hardware solution TSL/XCHG Key issue Busy waiting 2
Review: Mitigate Busy Waiting /* set lock to non-zero, proceed if it was 0 earlier */ enter_region: TSL Reg, Lock /* set Lock to 1, copy old value of Lock into Reg*/ If (Reg != 0) then /* not the first to set to zero */ { thread_yield() ; /* let somebody else run */ Jump enter_region /* try again */ } return leave_region: Lock = 0 return 3
In this lecture sleep() and wakeup() Producer-consumer problem Semaphores 4
Avoiding Busy Waiting If a process cannot enter critical region, the process calls sleep() to give up CPU. A process wakes up another process using wakeup() 5
Review: Mutual Exclusion using TSL /* set lock to non-zero, proceed if it was 0 earlier */ enter_region: TSL Reg, Lock /* set Lock to 1, copy old value of Lock into Reg*/ If (Reg != 0) then /* not the first to set to zero */ Jump enter_region /* try again */ return leave_region: Lock = 0 return 6
TSL without busy waiting /* set lock to non-zero, proceed if it was 0 earlier */ enter_region: TSL Reg, Lock /* set Lock to 1, copy old value of Lock into Reg*/ If (Reg != 0) then /* not the first to set to zero */ { sleep() Jump enter_region /* try again */ return leave_region: Lock = 0 wakeup(process_id) return 7
Producer Consumer Problem Producer Consumer Mutual exclusion Buffer Full Buffer Empty 8
How is this solution? #define N 100 int count = 0 No mutual exclusion PRODUCER CONSUMER While (TRUE) { if (count < N){ } } While (TRUE) { if (count > 0){ } } item = produce_item(); insert_item(item); count = count + 1; item = remove_item(); count = count - 1; consume_item(item); 9
Using sleep() and wakeup() #define N 100 int count = 0 PRODUCER CONSUMER While (TRUE) { item = produce_item(); if (count == N) sleep(); insert_item(item); count = count + 1; if (count == 1) wakeup(CONSUMER); } While (TRUE) { if (count == 0) sleep(); item = remove_item(); count = count - 1; if (count == N-1) wakeup(PRODUCER); consume_item(item); } 10
Producer Consumer Problem Need a way to block till some condition is satisfied Semaphores Condition variables 11
Semaphore: Interface S: Integer variable down(&S): when (S > 0) S = S 1; Atomic actions down(&S) block when S =0 up(S) never blocks up(&S): S = S + 1; 12
Semaphore: Implementation down(&S): If (S=0) then Suspend thread, put into a waiting queue Schedule another thread to run Else decrement S and return up(&S): Increment S If any threads in waiting queue, then release one of them (make it ready ) Both the above are done atomically by disabling interrupts by TSL/XCHG 13
Producer Consumer using Semaphores #define N 100 int mutex =1; int empty = N; int full = 0 PRODUCER CONSUMER While (TRUE) { item = produce_item(); down(&empty); down(&mutex); insert_item(item); up(&mutex); up(&full); } While (TRUE) { down(&full); down(&mutex); item = remove_item(); up(&mutex); up(&empty); consume_item(item); } 14
Mutual Exclusion Solutions Software solution Disabling interrupts Strict alternation Peterson s solution Hardware solution TSL/XCHG 15
Mutual Exclusion via Semaphore Initialize Semaphore mutex = 1 lock(&mutex)= down(&mutex) unlock(&mutex)= up(&mutex) 16
Mutual Exclusion via Semaphore lock(&mutex); critical_region(); unlock(&mutex); 17
Example Web Server can handle only 10 threads at a time Multiple points where threads are being created How to ensure no more than 10 active threads? Semaphore with initial value = 10 down() before Thread creation up() once Thread finishes 18
