Module 3: Semaphores & Mutex Flashcards
Locks and keys
- Lock blocks other threads from accessing a resource
- Only one thread has access to it
- Other threads need to wait
Busy waiting / spinning
- Sync technique
- Thread waits for a resource to become available =>Spins in a loop.
- Repeatedly cheks for a condition to be true
- Wastes CPU cycles = less efficient than semaphores/mutex
Semaphore type
- Counter, but not an int
- Keeps track of how many of a resource are available at a given time
- When thread wants semaphore: counter value decreases–
- Value is negative = threads must wait til 0 or positive
- Thread releases semaphore = value increases++
Structure of Semaphores
- Variable that controls access to common resources by multiple threads
- Avoids critical section problems
- Allows / disallows access to resource (depends on availability of the resource)
- Thread waiting => signaled by other thread releasing the resource
Semaphore Attribute: Value (int)
- int
- accessed thru methods P and V
- identifies how many threads are in CS at same time
- change during execution to see how many threads from blocked queue can enter CS
Semaphore Attribute: Queue
- each semaphore has associated queue of blocked threads
- not accessible for programmer
Semaphore Method: Initialize
- nr of available units of a resource, s
- Initialize(4) => 4 threads can enter CS at the same time
Semaphore Method: P (or Wait, down)
- called by thread that wants to enter CS
- (s–) semaphore value down
- s = 0, thread blocks (enters queue) until s > 0
- s < 0, thread waits (no more resources)
Semaphore Method: V (or Signal, up)
- called by thread to exit CS
- increment value (s++)
- if threads blocked for the semaphore = thread unblocks
P and V in C#
- P = WaitOne
- V = Release
P as a method
- semaphore calls P() atomically
- > 0, decrease by 1
- else, thread blocks self (waiting for resource)
- signals OS that a thread needs a resource. If not available = wait.
semProducer.WaitOne(); called in method Produce
V as a method
- semaphore calls v() atomically
- increment by 1 (no blocking)
- signals Os that a resource is free for other threads
semProducer.Release(); called in method Consume
Creating a Semaphore
Semaphore semProducer; // counts empty slots to write
Semaphore semConsumer; //counts full slots to read & remove
semProducer = new Semaphore(bufferSize, bufferSize) //initial & max units
Semaphore signal history
- no thread is waiting = signal is remembered when P is called next time
- semaphore remembers which thread released the resource
- sema = not owned by a thread. One thread can call P & another V of the same sema.
- sema = object, but doesn’t follow OOP. Any thread can call P and V on another thread.
Use of semaphores
- Sync access to shared resource (esp useful when of the same type)
- For each type fo shared resources, a seperate semaphore can be used
- Ex: one guards writers, one guards readers
Semaphores in CS
Non-critical code
Get Semaphore obj - Wait
Critical code
Release Semaphore obj - Signal
Non-critical code
Several semaphores in a code block
- Several sema can exist in an execution. Associate thread with correct semaphore when calling P/V
- Sema A = empty slots in a bounded buffer
- Sema B = filled slots in a bounded buffer
- Mutexes used to give access to section of code that can’t be executed concurrently by more than one thread
Unblocking and blocking with VP
- one or more threads waiting in queue, one is unblocked
- thread is placed in the ready queue to start execution
- which thread that becomes unblocked depends on thread’s priority & CPU scheduling
What are Counting semaphores good for?
- resource with many units available or when many threads are allowed to access the resource (eg for reading)
- nr of threads allowed to access units it determined by the count
- provied aquire mechanism = ensure only n threads can access certain resource at a time
What are binary semaphores good for?
- only 2 values
- 0 (wait)
- 1 (signal)
- only one thread can access a resource
- states are mostly lock-unlock
How do Counting semaphores work?
- 0 (no permit, no waiting)
- > n (n permits available)
- < n (n threads are waiting)
- Sema is created with initial nr of permits, n.
*n is not a max value. Can increment after initialization.
How do Binary semaphores work?
- used for mutual exclusion (ME)
- restricted values of 0 and 1. P only works when sema = 1, and V when = 0.
Semaphore sem = new Semaphore(1)
sem -> P()
// CS
sem -> V()
But – any thread can use the methods. Recommended to use locks when locking critical sections.
What is a Mutex?
- Locking mechanism
- Short for Mutual Exclusion
- Object that gives single access to shared resource
- Guarantees mutual exclusion
- count = 1
- Only 1 thread can aquire a mutex at a time. Ownership. (Only the owner can release the mutex)
Mutex vs Lock
- Mutex is a lock, but it can be shared by different threads unlike the Lock (tho lockable objects can be)
- Readers & Writers can share the same Mutex to access a buffer
- Mutex can be used for condition sync – Lock can’t!
Mutex vs Binary Semaphore
- Mutex NOT binary semaphore
- Mutex
- Locking mechanism used to sync access to resource
- Only 1 thread owns a mutex at a time, and only the owner can release it
- Purpose of mutex is to provide mutual exclusion
Binary Semaphore
* Signaling mechanism
* Two values (locked, unlocked)
* Not associated with ownership. Sema can be released by other threads too.
* Threads can increment or decrement value of semaphore
Producer-Consumer with semaphore
- 2 semaphores & 1 mutex
- emptySlots for producer
- fullSlots for consumers
- sharedMutex that gives exclusive access to the buffer
Writer-Reader with semaphore
- writers & readers should never access the shared resource at the same time
- multiple readers OK, only 1 writer
- when writer:
- first reader blocks writers
- all other readers block on mutex
- last reader signals waiting writer when exiting
- no writer = readers continue
Rule of thumb for Semaphores
- Use a seperate semaphore for each constraint
- Thread shouldn’t write/produce when buffer’s full
- Thread shouldn’t read/consume when buffer’s empty
- No 2 threads should access an element in the buffer simultaneously
Semaphore mutex
//mutual exclusion on particular element if buffer is an array/list
Semaphore fullBuffer
//nr of elements with data
Semaphore emptyBuffer
//nr of vacant elements
Semaphore Advantages
- Sync a CS for access by 1 or more threads
- Binary sem can be used for ME
- Can permit more than 1 thread in the CS
- Use CPU more efficiently. Threads are queued & proceed as resource is available rather than wasting time spinning.
Semaphore Disadvantages
- Don’t follow OOP (badly structured)
- Hard to develop / maintain / make readable
- Programmer must have good control over P() & V()
- Thread can call P & V repeatedly
- Must ensure P & V are in correct order
- Waiting for condition is independent of ME
- Any thread can call P & V on another thread
Alternatives to Semaphores?
- Use language support (C# Semaphore Class)
- Monitors
Bounded/Circular Buffer definition
Data structure that acts as a buffer in memory with fixed nr of slots/entries
What is a bounded buffer used for?
- used as a shared object/resource
- fixed size allows limitation of data to be stored at a given time
What is a semaphore used for in a bounded buffer?
Used to control access to the buffer. Tracks the number of available slots.
How to insert & remove positions in a buffer
- 2 variables, ex inPos & outPos
- inPos = position where next item should be inserted. New item queued = variable incremented +1. If it exceeds max size => restarts.
- outPos = same but with dequeing item
inPos and outPos formulas
inPos = (inPos + 1) % n
OutPos = (outPos + 1) % n
where n = buffer size
Producer-Consumer constraints EX
- Only 1 producer at a time
- Not a producer & consumer at the same time. Producer should block all waiting consumers & all other producers
Real world example of a shared buffer
Audio-Video player sharing a buffer, network and display threads
Behavior of a bounded buffer
- A producer tries to put in data
- A consumer tries to remove data
- Problem: Buffer is full, or empty.
- Need to synchronize: Either wait and go to sleep or discard data if the buffer is full ( & vice versa)
- Item consumed => consumer notifies producer to start filling buffer again.
How to sync buffer bound problem?
- Inter-thread communication is required
- Combination of semaphores & monitors
- BUT; both threads awakened = deadlock
Avoiding deadlock in a bounded buffer
- Producer always signals after producing (even if 0 waiting consumer threads)
- Consumer always signals after consuming (even if 0 waiting producer threads)
- Buffer empty = consumer wait for item to be added
- Buffer full = producer wait for consumer to take
Why have a mutex in buffer bound problem?
- Ensures that only 1 producer changes the shared data & only 1 consumer changes the consumer values at a time
- Ensures mutual exclusion
Why need semaphores when we already have locks?
- EX Mutex: only 1 external thread can access our application code at any given point in time
- Semaphore: more control over the number of external threads that can access our application code
Why use Mutex if we have locks/monitors?
- Mutex ensures thread safety for threads generated by external applications (external threads)
- EX: Launching a game. Clicking it several times. Maybe don’t want several instances of it open => only one external thread allowed to run it.
