1

1. September 18

1.1. Introduction Assessment
1. Explain the difference between user-mode operation and kernel- mode operation and why these different modes are required.
2. An operating system comprises many components - the low-level kernel, device drivers, managers etc. None of these are resident in the machine when it is powered off. Outline how these are 'loaded' into a machine when it is powered on or reset.

3. Explain what must be done to convert an OBJECT file into an EXECUTABLE file (begin by defining these two terms)

4. Explain what a stack frame is, how it is created and how it operates.

1.2. "A common mistake people make when trying to design something completely foolproof is to underestimate the ingenuity of complete fools." - D. Adams

"He who asks is a fool for five minutes; he who does not ask remains a fool forever." - Anonymous Chinese Proverb

program:process as class:object
process states and transitions
PCBs and PIDs.
process scheduling (queueing diagrams)
manipulating processes

Due date Wednesday September 18, 2002 10:00
Maximum grade 30
Instructions: Install the TCL/Tk Interpreter and execute the jassem.tlc program that simulates assembly code execution. It will ask you to load a program and you have 5 to choose from (with .jas extentions). Review the lecture notes linked in the calendar entry. Presumably you could now program in this assembly language and construct your own source file. Describe the format that source files for this simulation must take (extend the lecture notes). Confirm your assertions by seeing what happens when you change the structure of any of the given source files. Turn in a report of what you learned and how you verified it.

2. September 23

2.1. "The sooner you get behind in your work, the more time you have to catch up." - Anonymous

I have scheduled about 2 days per chapter or one week each. When you miss a day you are responsible for picking up on your own what was talked about in class. There is a homework assignment for each class period so you should always be doing something to get ready for class.

You will need your Java book and you might refresh yourself by reading through Appendix A. We will generally be modifying programs that the author supplies and using the language constructs that he has introduced, such as the Thread class. However, he does not include Threads in the appendix, but this should not be your first encounter with the class. Email me or use the discussion group to get Java questions resolved.

Chapter 4 is concerned with internal representation of processes and how the OS manipulates this representation.
It then introduces "light-weight processes" with the concept of Threads of execution.
in either case we can consider cooperating processes and how they communicate.

Assignment Due date Monday September 23, 2002 10:00
Maximum grade 30
Instructions: You have made the shared buffer and message passing programs run. Now make the following changes to the program, run them, and report what you find:

1. Add a timer to the programs so that each will stop after 30 seconds. Note that the Server does nothing but start the Consumer and Producer threads when it is created. You will need to invent a way to stop these threads. They each run infinite loops, so you can initiate a timer to end the threads. However, what happens then?

2. When the Consumer and Producer objects exit, let each print how much was consumed (produced) and how many times there was nothing to consume

3. September 25

3.1. "The person who says it cannot be done should not interrupt the person doing it." - Anonymous Chinese Proverb

This is a short chapter that provides some details to the introduction of threads in chapter 4. The author's slides inserted the Solaris discussion (5.5) into chapter 4 by mistake. The only new materials is in 5.6 where the details of Java threads and operations on threads are discussed.

Your last JAVA exercise sought to implement a way to break out of the infinite while loops that both the Consumer and Producer objects enter when their threads start. Let's consider the possible approaches to this problem:

There are four classes: Server contains main() and creates the Consumer and Producer objects and starts their threads. Server also creates the buffer or mailbox object and passes the object to each of the Producer and Consumer objects. One approach is for the Server to kill the Producer and Consumer thread that it creates.

