Tutorial Week 12

<li>  
Write an algorithm for implementing a simple binary semaphore using
  a) a hardware SWAP instruction
  b) A hardware Test and Set lock.

Ans: 
A h/w swap interchanges two memory locations as an indivisible operation. So 
you load one location with 1, swap and see what you had in the other location. 
If 0, then the semaphore was free, else in use.
  DOWN(s)
      x=1
      SWAP(x, s)
      if x == 1
          place this process on sleeping queue

  UP(s)
      s=0
      remove a process from sleeping queue and 
            let it run DOWN again.

Ans: 

  DOWN(s)
      if TEST-AND-SET(s, 1) == 1
          place this process on sleeping queue
  UP(s)
       if there is a process on sleeping queue
          remove process from queue
       s=0
       let process run

<li>  
Semaphore waiting lists are often implemented as queues served in FIFO order. 
Could they be implemented as stacks? If so, what problems might it cause?

Ans: 
Yes they can, but it means that a process at the bottom of the stack may suffer 
starvation.

<li>  
If an Operating System can disable interrupts, how can semaphores be implemented?

Ans: 
When a DOWN is attempted, interrupts are switched off. The process can then 
examine a piece of memory to see what its value is, and reset it to another 
value if desired. Interrupts are then switched back on and the proces continues. 
Note that they should only be switched off while the semaphore is being examined/modified. 
If you just tried keeping them off all the time the process executes, then 
effectively only one semaphore is allowed.

<li>  
In an electronic funds transfer system, there are hundreds of processes that 
work as follows: each process reads a line of information specifying an amount 
of money, the account to be debited and the account to be credited. Then it 
locks both accounts and transfers the money, releasing the locks when done. 
Can this deadlock? If so, devise a scheme to avoid deadlock.

Ans: 
Deadlock may occur if A's account is locked to debit it, and then B's account 
is locked. In the meantime, there may be a transfer the other way that results 
in the lock being placed on B first. This can be avoided by either (a) releasing 
all current locks if you can't get the next one, (b) ordering the locks, say 
by account number

<li>  
Suppose a shared queue is implemented using a wrap-around array. One way of 
controlling access to the queue is by a single semaphore that controls access 
to any part of the data structure. This means that it is not possible for one 
process to remove an element from the queue while another one simultaneously 
adds one. Would it be possible to use two or more semaphores to control access 
to each end of the queue independantly? If so, how?

Ans: 
One semaphore can be used to control access to the head of the queue, and another 
to the tail. Conflict may occur when the queue is empty, as both refer to the 
same location, or full. At these extremes both semaphores may need to be held 
at once, and you need to decide on an order eg head first.

Laboratory Week 12

<li>  
When an editor opens a file for editing, it makes a private copy and works 
on that. Multiple editors can be started on a single file, each with their 
own private copy. This can lead to inconsistent states between them. What does 
this mean?

Write a program

safe_edit

that uses a lock file to allow only one process to edit a given file at a time. 
The program should take one argument that is the file name, look for a suitable 
lock file and only execute the editor if the lock is not set.

What should the program do on exit? What happens if it crashes?

Ans: 
A suitable lock file is one based on the file name, eg made from the file name 
appended with ``.lock" This name has to be unique, but can be generated uniquely 
from the filename (or other processes would not be able to find the lock!). 
Attempt to create the file in read-only mode. If it succeeds, you have the 
lock. If it fails, you don't. Remove the lock file on exit. You will have to 
trap interrupts so that even if the user types ctrl-C you can still remove 
the lock. Your program should never crash of its own accord :-)