[IOS] Ch6 Synchronization #3

Ch 6.7 Monitors

• Problems with Semaphores:
  
  • Used for 2 independent purposes
    
    • Mutual exclusion
    • Condition Synchronization
  • Hard to get right while coding
    
    • signal(mutex) … wait(mutex) ： several processes may be executing in their critical sections simultaneously
    • wait(mutex) … wait(mutex) : deadlock
    • omitting of wait(mutex) or signal(mutex) (or both)
    • small mistake easily leads to deadlock / livelock
  • Separation of mutual exclusion and condition synchronization
  • Automatic wait and signal
• To solve it, develope monitor type:
  
  • A high-level abstraction that provides a convenient and effective
    mechanism for process synchronization

6.7.1 Usage

• A monitor type is an ADT
• Like a C++ class

    monitor monitor-name 
    {
        // shared variable declarations
        procedure P1(...) { ... }
        ...
        procedure Pn(...)｛ ... }
        initialization code(...) { ... }
        ...
    }

• A procedure defined within a monitor can access only those variables declared locally within the monitor and its formal parameters.
• Ensure only one process may be active within the monitor at a time
• But not powerful for modeling some synchronization constraint explicitly.
• Type condition:

    condition x, y;

• Operation:

    x.wait();       // Thread is put on queue for "x", goes to sleep.
    x.signal();     // If queue for "x" not empty, wake up on thread.
    x.broadcast();  // Wake up all threads waiting on queue for "x".

• x. signal() operation resumes exactly one suspended process.
• Suppose x.signal () operation is invoked by a process P, there exists a suspended process Q associated with condition x, two possibilities exist:
  
  • Signal and wait. P either waits until Q leaves the monitor or waits for
    another condition.
  • Signal and continue. Q either waits until P leaves the monitor or waits
    for another condition.
    
    • More resonable
  • A compromise between these two choices: When thread P executes the signal operation, it imncediately leaves the monitor. Hence, Q is immediately resumed.
• Bounded Buffer by Monitor:

    BoundedBuffer 
    {
        int BUFFER[MAX_SIZE];
        int head, tail, size;
        condition full, empty;

        Enque(int v) {
            while (size == MAX_SIZE)
                full.wait();
            BUFFER[tail] = v;
            tail = (tail + 1) % MAX_SIZE;
            size++;
            if (size == 1)
                empty.signal();
        }

        Deque(int v) {
            while (size == 0)
                empty.wait();
            int i = head;
            head = (head + 1) % MAX_SIZE;
            size--;
            if (size == MAX_SIZE - 1)
                full.signal();
            return BUFFER[i];
        }
    }

6.7.2 Dining-Philosophers Solution Using Monitors

    Monitor DP
    {
        enum { THINKING, HUNGRY, EATING} state [5] ; 
        /* Philosopher i can set the variable state [i] = EATING only if her two neighbors are not eating: (state [ (i +4) % 5] ! = EATING) and (state [ (i +1) % 5] '= EATING) */

        condition self [5];
        /* Philosopher i can delay herself when she is hungry but is unable to obtain the chopsticks she needs. */

        void pickup (int i) {
            state[i] = HUNGRY;
            test(i);
            if (state[i] != EATING) 
                self[i].wait;
        }

        void putdown (int i) {
            state[i] = THINKING;
            // test left and right neighbors
            test((i + 4) % 5);
            test((i + 1) % 5);
        }

        void test (int i) {
            if ( (state[(i + 4) % 5] != EATING) &&
                (state[i] == HUNGRY) &&
                (state[(i + 1) % 5] != EATING) ) {
                state[i] = EATING ;
                self[i].signal () ;
            }
        }

        initialization_code() {
            for (int i = 0; i < 5; i++)
                state[i] = THINKING;
        }
    }

• Philosopher i must invoke the operations pickup() and put down() in the following sequence:

    DiningPhilosophers.pickup(i);
    ...
    eat
    ...
    DiningPhilosophers.putdown(i);

• However, it is possible for a philosopher to starve to death.

6.7.3 Implementing a Monitor Using Semaphores

