Long Answers CS343

W23

External scheduling:

L1:
bool clientWaiting = false;
bool taxiWaiting = false;
 
 
L2: getTaxi
 
clientWaiting = true;
xclient = x;
yclient = y;
clientId = id;
 
_When(!taxiWaiting) _Accept(getClient) {}
 
clientWaiting = false;
 
 
L3: getClient
 
taxiWaiting = true;
taxiId = id;
 
_When(!clientWaiting) _Accept(getTaxi) {}
 
taxiWaiting = false;
x = xclient;
y = yclient;

Internal scheduling:

L1:
uCondition waitingTaxis, waitingClients;
 
L2: getTaxi
if (!waitingTaxis.empty()) { // A taxi is available
    xclient = x;
    yclient = y;
    clientId = id; // Store client details
    taxiId = waitingTaxis.front(); // Get the taxi from the front of the queue
    waitingTaxis.signalBlock(); // Unblock the waiting taxi
} else { // No taxis are available
    waitingClients.wait(id); // Block the client and wait for a taxi
    xclient = x;
    yclient = y;
    clientId = id; // Store client details once unblocked
}
 
 
L3: getClient
if (!waitingClients.empty()) { // A client available
    taxiId = id; // Store the taxi ID
    waitingClients.signalBlock(); // Unblock the waiting client
} else {
    waitingTaxis.wait(id); // Block the taxi and wait for a client
}

AUTOMATIC_SIGNAL: i give up

L1:
AUTOMATIC_SIGNAL;
int waitingTaxis = 0; waitingClients = 0;
 
L2: getTaxi
 
waitingCl
 
 
 

Administrator:

void MapleLeafTaxi::main(){
	Taxi* taxiT[NoOfTaxi]; // here it's 5
 
	// allocate taxis
	for(unsigned int i = 0; i < NoOfTaxi; i++) {
		taxiT[i] = new Taxi(*this, i); // assign id
	}
 
	for(;;) {
		_Accept(close) {
			break;
		} or _Accept(getClient or getTaxi) {
			LocnClient *n = client.front();
			clients.pop_front();
			
			// Store location of client
			xclient = n->x;
			yclient = n->y;
 
			// Find nearest taxi
			list<LocnTaxi*>::iterator closest = nearestTaxi(xlient, yclient, taxis);
 
			// Store the future taxi
			n->ftaxi.delivery(closest->id);
			delete n;
 
			// unblock assigned taxi
			closest->idle.signalBlock();
			taxis.erase(closet);
		}
	} // for
 
	osacquire( cout ) << "Closed for the day." << endl;
	
	// outstanding taxis blocked 
	while(clients.size() != 0) {
		LocnClient* c = clients.front();
		clients.pop_front();
		c->ftaxi.exception(new Closed); // Notify clients that no taxis are available
		delete client;
	}
 
	closed = true; // // Mark the dispatcher as closed
 
	// wait for remaining taxis
	for(int i = 0; i < NoOfTaxi; i++) {
		if(taxis.empty()) _Accept(getClient); // wait for taxi
		taxis.front()->idle.signalBlock(); //??
		taxis.pop_front(); // unblock with closed
	}
 
	for(int i = 0; i < NoOfTaxi; i++) delete taxiT[i];
}
 
 
 

F18

External scheduling:

_Monitor Semaphore {
	unsigned int cnt;
 
public:
	Semaphore(unsigned int cnt) : cnt(cnt) {}
 
	void P(){
		if(cnt == 0) {
			for(;;) {
				_Accept(V) {
				} _Accept(try P()){
				}
			} // for
		} // if
		cnt--;
	}
 
	bool tryP(){
		if(cnt == 0) {
			return false
		}
 
		cnt--; // why? didn't have it initially
		return true;
	}
 
	void P(Semaphore s) {
		s.V();
		P();
	}
 
	void V() {
		cnt++;
	}
}

counter of a semaphore only goes from 0 to 1.

P(Semaphore s)This sequence can occur in scenarios where:

• A higher-level resource allocation must be made available (s.V()).
• Immediately after, the current process or thread attempts to acquire the resource (P()). This could be because other tasks may also compete for the resource, and the code ensures the resource is claimed for use immediately after signalling availability.

Internal scheduling:

_Monitor Semaphore {
	unsigned int cnt;
	uCondition bench;
 
public:
	Semaphore(unsigned int cnt) : cnt(cnt) {}
 
	void P(){
		if(cnt == 0) bench.wait();
 
		cnt--;
	}
 
	bool tryP(){
		if(cnt == 0) return false;
 
		cnt--;
		return true;
	}
 
	void P(Semaphore s) {
		s.signal();
		P();
	}
 
	void V() {
		cnt--;
		bench.signal();
	}
}

F19

External scheduling:

L1: // Don't need any variables
 
L2:
if(voters < group) _Throw Quorum();
 
L3:
try {
	for(;;) {
		_Accept(done) {
			if(voters < group) break;
		} or _Accept(vote){
		
		}
	} // for
} catch (uMutexFailure::RendezvousFailure &){
 
} // try
 
 
L5: 
if(voters < group) _Throw Quorum();
 

Internal scheduling:

L1:
uCondition bench;
 
L2:
if(voters < group) _Throw Quorum();
 
L3:
bench.wait();
bench.signal();
if(voters < group) _Throw Quorum();
 
L4:
bench.signal();
 
L6:
if(voters < group) bench.signal();
 

Administrator:

void flush(bool kind) {
	for(int i = 0; i < votes.size(); i++) {
		votes[i]->(kind ? new Quorum : new Closed);
	} // for
	votes.clear();
}
 
