Midterm Examination 2

Directions:

Read and follow the directions.

• Write on three of the four questions.
• Read the entire exam. If there is anything you do not understand about a question, please ask at once.
• If you find a question ambiguous, begin your answer by stating clearly what interpretation of the question you intend to answer.
• Be sure I can read what you write.
• Write only on one side of a sheet.

Score Distribution:

Problem 1 Definitions

For each part, give four sub-parts:

1. Give a careful definition of the first term
2. Give a careful definition of the second term
3. Explain how the two concepts are similar
4. Explain how the two concepts are different

1. Deadlock vs. starvation
2. Thrashing vs. page fault (in the context of memory management)
3. Page vs. page frame vs. working set (in the context of memory management)
4. File vs. directory

1. Deadlock vs. starvation: See p. 283, 193, 238
   +2 if you pointed ahead to Problem 3
2. Thrashing vs. page fault: See p. 363, 386
3. Page vs. page frame vs. working set: See p. 329, 386
   
   Page is virtual; page frame is physical
4. File vs. directory: See Sections 10.1, 10.3.
   Both are virtual concepts. Give attributes and operations

As you prepare for our final exam, I encourage you to maintain a vocabulary list.

Problem 2 Memory Allocation

Consider a variable partition memory allocation scheme. Our computer has 20 blocks of memory. The operating system occupies blocks 0 - 5, so user processes use blocks 6 - 19. When a new user process is created, it requests the number of blocks of memory it needs. Each process can use only contiguous blocks. A user process may never ask for more memory, and it releases memory only when the process terminates.

Initially, at time t = 0, the only user process in memory is Process P₁, and it occupies memory blocks 10 - 14. Additional processes appear at the times shown, with memory requests as shown:

time	operation	# blocks		time	operation	# blocks
3	create P2	4		14	remove P2
4	create P3	2		17	create P7	1
5	create P4	1		20	remove P3
10	remove P1			22	create P8	3
11	create P5	2		33	create P9	4
13	create P6	2		36	remove P8

1. Describe the first-fit strategy for memory allocation.
   Show where the first-fit strategy places each process:

    

   Block	t = 0	3	4	5	10	11	13	14	17	20	22	33	36
   0 - 5	O P E R A T I N G   S Y S T E M
   6
   7
   8
   9
   10	P1
   11
   12
   13
   14
   15
   16
   17
   18
   19

    

   Explain any non-obvious choices you made.

    

2. Describe the best-fit strategy for memory allocation.
   Show where the best-fit strategy places each process:
   Explain any non-obvious choices you made.
3. Describe the worst-fit strategy for memory allocation.
   Show where the worst-fit strategy places each process:
   Explain any non-obvious choices you made.
4. Which is the best strategy for memory allocation? Why?

1. First fit:

    

   Block		0	3	4	5	10	11	13	14	17	20	22	33	36
   6										P7
   7			P2
   8												P8
   9
   10
   11							P5
   12		P1										&nnbsp;
   13								P6
   14
   15
   16				P3
   17					P4
   18
   19

    

   P9 does not fit

    

2. Best fit:

    

   Block		0	3	4	5	10	11	13	14	17	20	22	33	36
   6
   7			P2									P8
   8
   9
   10
   11								P6
   12		P1								P7
   13					&nbsnbsp;
   14													P9
   15
   16				P3
   17					P4
   18
   19							P5

    

   What if there are several holes equally good? Most assume allocation from the top of an available block.

   Many students said, "closest in size." Suppose a process needs 5 blocks, and there are blocks of size 4 and 8 available. 4 is closer to 5 than 8. Especially under time pressure, you must be wary of the Law of Unintended Consequences. Is there a valid interpretation of your words that is different from what you intend?

    

3. Worst fit:

    

   Block		0	3	4	5	10	11	13	14	17	20	22	33	36
   6
   7				P3
   8					P4
   9
   10							P5
   11
   12		P1						P6
   13										P7
   14
   15												P8
   16			P2
   17
   18
   19

    

   What if there are several holes equally good?

   P9 does not fit

    