• Need mutual exclusion semaphore mutex (init to 1) so
  that only one process is active within monitor.
• Need a semaphore next (next to exit) for the signaling
  process to suspend itself (initialized to zero)
• next_count is number of processes blocked on next
  
  • Before exiting a procedure, process must either:
    
    • Signal other waiting processes in monitor next before exiting, or
    • Signal mutex and exit
• The monitor “compiler” has to automatically insert this code into compiled procedures (Hoare style):

    Procedure F
    {
        wait(mutex);
        ...
        body of F
        ...
        if (next_count > 0)
            signal(next);
        else
            signal(mutex);
    }

• Each condition x has a count (x_count), and a standard semaphore (x_sem) initialized to 0:

    x.wait()
    {
        x_count++;
        if (next_count > 0)
            signal(next);
        else
            signal(mutex);
        wait(x_sem);
        x_count--;
    }

    x.signal()
    {
        if (x_count > 0) {
            next_count++;
            signal(x_sem);
            wait(next);
            next_count--;
        }
    }

• Mesa style:

    Procedure F
    {
        wait(mutex);
        ...
        body of F
        ...
        signal(mutex);
    }

    x.wait() {
        x_count++;
        signal(mutex);
        wait(x_sem);
        wait(mutex);
    }

    x.signal() {
        if (x_count > 0) {
            x_count--;
            signal(x_sem);
        }
    }

6.7.4 Resuming Processes within a Monitor

• To determine which process resume next:
  
  • FCFS
  • Sometime it doesn’t work, so we need conditional-wait
    
    • form: x.wait(c)
    • c: priority number
• A monitor to allocate a single resource

    monitor ResourceAllocator
    {
        boolean busy;
        condition x;
        void acquire(int time) {
            if (busy)
                x.wait(time);
            busy = true;
        }

        void release() {
            busy = false;
            x.signal();
        }

        initialization code() {
            busy = false;
        }
    }

• A process that needs to access the resource in question must observe the following sequence:

    R.acquire(t);
    // access the resource;
    // R is an instance of type ResourceAllocator
    R.release() ;

• Problems:
  
  • A process might access a resource without first gaining access permission to the resource.
  • A process might never release a resource once it has been granted access to the resource.
  • A process might attempt to release a resource that it never requested.
  • A process might request the same resource twice (without first releasing the resource).
• Difference between Monitors and Semaphores
  
  • Monitors enforce mutual exclusion
  • Semaphore wait vs Monitor wait
    
    • Semaphore wait blocks if value is 0
    • Monitor wait always blocks
  • Semaphore signal vs Monitor signal
    
    • Semaphore signal either wakes up a thread or increments value
    • Monitor signal only has effect if a thread waiting
  • Semaphores have “memory”

Ch 6.8 Syncronization Samples

6.8.1 Syncronization in Solaris

• Implements a variety of locks to support multitasking, multithreading (including real-time threads), and multiprocessing
• Uses adaptive mutexes for efficiency when protecting data from short code segments.
  
  • Protects access to every critical data item
  • For these longer code segments, condition variables and semaphores are used.
• Uses condition variables and readers-writers locks when longer sections of code need access to data.
• Uses turnstiles to order the list of threads waiting to acquire.
  
  • A queue structure containing threads blocked on a lock.
  • If one thread currently owns the lock for a synchronized object, all other threads trying to acquire the lock will block and enter the turnstile for that lock. When the lock is released,the kernel selects a thread from the turnstile as the next owner of the lock.
  • Solaris gives each kernel thread its own turnstile.

6.8.2 Syncronization in Windows XP

• Uses interrupt masks to protect access to global resources on uniprocessor systems.
• Uses spinlocks on multiprocessor systems.
• Also provides dispatcher objects which may act as either mutexes and semaphores.
• Dispatcher objects may also provide events
  
  • An event acts much like a condition variable
