End of Midterm Material

Question 1

Race Condition

Answer 1

Two or more processes accessing the same shared data at the same time and outcome depends on the order of execution.

Question 2

Critical-Section Problem Solution (3)

Answer 2

1. Mutual Exclusion - If process Pi is executing in its critical section, then no other processes can be executing in their critical sections
2. Progress - If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely
3. Bounded Waiting - A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted
   - >Assume that each process executes at a nonzero speed
   - >No assumption concerning relative speed of the n processes

Question 3

Critical-Section Handling in OS (2)

Answer 3

Preemptive – allows preemption (removed & replaced - interrupted) of process when running in kernel mode.
Non-preemptive – runs until exits kernel mode, blocks, or voluntarily yields CPU
->Essentially free of race conditions in kernel mode

Question 4

Critical-Section Problem Solutions

Hardware & Software options

Answer 4

Hardware
1. Test & lock
2. Swap
Software
1. Peterson's
2. Mutex locks
3. Semaphore

Question 5

Peterson’s Solution (Provable but not guaranteed on modern systems)

Answer 5

Two process solution!!
The processes alternate execution between their critical sections and remainder sections.
Assume that the load and store machine-language instructions are atomic; that is, cannot be interrupted (not the case on modern architectures)
Requires the two processes to share two variables:
->int turn;
->Boolean flag[2]
The variable turn indicates whose turn it is to enter the critical section
->If (turn == i), then Pi can enter its critical section
The flag array is used to indicate if a process is ready to enter the critical section.
->flag[i] = true implies that process Pi is ready!

Question 6

Synchronization Hardware
(locking & atomic definitions)

Answer 6

Uniprocessors – could disable interrupts

• > Currently running code would execute without preemption
• > Generally too inefficient on multiprocessor systems
• –>Operating systems using this not broadly scalable

Locking: protecting critical regions via locks.
Atomic: non-interruptible
->Either test memory word and set value
->Or swap contents of two memory words

Question 7

test_and_set instruction

Answer 7

Definition:
boolean test_and_set (boolean *target)
{
boolean rv = *target;
*target = TRUE;
return rv:
}
1. Executed atomically
2. Returns the original value of passed parameter
3. Set the new value of passed parameter to “TRUE”.

Question 8

Solution using test_and_set()

Answer 8

Shared Boolean variable lock, initialized to FALSE
Solution:
       do {
          while (test_and_set(&lock)) 
             ; /* do nothing */ 
                 /* critical section */ 
          lock = false; 
                 /* remainder section */ 
       } while (true);

Question 9

swap instruction

Answer 9

Definition:
     int swap(boolean *a, boolean *b) { 
         boolean temp = *a;
		  *a = *b;
         *b = temp; 
     } 
1. Executed atomically
2. Swaps the values of the two parameters
->Before: a=F, b=T 
->End: a=T, b=F

Question 10

Solution using compare_and_swap

mutual exclusion verified but not bounded-waiting. waiting for “luck”, swap function randomly executing

Answer 10

Shared boolean “lock” initialized to False; 
Local variable ”key”
Solution:
      do {
	key = TRUE;
        while (key == TRUE) 
            	Swap(&lock, &key);
          		/* critical section */ 
         lock = FALSE; 
          /* remainder section */ 
      } while (true);

Question 11

Bounded-waiting Mutual Exclusion with test_and_set (Good Solution!)

Answer 11

do {
    waiting[i] = true;
    key = true;
    while (waiting[i] && key) 
      key = test_and_set(&lock); 
   waiting[i] = false; 
   /* critical section */ 
   j = (i + 1) % n; (circular buffer)
   while ((j != i) && !waiting[j]) (search through each process)
      j = (j + 1) % n; 
   if (j == i) 
      lock = false; (Unlock for any process that comes after)
   else 
      waiting[j] = false; 
   /* remainder section */ 
} while (true);

Question 12

Mutex Locks

Answer 12

Protect a critical section by first acquire() a lock then release() the lock
->Boolean variable indicating if lock is available or not
Calls to acquire() and release() must be atomic
->Usually implemented via hardware atomic instructions
But this solution requires busy waiting
->This lock therefore called a spinlock