4. Depends. What is "best?"
   In this example, Best fit is best because it could handle Process P₉. That does NOT mean best fit is always best. Besides, best fit is more expensive to run.

Problem 3 Deadlock Characterization

1. List the four conditions that are necessary for a deadlock to arise.
2. For each condition, explain what it means.
3. For each condition, give one strategy for deadlock prevention that works by denying that condition.

See Sections 7.2 and 7.4, and Dr. Bylow kindly reviewed it for you on Wednesday.

1. Mutual exclusion
   A resource cannot be shared.
   Share it. No that does not work for some resources.
2. Hold and wait
   A process retains the resources it holds and waits until requested resources become available.
   If the operating system cannot satisfy a request, the requesting process must relinquish all resources it holds.
   Or, If the operating system cannot satisfy a request, the requesting process may do its best to continue without the requested resources.
   Or, a process must request all its resources at once.
3. No preemption
   Resources cannot be preempted.
   Preempt resources.
4. Circular wait
   Beware of a circular definition!
   A set {P₀, P₁, ..., P_n} of waiting processes must exist such that P₀ is waiting for a resource held by P₁, P₁ is waiting for a resource held by P₂, ..., P_n-1 is waiting for a resource held by P_n, and P_n is waiting for a resource held by P₀. Circular wait may involve more than two processes.
   Make processes request resources in a pre-defined order.
   Or, make each processes request all the resources it needs at the same time.

A process waits for a resource. One waits for a peer or a subordinate. One waits on a superior (in some sense). In a restaurant, you may wait for a server, but the server waits on you.

In the context of deadlock, a process waits for resources it has requested, not for another process. True, the requested resource must be released by the process that holds it. The wait on another process in indirect, while the wait on the resource is direct - the requesting process is in a wait queue for the requested resource, not process.

The CPU is but one of many resources the operating system manages. An answer that focused on the CPU as a resource is incomplete.

A critical section is but one of many resources the operating system manages. An answer that focused on a critical section as a resource is incomplete.

A modern operating system uses different strategies for different resources. For example, preemptive scheduling ensures that the CPU can be preempted, so the CPU cannot participate in a deadlock. A printer is owned by a print spool process. Processes needing to print send their print jobs to the spooler, denying Hold and Wait, so the printer cannot participate in a deadlock. Virtual memory has the effect of allowing processes to share physical memory, denying mutual exclusion, so memory cannot participate in a deadlock. If you devise a deadlock-proof semaphore mechanism, I might invest in your company.

Can you have a one process deadlock?

Problem 4 Process Synchronization - Monitors

A file is to be shared among different processes, each of which has a unique number. The file can be accessed simultaneously by several processes, subject to the following constraint: The sum of all unique numbers associated with all processes currently accessing the file must be less than n.

1. Write pseudo code for a monitor to coordinate access to the file.
2. Explain how it works

Hint: "Condition" describes a language construct with opaque state, intended to be associated with a monitor, say X. X.wait() suspends the calling process until a corresponding X.signal(). X.Signal() has no effect if called when no processes are waiting for that condition.

You might start with:

	monitor fileSharer
	{
	        enum {THINKING, WAITING, READING} state[N];
	        condition self[N];

	        void open(int i) { }
	        void close(int i) { }
	}

See Problem 6.29, p. 271. Your solution should resemble Figures 6.16, 6.19, or 6.20.

monitor fileSharer
{
        enum {THINKING, WAITING, READING} state[N];
        condition self[N];
        int total;

        void open(int i) {
                state[i] = WAITING;
                if (i + total >= N)
                { self[i].wait(); }  // Leaves monitor
                state[i] = READING;
                total += i;
        }

        void close(int i) {
                state[i] = THINKING;
                total -= i;
                // Can signal one waiting proc whose ID won't break bank.
                for (int x = N - total - 1; x >= 0; x--) {
                        if (state[x] == WAITING) {
                                self[x].signal(); break;
                        }
                }
        }

        initialization.code() {
                for (int i = 0; i < N; i++) {
                        state[i] = THINKING;
                }
                total = 0;
        }
}