Operating Systems 1

Tutorial 2

1. Distinguish between the terms 'concurrency', 'race condition', 'critical section' and 'mutual exclusion'.

• 'concurrency' is more than one process running simultaneously (or asynchronously)
• a 'race condition' is two or more concurrent process fouling up shared memory by attempting to make non-atomic changes simultaneously. Can also be one process making changes while other(s) attempting to read: more specifically, a race condition is where the result of the operation depends crucially on the exact timings of the concurrent processes.
• a 'critical section' is a region of code within a process which is potentially subject to race conditions---a section of code which makes non-atomic reads or writes to some shared memory.
• 'mutual exclusion' is stopping other critical regions being executed while one process is executing its critical section. (It's a solution to the problem of race conditions.)

2. Process 1 and process 2 share a single integer variable. Process 1 only writes to the variable; process 2 only reads from the variable. Is a race condition possible?

No. Both processes are performing atomic operations. There is no benefit in enforcing mutual exclusion of the operations. It would be different if there were more than one integer variable, and process 1 wanted to write to both of them and process 2 were reading from both---in that case process 1 might be interrupted between the two writes, and process 2 could get an inconsistent view of the data.

(In some cases, reading and writing integers may not be atomic. For example, an 8-bit computer writing a 16-bit integer would write the high and low bytes in two separate operations. So alternative correct answer: yes, a race condition is possible if (and only if) access to the integer variable is not atomic.)

3. One way to achieve mutual exclusion is to disable interrupts. What's wrong with this approach generally? Where might it be used?

What is wrong with this approach? Interrupts are essential; part of the beating heart of the software and hardware. (a) If they are disabled for too long, the system will fail to respond to hardware events, and task switching will not operate. More prosaically, (b) disabling interrupts is not a viable way to enforce mutual exclusion with more than one processor in the system (since the other processor is not prevented from running other processes). Also, (c) user code is not (or should not) be allowed to disable interrupts.

Disabling interrupts is a reasonable solution to mutual exclusion (a) for short sections of code, (b) on uniprocessor systems, (c) by the operating system itself.

4. Show that the following piece of code will not protect the critical section:

door = OPEN;
...

enterCriticalSection:
    while(door == CLOSED) /* busywait */;
    door = CLOSED;

/* Perform critical task. */

leaveCriticalSection:
    door = OPEN;
 
 

Follow carefully. If a second process runs just after the first has passed the while, but just before it has executed "door = CLOSED", the second process cannot know that the door is about to be shut; both processes will 'shut that door', and both processes enter the critical section together, with disastrous consequences.

How could you make it work, with a little help from the hardware?

The special hardware 'test and set' instruction may be used; it checks the value of a lock variable, and then sets it, as a single, indivisible act. To use it, the code should keep performing the test-and-set in a (busywaiting) loop, until it finds that the lock variable had been zero. When it leaves its critical region, it should itself set the lock variable to zero.

5. Show how you could use a semaphore to enforce mutual exclusion within a critical section.

Easy this one. Define a single binary semaphore, shared by the processes:

Semaphore mutualExclusion = new Semaphore(1);

Before the critical section, WAIT on the semaphore; afterwords SIGNAL on the semaphore:

mutualExclusion.wait();
// Nasty non-atomic access to shared variables.
mutualExclusion.signal();

6. What are the main differences between the low-level mutual exclusion primitives we have looked at, and the higher-level IPC (interprocess communication) mechanisms?

• disabling interrupts, test-and-set and other software solutions (Peterson's solution) are antisocial to other processes (disabling interrupts or busywaiting). The lower-level primitives are only (should only be) used by the operating system itself.
• higher-level primitives block when they cannot enter their critical section, and don't affect other, unrelated tasks when they are in their critical sections.

7. If a piece of code executes a WAIT operation on a semaphore, is it necessarily blocked? Explain.

No. It is blocked only if the semaphore's counter had a value of 0. Otherwise the counter is decremented at once, and the code does not block.

8. Three threads are blocked, all WAITing on the same semaphore. Another thread performs a SIGNAL on the semaphore. What happens?

One of the threads is allowed to run again, and complete the WAIT (i.e. to decrement the semaphore's counter). The other two threads remain blocked. (The definition of a semaphore says nothing about the order in which processes are awoken---it need not be the first of the three processes which WAITed on the semaphore.)

9. Under what circumstances may a semaphore's counter acquire a negative value?

Trick question. It can't.

10. Show code for two processes which use two binary semaphores, in which deadlock may occur.

    Semaphore // Two binary semaphores.     x = new Semaphore(1),     y = new Semaphore(1);
    process 1	process 2
    x.wait(); // I want x first, then y. y.wait(); // Critical section 1. y.signal(); x.signal();	y.wait(); // I acquire y first, then x. x.wait(); // Critical section 2. x.signal(); y.signal();

11. How might a message-passing system be implemented, making use of semaphores and shared memory? (Briefly!)

Define a message-port data structure, containing a queue for the messages, one semaphore for mutual exclusion (for access to the message queue), and one semaphore used to wait for messages.

public class MessagePort {
    Queue messages;
    Semaphore messageArrival = new Semaphore(0);
    Semaphore mutualExclusion = new Semaphore(1);
}

To receive a message from the port, WAIT on the 'messageArrival' semaphore, then remove a message from the queue (enforcing mutual exclusion with the binary semaphore).

To send a message to the port, add a message to the queue (protected by the 'mutualExclusion' semaphore), then SIGNAL the 'messageArrival' semaphore.

('messageArrival' semaphore effectively counts number of messages in the queue, causing receiving process to block if it attempts to RECEIVE when there are no messages.)

12. How might a message-passing system be implemented, making use only of pipes? Assume that there is only one process sending messages to the port, and only one process receiving messages from the port.

    Send the messages down the pipe. (Requires some mechanism by which the sender can obtain the writing end of the pipe, but that's an implementation detail.)

    The sender could write a message by first writing a 'length' field to the pipe, followed by all the bytes of a message (header then data).

    The RECEIVE call would read the length of the message, then allocate a block of memory for the message, and read all of length bytes into the memory. It could then return the block of memory to the user code which called it.

    Note that the RECEIVE call blocks automatically, by virtue of the fact that READing from an empty pipe blocks anyway. Also, messages are queued in the correct order by the buffer in the pipe.

    (The restriction of one writer and one reader is required because there are potential race conditions if more than one writer is writing or more than one reader is reading concurrently. Could be solved by adding in two semaphores; one to ensure mutual exclusion at the reading end, the other for mutual exclusion at the writing end.)