A blocking mutex, which allows up to N simultaneous locks. (We can find it in Java standard library!)
Let's consider the case of a 1G network interface. Suppose there are 5 zillion threads in total and each thread tries to access to the server. It's impossible for the server to satisfy every request from each thread right now. As a result, we need semaphore to manage the network traffic, and at most N lucky threads get the permission.
Suppose we have N initial slots. Here is the simple implement of Semaphore:
While (# of slots == 0)
Continue;
Run the thread;
# of slots --;
If we have N =1, then we have a standard blocking mutex (also called binary semaphore).
The Data Structure:
Struct sema {
int slots;
process_t * waiting;
lock_t l ; // spin lock
}
Two Operation Invented by Dijkstra (The "ijk" guy)
Example on implment P and V:
function V(semaphore S):
Atomically increment S
S = S + 1;
function P(semaphore S):
repeat:
Between repetitions of the loop other processes may operate on the semaphore
if S > 0:
Atomically decrement S - note that S cannot become negative
S = S - 1;
break;
1 struct pipe{
2 bmutext_t m;
3 char buff[N];
4 size_t r, w;
5 }
6
7 void writeC ( struct pipe *p , char c){
8 for (;;){
9 acquire ( &p -> m); // part of scheduling
10 if(&p->w - &p->r != m)
11 break;
12 release(&p->m); // put to sleep
13 }
14 &p->buff[&p->w ++ % N ] = c;
15 release (&p ->m );
16 }
wait_for( &p->m, &p->w - &p->r != N ); // primitive way
Struct Pipe
{
...
condvar_t nonfull, nonempty;
}
Three important User functions:
wait ( condvar_t *c, bmutex_t *b );
// hold precondition, otherwise create error
// release b
// block until some of thread notifies on C
// then reacquire b
// then return
notify( condvar_t *c );
// wake up one of the process
broadcast( condvar_t *c );
// wake up all of the processes
Using the API of condition variable, we can rewrite our writeC():
1 void writeC ( struct pipe *p, char c ) {
2 acquire(&p->m);
3 while (&p->w - &p-> r == N )
4 wait(&p->nonfull, &p->m);
5 &p->buff [&p->w++% N] = c;
6 notify(&p->nonempty);
7 release(&p->m);
8 }
Priority inversion is a problematic scenario in scheduling when a high priority task is indirectly preempted by a medium priority task effectively "inverting" the relative priorities of the two tasks. This violates the priority model that high priority tasks can only be prevented from running by higher priority tasks and briefly by low priority tasks which will quickly complete their use of a resource shared by the high and low priority tasks. You can think it as locks + scheduling priorities, and it feels sort of like a deadlock.
A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing. In other words, nobody waits but no work gets done. A good example is when requests are sending at 100 Gb/s to a bounded buffer of unhandled requests, the CPU can only process the requests at 10 Gb/s. Thus, it will drop 90% of the request through interrupt handler. The problem comes when the buffer is full, and there are still lots of incoming requests to send interrupts to CPU, then the interrupt handler will chew up the CPU, and nothing will be done.
Solution:
Simple Pesudocode:
1 For(;;){
2 Wait for any event e;
3 Act on (e); // even e must be fast, must not wait
4 // If we have a complex action, we need to split it up.
5 // Each sub-action sets up event handler for next.
6 }
Prons and Cons:
+ no lock, no threads, no scheduling =gt; no deadlock, no race condition
- Difficult to extend to excessively complex application code.
There are two types file system: disk and flash.
Two costs when reading random sector on a disk: