Problems

[Page 215 (continued)]

1.	Why is multiprogramming central to the operation of a modern operating system?
2.	What are the three main states that a process can be in? Describe the meaning of each one briefly.
	[Page 216]
3.	Suppose that you were to design an advanced computer architecture that did process switching in hardware, instead of having interrupts. What information would the CPU need? Describe how the hardware process switching might work.
4.	On all current computers, at least part of the interrupt handlers are written in assembly language. Why?
5.	Redraw Fig. 2-2 adding two new states: New and Terminated. When a process is created, it is initially in the New state. When it exits, it is in the Terminated state.
6.	In the text it was stated that the model of Fig. 2-6(a) was not suited to a file server using a cache in memory. Why not? Could each process have its own cache?
7.	What is the fundamental difference between a process and a thread?
8.	In a system with threads, is there normally one stack per thread or one stack per process? Explain.
9.	What is a race condition?
10.	Give an example of a race condition that could possibly occur when buying airplane tickets for two people to go on a trip together.
11.	Write a shell script that produces a file of sequential numbers by reading the last number in the file, adding 1 to it, and then appending to the file. Run one instance of the script in the background and one in the foreground, each accessing the same file. How long does it take before a race condition manifests itself? What is the critical section? Modify the script to prevent the race(Hint: use In file file.lock to lock the data file).
12.	Is a statement like In file file.lock an effective locking mechanism for a user program like the scripts used in the previous problem? Why (or why not)?
13.	Does the busy waiting solution using the turn variable (Fig. 2-10) work when the two processes are running on a shared-memory multiprocessor, that is, two CPUs, sharing a common memory?
14.	Consider a computer that does not have a TEST AND SET LOCK instruction but does have an instruction to swap the contents of a register and a memory word in a single indivisible action. Can that be used to write a routine enter_region such as the one found in Fig. 2-12?
15.	Give a sketch of how an operating system that can disable interrupts could implement semaphores.
16.	Show how counting semaphores (i.e., semaphores that can hold an arbitrarily large value) can be implemented using only binary semaphores and ordinary machine instructions.
	[Page 217]
17.	In Sec. 2.2.4, a situation with a high-priority process, H, and a low-priority process, L, was described, which led to H looping forever. Does the same problem occur if round-robin scheduling is used instead of priority scheduling? Discuss.
18.	Synchronization within monitors uses condition variables and two special operations, WAIT and SIGNAL. A more general form of synchronization would be to have a single primitive, WAITUNTIL, that had an arbitrary Boolean predicate as parameter. Thus, one could say, for example, WAITUNTIL x < 0 or y + z < n The SIGNAL primitive would no longer be needed. This scheme is clearly more general than that of Hoare or Brinch Hansen, but it is not used. Why not? (Hint: think about the implementation.)
19.	A fast food restaurant has four kinds of employees: (1) order takers, who take customer's orders; (2) cooks, who prepare the food; (3) packaging specialists, who stuff the food into bags; and (4) cashiers, who give the bags to customers and take their money. Each employee can be regarded as a communicating sequential process. What form of interprocess communication do they use? Relate this model to processes in MINIX 3.
20.	Suppose that we have a message-passing system using mailboxes. When sending to a full mailbox or trying to receive from an empty one, a process does not block. Instead, it gets an error code back. The process responds to the error code by just trying again, over and over, until it succeeds. Does this scheme lead to race conditions?
21.	In the solution to the dining philosophers problem (Fig. 2-20), why is the state variable set to HUNGRY in the procedure take_forks?
22.	Consider the procedure put_forks in Fig. 2-20. Suppose that the variable state[i] was set to THINKING after the two calls to test, rather than before. How would this change affect the solution for the case of 3 philosophers? For 100 philosophers?
23.	The readers and writers problem can be formulated in several ways with regard to which category of processes can be started when. Carefully describe three different variations of the problem, each one favoring (or not favoring) some category of processes. For each variation, specify what happens when a reader or a writer becomes ready to access the data base, and what happens when a process is finished using the data base.
24.	The CDC 6600 computers could handle up to 10 I/O processes simultaneously using an interesting form of round-robin scheduling called processor sharing. A process switch occurred after each instruction, so instruction 1 came from process 1, instruction 2 came from process 2, etc. The process switching was done by special hardware, and the overhead was zero. If a process needed T sec to complete in the absence of competition, how much time would it need if processor sharing was used with n processes?
25.	Round- robin schedulers normally maintain a list of all runnable processes, with each process occurring exactly once in the list. What would happen if a process occurred twice in the list? Can you think of any reason for allowing this?
	[Page 218]
