Computer Science 422/622 Test 1 - Oct 8 1997 Name________________________ 1. We studied a process state transition diagram that included the states running, ready, and suspended. Each of the following actions is causes a state transition. For each identify the original state and the destination state of the process that makes a transition. Original state Destination state | a. Dispatch Rdy | Run ---------------------|--------------------- Run | Susp 8 b. Suspend_Self | ---------------------|--------------------- Run | Rdy c. Preempt | ---------------------|--------------------- Susp | Rdy d. Unsuspend | | 2. Answer the following T or F. (Blocked == Suspended) _f_ a. A process must make at least one entry to the "Blocked" state for every entry it makes to the "Ready" state. _f_ b. A process could never enter the "Ready" state more times than it 8 entered the "Blocked" state. _f_ c. The number of processes in the "Ready" state can never exceed the number of processors in the computer system. _f_ d. The number of processes in the "Blocked" state could never exceed the number of processes in the "Ready" state. 3. Suppose a malicious user of a Unix OS (such as SUN's) running on an Intel CPU writes the C program shown on the left. The function CLI is an assembly language module shown on the right main() CLI: proc 3 { cli /* disable ints */ CLI(); ret while (1); } When the hacker tries to compile and execute it. Which of the following best describes what will occur. a. The hackers attempt to build b. The hacker can build an a.out an a.out will fail because users and when he starts it the system d aren't allowed to write in assembly. will crash. c. The hacker's a.out will loop d. The hacker's a.out will be indefinitely but other processes terminated the first time will be dispatched whenever the it attempts to execute the hacker's is preempted. cli instruction. Consider the following "solution" to the mutual exclusion problem int using[2]; void dek_lock(int pid) /* Pid = 0 or 1 */ { int me, other; [1] me = pid; [2] other = me ^ 1; [3] while(using[other]); [4] using[me] = 1; [5] return; } 4. The above solution is: a. Livelock prone b. Unsafe b c. Deadlock prone d. All of the above 5. The problem a. will occur EVERY time a b. may occur if a process is preempted process gets prempted between lines [3] and [4] (but can b between lines [3] and [4]. occur nowhere else). c. may occur if a process is d. Will occur if a process is preempted anywhere between preempted anywhere between lines [1] [5]. lines [1] [5]. 6. If lines [3] and [4] are interchanged the "solution" becomes: a. Livelock prone b. Unsafe c c. Deadlock prone d. Correct Consider the following "solution" to the mutual exclusion problem int using[2]; int turn; void pete_lock(int pid) /* Pid = 0 or 1 */ { int me, other; [1] me = pid; [2] other = me ^ 1; [3] using[me] = 1; [4] turn = other; [5] while(using[other] && turn == other); [6] return; } 7. The above solution is: d a. Livelock prone b. Unsafe c. Deadlock prone d. Correct 8. If line [4] is changed to "turn = me" and line [5] is changed to while(using[other] && turn == me); the solution is: d a. Livelock prone b. Unsafe c. Deadlock prone d. Correct 9. If lines [4] and [5] (as originally written) are interchanged the solution is: a. Livelock prone b. Unsafe b c. Deadlock prone d. Correct 10. Suppose PS == (no overhead RR) scheduling is used and four jobs are started at the same time. Two of the jobs require 3 hours of CPU time, one requires 1 hour, the other requires 5 hours. a. How long after the jobs start will the FIRST job finish. 4 b. How long after the jobs start will the last job finish. 12 12 c. What is the average response time for the four jobs. 9 d. What is the average response time if the SJF (shortest job first non preemptive scheduling policy is used 6 11. Suppose 2 processes are to be run and EACH ONE requires 8 minutes of processor time and 6 minutes of disk time. Suppose they are run on an ideal multitasking system in which perfect overlap of CPU and disk activity is achieved with no OS overhead at all. If they start at the same time, how long will it be until they both finish? 3 16 12. Answer the following T or F: _F_ a. A semaphore that has the value 0 always has at least one suspended process. _T_ b. A signal operation on a semaphore that has a non-zero value at the time of the signal always causes the value to be incremented by 1 (ignore such potential problems as reaching MAX_INT here). _T_ c. A semaphore that has at least one suspended process always has the value 0. Consider the following (correct) implementation of setlock: [0] CLI ;disable ints [1] RETRY: [2] CMPI LOCKVAL, 0 ;see if its 0 [3] JNZ RETRY ;if not, keep trying til it is. [4] TS LOCKVAL ;use the hardware to make sure. [5] JNZ RETRY ;start over if we got beat to the lock [6] RET 13. If statements [2] and [3] were removed which of the following BEST describes the result in a multiprocessor system: a. it would no longer work b. it would still work correctly correctly and but it would but it would be slower. b be faster. c. it still work correctly and it would be faster. 14. The conditional jump instruction on line [5] will a. Never be taken on single CPU b. Never be taken on single CPUs or mulitple CPU systems. but always taken at least once per call to setlock on multi CPUs d c. May or may not be taken on d. Never be taken on single CPU's both single and muliple CPU and may or may not be taken on systems. each call to setlock on a multi CPU system. 15. Consider the following implementation of unlock: [0] MOVI LOCKVAL,0 ;Reset the lock value. [1] STI ;Turn ints back on a. The statements are in the b. The statements are in the WRONG order. correct order b c. The order of the statements is irrelevant. 16. Preemption of a process should NEVER occur a. When the process holds a TS b. When a process holds a semaphore lock OR a mutex semaphore. -- but preempting a TS lock holder is OK. c c. When a process holds a TS lock d. Preempting either a lock or but preempting a semaphore holder semaphore holder is OK. is OK. 17. Consider the following code segment from a bounded buffer producer consumer problem; Producer Consumer wait(slot); wait(item); wait(mutex); wait(mutex); buffer[nxt_in] = new_item; consume = buffer[nxt_out]; nxt_in = (nxt_in + 1) % BUFSZ; nxt_out = (nxt_out + 1) % BUFSZ; signal(item); signal(slot); signal(mutex); signal(mutex); a. Is the order of the waits in the above example correct? (yes/no) 3 yes b. Now suppose the the order of the waits in the producer code were reversed but LEFT AS THEY APPEAR in the consumer code. In this case a deadlock could occur: 1. Only when the buffer was 2. Only when the buffer 2 empty. was full. 3 3. Any time to buffer was either 4. Anytime regardless of the full or empty. state of the buffer. c. The deadlock could occur: 1. Only if there were multiple 2. Only if there were multiple consumers. producers 3 4 3. Only if there were multiple 4. Even if there were a single producers AND consumers. producer and consumer. c. The mutex semaphore in the producer code is necessary 1. Never 2. Only if there are multiple 2 producers 3 3. If there are either multiple 4. Always.... even if there producers or consumers. is just one producer and one consumer. d. Can changing the order of the signal statements lead to deadlock if the producers and consumers all use the same mutex semaphore. 3 1. No, never 2. Yes, definitely 1 3. Only when multiple producers or consumers exist. 18. Write the unlocking part (the part that appears AFTER the READ();) of the reader priority solution to the readers and writers problem. 5 wait(rmutex) rcount -= 1; if (rcount == 0) signal(wsem) signal(rmutex)