nix

• A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait and signal.
• A semaphore is an object that consists of a counter, a waiting list of processes and two methods (e.g., functions): signal and wait.

         

• The n processes share a semaphore, mutex (standing for mutual exclusion), initialized to 1.

            7.4.2  Implementation
                     
                     
                     

• After decreasing the counter by 1, if the counter value becomes negative, then
  • add the caller to the waiting list, and then
  • block itself
• After increasing the counter by 1, if the new counter value is not positive, then
  • remove a process P from the waiting list,
  • resume the execution of process P, and return
• If S.count < 0, abs (S.count) is the number of waiting processes (In spinlock situation, the value of S.count always >= 0).
• This is because processes are added to (resp., removed from) the waiting list only if the counter value is < 0 (resp., <= 0)
• The type of semaphore that requires busy waiting is called a spinlock. The advantage of a spinlock is that no context switch is required when a process must wait on a lock.
• To overcome the need for busy waiting, the process can block itself. The block operation places a process into a waiting queue associated with the semaphore, and the state of the process is switched to the waiting state.
• The process is restarted by a wakeup operation, which changes the process from the waiting state to the ready state.
• The block operation suspends the process that invokes it. The wakeup (P) operation resumes the execution of a blocked process P.
• The waiting list can be implemented with a queue if FIFO order is desired.
• However, the correctness of a program should not depend on a particular implementation of the waiting list.
• The caller may be blocked in the call to wait ().
• The caller never blocks in the call to signal (). If S.count > 0, signal () returns and the caller continues. Otherwise, a waiting process is released and the caller continues. In this case, two processes continue.
• wait () and signal () must be executed atomically (i.e., as one uninterruptible unit), no two processes can execute wait () and signal () operations on the same semaphore at the same time.
• Otherwise, race conditions may occur.
• Three typical uses of semaphores
  • Mutual exclusion: Mutex locks, example: Dining Philosophers

                                 

• Count-down lock: keep in mind that semaphores have a counter, example: Dining Philosophers with 5 philosophers and 4 chairs.

                                 

• Notification: Indicate an event has occurred

                                 

• Deadlock: two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes.
• A ser of processes is in a deadlock state when every process in the set is waiting for an event that can be caused only by another process in the set.
• Indefinite blocking, starvation: processes wait indefinitely within the semaphore.

• A binary semaphore / counting semaphore is a semaphore with an integer value that can range only between 0 and 1 / over an unrestricted domain.

            7.5.1  The Bounded-Buffer Problem (Producer/Consumer Problem)
                     

• Suppose we have a circular buffer of n slots.
• Pointers in (resp., out) points to the first empty (resp., filled) slot.
• Producer processes keep adding info into the buffer.
• Consumer processes keep retrieving info from the buffer.
• A producer deposits info into Buf[in] and a consumer retrieves info from Buf[out].
• in and out must be advanced.
• in is shared among consumers.
• out is shared among producers.
• If Buf is full, producers should be blocked.
• If Buf is empty, consumers should be blocked.

                     

• We need a semaphore to protect the buffer.
• A second semaphore to block producers if the buffer is full.
• A third semaphore to block consumers if the buffer is empty.

                     

• Two groups of processes, readers and writers, are accessing a shared resource by the following rules:
  • Readers can read simultaneously.
  • Only one writer can write at any time.
  • When a writer is writing, no reader can read.
  • If there is any reader reading, all incoming writers must wait. Thus, readers have higher priority.
• We need a semaphore to block readers if a writer is writing.
• When a writer arrives, it must be able to know if there are readers reading. So, a reader count is required which must be protected by a lock.
• This reader-priority version has a problem: bounded waiting condition may be violated if readers keep coming, causing the waiting writers no chance to write.

                     

• When a reader comes in, it increases the count.
• If it is the 1^st reader, waits until no writer is writing.
• Reads data.
• Decreases the counter.
• Notifies the writer that no reader is reading if it is the last.
• When a writer comes in, it waits until no reader is reading and no writer is writing.
• Then, it writes data.
• Finally, notifies readers and writers that no writer is in.

                     

            7.5.3  The Dining-Philosophers Problem
                     

• Five philosophers are in a thinking – eating cycle.
• When a philosopher gets hungry, he sits down, picks up two nearest chopsticks, and eats.
• A philosopher can eat only if he has both chopsticks.
• After eating, he puts down both chopsticks and thinks.
• This cycle continues.

                     

• Chopsticks are shared items (by two philosophers) and must be protected.
• Each chopstick has a semaphore with initial value 1.
• A philosopher calls wait () before picks up a chopstick and calls signal () to release it.
• If all five philosophers sit down and pick up their left chopsticks at the same time, this program has a circular waiting and deadlocks.
• An easy way to remove this deadlock is to introduce a weirdo who picks up his right chopstick first!

                     

• If only four philosophers are allowed to sit down, no deadlock can occur (Count-down lock).
• Allow a philosopher to pick up her chopsticks only if both chopsticks are available.
• An odd philosopher picks up first her left chopstick and then her right chopstick, whereas an even philosopher picks up her right chopstick and then her left chopstick.

                     

• Monitor is a highly structured programming-language construct. It consists of
  • Private variables and private procedures that can only be used within a monitor.
  • Constructors that initialize the monitor.
  • A number of (public) monitor procedures that can be invoked by users.
