Computer Science 422/622 Test 1 - Oct 8 1999 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. Unsuspend susp | rdy ---------------------|--------------------- | b. Suspend_Self run | susp 4 ---------------------|--------------------- | c. Dispatch rdy | run ---------------------|--------------------- | d. Preempt run | rdy 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; } 2. The above solution is: a. Livelock prone x b. Unsafe 3 c. Deadlock prone d. All of the above 3. The problem a. will occur EVERY time a x b. may occur if a process is preempted process gets preempted between lines [3] and [4] (but can 3 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]. 4. If lines [3] and [4] are interchanged the "solution" becomes: a. Livelock prone b. Unsafe 3 x c. Deadlock prone d. Correct Consider the following (correct) 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 = me; [5] while(using[other] && turn == me); [6] return; 5. If lines [3] and [4] are interchanged the "solution" becomes: a. Livelock prone x b. Unsafe 3 c. Deadlock prone d. Remains safe 6. If we modify the original correct solution so that line [4] reads turn = other (but line [5] stays the same) the solution becomes: a. Livelock prone x b. Unsafe 3 c. Deadlock prone d. Remains safe (If two processes engage in a race to the C-S only one will win the race and get in, BUT if one process is ALREADY IN the C-S and gets preempted, then a second process can come right in... (It will set the turn variable to "other" and then block only if turn == "me"). 7. Suppose PS == (no overhead RR) scheduling is used and four jobs are started at the same time. Two of the jobs require 2 hours of CPU time, one requires 4 hours, the other requires 5 hours. a. How long after the jobs start will the FIRST job finish. 3 8 b. How long after the jobs start will the last job finish. 13 3 c. What is the average response time for the four jobs (with PS) scheduling. 3 (8 + 8 + 12 + 13) / 4 d. What is the average response time if the SJF (Shortest job first non preemptive scheduling policy is used 3 (2 + 4 + 8 + 13) / 4 8. Suppose 2 processes are to be run and EACH ONE requires 6 minutes of processor time and 6 minutes of disk time. Suppose they are run on an ideal multitasking system in which perfect 3 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? 12 Suppose a small transaction processing system is being run on a personal computer class system. Each transaction requires 0.10 seconds of CPU time and 0.20 seconds of disk time. 9. What is the maximum throughput in transactions per second a. 0.05 b. 0.2 3 x c. 5 d. 10 10. What is the minimum response time in seconds (assuming NO overlap of Disk and CPU processing) x a. 0.30 b. 0.20 3 c. 0.10 d. 1 11. Suppose the following code segment is executed and the child"n" functions RETURN INSTEAD OF EXITING. How many total processes (EXCLUDING the original parent will be created?) if (fork() == 0) (A previous test key said 6 here child1(); and so 6 was viewed as acceptable) if (fork() == 0) child2(); if (fork() == 0) child3(); a. 3 b. 6 x c. 7 d. 8 12. Consider the following code segment: [1] pid = fork() [2] pipe(pd); [3] if (pid == 0) [4] child_proc(); [5] else [6] parent_proc(); a. How many pipes (not pipe handles) will be created? 2 2 b. Will the parent and child be able to communicate using the pipe(s)? (Yes or No). If your answer is no, describe how to fix the code so that they can. 2 No, reverse the order of lines 1 and 2 13. Answer the following T or F: (These questions refer to "steady state" conditions (i.e. ignore transient states that might occur DURING the actual execution of a wait or signal). _T_ a. A semaphore that has the value 1 never has even one suspended process. _F_ b. A semaphore that has the value 0 always has at least one suspended process. 8 _T_ c. A signal operation on a semaphore that has a value of 0 may OR may not cause the value to be incremented. _T_ d. A wait operation on a semaphore with a non-empty wait queue never changes the value of the semaphore. 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 14. If statements [4] and [5] were removed which of the following BEST describes the result in a multiprocessor system. x a. it would no longer work b. it would still work correctly correctly and but it would but it would be slower. 3 be faster. c. it still work correctly and it would be faster. 15. If statements [4] and [5] were removed which of the following BEST describes the result in a single processor system: a. it would no longer work b. it would still work correctly correctly and but it would but it would be slower. 3 be faster. x c. it still work correctly and it would be faster. 16. If interrupts are not disabled while attempting to acquire a test and set lock in a system that uses strict priority scheduling a. Processes may deadlock in x b. Processes may deadlock single processor system in both single and multiple but not in an MP system. processor systems but the 3 likelihood of deadlock is greater on a single processor c. Processes may deadlock d. Processes may deadlock in in both single and multiple a multiple processor system processor systems but the but not in a single processor. likelihood of deadlock is greater on a multiprocessor 17. When a correct implementation of wait that contains disablement and test and set is used, the TS instruction will always succeed: a. On the first try on both x b. On the first try on single CPU single and multiple processor system but not necessarily 3 systems. on multiple processor systems. c. On the first try on single CPU d. Never on either single or system but never multiple processor systems. on multiple processor systems. 18. Answer the following questions T or F: _F_ a. The amount of CPU time consumed by a process while it was swapped out is an important factor in determining which process to swap in. _T_ b. It is generally more desirable to swap out processes that are suspended than processes that are ready to run. 8 _F_ c. A process should always be swapped back in after a fixed amount of time regardless of whether it is in the ready or suspended state. _F_ d. A process should be swapped out each time it is suspended to wait for the completion of a disk i/o operation. 19. Consider the following code segment from a producer/consumer problem: Producer Consumer wait(mutex); wait(item); wait(slot); 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 in the producer XOR the consumer (hint: yes is not an acceptable answer) 3 Consumer b. Now suppose the the order of the waits in the CONSUMER code were reversed but LEFT AS THEY APPEAR in the producer code. In this case a deadlock could occur: 1. Only when the buffer was 2. Only when the buffer empty. was full. 3 x 3. When the 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 3 consumers. producers 3. Only if there were multiple x 4. Even if there were a single producers AND consumers. producer and consumer. d. Can changing the order of the signal statements lead to deadlock if the producers and consumers all use the same mutex semaphore. x 1. No, never 2. Yes, definitely 3 3. Only when multiple producers or consumers exist. e. If code were changed so that the consumers used "cmutex" and the producers used "pmutex" the deadlock could occur 1. Only if there were multiple 2. Even if there were a single 3 producers AND consumers. producer and consumer. x 3. Deadlock would no longer occur at all. 20. Consider the following (partial) solution to the readers and writers problem: wait(rmutex); wait(wsem); rcount = rcount + 1; if (rcount == 1) write(); wait(wsem); signal(wsem); signal(rmutex); read(); Suppose a writer is writing and 5 readers are queued to read. The readers will be distributed as follows: a. All will be blocked at x b. All will be blocked at wsem rmutex 3 c. All but one will be d. All but one will be blocked blocked at wsem at rmutex. 21. Suppose the reader code is completed as follows: [1] wait(rmutex); [2] rcount = rcount - 1; [3] if (rcount == 0) [4] signal(wsem); [5] signal(rmutex); Which of the follow best describes the effect of moving statement [5] to between statements [2] and [3]. a. This has no effect on b. This could lead to simultaneous 3 correctness reading and writing c. This would correct an x d. This could lead to a deadlock. error present in the solution shown above.