Assignment #5 Solution

Description

1. [40 points] ProblemSet
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 followingvariables:
boolean flag[2]; /* initially false */
intturn;
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.21The structure of processPiin 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-levelprograms.
3. [10 points] 6.23 How does thesignal()operation associated with monitors differ from the corresponding operation defined forsemaphores?

2. [60 points] ProgrammingExercise
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 parkinglot:
● a counting semaphore for the number of parkingspots
● a list to represent the spots (i.e., record which car is parked in whichposition)
● another synchronizing data structure of your choice when modifying the list of spots Use the following template for making the parking lot datastructure
import threading
defMakeParkingLot(N):
globalsem #semaphorefor theparkinglot
globalspots # list for the spots
globalspotsSync # forsynchronizing accessto spotsspots=[Noneforiinrange(N)]
# your codetoinitializesem andspotsSync
You have several choices of data structures forspotsSyncandspots.You may even choose some alternative tospotsinstead 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 forspotsSync.Check out the available synchronization primitives fromthreadingmodule. 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 ofthem.
defMakeCars(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 necessarystatements
defPark(car):
globalsem, 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] ###########################################
#afterconfirmingoneparkingspot,modifythespots(Pythonlistoryourchoice
# 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 parkingspots.
# Do you need to protect access to the following block of code? If so, # add code to protect it; if not, explain why not.
foriinrange(len(spots)):
ifspots[i]isNone: spots[i] = carbreak
snapshot=spots[:] #makeacopyforprinting
# 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!
importtime
importrandom
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 thespots
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)
foriinrange(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 gotspot:[0,None, None, None,None] Car 1 gotspot:[0, 1,None, None,None]
Car 2 got spot: [0, 1, 2, None, None]
Car 3 gotspot:[0, 1, 2, 3,None]
Car 4 gotspot:[0, 1, 2, 3,4]
Car 0left after3sec, [None,1, 2, 3,4]
Car 5 gotspot:[5, 1, 2, 3,4]
Car 2 left after3sec,[5, 1,None,3, 4]
Car 6 got spot: [5, 1, 6, 3, 4]
Car 3 left after4sec,[5, 1, 6,None, 4]
Car 7 got spot: [5, 1, 6, 7, 4]
Car 6 left after1sec,[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 1left after8sec,[9,None,8, 7,4]
Car 4left after8sec,[9,None,8, 7,None]
Car 10 gotspot:[9, 10, 8, 7,None]
Car 11 gotspot:[9, 10, 8, 7,11]
Car 10 left after3sec,[9,None,8, 7,11]
Car 12 got spot: [9, 12, 8, 7, 11]
Car 7 left after7sec,[9, 12, 8,None,11]
Car 13 got spot: [9, 12, 8, 13, 11]
Car 11 left after5sec,[9, 12, 8, 13,None]
Car 14 got spot: [9, 12, 8, 13, 14]
Car 8 left after9sec,[9, 12,None,13,14]
Car 9 left after9sec, [None,12,None,13,14]
Car 13left after6sec, [None,12,None, None,14] Car 14left after6sec, [None,12,None, None,None]
Car 12left after9sec, [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?