semaphores

Question 1

what does semaphores do

Answer 1

Synchronisation too
Simplifies synchronisation for the programmer
Does not require (much) busy waiting: We don’t busy-wait for the critical section, usually only to achieve atomicity to check
if we need to sleep or not, etc.
Can guarantee bounded waiting time and progress

Question 2

what do semahpres consist of

Answer 2

A semaphore type S, that records a list of waiting processes and an integer
Two standard atomic (← very important) operations by which to modify S: wait() and signal()
Originally called P() and V() based on the equivalent Dutch words

Question 3

what does semaphore type S do

Answer 3

records a list of waiting processes and an integer

Question 4

what are the sutch equivalent to wait() and signal()

Answer 4

P() and V()

Question 5

how does semaphores work?

Answer 5

the semaphore is initialised with a count value of the
maximum number of processes allowed in the critical section
at the same time.
When a process calls wait(), if count is zero, it adds itself to
the list of sleepers and blocks, else it decrements count and
enters the critical section
When a process exits the critical section it calls signal(),
which increments count and issues a wakeup call to the
process at the head of the list, if there is such a process
It is the use of ordered wake-ups (e.g. FIFO) that makes
semaphores support bounded (i.e. fair) waiting.

Question 6

what are the 2 types of semaphores

Answer 6

binary semaphores
counting semaphores

Question 7

what is a counting semaphore

Answer 7

integer value can range over an
unrestricted domain (e.g. allow at most N threads to read a
database, etc.)

Question 8

what is a binary semaphore

Answer 8

integer value can range only between 0 and 1
Also known as mutex locks, since ensure mutual exclusion.
Basically, it is a counting semaphore initialised to 1

Question 9

what else are binary semaphores known as and why

Answer 9

Also known as mutex locks, since ensure mutual exclusion

Question 11

how can you implemey semaphore in a kernel using state and wait
(code)

Answer 11

typedef struct {
int count;
process_list; // Hold a list of waiting processes/threads
} Semaphore;
void wait(Semaphore *S) {
S->count–;
if (S->count < 0) {
add process to S->process_list;
sleep();
}
}

Question 12

in our state and wait implementation we decrement the wait counter, why?

Answer 12

this does not alter functionality but has the useful side-effect that the negative count value reveals
how many processes are
currently blocked on the semaphore.

Question 13

code for signal semaphore implementation

Answer 13

void signal(Semaphore *S) {
S->count++;
if (S->count <= 0) { // If at least one waiting process, let him in.
remove next process, P, from S->process_list
wakeup(P);
}
}

Question 15

what is deadlock

Answer 15

Two or more processes are waiting indefinitely for
an event that can be caused by only one of the waiting
processes

Question 16

what is priority inversion

Answer 16

Scheduling problem when lower-priority
process holds a lock needed by higher-priority process

Question 17

what do we have to look out for in semaphores

Answer 17

deadlock
priority inversion

Question 18

what are the 2 problems semaphores face

Answer 18

bounded buffer problem
readers-writers problem

Question 19

describe the bounded buffer problem solution

Answer 19

The solution set-up:
A buffer to hold N items, each can hold one item
Semaphore mutex initialized to the value 1
Semaphore full slots initialized to the value 0
Semaphore empty slots initialized to the value N

Question 20

describe readers-writers problem

Answer 20

A data set is shared among a number of concurrent processes
Readers - only read the data set; they do not perform any updates
Writers - can both read and write
Problem:
Allow multiple readers to read at the same time if there is no writer in there.
Only one writer can access the shared data at the same time