• Difference between mutex and binary semaphore:
  

  They are NOT the same thing.
  They are used for different purposes!
  While both types of semaphores have a full/empty state and use the same API, their usage is very different.
  Mutual Exclusion Semaphores:
  Mutual Exclusion semaphores are used to protect shared resources (data structure, file, etc..).
  A Mutex semaphore is “owned” by the task that takes it. If Task B attempts to semGive a mutex currently held by Task A, Task B’s call will return an error and fail.
  Mutexes always use the following sequence:
  

  • SemTake
  • Critical Section
  • SemGive

  Here is a simple example:

  Thread A                     Thread B
   Take Mutex
     access data
     ...                        Take Mutex  <== Will block
     ...
   Give Mutex                     access data  <== Unblocks
                                  ...
                                Give Mutex

Binary Semaphore
Binary Semaphore address a totally different question:
Task B is pended waiting for something to happen (a sensor being tripped for example).
Sensor Trips and an Interrupt Service Routine runs. It needs to notify a task of the trip.
Task B should run and take appropriate actions for the sensor trip. Then go back to waiting.

   Task A                      Task B
   ...                         Take BinSemaphore   <== wait for something
   Do Something Noteworthy
   Give BinSemaphore           do something    <== unblocks

Note that with a binary semaphore, it is OK for B to take the semaphore and A to give it.
Again, a binary semaphore is NOT protecting a resource from access. The act of Giving and Taking a semaphore are fundamentally decoupled.
It typically makes little sense for the same task to so a give and a take on the same binary semaphore.

Via stackoverflow

6.8.3 Synchronization in Linux

• Linux:
  
  • Prior to kernel Version 2.6, disables interrupts to implement short critical sections
  • Version 2.6 and later, fully preemptive
• Linux provides:
  
  • semaphores
  • spin locks ( implemented by busy waiting )

6.8.4 Synchronization in Pthreads

• Pthreads API is OS-independent
• It provides:
  
  • mutex locks
  • condition variables
• Non-portable extensions include:
  
  • read-write locks
  • spin locks
• Java style monitor:

    public class SynchronizedCounter {
        private int c = 0;

        public synchronized void increment() {
            c++;
        }

        public synchronized void decrement() {
            c--;
        }

        public synchronized int value() {
            return c;
        }
    }

Ch 6.9 Atomic Transactions

6.9.1 System Model

• Assures that operations happen as a single logical unit of work, in its entirety, or not at all
• Related to field of database systems
• Challenge is assuring atomicity despite computer system failures
• Transaction - collection of instructions or operations that performs single logical function
  
  • Here we are concerned with changes to stable storage – disk
  • Transaction is series of read and write operations
  • Terminated by commit (transaction successful) or abort (transaction failed) operation
  • Aborted transaction must be rolled back to undo any changes it performed
• Volatile storage – information stored here does not survive system crashes
  
  • Example: main memory, cache
• Nonvolatile storage – Information usually survives crashes
  
  • Example: disk and tape
• Stable storage – Information never lost
  
  • Not actually possible, so approximated via replication or RAID to devices with independent failure modes
  • Goal: assure transaction atomicity where failures cause loss of information on volatile storage

6.9.2 Log-Based Recovery

• Record to stable storage information about all modifications by a transaction
• Most common is write-ahead logging
  
  • Log on stable storage, each log record describes single transaction write operation, including
    
    • Transaction name
    • Data item name
    • Old value
    • New value
  • <Ti starts> written to log when transaction Ti starts
  • <Ti commits> written when Ti commits
• Log entry must reach stable storage before operation on data occurs
• Using the log, system can handle any volatile memory errors
  
  • Undo(Ti) restores value of all data updated by Ti
  • Redo(Ti) sets values of all data in transaction Ti to new values
• Undo(Ti) and redo(Ti) must be idempotent
  
  • Multiple executions must have the same result as one execution
• If system fails, restore state of all updated data via log
  
  • If log contains <Ti starts> without <Ti commits>, undo(Ti)
  • If log contains <Ti starts> and <T i commits>, redo(Ti)

6.9.3 Checkpoints

• Log could become long, and recovery could take long.
• Checkpoints shorten log and recovery time.
• Checkpoint scheme:
  
  1. Output all log records currently in volatile storage to stable storage
  2. Output all modified data from volatile to stable storage
  3. Output a log record to the log on stable storage
• Now recovery only includes Ti, such that Ti started executing before the most recent checkpoint, and all transactions after Ti
  
  • All other transactions already on stable storage

6.9.4 Concurrent Transactions

• Must be equivalent to serial execution – serializability
• Could perform all transactions in critical section
  
  • Inefficient, too restrictive
  • Concurrency-control algorithms provide serializability
  • Maintained by simply executing each transaction within a critical section
    
    • All transactions share a common semaphore mutex, which is initialized to 1.
    • When a transaction starts executing, its first action is to execute wait(mutex).
    • After the transaction either commits or aborts, it executes signal(mutex).

6.9.4.1 Serializability

• Consider two data items A and B
• Consider Transactions T0 and T1
• Execute T0 , T1 atomically
• Execution sequence called schedule
• Atomically executed transaction order called serial schedule
• For N transactions, there are N! valid serial schedules
• Schedule I: A serial schedule in which T0 is followed by T1

T0	T1
read(A)
write(A)
read(B)
write(B)
	read(A)
	write(A)
	read(B)
	write(B)

• Schedule 2: Concurrent Serializable Schedule

T0	T1
read(A)
write(A)
	read(A)
	write(A)
read(B)
write(B)
	read(B)
	write(B)

Nonserial Schedule:

• Nonserial schedule allows overlapped execute
  
  • Resulting execution not necessarily incorrect
• Consider schedule S, operations Oi , Oj
  
  • Conflict if access same data item, with at least one write
• If Oi , Oj consecutive and operations of different transactions & Oi and Oj don’t conflict
  
  • Then S’ with swapped order O j O i equivalent to S
• If S can become S’ via swapping nonconflicting operations
  
  • S is conflict serializable

6.9.4.2 Locking Protocol

• Ensure serializability by associating lock with each data item
  
  • Follow locking protocol for access control
• Locks
  
  • Shared – Ti has shared-mode lock(S) on item Q, Ti can read Q but not write Q
  • Exclusive – Ti has exclusive-mode lock (X) on Q, Ti can read and write Q
• Require every transaction on item Q acquire appropriate lock
• If lock already held, new request may have to wait
  
  • Similar to readers-writers algorithm
• Generally ensures conflict serializability
• Each transaction issues lock and unlock requests in two phases
  
  • Growing – obtaining locks
  • Shrinking – releasing locks
• Does not prevent deadlock

6.9.4.3 Timestamp-Based Protocols

• Select order among transactions in advance – timestamp-ordering
• Transaction Ti associated with timestamp TS(Ti) before Ti starts
  
  • TS(Ti) < TS(Tj) if Ti entered system before Tj
  • TS can be generated from system clock or as logical counter incremented at each entry of transaction
• Timestamps determine serializability order
  
  • If TS(Ti) < TS(Tj), system must ensure produced schedule equivalent to serial schedule where Ti appears before Tj

Implement:

• Data item Q gets two timestamps
  
  • W-timestamp(Q) – largest timestamp of any transaction that executed write(Q) successfully
  • R-timestamp(Q) – largest timestamp of successful read(Q)
• Updated whenever read(Q) or write(Q) executed
• Timestamp-ordering protocol assures any conflicting read and write executed in timestamp order
• Suppose Ti executes read(Q)
  
  • If TS(Ti) < W-timestamp(Q), Ti needs to read value of Q that was already overwritten
    
    • read operation rejected and Ti rolled back
  • If TS(Ti) ≥ W-timestamp(Q)
    
    • read executed, R-timestamp(Q) = max(R-timestamp(Q), TS(Ti))
• Suppose Ti executes write(Q)
  
  • If TS(Ti) < R-timestamp(Q), value Q produced by Ti was needed previously and Ti assumed it would never be produced
    
    • Write operation rejected, Ti rolled back
  • If TS(Ti) < W-timestamp(Q), Ti attempting to write obsolete value of Q
    
    • Write operation rejected, Ti rolled back
  • Otherwise, write executed
• Any rolled back transaction Ti is assigned new timestamp and restarted
• Algorithm ensures conflict serializability and freedom from deadlock