26.	Measurements of a certain system have shown that the average process runs for a time T before blocking on I/O. A process switch requires a time S, which is effectively wasted (overhead). For round-robin scheduling with quantum Q, give a formula for the CPU efficiency for each of the following: (a) Q = (b) Q > T (c) S < Q < T (d) Q = S (e) Q nearly 0
27.	Five jobs are waiting to be run. Their expected run times are 9, 6, 3, 5, and X. In what order should they be run to minimize average response time? (Your answer will depend on X.)
28.	Five batch jobs A through E, arrive at a computer center at almost the same time. They have estimated running times of 10, 6, 2, 4, and 8 minutes. Their (externally determined) priorities are 3, 5, 2, 1, and 4, respectively, with 5 being the highest priority. For each of the following scheduling algorithms, determine the mean process turnaround time. Ignore process switching overhead. (a) Round robin. (b) Priority scheduling. (c) First-come, first-served (run in order 10, 6, 2, 4, 8). (d) Shortest job first. For (a), assume that the system is multiprogrammed, and that each job gets its fair share of the CPU. For (b) through (d) assume that only one job at a time runs, until it finishes. All jobs are completely CPU bound.
29.	A process running on CTSS needs 30 quanta to complete. How many times must it be swapped in, including the very first time (before it has run at all)?
30.	The aging algorithm with a = 1/2 is being used to predict run times. The previous four runs, from oldest to most recent, are 40, 20, 40, and 15 msec. What is the prediction of the next time?
31.	In Fig. 2-25 we saw how three-level scheduling works in a batch system. Could this idea be applied to an interactive system without newly-arriving jobs? How?
32.	Suppose that the threads of Fig. 2-28(a) are run in the order: one from A, one from B, one from A, one from B, etc. How many possible thread sequences are there for the first four times scheduling is done?
33.	A soft real-time system has four periodic events with periods of 50, 100, 200, and 250 msec each. Suppose that the four events require 35, 20, 10, and x msec of CPU time, respectively. What is the largest value of x for which the system is schedulable?
34.	During execution, MINIX 3 maintains a variable proc_ptr that points to the process table entry for the current process. Why?
35.	MINIX 3 does not buffer messages. Explain how this design decision causes problems with clock and keyboard interrupts.
	[Page 219]
36.	When a message is sent to a sleeping process in MINIX 3, the procedure ready is called to put that process on the proper scheduling queue. This procedure starts out by disabling interrupts. Explain.
37.	The MINIX 3 procedure mini_rec contains a loop. Explain what it is for.
38.	MINIX 3 essentially uses the scheduling method in Fig. 2-43, with different priorities for classes. The lowest class (user processes) has round-robin scheduling, but the tasks and servers always are allowed to run until they block. Is it possible for processes in the lowest class to starve? Why (or why not)?
39.	Is MINIX 3 suitable for real-time applications, such as data logging? If not, what could be done to make it so?
40.	Assume that you have an operating system that provides semaphores. Implement a message system. Write the procedures for sending and receiving messages.
41.	A student majoring in anthropology and minoring in computer science has embarked on a research project to see if African baboons can be taught about deadlocks. He locates a deep canyon and fastens a rope across it, so the baboons can cross handover-hand. Several baboons can cross at the same time, provided that they are all going in the same direction. If eastward moving and westward moving baboons ever get onto the rope at the same time, a deadlock will result (the baboons will get stuck in the middle) because it is impossible for one baboon to climb over another one while suspended over the canyon. If a baboon wants to cross the canyon, he must check to see that no other baboon is currently crossing in the opposite direction. Write a program using semaphores that avoids deadlock. Do not worry about a series of eastward moving baboons holding up the westward moving baboons indefinitely.
42.	Repeat the previous problem, but now avoid starvation. When a baboon that wants to cross to the east arrives at the rope and finds baboons crossing to the west, he waits until the rope is empty, but no more westward moving baboons are allowed to start until at least one baboon has crossed the other way.
43.	Solve the dining philosophers problem using monitors instead of semaphores.
44.	Add code to the MINIX 3 kernel to keep track of the number of messages sent from process (or task) i to process (or task) j. Print this matrix when the F4 key is hit.
45.	Modify the MINIX 3 scheduler to keep track of how much CPU time each user process has had recently. When no task or server wants to run, pick the user process that has had the smallest share of the CPU.
46.	Modify MINIX 3 so that each process can explicitly set the scheduling priority of its children using a new system call setpriority with parameters pid and priority.
47.	Modify the hwint_master and hwint_slave macros in mpx386.s so the operations now performed by the save function are performed inline. What is the cost in code size? Can you measure an increase in performance?
48.	Explain all of the items displayed by the MINIX 3 sysenv command on your MINIX 3 system. If you do not have access to a running MINIX 3 system, explain the items in Fig. 2-37.
	[Page 220]
49.	In the discussion of initialization of the process table we mentioned that some C compilers may generate slightly better code if you add a constant to the array instead of the index. Write a pair of short C programs to test this hypothesis.
50.	Modify MINIX 3 to collect statistics about messages sent by whom to whom and write a program to collect and print these statistics in a useful way.