Computer Science 422/622 Test 1 - 9 Oct 1996 Name________________________ 1. The maximum number of processes actually executing instructions on a computer system at any instant in time is: (b) a. 1 b. The number of CPU's in the system. 3 c. The maximum number of d. The number of processes processes the OS can support. currently in memory. 2. The rate at which as multiuser Unix systems dispatches, blocks and, preempts processes is closest to: (d) a. Once a day b. Once an hour. 3 c. Once a minute d. Many times per second. 3. Both of the following proposed solutions to the mutual exclusion problem suffers from a fatal flaw that can be triggered if a process is preempted within a particular statement range... identify the precise nature of the problem and the statement range a. Process 1 Process 2 [1] while (p2using == TRUE); [1] while (p1using == TRUE); [2] p1using = TRUE; [2] p2using = TRUE; [3] -- critical section --- [3] -- critical section --- [4] p1using = FALSE; [4] p2using = FALSE; 2 Problem that occurs: Unsafe 2 Can occur if process attempting to access critical section is preempted AFTER executing stmt ___1___ and before executing stmt __2___. b. Process 1 Process 2 [1]p1using = TRUE; [1] p2using = TRUE; [2]while (p2using == TRUE); [2] while (p1using == TRUE); [3]-- critical section --- [3] -- critical section --- [4]p1using = FALSE; [4] p2using = FALSE; 2 Problem that occurs: Deadlock 2 Can occur if process attempting to access critical section is preempted AFTER executing stmt ___1___ and before executing stmt ___2__. 4. Although Dekker was able to correct these problems and invent a correct algorithm, his algorithm still suffered from two major disadvantages that are corrected by the use of semaphores. Identify that: 2 a. Uses busy waiting 2 b. Only works for two processES (not processors). The algorithm works for some ... but not all multiprocessor architectures. 5. Identify which of the "Real OS hardware requirements" are used in both of the following OS functions: 2 _b_ 1. Preventing a user process a. A general interrupt mechanism initiating an I/O operation b. Two operating CPU states 2 _d_ 2. Regaining control from a with privileged instructions looping user program. c. An on-chip Deus ex machina d. A programmable timer that can generate interrupts. 6. Which of the following state transitions would be LEAST likely to occur in a system that used swapping. (c) a. In Ready to Out Ready b. Out Ready to In Ready 3 c. Out Blocked to In Blocked d. In Blocked to Out Blocked 7. Answer the following T or F: 2 _T_ a. A semaphore that has the value 1 never has any suspended processes. 2 _T_ b. A signal operation on a semaphore that has a non-zero value at the time of the signal always causes the value to be incremented by 1 (ignore such potential problems as reaching MAX_INT here). 2 _T_ c. A semaphore that has at least one suspended process always has the value 0. 2 _F_ d. A signal operation on a semaphore that has the value 0 at the time of the signal always causes a process to become unsuspended. 8. a. Suppose 2 processes are to be run and EACH ONE requires 8 minutes of processor time and 5 minutes of disk time. Suppose they are run on an ideal multitasking system in which perfect 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 finish? A total of 16 minutes of cpu time is required. Therefore there is no way that the two jobs can complete in < 16 minutes 3 (without invoking a time warp!) However, the 5 minutes of disk time required by each process can be completely overlapped with the CPU usage of the other.. Thus the answer is 16 min. b. Suppose PS (processor sharing) scheduling is used and four jobs are started at the same time. None of the jobs do any I/O. Two require 2 hours of CPU time and two require 1 hour of cpu time. How long after all the jobs start will the last two jobs finish? ((a) 2 * 2 + 2 * 1 = 6 hours) a. 6 hours. b. 8 hours. 3 c. 10 hours d. 12 hours. c. What will be the average response time if the jobs are run using nonpreemtive FCFS scheduling in the following order: 3 2hr job - 1hr job - 2hr job - 1hr job (2 + 3 + 5 + 6) / 4 = 4hrs. 9. Answer the following questions T or F: 2 _F_ a. An important factor in deciding when to swap a process back in is how much CPU time it has used since it was swapped out. 2 _T_ b. It is generally more desirable to swap out processes that are suspended than processes that are ready to run. 2 _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. 2 _F_ d. A process should be swapped out each time it is suspended to wait for the completion of a disk i/o operation. 10. Consider the following code segment: [1] pipe(pd1); [2] pid = fork() [3] pipe(pd2); [4] if (pid == 0) [5] child_proc(); [6] else [7] parent_proc(); a. How many pipes (not pipe handles) will be created? 3 3 b. The parent and child will be able to communicate using:(a) 3 a. pd1 but not pd2 b. pd2 but not pd1 c. both pd1 and pd2 d. neither pd1 nor pd2 11. Consider the following code segment: int a; void xthread( 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) a. The variable 'a' is shared b. 'a' and 'x' are shared but 3 but both threads have private 'c' is private. 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. 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 12. If statements [4] and [5] were removed which of the following BEST describes the result in a multiprocessor system: (a) a. it would no longer work b. it would still work correctly 3 correctly and but it would but it would be slower. be faster. c. it still work correctly and it would be faster. 13. If statements [4] and [5] were removed which of the following BEST describes the result in a single processor system: (c) 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. 14. Consider the following code segment from a bounded buffer producer consumer problem; Producer Consumer wait(slot); wait(mutex); wait(mutex); wait(item); 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. In the above example correct which process has its waits in the wrong order (2) 3 1. Producer 2. Consumer 3. Both 4. Neither b. With the waits in the order shown, a deadlock could occur (1) 1. Only when the buffer was 2. Only when the buffer 3 empty. was full. 3. Any time to buffer was either 4. Any time at all full or empty. c. Can changing the order of the signal statements lead to deadlock if the producers and consumers all use the same mutex semaphore (1). 1. No, never 2. Yes, definitely 3 3. Only when multiple producers or consumers exist. 15. Consider the following solution to the readers and writers problem: wait(rmutex); wait(wsem); if (rcount == 0) write(); wait(wsem); signal(wsem); rcount = rcount + 1; signal(rmutex); read(); a. The reader solution is INCOMPLETE. Complete it. Supply ONLY the code that FOLLOWS the read() function call. DO NOT REPRODUCE the portion of the reader code shown above (unless you desire a nasty deduction!). wait(rmutex) rcount -= 1; 5 if (rcount == 0) signal(wsem) signal(rmutex); b. Does this solution permit either readers or writers to starve? If so who? Writers can starve if readers arrive in such a way that the number of readers reading never falls to 0. 3 16. Which of the following pairs of approaches to synchonization is most compatible with the way Unix pipes work: (b) a. Blocking writes and b. Blocking reads and non-blocking reads non-blocking writes 3 c. Non-blocking reads and d. Blocking reads and non-blocking writes. Blocking writes 17. Which of the following typically leads to busy waiting (c) a. blocking reads b. blocking writes 3 c. non-blocking reads d. non-blocking writes