course: operating system 2. There are many one lane bridges in the upper Northea
ID: 3589876 • Letter: C
Question
course: operating system
2. There are many one lane bridges in the upper Northeast. Assume such a bridge exists between a set of farms and the fields in which the farmers harvest their crops. Also assume that there are 15 farms on one side of the bridge, and every day each farmer that lives on his farm will want to go back and forth across the bridge, harvesting crops in the field and bringing them back to the farm. Not every farmer works at the same pace. If a farmer gets to the bridge and wants to cross it, the following must occur. If there is nobody else on the bridge, the farmer may drive across. If there is already a farmer driving across the bridge in the other direction, the farmer must wait until the bridge is empty before crossing. If there is already a farmer driving across the bridge in the same direction, the new farmer may follow after him and be on the bridge at the same time.
a) Write a pseudocode algorithm using semaphores/counters/etc. for a farmer's daily actions to control access to the bridge and stop any accidents from happening. Assume the bridge is big enough to hold the cars of all 15 farmers at once if necessary.
b) Now assume the bridge is only big enough to allow three cars onto it at the same time. Show how your algorithm needs to be modified to work in this situation.
Explanation / Answer
(a) Answer:
We will take two Global variables (semaphores) S=0 and N=0;
three common functions:
//val can be S or N
//to check any farmer coming in other direction
check_otherDirection(val){
while(val>0){
}
}
//moving
Move(val){
val++;
}
//indicating end of trip
End_trip(val){
val--;
}
Farmer in south will Execute:
start_south(){
check_otherDirection(N);
Move(S);
//we can add wait time to cross bridge in between moving and ending trip.
End_trip(S);
}
Farmer in North will Execute:
start_north(){
check_otherDirection(S);
Move(N);
//we can add wait time to cross bridge in between moving and ending trip.
End_trip(N);
}
(b) Answer :
Now we need to modify semaphores to restrict only three cars by initializing them to 3.
while moving decrement respective semaphore by 1.
after ending increment respective semaphore by 1.
We will take two global variables (semaphores) S=3 and N=3;
three common functions:
//to check any farmer coming in other direction
check_Bridge(val1,val2){
while(val1==3 and val2>0){
}
}
//moving
Move(val){
val--;
}
//indicating end of trip
End_trip(val){
val++;
}
Farmer in south will Execute:
start_south(){
check_Bridge(N,S);
Move(S);
//we can add wait time to cross bridge in between moving and ending trip.
End_trip(S);
}
Farmer in North will Execute:
start_north(){
check_Bridge(S,N);
Move(N);
//we can add wait time to cross bridge in between moving and ending trip.
End_trip(N);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.