CS162 Homework #1 Solution

Last updated February 9, 2001 by Matt Welsh, mdw@cs.berkeley.edu

This is a trace of the operations which occur when running the code in Homework assignment #1. I have labelled the "interesting" features of this trace. Text which appears in blue indicates calls which are made with interrupts disabled. (Can you see why interrupts are disabled for these calls?)

See if you can trace through each of the calls shown here and understand why the order is this way. Of course, also let me know if I made a mistake in the following -- I did this trace by hand!

Matt

Ready queue Current thread Current method call
    Startup
NULL main CALL KThread.SelfTest2()
NULL main CALL Runnable.Runnable() /* Create myrunnable1 */
NULL main RETURN FROM Runnable.Runnable()
NULL main CALL Runnable.Runnable() /* Create myrunnable2 */
NULL main RETURN FROM Runnable.Runnable()
NULL main CALL KThread.KThread(myrunnable1)
NULL main CALL KThread.KThread()
NULL main CALL TCB.TCB()
NULL main RETURN FROM TCB.TCB()
NULL main RETURN FROM KThread.KThread()
NULL main RETURN FROM KThread.KThread(myrunnable1)
NULL main CALL KThread.setName("child 1")
NULL main RETURN FROM KThread.setName("child 1")
NULL main CALL KThread.KThread(myrunnable2)
NULL main CALL KThread.KThread()
NULL main CALL TCB.TCB()
NULL main RETURN FROM TCB.TCB()
NULL main RETURN FROM KThread.KThread()
NULL main RETURN FROM KThread.KThread(myrunnable2)
NULL main CALL KThread.setName("child 2")
NULL main RETURN FROM KThread.setName("child 2")
    Forking thread 1
NULL main CALL KThread.fork() for t1
NULL main CALL Machine.interrupt().disable()
NULL main RETURN FROM Machine.interrupt().disable()
NULL main CALL TCB.start(new Runnable() for KThread.runThread())
NULL main RETURN FROM TCB.start()
NULL main Call KThread.ready() on t1
NULL main CALL readyQueue.waitForAccess(this) /* Places t1 on readyQueue */
t1 main RETURN FROM readyQueue.waitForAccess(this)
t1 main RETURN FROM KThread.ready()
t1 main CALL Machine.interrupt().restore()
t1 main RETURN FROM Machine.interrupt().restore()
t1 main RETURN FROM KThread.fork()
    Forking thread 2
t1 main CALL KThread.fork() for t2
t1 main CALL Machine.interrupt().disable()
t1 main RETURN FROM Machine.interrupt().disable()
t1 main CALL TCB.start(new Runnable() for KThread.runThread())
t1 main RETURN FROM TCB.start()
t1 main Call KThread.ready() on t2
t1 main CALL readyQueue.waitForAccess(this) /* Places t2 on readyQueue */
t1, t2 main RETURN FROM readyQueue.waitForAccess(this)
t1, t2 main RETURN FROM KThread.ready()
t1, t2 main CALL Machine.interrupt().restore()
t1, t2 main RETURN FROM Machine.interrupt().restore()
t1, t2 main RETURN FROM KThread.fork()
    Main yields
t1, t2 main CALL KThread.yield()
t1, t2 main CALL Machine.interrupt().disable()
t1, t2 main RETURN FROM Machine.interrupt().disable()
t1, t2 main CALL currentThread.ready()
t1, t2 main CALL readyQueue.waitForAccess(this) /* Places main on readyQueue */
t1, t2, main main RETURN FROM readyQueue.waitForAccess(this)
t1, t2, main main RETURN FROM currentThread.ready()
t1, t2, main main CALL KThread.runNextThread()
t1, t2, main main CALL readyQueue.nextThread() /* Pops t1 from ready queue */
t2, main main RETURN FROM readyQueue.nextThread()
t2, main main CALL nextThread.run()
t2, main main CALL Machine.yield() /* Just a housekeeping function */
t2, main main RETURN FROM Machine.yield() /* Just a housekeeping function */
t2, main main CALL currentThread.saveState()
t2, main main RETURN FROM currentThread.saveState()
t2, main main CALL tcb.contextSwitch();
    Thread 1 gets control
t2, main t1 CALL KThread.runThread()
t2, main t1 CALL KThread.begin()
t2, main t1 CALL KThread.restoreState()
t2, main t1 RETURN FROM KThread.restoreState()
t2, main t1 CALL Machine.interrupt().enable()
t2, main t1 RETURN FROM Machine.interrupt().enable()
t2, main t1 RETURN FROM KThread.begin()
t2, main t1 CALL myrunnable1.run()
    Thread 1 yields
t2, main t1 CALL KThread.yield() /* Inside myrunnable1.run() */
t2, main t1 CALL Machine.interrupt().disable()
t2, main t1 RETURN FROM Machine.interrupt().disable()
t2, main t1 CALL currentThread.ready()
t2, main t1 CALL readyQueue.waitForAccess(this) /* Places t1 on readyQueue */
t2, main, t1 t1 RETURN FROM readyQueue.waitForAccess(this)
t2, main, t1 t1 RETURN FROM currentThread.ready()
t2, main, t1 t1 CALL KThread.runNextThread()
main, t1 t1 CALL readyQueue.nextThread() /* Pops t2 from ready queue */
main, t1 t1 RETURN FROM readyQueue.nextThread()
main, t1 t1 CALL nextThread.run()
main, t1 t1 CALL Machine.yield() /* Just a housekeeping function */
main, t1 t1 RETURN FROM Machine.yield() /* Just a housekeeping function */
main, t1 t1 CALL currentThread.saveState()
main, t1 t1 RETURN FROM currentThread.saveState()
main, t1 t1 CALL tcb.contextSwitch();
    Thread 2 gets control
