----------------------------- CS571 TECHNICAL NOTE (2/26/02) ----------------------------- The commentary below addresses several issues you raised in your feedback slips. ANALYZING ELEVATOR SIMULATOR RESULTS One objective of the P1 project is to simulate the elevator system under different load conditions and elevator policies, then draw conclusions about the effectiveness of the policies as a function of load. When doing this, you need to lay out an "experimental design" -- a set of test cases that cover all the important values of parameters. Then you run the simulator for each test case and measure the metrics. Finally you look to see how the metrics vary with the different parameters. Here is an example. You observe that the number of threads N and the passenger thread delay D affect the load on the elevator. You decide you want to test for N=5,10,15,20,30,40,50 and for D=1,2,5,10 mins. That is a total of 28 test runs. For each test run you will measure the queueing time and the ride time (the total service time is the sum of these two). You need to run the simulator long enough that you have meaningful results. You decide to run the simulator until 200 rides are completed in each test case. When you're done, you can plot the queueing time and the ride time versus N and versus D. You can also try a few test runs with 300 or 400 rides to see if there are any significant changes in the averages. You repeat the above with a simulator modified for a second policy. You can compare policies by plotting the data on the same graph. KEEPING THE ELEVATOR MOVING It is indeed important to arrange for your elevator thread to keep moving when there are requests. The solution outlined in the class slides for 2/19/02 shows the elevator thread waiting on a condition "timetoMove" and the passenger threads signaling that condition whenever they place any request (CALL or SELECT). The signals have no effect if the elevator thread is already moving at the time of the signal. SYNCHRONIZING JAVA THREADS Java does not have full monitors, in particular condition variables. One of the technical problem with monitors is that they lock the threads to attain their mutual exclusion. If there are many threads using the monitor, they can encounter significant waits at the monitor lock even if they are not actually contending for the same resources inside the monitor. To reduce contention, it is better to place the locks on the individual objects and let threads lock up only the objects they need. This is the basis of the Java strategy. Since Java does not have condition variables, you need to simulate them. Examples of this are shown at the end of the "Monitors" slides in the Art of OS slide book. One of the annoyances of Java is that there is one wait() operation and no way to distinguish what condition a thread is waiting for. The notify() operation awakens a random thread from among those waiting. That thread needs to check to see if the condition it was waiting for is now true, otherwise it waits again. Many times you will use notifyAll(), which will release all waiting threads, which will all check their conditions, and only those whose conditions are satisfied can proceed. It is not as elegant as the condition variable method, but it does work. LINKING THE TOP LEVELS Here is the little story I told that links the functions of the top levels of the OS. The validated user types a command to the shell. The shell parses the command and creates one or more virtual machines executing the individual command names found in the command line. The shell links these VMs by connecting their IN and OUT ports with pipes and putting any specified info objects at the beginning and end of the pipeline. The shell sets the VMs into execution with its COMPUTE command and sleeps until all have EXITed. The shell then tears down the pipeline and returns to a prompt, awaiting the next user command. In the process of doing all this, the user is faced with managing and protecting a large number of handles -- for files (potentially thousands), pipes (tens), devices (hundreds), VMs (tens). The directory system is used to permit users to assign their own names to objects and to store the associations between those names and the system's handles for them. The internals of directories are hidden from users, hence they cannot modify or tamper with handles. ----------------------------- CS571 TECHNICAL NOTE (2/19/02) ----------------------------- Your feedback told me this was a quieter week for you. You brought up two technical issues. Responses are below. WAIT/SIGNAL OPERATION IN MONITORS The wait and signal within monitors do not use semaphores and do not work the same as the wait/signal operations on semaphores. Monitor wait/signal are for synchronizing on conditions. A condition variable, say X, stands for a condition. The statement X.wait means wait until the condition X becomes true. The statement X.signal means tell one thread (if any) waiting for X to become true, that X has become true. X.signal has no effect if no thread is waiting on condition variable X. The programmer of a thread issuing X.signal must be sure to prove that condition X is true at the time X.signal is performed. To assure that the recipient thread can act while X is still true, the signaler is suspended immediately and the recipient is resumed immediately. The signaller will continue only after the recipient has acted on the signal and left the monitor. Note how the scheduling works here. First, when a thread enters the monitor, the entire monitor is locked and no other thread can enter the monitor. Second, when a thread in the monitor executes a signal, it is immediately suspended in favor of the recipient. Third, when a thread leaves the monitor (via a return from its called procedure), the monitor lock is released. The next thread to execute in the monitor will be (a) a thread that has been delayed at a signal operation as above, or else (b) an external thread trying to call a monitor procedure. PAUSE AFTER CALL IN ELEVATOR PROBLEM The passenger thread outlined in my monitor for the elevator controller has the subsequence "CALL(i,d); SELECT(j)". Someone in class noted that when CALL returns, the monitor is unlocked and it is possible for the elevator car thread to enter the monitor before this passenger thread calls SELECT. Does this present a problem? It should not. Even if these people have not yet made their selections before the car starts moving, the controller has already taken into account their intentions expressed as up or down requests. If a passenger takes more than 15 seconds between CALL and SELECT, the car will make it to another floor; and because it does not see the passenger's selection, it may reverse direction. This sort of behavior occurs in real elevators and can cause annoyance. REVISION OF ELEVATOR MONITOR After the class discussion, I revised the monitor description to clarify the answers to some of your questions. I added a linkage between entering passengers and their selections; the internal variable "sel" counts how many passengers have been admitted to the car (at a given floor) but have not yet made their selections. The SELECT procedure signals the CHECKFLOOR procedure when all those selections are made, allowing CHECKFLOOR to return to the car thread with a correct direction. The new condition variable "selectionsMade" is used for this synchronization. See the February 19 slides, which have now been updated with these changes. ----------------------------- CS571 TECHNICAL NOTE (2/12/02) ----------------------------- We spent half the class on the deadlock issue. The purpose of the discussion was to give an overview of the deadlock problem and reveal the essential distinctions. For more detail, including deadlock examples and deadlock detection algorithms, read the Deadlock chapter in the book (Ch 8 of Applied Operating Systems Concepts or Ch 3 of Tanenbaum's Modern Operating Systems). PREPARATION FOR NEXT CLASS Next class we will visit the upper levels of the operating system: the shell, directories, info-objects, and virtual machines. In preparation for this, read the Unix and Linux case studies at the end of the Silberschatz book, and read the notes on virtual machines linked to the resources section of the CS471 web site. CONCERNS EXPRESSED Most of your concerns this week are focused on time management, getting an elevator control monitor working, and proving that the monitor is correct. Someone said that last week's class was confusing, this week's clear. Thanks. It is good to remember that confusion is a mood in the observer. If you are a confused observer, ask questions and I will help you sort them out. THREADS AND MONITORS Someone asked: do threads call monitor methods? If so, are they passed by reference? The answer to the first question is yes. As a programmer, you deal with procedures which, when executed, control threads. A monitor method call is simply a procedure call. When your thread comes to the procedure call, it invokes the monitor method. The second question is not well formed. Passing by reference refers to passing parameters by passing an address of a memory location in which the parameter is stored. When a thread calls a monitor method, it can pass parameters; whether those are passed by value or reference depends on the declarations you have made in the procedure definition. The calling thread accesses the method by a normal procedure call. Someone asked: is holding a critical section confined to the part of a thread where access is needed, or does it apply to the whole thread? The answer is: yes to both. The critical section code is delimited by the wait(mutex) and signal(mutex) statements on the semaphore mutex. The thread stops and waits if ANOTHER thread is inside the critical section (i.e., executing instructions between the wait and signal statements). The WHOLE thread stops because no part of a thread can operating in parallel with another part of the same thread. CHANGING THE KERNEL Someone asked: can we have experience in particular OS (e.g., Linux) such as changing the kernel? The answer is yes, but it is not part of CS571 to do this. The skill of kernel programming is a more advanced skill -- it's in the level of competent or higher in the field -- and we promise only advanced beginning level of skill from CS571. If you are interested in pursuing this direction, you can get Linux source code and practice writing routines or modifying existing routines. ----------------------------- CS571 TECHNICAL NOTE (2/6/02) ----------------------------- You expressed a number of opinions and questions in your feedback slips. I will respond to the main ones here. THREADS AND SYNCHRONIZATION At first this topic can be confusing. It is inherently a complex subject and it takes time to get used to the subtleties and nuances. The slides on time sharing give an overview of a method to multiplex threads on a single CPU and also to allow threads to stop and wait on semaphores for specific conditions. The slides on synchronization give an overview of a set of common synchronization problems and their solutions, leading up to monitors as the most general approach to programming multi-threaded synchronizations. If you are still confused, I suggest that you review the chapters in the book that deal with synchronization. The book Applied Operating System Concepts (Silberschatz) gives numerous examples of Java code segments that implement various solutions to the synchronization problems. You will find that a second reading will be much more enlightening, now that you are armed with an overview of the subject. Someone asked for more examples of actual implementations, including the details of how they are done. Sure, I could do that, but I don't think that is best use of class time. My objective in class is to give the overviews and make sure you understand the big picture. If I give detailed coverage of implementations, we will not cover everything and many of you will complain that we have lost sight of the big picture. From past experience, I know that most of you would rather study detail at home than have me walk through it line by line in class. As just noted, there are numerous code examples in the book(s). You should have no difficulty seeing all the detail you need there. For those who want to see how the concepts are implemented in particular systems, you will find excellent case studies in the appendices at the end of the book. There's a chapter on Unix, another on Windows. I urge you to look at these chapters. They will help you appreciate how systems designers have put the concepts to work in practice. At the end of the monitors slides, I noted a transformation from the monitor condition variable to the Java synchronized object. In the example, one of the monitor functions is GetUnit:{ if poolsize=0 then nonempty.wait h = "remove unit from pool" return h } With the Java transformations I suggested, you would define a condition "empty" to mean "poolsize=0" and do GetUnit: { while poolsize=0 do wait() h = "remove unit from pool" return h } ReturnUnit(h): { "link h back into pool" notify() return WHAT TO READ, WHEN TO ASK QUESTIONS Several people said they were not sure what to read and asked that I assign reading prior to discussing topics in class. I have anticipated this request. You have to do your part. The syllabus is published on the web page, telling you on which dates we will be covering which topics. You can pre-read the slides corresponding to the upcoming topic and the book chapter that covers the same material. I assume you are mature, successful people with initiative and that you can do this reading without my explicitly saying so. If you have questions about any of this material, you are invited -- urged! -- to ask them by email or in class. One of my objectives is to help you past any confusions you encounter. You need to let me know what they are when they occur. As much as I would like to, I cannot read your mind. WHAT IS IMPLEMENTED WHERE Someone asked which parts of the system are actually implemented in hardware, OS, language support systems, or user applications. Although there are conventions that the OS levels we are discussing are mostly implemented by the OS kernel and hardware, some language support systems and some applications also get involved. Look at the appendices in the book about Unix, Windows, and the other systems. You will see that they don't draw the lines in the same ways and you will find it helpful to see the different approaches to doing the same things. RECEIVING THE SIGNAL Someone asked how a process waiting for a signal actually receives the signal. Someone else asked how execution "flows" when there are multiple threads executing. One of the purposes of the process (and semaphore) abstractions is to let us use language statements to refer to hardware signals. We can pretend that a process runs on its own CPU and does not interact with the other process-CPUs unless it explicitly seeks or sends a signal. At the level of the abstraction, then, "how you send a signal" is simply to place the line "signal(sem)" in your program. And "how to receive" is simply to place the line "wait(sem)." It's the responsibility of the OS implementation to implement the multiplexing and queueing needed to create these illusions. So the thread manager maintains a ready list and uses the clock interrupt and context switch to cycle the ready processes past the CPU, a time slice each. When a process calls "wait(sem)", the thread-manager takes the process off the CPU and puts it in the queue of "sem". When a process calls "signal(sem)" thread-manager moves the process from queue "sem" to the ready list. All these movements are invisible to the users of threads. Does this answer the question?