NO CONTEXT SWITCH NEEDED, reduces overhead

Question 13

acquire() and release() code

Answer 13

acquire() {
       while (!available) 
          ; /* busy wait */ 
       available = false;; 
    } 
   release() { 
       available = true; 
    } 
   do { 
    acquire lock
       critical section
    release lock 
      remainder section 
 } while (true);

Question 14

Semaphore

Answer 14

Synchronization tool that provides more sophisticated ways (than Mutex locks) for process to synchronize their activities.
Semaphore S – integer variable
Can only be accessed via two indivisible (atomic) operations (wait & signal)
->wait() and signal()
--->Originally called P() and V()
Definition of  the wait() operation
wait(S) { 
    while (S <= 0)
       ; // busy wait
    S--;
}
Definition of  the signal() operation
signal(S) { 
    S++;
}

Question 15

Semaphore Usage

Answer 15

Counting semaphore – integer value can range over an unrestricted domain
Binary semaphore – integer value can range only between 0 and 1
->Same as a mutex lock
Can solve various synchronization problems
Consider P1 and P2 that require S1 to happen before S2
Create a semaphore “synch” initialized to 0
P1:
S1;
signal(synch);
P2:
wait(synch);
S2;

Question 16

Semaphore Implementation

Answer 16

Must guarantee that no two processes can execute the wait() and signal()on the same semaphore at the same time
Thus, the implementation becomes the critical section problem where the wait and signal code are placed in the critical section
->Could now have busy waiting in critical section implementation
—>But implementation code is short
—>Little busy waiting if critical section rarely occupied
Note that applications may spend lots of time in critical sections and therefore this is not a good solution

Question 17

Semaphore Implementation with no Busy waiting

Answer 17

When semaphore is zero, rather than busy wait, the process can block itself.
A process blocked waiting on a semaphore S, should be restarted when the signal() operation is executed. The process is woken up by a wake() operation, which changes the process state from waiting to ready.

With each semaphore there is an associated waiting queue (FIFO queue ensures bounded waiting; however, can use any queueing strategy)
Each entry in a waiting queue has two data items:
->value (of type integer)
->pointer to next record in the list
Two operations:
->block – place the process invoking the operation on the appropriate waiting queue
->wakeup – remove one of processes in the waiting queue and place it in the ready queue

Question 18

Semaphore Implementation with no Busy waiting (code)

Answer 18

typedef struct{
int value;
struct process *list;
} semaphore;

wait(semaphore *S) { 
   S->value--; 
   if (S->value < 0) {
      add this process to S->list; 
      block(); 
   } 
}

signal(semaphore *S) { 
   S->value++; 
   if (S->value <= 0) {      remove a process P from S->list; 
      wakeup(P); 
   } 
}

Question 19

Deadlock and Starvation

Answer 19

Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes
Let S and Q be two semaphores initialized to 1
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
… …
signal(S); signal(Q);
signal(Q); signal(S);

Starvation – indefinite blocking (one process)
A process may never be removed from the semaphore queue in which it is suspended
Priority Inversion – Scheduling problem when lower-priority process holds a lock needed by higher-priority process
Solved via priority-inheritance protocol

Question 20

Bounded-Buffer Problem

Answer 20

Producer and Consumer share the following data structure:

• > n buffers, each can hold one item
• > Semaphore mutex initialized to the value 1
• > Semaphore full initialized to the value 0
• > Semaphore empty initialized to the value n

Question 21

Bounded Buffer Problem (Structure of producer process)

Answer 21

The mutex is needed to avoid problems in producer to understand the correct buffer where to write.

 do { 
          ...
         /* produce an item in next_produced */ 
          ... 
        wait(empty); 
        wait(mutex); 
           ...
           /* add next produced to the buffer */ 
           ... 
        signal(mutex); 
        signal(full); 
     } while (true);

Question 22

Bounded Buffer Problem (Structure of consumer process)

Answer 22

Do { 
        wait(full); 
        wait(mutex); 
           ...
           /* remove an item from buffer to next_consumed */ 
           ... 
        signal(mutex); 
        signal(empty); 
           ...
           /* consume the item in next consumed */ 
           ...
      } while (true);