Computer Science 422/622 Test 1 - Feb 26 2004 Name________________________ We considered a time-line like the following one in class Proc A ------ ----- ------ Proc B ------ ----- OS --- --- ---- ----- 1. The relative lengths of the ---- lines shown above are: a. Realistic reflections of b. Wrong.. The user lines should 3 a typical system behavior be longer b c. Wrong.. The OS lines should d. Wrong.. All --- lines should have be longer. EXACTLY the same length. 2. The mechanism used to effect a downward vertical transition from the application process to the OS is: a. a subroutine call b. an interrupt instruction 3 b c. an iret instruction d. Both (a.) and (b.) are used 3. We studied a process state transition diagram that included the states Running, Ready, and Blocked. 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 ---------------------|--------------------- Run Blk/Susp 6 b. Suspend_Self | ---------------------|--------------------- Rdy Run c. Dispatch | ---------------------|--------------------- 4. 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. 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. 6 __O_ b. Save the contents of the Stack Pointer (SP) register in the Process Control Block (PCB) of the interrupted process __I_ c. Alter the flags register putting the processor into kernel (as opposed to user) mode. 5. 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. 3 a. Running to Ready b. Blocked to Ready b c. Blocked to Running d. Running to zombie Consider the following "solution" to the mutual exclusion problem (The ^ operator in the C language is exclusive or). 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: 3 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 3 process gets preempted between lines [3] and [4] (but can between lines [3] and [4]. occur nowhere else). b 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: 3 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. This "solution" is 3 a. Livelock prone b. Unsafe b c. Deadlock prone d. Safe 10. If lines [3] and [4] are interchanged the "solution" becomes: 3 a. Livelock prone b. Unsafe d c. Deadlock prone d. Safe 11. Suppose PS == (no overhead RR) scheduling is used and three jobs are started at the same time. One of the jobs require 12 minutes of CPU time, one requires 4 minutes, and the other requires 6 minutes. a. How long after the jobs start will the FIRST job finish. 2 12 b. How long after the jobs start will the last job finish. 22 2 c. What is the average response time for the three jobs (with PS) scheduling. 2 12 + 16 + 22 ------------- 3 d. What is the average response time if non pre-emptive FIFO(FCFS) scheduling is used and the jobs are started in the order (12, 4, 6) 12 + 16 + 22 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.25 seconds of disk time. (<>) 12. What is the maximum throughput in transactions per second 3 1 / 0.25 = 4 13. What is the minimum response time in seconds 3 0.20 + 0.25 14. Suppose the CPU is replaced with one which is twice as fast. The effect will be: 3 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 throughput 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. communications is possible and child2 will see EOF when child1 _1_ b. 2nd close activated closes the pipe. 8 2. communication via the pipe is not _3_ c. 3rd close activated possible 3. communication via the pipe is _3_ d. NO close activated possible but child2 won't see EOF when child 1 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 and conditions such as MAX_INT being reached)) _T_ a. A signal operation on a semaphore which has an empty wait queue will always cause the value of the semaphore to be incremented. 6 _T_ b. A signal operation on a semaphore that has a value of 0 may or may not cause the value to be incremented. _F_ c. A wait operation on a semaphore with a non-empty wait queue may or may not change 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 [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. 3 c. it still work correctly and it would be faster. 19. 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 3 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 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 systems. on multiple processor systems. 3 B 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. 3 B c. either approach works fine. 22. 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 (the producer or the consumer) has the waits in the CORRECT order. 2 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. 3 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 3 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 3 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 3 producers AND consumers. producer and consumer. 3. Deadlock would no longer occur at all. 23. 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: 3 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. 24. 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 3 correctness reading and writing D c. This would correct an d. This could lead to a deadlock. error present in the solution shown above. Consider the following implementation of a wait operation on a counting semaphore that is based upon locks and condition variables. wait(sem_t s) { [1] pthread_mutex_lock(&s->mtx); [2] while (s->value == 0) { [3] pthread_cond_wait(&s->cv, &s->mtx); [4] printf("Sem value presently %d \n", s->value); } [5] pthread_mutex_lock(&s->mtx); } 25. Answer the following T or F: ___ a. When a process is in the blocked state because it called pthread_cond_wait(), it will continue to hold the mutex X s->mtx. ___ b. When a process executes statement [4] it will hold the mutex s->mtx. ___ c. When the pthread_cond_broadcast() is executed in the call to signal at most one process waiting on s->cv will be moved from the blocked to the ready state.