main, t1 t2 CALL KThread.runThread()
main, t1 t2 CALL KThread.begin()
main, t1 t2 CALL KThread.restoreState()
main, t1 t2 RETURN FROM KThread.restoreState()
main, t1 t2 CALL Machine.interrupt().enable()
main, t1 t2 RETURN FROM Machine.interrupt().enable()
main, t1 t2 RETURN FROM KThread.begin()
main, t1 t2 CALL myrunnable2.run()
    Thread 2 yields
main, t1 t2 CALL KThread.yield()
main, t1 t2 CALL Machine.interrupt().disable()
main, t1 t2 RETURN FROM Machine.interrupt().disable()
main, t1 t2 CALL currentThread.ready()
main, t1 t2 CALL readyQueue.waitForAccess(this) /* Place t2 on ready queue */
main, t1, t2 t2 RETURN FROM readyQueue.waitForAccess(this)
main, t1, t2 t2 RETURN FROM currentThread.ready()
main, t1, t2 t2 CALL KThread.runNextThread()
main, t1, t2 t2 CALL readyQueue.nextThread() /* Pop t1 from ready queue */
main, t2 t2 RETURN FROM readyQueue.nextThread()
main, t2 t2 CALL nextThread.run()
main, t2 t2 CALL Machine.yield() /* Just a housekeeping function */
main, t2 t2 RETURN FROM Machine.yield() /* Just a housekeeping function */
main, t2 t2 CALL currentThread.saveState()
main, t2 t2 RETURN FROM currentThread.saveState()
main, t2 t2 CALL tcb.contextSwitch();
    Thread 1 gets control back.
Note that main could have been chosen instead - we just chose t1 arbitrarily to make the order of events easier to follow. In fact, t2 could have been chosen next as well! It's all up to the scheduler.
main, t2 t1 RETURN FROM tcb.contextSwitch();
main, t2 t1 CALL currentThread.restoreState()
main, t2 t1 RETURN FROM currentThread.restoreState()
main, t2 t1 RETURN FROM nextThread.run()
main, t2 t1 RETURN FROM KThread.runNextThread()
main, t2 t1 CALL Machine.interrupt().restore(intStatus)
main, t2 t1 RETURN FROM Machine.interrupt().restore(intStatus)
main, t2 t1 RETURN FROM KThread.yield()
main, t2 t1 RETURN FROM myrunnable1.run()
main, t2 t1 CALL KThread.finish()
main, t2 t1 CALL Machine.interrupt().disable()
main, t2 t1 RETURN FROM Machine.interrupt().disable()
main, t2 t1 CALL KThread.sleep()
main, t2 t1 CALL KThread.runNextThread()
main, t2 t1 CALL readyQueue.nextThread() /* Pop t2 from ready queue */
main t1 RETURN FROM readyQueue.nextThread()
main t1 CALL nextThread.run()
main t1 CALL Machine.yield() /* Just a housekeeping function */
main t1 RETURN FROM Machine.yield() /* Just a housekeeping function */
main t1 CALL currentThread.saveState()
main t1 RETURN FROM currentThread.saveState()
main t1 CALL tcb.contextSwitch();
    Thread 2 gets control back.
(Note that main could have been chosen instead.)
main t2 RETURN FROM tcb.contextSwitch();
main t2 CALL currentThread.restoreState()
main t2 RETURN FROM currentThread.restoreState()
main t2 RETURN FROM nextThread.run()
main t2 RETURN FROM KThread.runNextThread()
main t2 CALL Machine.interrupt().restore(intStatus)
main t2 RETURN FROM Machine.interrupt().restore(intStatus)
main t2 RETURN FROM KThread.yield()
main t2 RETURN FROM myrunnable2.run()
main t2 CALL KThread.finish()
main t2 CALL Machine.interrupt().disable()
main t2 RETURN FROM Machine.interrupt().disable()
main t2 CALL KThread.sleep()
main t2 CALL KThread.runNextThread()
main t2 CALL readyQueue.nextThread() /* Pop main from ready queue */
NULL t2 RETURN FROM readyQueue.nextThread()
NULL t2 CALL nextThread.run()
NULL t2 CALL Machine.yield() /* Just a housekeeping function */
NULL t2 RETURN FROM Machine.yield() /* Just a housekeeping function */
NULL t2 CALL currentThread.saveState()
NULL t2 RETURN FROM currentThread.saveState()
NULL t2 CALL tcb.contextSwitch();
    Main gets control back
NULL main RETURN FROM tcb.contextSwitch();
NULL main CALL currentThread.restoreState()
NULL main RETURN FROM currentThread.restoreState()
NULL main RETURN FROM nextThread.run()
NULL main RETURN FROM KThread.runNextThread()
NULL main CALL Machine.interrupt().restore(intStatus)
NULL main RETURN FROM Machine.interrupt().restore(intStatus)
NULL main RETURN FROM KThread.yield()
NULL main RETURN FROM KThread.SelfTest2() /* That's all we're going to show! */