Computer Science 422/622 Test 1 - Feb 26 2002 Name________________________ 1. In the process state transition model that we discussed in class, which of the following state transitions would be made MOST OFTEN by a process that did a tremendous amount of computation but no I/O at all. a. Running to Ready b. Blocked to Ready A c. Running to Blocked d. Running to zombie 2. In the process state transition model that we discussed in class, which of the following state transitions would be made MOST OFTEN by a process that did a tremendous amount of I/O with a VERY SMALL amount of CPU time consumed between each I/O request. B a. Running to Ready b. Blocked to Ready c. Blocked to Running d. Running to zombie 3. For the process switching model that we discussed in class, identify whether each of the following functions is performed by the application itself (A), the interrupt hardware (I), or the OS (O): _I__ a. Alter the flags register putting the processor into kernel (as opposed to user) mode. 6 _O__ b. Save the contents of the Stack Pointer (SP) register in the Process Control Block (PCB) of the interrupted process _I__ c. Copy the address of the first instruction of an OS interrupt service routine from the Interrupt Vector Table in memory to the IP (instruction pointer) register. 4. In the multitasking model that we discussed in class, OS code runs: a. each time a switch between b. only after all tasks have two application tasks occurs. had a chance to run. A c. after each instruction is d. only when there are no executed by an application. applications available to run. 5. 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 { 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 aren't allowed to write in assembly. will crash. D 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; /* If me == 0, other = 1 and vice versa */ [3] while(using[other]); [4] using[me] = 1; [5] return; } 6. The above solution is: a. Livelock prone b. Unsafe B c. Deadlock prone d. All of the above 7. The problem a. will occur EVERY time a b. may occur if a process is preempted process gets preempted 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]. 8. 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] turn = me; [4] using[me] = 1; [5] while(using[other] && turn == me); [6] return; 9. As written the solution is a. Livelock prone b. Unsafe B c. Deadlock prone d. Correct 10. If lines [3] and [4] are interchanged the "solution" becomes: a. Livelock prone b. Unsafe D c. Deadlock prone d. Safe 11. 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 four jobs start will the jobs that require 2 hours of CPU time finish. 8 b. How long after the jobs start will the last job finish. 8 13 c. What is the average response time for the four jobs (with PS) scheduling. (8 + 8 + 12 + 13) / 4 d. What is the average response time if the SJF (Shortest job first non preemptive scheduling policy is used (2 + 4 + 8 + 13) / 4 Suppose a small transaction processing system is being run on a personal computer class system. Each transaction requires 0.020 seconds of CPU time and 0.050 seconds of disk time. 12. What is the maximum throughput in transactions per second 20 13. What is the minimum response time in seconds (assuming NO overlap of Disk and CPU processing) 0.070 14. Suppose the CPU is replaced with one which is twice as fast. The effect will be: a. Shorter min response and b. Same min response but higher max throughput higher max throughput C c. Shorter min response but d. Same min response and same max througput same min througput 15. 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. 6 _T_ b. It is generally more desirable to swap out processes that are suspended than processes that are ready to run. _F_ c. A process should be swapped out each time it is suspended to wait for the completion of a disk i/o operation. 16. Recall the program discussed in class .. child1 wrote into a pipe and child2 read from it. void main(void) { int pipeids[2]; int pid; int status; pipe(pipeids); /* close(pipeids[1]); */ /* 1st close */ if (fork() == 0) { child1(pipeids); } /* close(pipeids[1]) */ /* 2nd close */ if (fork() == 0) { child2(pipeids); } /* close(pipeids[1]) */ /* 3rd close */ wait(0); wait(0); Identify the best description of what will happen in each of the following situations: (nth close activated means that the comments surrounding the nth close <> are removed. _2_ a. 1st close activated 1. communication via the pipe is possible but child2 won't see EOF _3_ b. 2nd close activated when child 1 closes the pipe 8 2. communication via the pipe is not _1_ c. 3rd close activated possible 3. communications is possible and _1_ d. NO close activated child2 will see EOF when child1 closes the pipe. 17. 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. _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 18. 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. 19. If statements [4] and [5] were removed which of the following BEST describes the result in a multi-processor system: a. it would no longer work b. it would still work correctly correctly and but it would but it would be slower. A be faster. c. it still work correctly and it would be faster. 20. 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 b. On the first try on single CPU single and multiple processor system but not necessarily B 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. 21. When a test and set lock is released interrupts should be enabled a. before the lock is set to 0. b. after the lock is set to 0. B c. either approach works fine. 22. A simplified version of the condition variable based implementation of signal() looks like: pthread_mutex_lock(&s->mtx); s->value += 1; pthread_cond_broadcast(&s->cv); pthread_mutex_unlock(&s->mtx); The location of the broadcast is: a. Correct as is and moving it b. Should be moved before s->value before s->value += 1 breaks the code. += 1; C c. Works equally well in either place. 23. Consider the following code segment: int a = 0; |---> for (c = 0; c < 100000; c++) void xthread( | a = a + 1; int x, | int y) | } { | int c, d; --------- Suppose two threads are created and both run the function xthread which of the following BEST characterizes the sharing of data. a. The variable 'a' is shared b. 'a' and 'x' are shared but but both threads have private 'c' is private. A copies of 'x' and 'c'. c. All five variables are shared d. all five variables are private. (i.e. if either thread changes one of them, the change is seen by the other thread. 24. Suppose the above function is run concurrently as 4 separate threads. After all threads complete the value of "a" will be: a. somewhat less than 400000 b. somewhat greater than 400000 or possibly even equal to or possibly even equal to A 400000 400000 c. exactly 100000 d. exactly 400000 25. 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) 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 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 consumers. producers 4 3. Only if there were multiple 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. 1. No, never 2. Yes, definitely 1 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. 3. Deadlock would no longer occur at all. 26. Consider the following (partial) solution to the readers and writers problem: READER: WRITE: 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 b. All will be blocked at D wsem rmutex c. All but one will be d. All but one will be blocked blocked at wsem at rmutex. 27. Suppose the reader code is completed as follows: [1] wait(rmutex); [2] rcount = rcount - 1; [3] signal(rmutex); [4] if (rcount == 0) [5] signal(wsem); This solution is: a. Correct b. Could lead to simultaneous reading and writing C c. Could cause a deadlock Which of the follow best describes the effect of moving statement [3] to after statement [5]. a. It has no effect on b. It could lead to simultaneous C correctness reading and writing c. It would correct an d. It could lead to a deadlock. error present in the solution that is shown above.