Description
1. [40 points] Problem Set
1. [20 points] 6.2 The first known correct software solution to the critical-section
problem for two processes was developed by Dekker. The two processes, P0 and
P1, share the following variables:
boolean flag[2]; /* initially false */
int turn;
The structure of process Pi
(i == 0 or 1) is shown in Figure 6.21. The other process is
Pj (j == 1 or 0). Prove that the algorithm satisfies all three requirements for the
critical-section problem.
——————— (The following is Fig. 6.21) —————–
do {
flag[i] = true;
while (flag[j]) {
if (turn == j) {
flag[i] = false;
while (turn == j) ; /* do nothing */
flag[i] = true;
}
}
/* critical section */
turn = j;
flag[i] = false;
/* remainder section */
} while (true);
Figure 6.21 The structure of process Pi
in Dekker’s algorithm.
2. [10 points] 6.4 Explain why implementing synchronization primitives by disabling
interrupts is not appropriate in a single-processor system if the synchronization
primitives are to be used in user-level programs.
3. [10 points] 6.23 How does the signal() operation associated with monitors differ
from the corresponding operation defined for semaphores?
2. [60 points] Programming Exercise
In this assignment, you are to implement a parking simulation program in Python using
semaphores.
A parking lot is a good match with (counting) semaphores because it is a resource with
multiple instances (i.e., N parking spots). So, it will allow up to N simultaneous users to use
the shared resources. Any time the occupancy is less than N, there is no blocking; but if
more than N, then some will have to block.
2.1 [20 points] You will need several data structures for the parking lot:
● a counting semaphore for the number of parking spots
● a list to represent the spots (i.e., record which car is parked in which position)
● another synchronizing data structure of your choice when modifying the list of spots
Use the following template for making the parking lot data structure
import threading
def MakeParkingLot(N):
global sem # semaphore for the parking lot
global spots # list for the spots
global spotsSync # for synchronizing access to spots
spots = [None for i in range(N)]
# your code to initialize sem and spotsSync
You have several choices of data structures for spotsSync and spots. You may even
choose some alternative to spots instead of the code shown here, but if you use a plain
list, then you would need something like a mutex, a lock, or another semaphore for
spotsSync. Check out the available synchronization primitives from threading module.
What would you choose and why?
2.2 [5 points] Each car can be represented by a thread. In the next function, MakeCars(C),
create C threads and return a list of them.
def MakeCars(C):
# your code here to spawn threads
# don’t forget to return the list
2.3 [30 points] Next, you are to write the function to be attached to each thread, i.e., the
action of parking the car, leaving it there for some time, and leaving. it will make use of
the same global data structures declared earlier. Use the comments in the following
template code to fill in the necessary statements
def Park(car):
global sem, spots, spotSync
# 2.3.1 [5 points] ############################
# if spot available, grab it; otherwise wait until available.
# Hint: don’t use if/else statement! this is just one line.
# 2.3.2 [10 points] ###########################################
# after confirming one parking spot, modify the spots (Python list or your choice
# of list-like data structure to put this car into the spot. The following is an example
# of what it can do, but you may have a different way of grabbing parking spots.
# Do you need to protect access to the following block of code? If so,
# add code to protect it; if not, explain why not.
for i in range(len(spots)):
if spots[i] is None:
spots[i] = car
break
snapshot = spots[:] # make a copy for printing
# now let us print out the current occupancy
print(“Car %d got spot: %s” % (car, snapshot))
# leave the car on the lot for some (real) time!
import time
import random
st = random.randrange(1,10)
time.sleep(st)
# now ready to exit the parking lot. What do we need to
# 2.3.3 [5 points] #################################
# (1) give the spot back to the pool (hint: semaphore operation)
# 2.3.4 [10 points] ################################
# (2) update the spots data structure by replacing the spot
# that current car occupies with the value None; protect code if needed
# (3) print out the status of the spots
print(“Car %d left after %d sec, %s” %
(car, st, myCopySpots))
# Finally, have the main program run it:
if __name__ == ‘__main__’:
MakeParkingLot(5)
cars = MakeCars(15)
for i in range(15): cars[i].start()
Here is sample output. Your output may be in a different order, but it must be
consistent.
$ python3 parking.py
Car 0 got spot: [0, None, None, None, None]
Car 1 got spot: [0, 1, None, None, None]
Car 2 got spot: [0, 1, 2, None, None]
Car 3 got spot: [0, 1, 2, 3, None]
Car 4 got spot: [0, 1, 2, 3, 4]
Car 0 left after 3 sec, [None, 1, 2, 3, 4]
Car 5 got spot: [5, 1, 2, 3, 4]
Car 2 left after 3 sec, [5, 1, None, 3, 4]
Car 6 got spot: [5, 1, 6, 3, 4]
Car 3 left after 4 sec, [5, 1, 6, None, 4]
Car 7 got spot: [5, 1, 6, 7, 4]
Car 6 left after 1 sec, [5, 1, None, 7, 4]
Car 8 got spot: [5, 1, 8, 7, 4]
Car 5 left after 3 sec, [None, 1, 8, 7, 4]
Car 9 got spot: [9, 1, 8, 7, 4]
Car 1 left after 8 sec, [9, None, 8, 7, 4]
Car 4 left after 8 sec, [9, None, 8, 7, None]
Car 10 got spot: [9, 10, 8, 7, None]
Car 11 got spot: [9, 10, 8, 7, 11]
Car 10 left after 3 sec, [9, None, 8, 7, 11]
Car 12 got spot: [9, 12, 8, 7, 11]
Car 7 left after 7 sec, [9, 12, 8, None, 11]
Car 13 got spot: [9, 12, 8, 13, 11]
Car 11 left after 5 sec, [9, 12, 8, 13, None]
Car 14 got spot: [9, 12, 8, 13, 14]
Car 8 left after 9 sec, [9, 12, None, 13, 14]
Car 9 left after 9 sec, [None, 12, None, 13, 14]
Car 13 left after 6 sec, [None, 12, None, None, 14]
Car 14 left after 6 sec, [None, 12, None, None, None]
Car 12 left after 9 sec, [None, None, None, None, None]
2.4 [5 points] Show your typescript. Run your code multiple times. Does it show the same or
different output? Why?