It should be intuitive that server and consumer and producer run on separate threads. How do these threads end? User threads end when they finish executing the method that called them into existence (main() for server, run() called by start for threads). Therefore the server thread exits as soon as a new server is created (the last statement in main() ), leaving only two threads going.
once started, neither consumer or producer ever exit their run() methods so the program runs until the user aborts the JVM.
to kill the runaway treads, one suggestion was for Server to start a java.util.Timer(http://java.sun.com/docs/books/tutorial/essential/threads/timer.html ). Timer objects run on individual threads, and when their setting is reached they execute a TimerTask object (whence they are done or else they reset themselves). While the Timer object is running, other threads can call its schedule method and schedule other TimerTasks to be performed at specific or periodic intervals. Thus, Timers could run forever (Timer objects have a cancel() method so that they can be killed).
So the Server starts the consumer and producer threads and starts a timer thread that will execute kill threads on the producer and consumer when its setting is reached (and then exits). The timer kills consumer and producer, and since that was its only task, it exits, and the JVM has no running processes, so it exits.

a second idea was to use java.swing.Timer (http://java.sun.com/docs/books/tutorial/uiswing/misc/timer.html ). When this timer goes off, an action listener is notified and performs the response required. The timer runs on the the JVM event thread and the user can start and stop the timer and change its alarm setting or set it to repeat. The user can add or remove ActionListeners. The user cannot kill the timer, only turn it off (or empty the list of Listeners so that nothing happens when it triggers). The question is what should the actionListener object do? One possibility is to kill the consumer and producer threads. Once the timer is initialized by Server, the server thread exits, and then when the consumer and producer threads are killed, there will be no more user processes, so the JVM will stop.
What happens when a thread is killed? Its context block is destroyed, returning its local data to the system. Thus there is no opportunity for the process to put its affairs in order. Killing is a clumsy way to break out of an infinite loop.
Since in either case the timer object runs on a separate thread, its choices are to kill the external process or to communicate via data that the external process will examine when it is executing.

If the TimerTask object or the ActionListener object are external to the consumer and producer objects then some global data must be created for all to share.
TimerTask objects and ActionListener objects are usually anonymous inner classes that share the outer class's data, so it is feasible to let consumer and producer create the timers and thus give them access to local data.
In either case, the common data could be used to control the while loop (a boolean flag initially true that is set to false when the timer goes off). The goal of breaking an infinit while loop is acomplished by making while (true) into while (condition).
you should have notices the message passed from producer to consumer is derived from a Date object so that you can observe the time differential between production and consumption. Instead of initializing a Timer object and an anonymous class in the constructor method, you can just initialize a local variable with the time in the future that you want the while loop to exit. The while loop is then controlled by obtaining the current time and comparing it to the exit time (exactly what the Timer classes do!). The getTime() method of Date gives you a millisecond count from the system clock as a long integer, to which you can add the fixed number of milliseconds to obtain the exit count.

Revised due date because you are behind.
Due date Sunday September 29, 2002 10:00
Maximum grade 50
Instructions: You have introduced yourself to the assembly language and the assembly simulator. Now I'd like to have you modify the fact4.jsm program which demonstrates recursion (multiple stack frames) so that instead of computing 4! you compute fib6, the sixth fibinacchi number, 8 (1,1,2,3,5,8,....). The recursion is not tail recursion but the following: fib(n)= fib(n-1) + fib(n-2) where fib(1)=1 and fib(2)=1.

Your main routine will start by loading 6 into register 0 and then it will make a call to subroutine fib copying the contents of register 0 to the stack as a parameter, and fib will leave its value on the stack in place of the parameter when it returns.

The logic of fib will be to test to see if the parameter is 1 or 2, and if so, to return 1 in the parameter location. If not, fib must make two calls to fib and add the two results. Therefore it needs to push two variables on the stack, n-1 and n-2, and jsr to fib. Upon return the contents of its two stack locations must be exchanged and another call to fib made. Upon return the two stack locations must be added and the sum placed in the original parameter location before returning. Upon return to main the parameter must be retrieved and left in register 0 (where the original 6 has long since been overwritten).

4. September 30

4.1. "The first step in fixing a broken program is getting it to fail repeatably (on the simplest example possible)." - T. Duff

excerpt from Inside the Java Virtual Machine
The Architecture of the Java Virtual Machine
In the Java virtual machine specification, the behavior of a virtual machine instance is described in terms of subsystems, memory areas, data types, and instructions. These components describe an abstract inner architecture for the abstract Java virtual machine. The purpose of these components is not so much to dictate an inner architecture for implementations. It is more to provide a way to strictly define the external behavior of implementations. The specification defines the required behavior of any Java virtual machine implementation in terms of these abstract components and their interactions.

Figure 5-1 shows a block diagram of the Java virtual machine that includes the major subsystems and memory areas described in the specification. As mentioned in previous chapters, each Java virtual machine has a class loader subsystem: a mechanism for loading types (classes and interfaces) given fully qualified names. Each Java virtual machine also has an execution engine: a mechanism responsible for executing the instructions contained in the methods of loaded classes.

Figure 5-1. The internal architecture of the Java virtual machine.
When a Java virtual machine runs a program, it needs memory to store many things, including bytecodes and other information it extracts from loaded class files, objects the program instantiates, parameters to methods, return values, local variables, and intermediate results of computations. The Java virtual machine organizes the memory it needs to execute a program into several runtime data areas.

Although the same runtime data areas exist in some form in every Java virtual machine implementation, their specification is quite abstract. Many decisions about the structural details of the runtime data areas are left to the designers of individual implementations.

Different implementations of the virtual machine can have very different memory constraints. Some implementations may have a lot of memory in which to work, others may have very little. Some implementations may be able to take advantage of virtual memory, others may not. The abstract nature of the specification of the runtime data areas helps make it easier to implement the Java virtual machine on a wide variety of computers and devices.

Some runtime data areas are shared among all of an application's threads and others are unique to individual threads. Each instance of the Java virtual machine has one method area and one heap. These areas are shared by all threads running inside the virtual machine. When the virtual machine loads a class file, it parses information about a type from the binary data contained in the class file. It places this type information into the method area. As the program runs, the virtual machine places all objects the program instantiates onto the heap. See Figure 5-2 for a graphical depiction of these memory areas.

Figure 5-2. Runtime data areas shared among all threads.

As each new thread comes into existence, it gets its own pc register (program counter) and Java stack. If the thread is executing a Java method (not a native method), the value of the pc register indicates the next instruction to execute. A thread's Java stack stores the state of Java (not native) method invocations for the thread. The state of a Java method invocation includes its local variables, the parameters with which it was invoked, its return value (if any), and intermediate calculations. The state of native method invocations is stored in an implementation-dependent way in native method stacks, as well as possibly in registers or other implementation-dependent memory areas.

The Java stack is composed of stack frames (or frames). A stack frame contains the state of one Java method invocation. When a thread invokes a method, the Java virtual machine pushes a new frame onto that thread's Java stack. When the method completes, the virtual machine pops and discards the frame for that method.

The Java virtual machine has no registers to hold intermediate data values. The instruction set uses the Java stack for storage of intermediate data values. This approach was taken by Java's designers to keep the Java virtual machine's instruction set compact and to facilitate implementation on architectures with few or irregular general purpose registers. In addition, the stack-based architecture of the Java virtual machine's instruction set facilitates the code optimization work done by just-in-time and dynamic compilers that operate at run-time in some virtual machine implementations.

See Figure 5-3 for a graphical depiction of the memory areas the Java virtual machine creates for each thread. These areas are private to the owning thread. No thread can access the pc register or Java stack of another thread.

Figure 5-3. Runtime data areas exclusive to each thread.

Figure 5-3 shows a snapshot of a virtual machine instance in which three threads are executing. At the instant of the snapshot, threads one and two are executing Java methods. Thread three is executing a native method.

In Figure 5-3, as in all graphical depictions of the Java stack in this book, the stacks are shown growing downwards. The "top" of each stack is shown at the bottom of the figure. Stack frames for currently executing methods are shown in a lighter shade. For threads that are currently executing a Java method, the pc register indicates the next instruction to execute. In Figure 5-3, such pc registers (the ones for threads one and two) are shown in a lighter shade. Because thread three is currently executing a native method, the contents of its pc register--the one shown in dark gray--is undefined.

Exercise 5.9 on p. 132 asks that you revise the MessageQueue class on page 108.
The encapsulated storage structure will be changed to add a SIZE constraint (we could replace the Vector with a circular array but it is not necessary). The mailbox instance will now need to keep a count of how many elements it has to know if it is full. send() and received() have to be rewritten so that send cannot be invoked when the mailbox is full or the received invoked when the mailbox is empty. The author suggests we use suspend() and resume() and he illustrates them in fig 5.9 (ClockApplet). In the shared buffer example the bock was a busy wait. This time we want to free the CPU to execute other threads.

One way to do this is to add methods sendPermission(Producer) and receivePermission(Consumer)to the MessageQueue class. If the mailbox is full, the SP method places the Producer reference in a Vector and suspends the producer thread. Similarly for RP. The receive method is then ammended to resume one suspend consumer. The receive method is also ammended to resume one suspended consumer.

The new methods have signature public void sendPermission(Thread producer) etc. and the call is made immediately before the send: mbox.sendPermission(this);
mbox.send(message);

Deposit your consumer, producer and messagequeue source files in the drop box after testing to see that they work with the Server class. Also deposit a file of your run output and an analysis of what you see there (how well does the program work?).

5. October 2

5.1. "The most likely way for the world to be destroyed, most experts agree, is by accident. That's where we come in; we're computer professionals. We cause accidents." - N. Borenstein

Chapter 6 concerns methods to schedule processes to accomplish sharing, present the user to impression of responsiveness, and minimize wasted time.

6. October 7

6.1. "Good judgment comes from experience; experience comes from bad judgment." - F. Brooks

We got into 6.5 on Real-Time Scheduling last time. Hard real-time systems cannot share resources or depend upon secondary storage access, so such systems are designed to be dedicated (which is why there are so many different computers in automobiles). We will pick up with soft real-time OS considerations and then look at Thread scheduling, particulary in Java.

section 6.8 concerns how to measure and predict how effective a scheduling policy (SJF, FCFS, RR have been discussed) will be given some assumed job characteristics. The author discusses

hypothetical test cases for which the average under each policy can be computed,
Queueing Models that use Little's formula which says that if the system is working, it must be that the average number of processes arriving at the queue equals the average number leaving (it can't be that more leave, and if less leave the queue quickly overflows so there is no steady state). The only question is what is the average queue size (determined by the average wait time and the arrival rate during that period).
simulation in which random rather than determined job streams are fed through the policy simulator and the running averages are observed.

The homework due today involves experimenting with the author's scheduler class: The author provides the code for his round-robin scheduler. You run this scheduler by running TestScheduler. Think about what happens when you do this:

the main method of a TestScheduler object begins to execute on a user thread.
it starts an new thread running a new Schedular object, and then starts three TestThread objects, each runing on its own thread. Five threads are now sharing CPU cycles. Four of these threads are in infinte loops. the main method "adds" each of the TestThread threads to the Schedule object. What does this mean? What does the assembly-level program do to accomplish this? What difference does it make if you DON't add one of the threads to the Schedule object (modify and run the code and compare). The TestScheduler thread ends.
Why does the Schedule thread sleep and none of the other threads do? In the scheduleSleep() method there is a call to Thread.sleep(). Explain why the call to a static method instead of this.sleep() [try the alternative].
Explain the while loop in Scheduler. It does queue.getNext() infinitely. No threads are ever removed from the queue. Under what circumstances will a null be retrieved? Why the test for isAlive()? What happens while the scheduler is asleep?
modify the program so that addThread sets the priority to 3. Describe how the program runs differently.
modify addThread so that the priority is set to 5. How does that change how the program runs?

Do the above experiments and answer the questions posed.

7. October 9

7.1. 'We think too much about effective methods of teaching and not enough about effective methods of learning. No matter how good teaching may be, each student must take the responsibility for his own education." - J. Carolus S.J.

" Any sufficiently advanced technology is indistinguishable from magic." - A. Clarke

Chapter 7 is long and sophisticated. We are learning to deal with concurrency and to understand the intricacies of sharing. Unfortunately, there is no indication that the class has grasped scheduling since homework has not been turned in.

The author illustrates what your programming exercises were intended to reveal (in bounded buffer problems) that when you do not control when code can be interrupted, you can experience problems with shared data. We want to enforce mutual exclusion to solve these problems, but our efforts are hampered by not being able to control when our enforcement will be interrupted, allowing deadlock. The solution is to insure that some operations are NEVER interrupted. We can do this with hardware (special instructions or disabling interrupts).

This chapter presents three classic synchronization problems that make it easier to see the difficulties of enforcing mutual exclusion without encountering deadlock or starvation: Bounded Buffer (what do you do when the buffer is full?), the Reader/Writer problem (how do you prevent Writers from changing data in the middle of a read or writers from overwriting each other?) and the Dining Philosopher problem (how do you avoid deadlock when multiple resources are being acquired in some order?). In trying to solve these problems we illustrate critical sections, locking, semaphores, and monitors.

The homework due today was question answers from chapter 6

8. October 14

8.1. "Every now and then go away, have a little relaxation, for when you come back to your work your judgment will be surer. Go some distance away because then the work appears smaller and more of it can be taken in at a glance and a lack of harmony and proportion is more readily seen." - L. Da Vinci

"One can think effectively only when one is willing to endure suspense and to undergo the trouble of searching." - J. Dewey

Semaphores must be supported in hardware because they must complete an operation on a data item without interruption. One operation is to test and wait if not positive, then decrement, the other is to increment.

9. October 16

9.1. "As long as there were no machines, programming was no problem at all; when we had a few weak computers, programming became a mild problem, and now [1972] that we have gigantic computers, programming has become a gigantic problem. […] As the power of available machines grew by a factor of more than a thousand, society's ambition to apply these new machines grew in proportion, and it was the poor programmer who found his job in this exploded field of tension between the ends and the means. The increased power of the hardware, together with the perhaps more dramatic increase in its reliability, made solutions feasible that the programmer had not dared to dream about a few years before. And now, a few years later, he had to dream about them and even worse, he had to transform such dreams into reality! It is no wonder that we found ourselves in a software crisis" - E. Dijkstra (The Humble Programmer, "ACM Turing Award Lectures: The First 25 Years", Addison-Wesley, 1987, pages 17-32)

Dr. Dijkstra, the inventor of semaphores, died last month.

Today we survey how Java implements cooperating processes by looking at thread synchronization.

10. October 21

10.1. EXAM 1 FOCUS

At this point you should be able to explain the following concepts:

why do we have operating systems?

how do OS differ from one another?
what is POSIX and why are some OS POSIX compliant?
how does Windows 2000 get control of your computer?
how does an OS configure itself?
when an OS is managing the computer, what is it doing?

what is a process?
how does a user process and the OS interact?
how are operating systems designed?

what do the terms kernel, supervisor mode, interrupt, and exception pertain to operating systems?
what is a context switch and how does it occur?
how are processes segregated from each other?

why does the CPU need to be managed by an OS?

what causes a process to block?
how does the CPU process instruction streams?
how does the CPU process an instruction?
how do instructions move from disk to CPU?

how do instructions get to disk?

what do assembly instructions look like and how do they correspond to machine language instructions?
programmers use symbolic addresses, what are these?
what is accomplished in each of the passes of a two-pass assembler?
what does the linking of object files accomplish and how is it done?
what is meant when an object file is relocatable?
what is done when a file is loaded (the loader process is given a file address and a memory location by the OS)?

describe the life-cycle of a process, the different states it cycles through.
what factors are used by the OS to schedule processes?
what data is kept by the OS on each process and how is this data maintained?
what is the difference between cooperating processes and parent/child processes?
how to processes communicate?

what are the characteristics of a communication link?
explain the terms symmetric addressing, port, synchronous and asynchronous, zero capacity buffer.
what is the bounded buffer problem and why is it a problem?

what is a thread of execution?
what is multithreading and why do operating systems support it?
how is thread execution managed?

what are the different kinds of job scheduling?
what are the goals of CPU scheduling and what data is used by the scheduler to pursue these goals?
describe 4 scheduling algorithms and give the advantages and weakness of each.
what is multilevel feedback-queue scheduling?
what complications arise when you try to schedule multiple processors or to satisfy real-time constraints?
what support does Java provide for threads and how does it schedule their execution?

As a consequence of your completing the homework exercises you should be able to trace and comment a JAS assembly program or a Java program dealing with buffer/message passing and thread scheduling. Expect to define several terms (any bolded words in the text). About 25% of the exam will be objective, the rest short answer.