Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Flertrådad programmering > Module 3: Semaphores & Mutex > Flashcards

Module 3: Semaphores & Mutex Flashcards

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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++
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Semaphore Attribute: Queue

A
  • each semaphore has associated queue of blocked threads
  • not accessible for programmer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

P and V in C#

A
  • P = WaitOne
  • V = Release
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Semaphores in CS

A

Non-critical code
Get Semaphore obj - Wait
Critical code
Release Semaphore obj - Signal
Non-critical code

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
Q

Mutex vs Binary Semaphore

A
  • 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
Q

Producer-Consumer with semaphore

A
  • 2 semaphores & 1 mutex
  • emptySlots for producer
  • fullSlots for consumers
  • sharedMutex that gives exclusive access to the buffer
27
Q

Writer-Reader with semaphore

A
  • 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
Q

Rule of thumb for Semaphores

A
  • 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
Q

Semaphore Advantages

A
  • 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
Q

Semaphore Disadvantages

A
  • 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
Q

Alternatives to Semaphores?

A
  • Use language support (C# Semaphore Class)
  • Monitors
32
Q

Bounded/Circular Buffer definition

A

Data structure that acts as a buffer in memory with fixed nr of slots/entries

33
Q

What is a bounded buffer used for?

A
  • used as a shared object/resource
  • fixed size allows limitation of data to be stored at a given time
34
Q

What is a semaphore used for in a bounded buffer?

A

Used to control access to the buffer. Tracks the number of available slots.

35
Q

How to insert & remove positions in a buffer

A
  • 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
Q

inPos and outPos formulas

A

inPos = (inPos + 1) % n
OutPos = (outPos + 1) % n

where n = buffer size

37
Q

Producer-Consumer constraints EX

A
  • Only 1 producer at a time
  • Not a producer & consumer at the same time. Producer should block all waiting consumers & all other producers
38
Q

Real world example of a shared buffer

A

Audio-Video player sharing a buffer, network and display threads

39
Q

Behavior of a bounded buffer

A
  • 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
Q

How to sync buffer bound problem?

A
  • Inter-thread communication is required
  • Combination of semaphores & monitors
  • BUT; both threads awakened = deadlock
41
Q

Avoiding deadlock in a bounded buffer

A
  • 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
Q

Why have a mutex in buffer bound problem?

A
  • Ensures that only 1 producer changes the shared data & only 1 consumer changes the consumer values at a time
  • Ensures mutual exclusion
43
Q

Why need semaphores when we already have locks?

A
  • 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
Q

Why use Mutex if we have locks/monitors?

A
  • 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.

Flertrådad programmering (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions