In UNIX, it's understood that processes sleep on a particular event (for example, unlocking of a buffer). But, actually processes don't sleep on an event, they sleep on an address. This system has some disadvantages. If there are many processes sleeping on a buffer to become unlocked, then the kernel wakes up all the processes whenever the buffer gets unlocked, even though many of them will go back to sleep after entering the kernel mode.

Another disadvantage is that multiple events can map to a single address. As shown in the figure below:

There are two events 1. awaiting I/O completion and 2. Waiting for a buffer. Many processes are waiting on addr A but some are waiting for the buffer while a process is awaiting I/O completion. On the occurrence of any of these two events, all the processes will be woken up. Even though any one of these two events occurs, all the process will be woken up since they are sleeping on the same address. It would have been better if there was a one-to-one mapping, but practically, such clashes are rare and system performance is not affected.

Algorithms for Sleep and Wakeup

Algorithm for sleep is given below:

/* Algorithm: sleep
* Input: sleep address
* priority
* Output: 1 if a process awakened as a result of a signal that process
catches,
* longjmp if the process is awakened as a result of a signal it does not
catch,
* 0 otherwise
*/

{
    raise processor execution level to block all the interrupts;
    set process state to sleep;
    put process on sleep hash queue, based on sleep address;
    save sleep address in process table slot;
    set process priority level to input priority;
    if (process sleep is not interruptible)
    {
        do context switch;
        // process resumes execution here when it wakes up
        reset processor priority level to allow interrupts as when

        process went to sleep;
        return (0);
    }
    // here, process is interruptible by signals
    if (no signal pending against process)
    {
        do context switch;
        // process resumes execution here when it wakes up
        if (no signal pending against process)
        {
            reset processor priority level to allow interrupts as

            when process went to sleep;
            return (0);
        }
    }
    remove process from sleep hash queue, if still there;
    reset processor priority level to what it was when the process went to sleep;
    if (process sleep priority set to catch signals)
    return 1;
    do longjump algorithm;
}

The kernel raises the processor execution level, it stores the old level so that it can be restored when the process wakes up. The kernel saves the sleep address and sleep priority in the process table.

The algorithm for wakeup is given below:

/* Algorithm: wakeup
* Input: address of sleep
* Output: none
*/
{
    raise process execution level to block all the interrupts;
    find sleep hash queue for sleep address;
    for (every process asleep on sleep address)
    {
        remove process from hash queue;
        mark process as "ready to run";
        put process on scheduler list of processes ready to run;
        clear field in process table entry for sleep address;
        if (process not loaded in memory)
        wake up swapper process (0);
        else if (awakened process is more eligible to run than currently

        running process)

        set scheduler flag;

    }
    restore processor execution level to original level;
}

If a process that is woken up is not loaded in the memory, the kernel wakes up the swapper process to swap the process in memory. Otherwise, if the awakened process is more eligible to run than currently executing the process, the kernel sets a scheduler flag so that it will go through the scheduling algorithm after the process enters the user mode.

Due to wakeup, the process could not be scheduled immediately; it only makes the process eligible to get scheduled.

When events are guaranteed to occur, processes generally sleep on those events. e.g. I/O of a buffer or an inode/buffer to get unlocked. But processes also might sleep on events that are not guaranteed to happen. In such cases, there must be a technique through which processes can wake up and regain control. The kernel can send a signal to such processes and wake them up. A signal can be sent selectively to a process, and as a result, it wakes up and it can recognize that a signal has been received.

If the priority of sleep is above a threshold value, a process will not wake up at the time of receiving a signal but will sleep until the event occurs. But if the priority is below a threshold value, it will wake up immediately on receipt of a signal.

In the case where a signal has arrived when a process enters the sleep algorithm, the process will sleep if the sleep priority is above a threshold value, but if the priority value is below the threshold, it will never sleep and respond to the signal as if it had arrived while it was sleeping. If it had slept, the signal might not arrive later and the process might never wake up.

If a process wakes up (or never sleeps as described above) on the reception of a signal, the process may do a longjmp depending on the event that it had slept on. The kernel does a longjmp if the signal is received, there is no way to complete the system call. For instance, if a process is reading from a terminal and that terminal is switched off, there is no way for read to complete and it should give an error. This holds for all system calls that can be interrupted while they are in sleep. In the algorithm syscall, the kernel saves the previous context using setjmp in anticipation of the need for a later longjmp.

There are conditions where kernel wants to wake up on receipts of a signal but do not want to do a longjmp. The kernel calls the sleep algorithm with a special priority parameter that suppresses execution of the longjmp and causes the sleep algorithm to return the value 1. The reason is to allow the kernel to clear the local data structures. For example, a device driver may allocate private data structures and then sleep at an interruptible priority; if it wakes up because of a signal, it should free the allocated data structures, then longjmp if necessary.