cs110 Practice Final 1
cs110 Practice Final 1 PROBLEM 1 1a. MAIN C: 0
SIG: h1
PID: KID
C: 1
wait on KID.
done.
counter = 1
done.
KID C: 0
SIG: h1
PID: 0
SIG: H2
PID: GK
C: 30
Print: counter = 30
C: 31
wait on GK
KID killed! …h2
C: 20031
h1
C: 27031
print: counter = 27031
kill -> GK
still waiting on GK.
done.
print: counter = 27031
exit.
GK C: 0
SIG: h1
PID: 0
SIG: H2
PID: 0
C: 500
Print: counter = 500
SIG: h1
kill -> KID
GK killed!… h1
C: 7500
print: counter = 7500
exit.
Therefore, the last line should read counter = 1
1b. the first two lines could be switched. There’s no constraint on them. Otherwise, constrained.
1c. The 7500 line might be missing. The grandchild is not hanging around waiting for a signal. It might just exit first.
PROBLEM 2 ERROR: They used a semaphore, not a mutex, for reviewingLock ERROR: mutex for global studentsLeft!
static struct ta { mutex attentionLock;
semaphore workToDo(0);
mutex reviewingLock;
int numRaceConditions;
} tas[kNumTAs];
semaphore powerOutlets(kNumPowerOutlets); int studentsLeft = kNumstudents;
void ta(size_t id) { while (true)
tas[id].reviewingLock.lock();
tas[id].workToDo.wait();
if (studentsLeft == 0) break;
tas[id].numRaceConditions = review();
tas[id].reviewingLock.unlock();
grade(); }
}
void student() { int errors;
int rounds = 0;
powerOutlets.wait();
while (true) {
rounds ++;
debug();
int ta = random();
tas[ta].attentionLock.lock();
tas[ta].worktoDo.signal();
tas[ta].reviewingLock.lock();
errors = tas[ta].numRaceConditions;
tas[ta].reviewingLock.unlock();
tas[ta].attentionLock.unlock();
if (errors == 0 || rounds == 5) break;
}
if (errors == 0) squeal();
submit();
powerOutlets.signal(); studentsLeft —;
if (studentsLeft == 0) {
for (ta t:tas) ta.workToDo.signal();
}
}
PROBLEM 3 [already did most of this in lab]
PROBLEM 4 ERROR: Need a mutex on rss so we don’t interleave string processing. ERROR: Semaphore.wait blocks until the semaphore value is 0.
function<void(void)> DNSServer::buildRequestHandler(int client) {
return [this, client] { // note that we’re returning a thunk! that’s okay
sockbuf rsb(client);
iosockstream rss(&rsb);
vector
vector
for (auto sr:slaveRequests) {
const string& address = sr.first;
const vector
outboundRequests.schedule(buildRequestIssuer(sem,address, names, responses));
}
sem.wait();
writeLines(rss, responses); rss.close();
} }
function<void(void)> DNSServer::buildRequestIssuer(semaphore sem, string& address, vector
sockbuf csb(createClientSocket(address));
iosockstream css(&csb);
writeLines(css, names); for (string response: pullAllNames(css)) responses.push_back(response);
csb.close();
sem.signal(); }
}
function writeLines(iosockstream& ss, vector
ss « “\n”; }
PROBLEM 4 SHORT ANSWERS b. Work done on the main thread blocks other incoming requests. The work to be done here depends on other servers, over which we have little control.
c. We need some balance between accepting new jobs and completing existing jobs. Otherwise, we might get overcommitted accepting jobs and be unable to efficiently fulfill them.
d. Delegation. For DNSServer, each server resolves one step, and then hands the work off to someone else. In pathname resolution, each inode knows how to resolve one pathname token, and then hands resolution off to another inode.
e. This application collates requests to many servers, so we can expect threads to spend most of their time waiting. We can parallelize the wait time by using a lot of threads. It would be bad to have so many threads in an application where threads are hard at work, like farm.
ERROR: Better to use network-bound, CPU-bound terms.
PROBLEM 5 SHORT ANSWERS a. Multiprocess pro: better parallization across cores Multiprocess con: would have required more work to share global data like blacklists
b.
- threads: one process appears to be many
- filesystem: potentially many drives appear as one
- mapper, reducer: one function invocation used many times
- processes: (one) core appears to be doing many tasks at once
- ssh: many computers appear to be in my one shell
c.
- system calls
- function calls
- mutexes