1
Q
Locks and keys
A
- Lock blocks other threads from accessing a resource
- Only one thread has access to it
- Other threads need to wait
2
Q
Busy waiting / spinning
A
- 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
3
Q
Semaphore type
A
- 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++
4
Q
Structure of Semaphores
A
- 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
5
Q
Semaphore Attribute: Value (int)
A
- 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
6
Q
Semaphore Attribute: Queue
A
- each semaphore has associated queue of blocked threads
- not accessible for programmer
7
Q
Semaphore Method: Initialize
A
- nr of available units of a resource, s
- Initialize(4) => 4 threads can enter CS at the same time
8
Q
Semaphore Method: P (or Wait, down)
A
- 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)
9
Q
Semaphore Method: V (or Signal, up)
A
- called by thread to exit CS
- increment value (s++)
- if threads blocked for the semaphore = thread unblocks
10
Q
P and V in C#
A
- P = WaitOne
- V = Release
11
Q
P as a method
A
- 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
12
Q
V as a method
A
- 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
13
Q
Creating a Semaphore
A
Semaphore semProducer; // counts empty slots to write
Semaphore semConsumer; //counts full slots to read & remove
semProducer = new Semaphore(bufferSize, bufferSize) //initial & max units
14
Q
Semaphore signal history
A
- 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.
15
Q
Use of semaphores
A
- 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
16
Q
Semaphores in CS
A
Non-critical code
Get Semaphore obj - Wait
Critical code
Release Semaphore obj - Signal
Non-critical code
17
Q
Several semaphores in a code block
A
- 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
18
Q
Unblocking and blocking with VP
A
- 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
19
Q
What are Counting semaphores good for?
A
- 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
20
Q
What are binary semaphores good for?
A
- only 2 values
- 0 (wait)
- 1 (signal)
- only one thread can access a resource
- states are mostly lock-unlock
21
Q
How do Counting semaphores work?
A
- 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.
22
Q
How do Binary semaphores work?
A
- 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.
23
Q
What is a Mutex?
A
- 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)
24
Q
Mutex vs Lock
A
- 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!
25
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
26
Producer-Consumer with semaphore
- 2 semaphores & 1 mutex
- emptySlots for producer
- fullSlots for consumers
- sharedMutex that gives exclusive access to the buffer
27
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
28
Rule of thumb for Semaphores
- Use a seperate semaphore for each constraint
1. Thread shouldn't write/produce when buffer's full
2. Thread shouldn't read/consume when buffer's empty
3. 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
29
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.
30
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
31
Alternatives to Semaphores?
- Use language support (C# Semaphore Class)
- Monitors
32
Bounded/Circular Buffer definition
Data structure that acts as a buffer in memory with fixed nr of slots/entries
33
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
34
What is a semaphore used for in a bounded buffer?
Used to control access to the buffer. Tracks the number of available slots.
35
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
36
inPos and outPos formulas
inPos = (inPos + 1) % n
OutPos = (outPos + 1) % n
where n = buffer size
37
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
38
Real world example of a shared buffer
Audio-Video player sharing a buffer, network and display threads
39
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.
40
How to sync buffer bound problem?
- Inter-thread communication is required
- Combination of semaphores & monitors
- BUT; both threads awakened = deadlock
41
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
42
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
43
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
44
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.
