Computer Science 422/622 Test 1 - Oct 9 2000 Name________________________ (multiple choice questions are 3pts each) 1. The mechanism used to effect a transfer of control from a running application to the operating system is: a. a subroutine call b. an interrupt b instruction c. an iret instruction d. Both (a.) and (b.) are used interchangeably 2. 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 | rdy ---------------------|--------------------- 6 | b. Suspend_Self run | susp ---------------------|--------------------- | c. Dispatch rdy | run ---------------------|--------------------- 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. _O__ b. Save the contents of the Stack Pointer (SP) register in the 6 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. 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. 5. How many child processes EXCLUDING the original parent will be created by the following code: int i = 8; while (i > 0) { 3 fork(); 15 Children i = i / 2; } 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; } 6. The above solution is: a. Livelock prone b. Unsafe b c. Deadlock prone d. Requires strict turn taking 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 9. 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 3 hours, the other requires 5 hours. a. How long after the jobs start will the FIRST job finish. 6 b. How long after the jobs start will the last job finish. 10 c. What is the average response time for the four jobs (with PS) scheduling. 6 + 8 + 10 ----------- = 8 3 d. What is the average response time if the SJF (Shortest job first non preemptive scheduling policy is used ( 2 + 5 + 10 ) / 3 = 5 2/3 Suppose a small transaction processing system is being run on a personal computer class system. Each transaction requires 0.20 seconds of CPU time and 0.50 seconds of disk time. 10. What is the maximum throughput in transactions per second a. 1 b. 2 b c. 5 d. none of the above 11. What is the minimum response time in seconds (assuming NO overlap of Disk and CPU processing) a. 0.20 b. 0.50 c c. 0.70 d. none of the above 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]); */ if (fork() == 0) { child1(pipeids); } /* close(pipeids[1]) */ if (fork() == 0) { child2(pipeids); } /* close(pipeids[1]) */ wait(0); wait(0); 12. In the program segment above, which instance of close() call should be uncommented in order for the program to work correctly and for child2 to get EOF on the pipe when child one executes close(pipeids[1]); a. The first one b. The second one b c. The third one d. All work equally well 13. Suppose that the call to the pipe() function was moved from its present location to a spot immediately before the 2nd close(). Which of the following best characterizes the resulting situation: a. The program will continue b. Two pipes will now be created and to work just as before communication between the children b remains possible using either one. c. Two pipes will be created d. Two pipes will be created and and communication between communication between the children children remains possible will not be possible using either using the pipe created by one. the parent. 14. 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)) _T_ a. A signal operation on a semaphore which has an empty wait queue always causes the value of the semaphore to be incremented. _F_ b. A semaphore that has the value 0 always has at least 8 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 15. If statements [2] and [3] were removed which of the following BEST describes the result in a multiprocessor system. a. it would still work b. it would still work correctly correctly and it would but it would cause a performance b be faster. problem. c. it would no longer work correctly 16. 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. c be faster. c. it still work correctly and it would be faster. 17. 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 likelihood of deadlock is greater b 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 18. 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. Consider the following implementation of unlock: [0] STI ;Turn ints back on [1] MOVI LOCKVAL, 0 ;Set lock back to zero 19. The order of the two statements is a. Correct as shown b. Incorrect as shown b c. Irrelevant 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. Is the order of the waits in the above example correct in the producer XOR the consumer (hint: yes is not an acceptable answer) 3pts 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 producers AND consumers. producer and consumer. 3 3. Deadlock would no longer occur at all. 21. 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. 22. 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 23. When a new thread is created using pthread_create, execution of the new thread begins at: a. the point of return from b. Back at the start of the thr_create (like fork) function that called thr_create c c. At the start of the function d. At the main() function in the specified in thr_create new a.out specifed in thr_create