Jan Fan     About     Archive     Feed     中文博客

Disk Driver and Lock

How to handle concurrent request from multi-processors to read/write data from/into disk? The Disk Driver maintains a linked list, once a processor make request, append a node to the list.

If efficiency is not important, one can just use unique-processos, or use "giant-kernel-lock" to protect the data.

The choice of lock granularity. The more locks used, the more efficient in general, but more complicated.

No interrupt during the operations in Critical Section. After those operations, the code release the lock, and enable interrupt.

If the Critical Section has to wait for some external device, it usually releases the lock and enables the interrupt after communication with external device, then makes itslef SLEEP and switches to scheduler to other processes. Once the IO operation is done, the external device issues an interrupt, then the interrupt handler set the sleeping process RUNNABLE. Then the process will be waken up by scheduler and get the IO data from external device.

!--more--

processes and processors

To prevent race conditions between processors, the first processor locks the lock, and make the subsequent processors busy waiting when they try to acquire the locked lock.

Things are a bit diff between processes.

When one process is in the Critical Section, the interrupt is disabled, so no other interrupt handlers or processes can run the same time, i.e., it won't switch to them.

So generally the lock is in no use, since no other can run, and try to acquire the lock.

If the process has to wait for the external IO, it can release the lock, enable the interrupts and go to sleep, while the kernel needs to maintains a data structure like QUEUE for the IO device to receive concurrent requests. Then still no use of the lock.

So Those stuff are useful only if we want our processes enter critical region with interrupts enable.

IPC

Approachs: 1. Shared memory 2. Shared file mode 3. Message passing

Processes Synchronization

Race Condition: Critical Resource: Critical Region

Now we talk about Mutual Exclusion

that is, some way of making sure that if one process is using a shared variable or file, the other processes will be excluded from doing the same thing 5 Solutions:

The conclusion is: disabling interrupts is often a useful technique within the operating system itself but is not appropriate as a general mutual exclusion mechanism for user processes.

while (TRUE){
    while (turn != 0) /*loop*/ ;
    critical _region(); 
    turn = 1; 
    noncritical_region();
}

while (TRUE) { 
    while (turn != 1) /*loop*/ ;
    critical_region( ); 
    turn = 0;
    noncritical_ region();
}

No need for Test and Set. Two processes just alternates and set the flag for each other. the Single set is atomic. You can extent this idea to multiple processes like a TOKEN.

But this solution is not a good candidate because even if process A doesn't need to enter critical region, it still blocks process B that wants to enter.

A lock that uses busy waiting is called a spin lock.

Both Peterson's solution and the solutions using TSL or XCHG are correct, but both have the defect of requiring busy waiting.

producer-consumer problem, (also known as the bounded-buffer problem).

#define N 100 
int count = 0;

void producer(void){
int item;
while (TRUE) {
    item = produce_item();
    if (count == N) sleep(); 
    insert_item(item);
    count = count + 1;
    if (count == 1) wakeup(consumer);
}
}

consumer(void){
int item;
while (TRUE) f
    if (count == 0) sleep();
    item = remove_item( );
    count = count  1;
    if (count == N  1) wakeup(producer); 
    consume_item(item);
}
}

Race can occur because access to count is unconstrained. lost-wakeup problem

Samaphore

A semaphore could have the value 0, indicating that no wakeups were saved, or some positive value if one or more wakeups were pending.

Dijkstra proposed having two operations, down and up (generalizations of sleep and wakeup, respectively).

Checking if the value is 0, changing it, and possibly going to sleep, are all done as a single, indivisible atomic action.

three semaphores: * one called full for counting the number of slots that are full, * one called empty for counting the number of slots that are empty, and * one called mutex to make sure the producer and consumer do not access the buffer at the same time.

#define N 100
typedef int semaphore; 
semaphore mutex = 1; 
semaphore empty = N; 
semaphore full = 0;

void producer(void){ 
    int item;
    while (TRUE) {
        item = produce_item( ); 
        down(&empty); 
        down(&mutex); 
        insert_item(item); 
        up(&mutex);
        up(&full);
    }
}

void consumer(void) {
    int item;
    while (TRUE) { 
        down(&full);
        down(&mutex);
        item = remove_item( ); 
        up(&mutex); 
        up(&empty); 
        consume_item(item);
    }
}

Sleep and wait needs to solve two problems:

The Linux kernel’s sleep uses an explicit process queue instead of a wait channel

Semaphores are another common coordination mechanism.

wait and sleep

In a word, when a process exits, it clears all it ZOMBIE children processes, and let init adopt it's alive children process, and finally, mark itself as a ZOMBIE process. Like a tree, processes get cleared upward, and eventually some top processes are cleared up by init process.

What is a ZOMBIE process? A process that has exited, but not been cleared up completely.

When does a process go to sleep? A process goes to sleep when it calls wait() but no children has exited.

When a process calls wait()? Does init process invokes wait() forever? What is the relationships between sleep/wakeup and wait/signal?

kill process, ask the process to call exit()

why we need to kill processes in this way? Make every process killed as the current process, using the some routines to die. Some more things to do with process that is killed, can't make them exit right away.

Comments

comments powered by Disqus