• Note that monitors have no public data.
• A monitor is a mini-OS with monitor procedures as system calls.

         

• Mutual Exclusion
  • There is no more than one process can be executing within a monitor. Thus, mutual exclusion is guaranteed within a monitor.
  • When a process calls a monitor procedure and enters the monitor successfully, it is the only process executing in the monitor.
  • When a process calls a monitor procedure and the monitor has a process running, the caller will be blocked outside of monitor.

         

• All variables are private.
• Monitor procedures are public; however, we can make some procedures private so that they can only be used within the monitor.
• Initialization procedures (i.e., constructors) execute only once when the monitor is created.

         

• With monitors, mutual exclusion is an easy task.
• A programmer might want to block a process and force it to wait until an event occurs while the process is executing within a monitor.
• Thus, each programmer-defined event is artificially associated with a condition variable.
• A condition variable, or a condition, has a waiting list, and two methods: signal and wait.
• Note that a condition variable has no value and cannot be modified.
• Condition wait
  • Let cv be a condition variable. The use of methods signal and wait on cv are cv.signal () and cv.wait ().
  • Condition wait and condition signal can only be used within a monitor.
  • A process that executes a condition wait blocks immediately and is put into the waiting list of that condition variable.
  • This means that this process is waiting for the indicated event to occur.
• Condition signal
  • Condition signal is used to indicate an event has occurred.
  • If there are processes waiting on the signaled condition variable, one of them will be released.
  • If there is no waiting process waiting on the signaled condition variable, this signal is lost as if it never occurs.
  • How about the released process (from the signaled condition) and the process that signals? There are two processes executing in the monitor, and mutual exclusion is violated!
• After a signal, the released process and the signaling process may be executing in the monitor.
• There are two common and popular approaches to address this problem:
  • Hoare Type (proposed by C.A.R.Hoare): The released process takes the monitor and the signaling process waits somewhere.
  • Mesa Type (proposed by Lampson and Redell): The released process waits somewhere and the signaling process continues to use the monitor.
  • There is a waiting bench in a monitor for these processes to wait.

• As a result, each process that involves in a monitor call can be in one of the four states:
  • Active: The running one.
  • Entering: Those blocked by the monitor.
  • Waiting: Those waiting on a condition variable.
  • Inactive: Those waiting on the waiting bench.

         

• Processes suspended due to signal/wait are in the Re-entry list (i.e., waiting bench).
• When the monitor is free, a process is released from either from incoming or re-entry.

         

• Dining philosophers revisited, instead of picking up chopsticks one by one, we insist that a philosopher can eat only if he can pick up both simultaneously.

         

• Monitor: GET () and PUT ()

         

• Monitor: Producer / Consumer

         

• Monitor: PUT () and GET()

         

• Dining Philosophers: Again
  • In addition to thinking and eating, a philosopher has one more state, hungry, in which he is trying to get chops.
  • We use an array state [] to keep track the state of a philosopher. Thus, philosopher i can eat (i.e., state [i] = EATING) only if his neighbors are not eating (i.e., state [(i+4) %5] and state [(i+1) %5] are not EATING).

                     
                     
                     

• This solution does not have deadlock, because
  • The only place where eating permission is granted is in procedure test (), and
  • Philosopher k can eat only if his neighbors are not eating. Thus, no two neighboring philosophers can eat at the same time.
• Hoare Type vs. Mesa Type
  • When a signal occurs, Hoare type monitor uses two context switches, one switching the signaling process out and the other switching the released in. However, Mesa type monitor uses one.
  • Process scheduling must be very reliable with Hoare type monitors to ensure once the signaling process is switched out the next one must be the released process.
  • With Mesa type monitors, the condition variable may be evaluated multiple times. However, incorrect signals will do less harm because every process checks its own condition variable.

                     

7.8.1  synchronization in Solaris 2

• A turnstile is a queue structure containing threads blocked on a lock.
• To prevent a priority inversion, turnstiles are organized according to a priority inheritance protocol.

7.8.2  Synchronization in Windows 2000

• The kernel ensures that a thread will never be preempted while holding a spinlock.

7.9.1  System Model

• A collection of instructions (or operations) that performs a single logical function is called a transaction.
• A transaction is a program unit that access and possibly updates various data items that may reside on the disk within some files.
• The effect of a committed transaction cannot be undone by abortion of the transaction.
• Roll back: the state of the data accessed by an aborted transaction must be restored to what it was just before the transaction started executing.

7.9.2  Log-Based Recovery

• Write-ahead logging.
• undo (Ti) / redo (Ti), which restores / sets the value of all data updated by transaction Ti to the old / new values.
• The undo and redo operations must be idempotent (that is, multiple executions of an operation have the same result as does one execution) to guarantee correct behavior, even if a failure occurs during the recovery process.

7.9.3  Checkpoints
7.9.4  Concurrent Atomic Transactions

7.9.4.1         Serializability

• Serializability: the concurrent execution of transactions must be equivalent to the case where these transactions executed serially in some arbitrary order.

7.9.4.2         Locking Protocol

• Shared lock: Ti can read item, but cannot write item.
• Exclusive lock: Ti can both read and write item.

7.9.4.3         Timestamp-Based Protocols