Computer Science 422/622 Test 1 - Oct 9 2002 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. Preempt Run | Ready ---------------------|--------------------- Run | Susp/Blocked b. Suspend_Self | ---------------------|--------------------- | c. Dispatch Ready | Run ---------------------|--------------------- 2. 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. _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. 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 { 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] using[me] = 1; [4] while(using[other]); [5] return; } 4. The above solution is: a. Livelock prone b. Unsafe C 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 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]. 6. If lines [3] and [4] are interchanged the "solution" becomes: a. Livelock prone b. Unsafe B 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; 7. If lines [3] and [4] are interchanged the "solution" becomes: a. Livelock prone b. Unsafe B c. Deadlock prone d. Remains safe 8. Suppose PS == (no overhead RR) scheduling is used and three jobs are started at the same time. One of the jobs require 2 hours of CPU time, one requires 5 hours, and the other requires 6 hours. a. How long after the jobs start will the FIRST job finish. 6 Hours b. How long after the jobs start will the last job finish. 13 Hours c. What is the average response time for the three jobs (with PS) scheduling. 6 + 12 + 13 ---------- 3 d. What is the average response time if the SJF (Shortest job first non preemptive scheduling policy is used 2 + 7 + 13 ---------- 3 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.25 seconds of disk time. 9. What is the maximum throughput in transactions per second 1 ------ = 4 Tx / sec 0.25 10. What is the minimum response time in seconds (assuming NO overlap of Disk and CPU processing) 0.35 sec 11. 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 12. 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) child1(); if (fork() == 0) 7 Children (1 + 2 + 4) child2(); if (fork() == 0) child3(); 11. 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. _F_ c. A process should be swapped out each time it is suspended to wait for the completion of a disk i/o operation. 13. 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 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. 12. 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 and conditions such as MAX_INT being reached)) _F_ a. A signal operation on a semaphore which has an empty wait queue may or may not cause the value of the semaphore to be incremented. _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 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. 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. be faster. A c. it still work correctly and it would be faster. 15. 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 b. Processes may deadlock single processor system in both single and multiple but not in an MP system. processor systems but the B 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 16. 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. 17. 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. 18. 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 Label each of the following variables P or S depending upon whether each thread has a Private copy or if the variable is Shared by all threads _S_ a. a _P_ b. x _P_ c. c 19. 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 20. 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. Which one has the waits in the CORRECT order. Consumer b. With the waits as they are now deadlock can occur: 1. Only when the buffer was 2. Only when the buffer empty. was full. 2 3. When the buffer was neither 4. Only when the buffer was not full nor empty. empty. 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 the 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. 21. 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 b. All will be blocked at wsem rmutex D c. All but one will be d. All but one will be blocked blocked at wsem at rmutex. 22. Suppose the reader code exit 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 correctness reading and writing D c. This would correct an d. This could lead to a deadlock. error present in the solution shown above.