Sync w/o Busy Waiting

Question 1

Race Condition

Answer 1

If final program result depends on the execution/scheduling sequence

Question 2

Critical Section

Answer 2

Program region that has to access shared data in a synchronized way or else race condition will occur

Question 3

Mutual Exclusion

Answer 3

Preventing two or more processes from being inside a critical section simultaneously

Question 4

lock() code

Answer 4

p = 0 #shared between processes

void lock( int *p ) {
while( test_and_set(&p) == 1 );
}

Question 5

Semaphore

Answer 5

• has counter to indicate the number of available resources
• has queue holding processes waiting for the semaphore
• has a busy-waiting lock ( based on test_and_set() )
• has two functions: DOWN() and UP()

Question 6

unlock() code

Answer 6

p = 0 #shared between processes

void unlock( int *p ) {
*p = 0 }

Question 7

test_and_set() code

Answer 7

int test_and_set( int *p ) {
int t= *p
*p = 0
return t

Question 8

down() code

Answer 8

semaphore S
down(S) {
if( S.num > 0 ) S.num –;
else { put current process in wait queue; }
}

Question 9

up() code

Answer 9

semaphore S
up(S) {
if( any processes in wait queue) { pop process from wait queue; resume process; }
else { S.num ++; }
}

Question 10

Binary Semaphore

Answer 10

Semaphore whose counter value is restricted to 0 or 1

Question 11

Monitor

Answer 11

Programming language construct that supports controlled access to shared data. Has mutex lock and queue. Encapsulates:
- shared data
- shared data procedures
- synchronization between concurrent processes

Question 12

Monitor Java Method

Answer 12

• uses “Synchronized” label to implement Monitor object
• inserts lock() and unlock() at entry and exit of each procedure

Question 13

CV

Answer 13

Condition Variable. Used to show events like availability of shared variables. Three operations:
- wait(c, lock): puts process in wait queue and unlock
- signal(c): move process from CV queue to monitor queue
- broadcast(c): wake all processes from CV queue to monitor queue

Question 14

CV vs Semaphore

Answer 14

• semaphore has counter and wait queue
• CV only has wait queue

Question 15

Look at semaphore use examples