void main(){
	for(;;){
		_Accept(~TallyVotes){ // shutdown
			break;
		} or _Accept(done) { // voter leaves
			voters -= 1;
			if(voters < group && voters.size()) { // failure?
				flush(true); // Quorum failure
			}
		} or _Accept(vote) { // voter
		
		} or _Accept(tour) { //guide
			if(!wguides.empty() && voters.size() > group) {
				for(int i = 0; i < group; i++){ //compute rank
					add(voters->[i]->ballot);
				} // for
 
				gtour = tally(); // computer vote
				for(int i = 0; i < group; i++) { // put vote in futures
					votes[i]->ftour.delivery(gtour);
					delete votes[i];
				} // for
 
				votes.erase(votes.begin(), votes.begin()+group) // shorten
				wguides.signalBlock(); // unblock guide
				reset(); // reset vote counters
			} // if
		} // Accept
	} // for
 
	// Shut down and tell the tourists/guides to go home
	closed = true;
	for(int i = 0; i < guides; i++){
		if(wguides.empty()) _Accept(tour); 
	} // for
 
	flush(false); // CLosed failure
}

External scheduling:

unsigned int winner;
bool shutdownStarted = false;
 
TallyBets::Payout TallyBets::placeBet(BetSlip slip) {
	if(shutdownStarted) _Throw Leave();
 
	try {
		_Accept(done) {
		} or _Accept(race) {
		} or _Accept(placeBet) {
		}
	} catch(uMutexFailure::RendezvousFailure & ) {}
 
	if(shutdownStarted) _Throw Leave();
	return tally(slip);
} // TallyBets::placeBet
 
void TallyBets::race(unsigned int winner) {
	TallyBets::winner = winner;
} // TallyBets::race
 
void done() {
	shutdownStarted = true;
} // TallyBets::done
 

Internal scheduling

uCondition bench;
 
TallyBets::Payout TallyBets::placeBet(BetSlip slip) {
	if(shutdownStarted) _Throw Leave();
	bench.wait();
	bench.signal();
	if(shutdownStarted) _Throw Leave();
	return tally(slip);
} // TallyBets::placeBet
 
void TallyBets::race(unisgned int winner) {
	TallyBets::winner = winner;
	bench.signal();
} // TallyBets::race
 
void done(){
	shutdownStarted = true;
} // TallyBets::done
 

Automatic signal:

AUTOMATIC_SIGNAL;
unsigned int numBets = 0;
 
TallyBets::Payout TallyBets::placeBet(BetSlip slip) {
	if(shutdownStarted) _Throw Leave();
	numBets += 1;
	WAITUNTIL(numBets == 0, , );
	if(shutdownStarted) _Throw Leave();
	EXIT();
	return tally(slip);
} // TallyBets::placeBet
 
void TallyBets::race(unsigned int winner) {
	TallyBets::winner = winner;
	numBets = 0;
	EXIT();
} // TallyBets::race
 
void done() {
	shutdownStarted = true;
} // TallyBets::done

Administrator:

struct Work {
	BetSlip slip;
	FPayout fpayout;
	Work(BetSlip slip): slip(slip) {}
};
 
FPayout placeBet(BetSlip slip);
Work* node;
list<Work*> students; // students waiting for race results
unsigned int numStuds;
 
TallyBets(unsigned int numStuds): numStuds(numStuds) {}
TallyBets::FPayout TallyBets::placeBet(BetSlip slip) {
	node = new Work(slip);
	return node->fpayout; // why?
} // TallyBets::placeBet
 
// same as monitor
void TallyBets::race(unsigned int winner) {}
 
// same as monitor
void TallyBets::done(){}
 
void TallyBets::main() {
	for(;;) {
		_Accept(done) {
			break;
		} or _Accept(race) {
			while(!students.empty()) {
				Work* n = students.front();
				students.pop_front();
				n->fpayout.delivery(tally(n->slip));
				delete n;
			} // while
		} or _Accept(placeBet) {
			students.push_back(node); // store future
		} // _Accept
	} // for
 
	// Students not waiting on futures.
	unsigned int rem - numStuds - 1 - students.size();
	for(unsigned int b = 0; b < rem; b+=1) {
		_Accept(placeBet) {
			students.push_back(node);
			Work* n = students.front();
			students.pop_front();
			n->fpayout.delivery(new Leave());
			delete n;
		} or _Accept(done) {}
	} // for
 
	// Students waiting on futures
	while(!students.empty()) {
		Work* n = students.front();
		students.pop_front();
		n->fpayout.delivery(new Leave());
		delete n;
	} // while
} // TallyBets::main
 

F15

Write a counting semaphore using μC++ monitors that implements the semaphore lock

External scheduling:

void P() {
	if(counter == 0) {
		_Accept(V) {}
	}
 
	counter--;
}
 
void V() {
	counter++;
}

Internal scheduling:

uCondition bench;
 
void P() {
	if(counter == 0) {
		bench.wait();
	}
 
	counter--;
}
 
 
void V() {
	bench.signal();
	counter++;
}

Internal scheduling with barging, using only routines wait() and signalAll():

int tickets = 0;
int servings = 0;
 
void P() {
	unsigned int myticket = tickets;   // select ticket
	ticket++;                          // advance ticket for next barger
	while(myticket != serving) wait(); // my turn to go?
}
 
void V() {
	serving++;
	signalAll();
}

Automatic signal:

AUTOMATIC_SIGNAL;
 
void P() {
	WAITUNTIL(counter != 0, , )
	counter--;
}
 
void V() {
	counter++;
	EXIT()
}

Administrator: