Solutions15-410, Spring 2007 Homework Assignment 1.1 Stack Madness (10 pts.)This setup is halfway between a real stack and genuine heap-allocated frames. In some sense it suffers froman ISA with too few registers, since it would be nice to have one register pointing to parameters in the callingframe and another pointing to locals in the called frame. But having a “more real” setup would have madethe code more complicated.1.1 Entry proto col (7pts).globl frametops.globl framenum######################################################################## "function entry protocol" (use only caller-save registers at first)# N.B. "There is more than one way to do it"#######################################################################movl framenum, %eax # value of C’s framenummovl frametops(,%eax,4), %eax # value of C’s frametops[framenum]movl %esp, (%eax) # save caller’s %espmovl %eax, %esp # assume new %esp, and...pushl %ebp # ...save caller’s %ebpmovl %esp, %ebp # %ebp ready to address our localssubl $1, framenum # your soln might have this earlier# depending on your interpretation######################################################################## compiler or human inserts function body here# note clever omission of references to params#######################################################################1.2 Exit protocol (2pts)# "function exit protocol" (don’t whack %eax)addl $1, framenummovl %ebp, %esp # point to caller’s %ebppopl %ebp # restore caller’s %ebppopl %edx # obtain caller’s %esp...movl %edx, %esp # ...and assume it...# (I wonder what "popl %esp" does?)ret # CALL saved ret addr on caller’s stack1.3 Restrictions (1pt)No function can have more than 4088 bytes of local variables and scratch space (4084 if the function callsanother).2 Get to work! (10 pts.)2.1 How to add preforking to thrgrps (9pts)The basic idea is for thrgrpprepare() to pre-thr create() a bunch of threads which enqueue themselvesinside the threadgroup so that thrgrp create() can give the one at the head of the queue its func and arg1and start it running.Probably the “approach of least typing” involves:• To the thrgrp group t struct add a “prefork queue” analogous to the existing “zombie queue.” Theprefork queue will be protected by the same mutex currently covering the rest of the struct. Elementsof the queue will be the thrgrp tmp data t arm of the union, with the interesting fields (func andarg) not yet filled in.• Also add to the thrgrp group t struct a semaphore, initialized to zero, which tracks the number ofentries at the head of prefork queue which contain valid func and arg fields.• The number of blank elements in the queue will be tracked by an int, pf nblank.The system operates as follows:• The thrgrp prepare() function locks the thrgrp, adds n “blank” prefork blobs to the tail of the preforkqueue, adds n to pf nblank, and unlo cks the thrgrp. It then uses thr create() to launch n threadsrunning thrgrp prefork bottom(&eg) (that is, the threads receive a pointer to the threadgroup theyhave been pre-forked into).• The thrgrp prefork bottom() function wait()s on the semaphore, locks the thrgrp, removes theprefork elem ent at the head of the queue, and unlocks the thrgrp. Then it can invoke the existingthrgrp bottom().• Now thrgrp create() can operate as follows. First, lock the thrgrp mutex. If pf nblank is positive,the prefork queue contains at least one not-filled-in element (and a corresponding thread either hasalready slept on the semaphore or will “soon”). Fill in the first blank queue element, decrementpf nblank, drop the mutex, and signal the semaphore. If pf nblank is less than one, there are noblank prefork elements on the queue, so drop the thrgrp mutex and just spawn a thread the old way.Note that this solution is less than optimal in the sense that the semaphore provides thread queueing butdoes not in parallel queue the data the threads nee d to operate, so two queues exist when one could suffice.Semaphores are like that.2.2 A further extension? (1pt)It is possible for thrgrp bottom() and thrgrp join() to cooperate so that logically-exiting worker threadsdon’t actually exit but instead return themselves to the prefork queue. This would add noticeable com-plexity, since one might wish to cap the size of the prefork queue and would regardless need to handle thecase of destroying a thread group which still contained invisible threads (so far we have assumed that acall to thrgrp prepare() will be followed by an appropriate number of thrgrp create() calls, so thatthrgrp destroy group() could include a check that the prefork queue is empty instead of needing to dealwith cleaning up preforked threads).3 Plumbers (4 pts.)3.1 First state (2 pts)This state is not safe.Given the resources currently held by each plumber and the resources currently unalloc ated, no plumbercan assuredly run to completion. In particular, no hammers are available, which means that any plumberrequesting a hammer will sleep. But since each plumber’s pre-declared maximum usage includes one morehammer than he or she currently holds, every plumber is allowed to make a sleep-inducing hammer request.If they all do, a deadlock will result. Since there is no “progressor,” there can be no safe sequence, so thestate is unsafe.Observe that the system is not deadlocked and would not necessarily enter a deadlock even if two of theplumbers went to sleep. It is perfectly pos sible for two plumbers to request hammers and go to sleep butfor the third plumber (which would need to be Bob or Cameron) to finish the current job and relinquish alltools.23.2 Second state (2 pts)This state is safe (even though no resources are currently free!) because B ob has all of his resources and cancomplete his current job without slee ping. Bob’s current holdings are e nough for Cameron to acquire a fullset of tools, complete a job, and release tools. Alice’s situation is interesting—on the one hand, she alreadyhas a full set of tools and can complete her job without sleeping. On the other hand, her set of tools isn’tenough to satisfy Cameron, and doesn’t help Bob, so her completion doesn’t help us find a safe sequence.One s afe sequence is “Bob, then Cameron, then Alice,” so the system is in a safe state (there are othersafe sequences, but we need only one to constructively prove
View Full Document
Unlocking...