Computer Science 422/622 Test 1 - Oct 5 1998 Name________________________ 1. Answer the following T or F. (Blocked == Suspended) _F_ a. A process could never enter the "Ready" state more times than it entered the "Blocked" state. _F_ b. A process must make at least one entry to the "Blocked" state for every entry it makes to the "Ready" state. 8pts _T_ c. The number of processes in the "Run" state can never exceed the number of processors in the computer system. _F_ d. The number of processes in the "Blocked" state could never exceed the number of processes in the "Ready" state. 2. Consider the following "solution" to the mutual exclusion process: (Note that Process 1 and Process 2 use DIFFERENT algorithms!!) Process 1 Process 2 while(1) while(1) { { p1using = 1; RETRY: p2using = 1; while (p2using == 1); if (p1using == 1) { critical-section; p2using = 0; while (p1using == 1); goto RETRY; p1using = 0; } } critical-section; p2using = 0; } Answer the following T or F. _F_ a. This "solution" is unsafe (both processes can execute the critical-section at the same time).. 6 _F_ b. This "solution" can lead to a deadlock between the processes. _F_ c. This "solution" can lead to livelock (when both processes try to access the critical-section at the same time, they can both suffer indefinite postponement) d. Under this "solution" when both processes try to enter the critical- section at the same time: ((1.) this is exactly the asymmetric Process 1 priority solution) 1. Process 1 is more likely 2. Process 2 is more likely to get in. to get in. 2 3. Both processes are equally likely to get in. 3. We identified 4 basic hardware requirements needed by a robust multitasking computer operating system.. Two of them were "memory protection" and an "interrupt capability". What were the other two? a. Priviledged instructions 3 b. A programmable timer that can generate interrupts. Consider the following implementation of Peterson's algorithm presented in the same form as the two process/thread version of the solution to programming assignment 3. 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 = other; [5] while(using[other] && turn == other); [6] return; } 4. The above solution is: (d.) This IS Peterson's alg. a. Livelock prone b. Unsafe 3 c. Deadlock prone d. Correct 5. If lines [4] and [5] (as originally written) are interchanged the solution is: (b.) Unsafe.. Suppose turn is initialized to 0 and thread 0 tries to enter the C.S. Since turn = 0 and other = 1, it will succeed. Since lines 4 and 5 are interchanged thread 0 will set turn = 1 before entering the C.S. If thread 0 is preempted in the C.S. and thread 1 is dispatched and tries to enter the C.S. it will find turn = 1, other = 0 and thus drive right on in.. a. Livelock prone b. Unsafe 3 c. Deadlock prone d. Correct 6. 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 3 hour, the other requires 4 hours. a. How long after the jobs start will the FIRST job finish. 3 8 b. How long after the jobs start will the last job finish. 11 3 c. What is the average response time for the four jobs (with PS) scheduling. 3 (8 + 8 + 10 + 11) / 4 d. What is the average response time if the LJF (LONGEST job first non preemptive scheduling policy is used 3 (4 + 7 + 9 + 11) / 4 7. Suppose 2 processes are to be run and EACH ONE requires 4 minutes of processor time and 6 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. a. If they start at the same time, how long will it be until they both finish? 3 12 Minutes b. How many minutes will the CPU be IDLE during the time that the jobs are running. 3 4 Minutes 8. 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); } In complete, legible, and grammatically correct English sentences, describe what will occur when the hacker runs this program. The cli instruction is priviledged. Therefore, the hackers program will generate an interrupt when it attempts to execute the priviledged 4 instruction while executing in user mode. The OS will then terminate the hacker's program. 9. Consider the following implementation of unlock: [1] STI ;Turn ints back on [2] MOVI LOCKVAL,0 ;Reset the lock value. (a.) In this order the lock will be held with interrupts enabled. On a priority scheduled system, a (very infrequent) potential for deadlock will be created. a. The statements are in the b. The statements are in the WRONG order. correct order 3 c. The order of the statements is irrelevant. 10. Answer the following T or F: (Hint: these are NOT trick questions involving race conditions or transient states) _T_ a. A semaphore that has a positive value never has any suspended processes. _T_ b. A semaphore that has at least one suspended process always has the value 0. 8 _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 postive value will never cause the process to block. 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 11. If statements [4] and [5] were replaced by the statement MOVI LOCKVAL, 1 what BEST describes the result in a multiprocessor system: a. On an MP two processes running in locked step through the locking code could both "obtain" the lock. 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. 12. The conditional jump instruction on line [3] will d. On a UP if the jnz is taken once, it will be taken FOREVER. On an MP the jnz will NOT be taken unless the lock is already held by another process a. Never be taken on single CPU b. Never be taken on single CPUs or mulitple CPU systems. but always taken at least once per call to setlock on multi CPUs 3 c. May or may not be taken on d. Never be taken on single CPU's both single and muliple CPU and may or may not be taken on systems. each call to setlock on a multi CPU system. 13. Consider the following code segment: [1] pid = fork() [2] pipe(pd); [3] if (pid == 0) [4] child_proc(); [5] else [6] parent_proc(); a. How many pipes (not pipe handles) will be created? 3 2 pipes b. Will the parent and child be able to communicate using the pipe(s)? (Yes or No). If your answer is no, describe how to fix the code so that they can. 3 Switch the order of stmts 1 and 2 14. 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) Parent: 3 children child1(); Child1 2 children if (fork() == 0) Child2a 1 child Child2b 1 child child2(); --- if (fork() == 0) 7 children total child3(); a. 3 b. 6 3 c. 7 d. 8 15. Consider the following code segment from a bounded-buffer producer-consumer problem; Producer Consumer wait(mutex); wait(mutex); wait(slot); 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. Is the order of the waits in the above example correct? (yes/no) 3 NO 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: (2) Only when the buffer is full: The producer will lock mutex and block on slot. The consumer will be unable to consume. 1. Only when the buffer was 2. Only when the buffer empty. was full. 3 3. Any time to buffer was either 4. Anytime regardless of the full or empty. state of the buffer. c. The deadlock could occur: (4) 1. Only if there were multiple 2. Only if there were multiple 3 consumers. producers 3. Only if there were multiple 4. Even if there were a single producers AND consumers. producer and consumer. d. The mutex semaphore in the consumer code is necessary This question was broken and not counted the correct answer was only if there were multiple consumers.. 1. Never 2. Only if there are multiple producers 3. If there are either multiple 4. Always.... even if there producers or consumers. is just one producer and one consumer. e. Can changing the order of the signal statements lead to deadlock if the producers and consumers all use the same mutex semaphore. (1.) Since signals don't block order is irrelevant 1. No, never 2. Yes, definitely 3 3. Only when multiple producers or consumers exist. f. Suppose, instead of using a common mutex semphore called "mutex", all producers use a mutex semaphore called "pmutex" and all consumers used a mutex semaphore called "cmutex". Can a deadlock still occur if the order is incorrect?? (yes/no) 3 NO.. With a single mutex producers and consumers cannot impede each other. 16. 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.) threads don't share stacks and local and parameter variables are stack resident. a. The variable 'a' is shared b. 'a' and 'x' are shared but but both threads have private 'c' is private. copies of 'x' and 'c'. 3 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. 17. 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: (d.) The first reader will lock rmutex and block at wsem. Thus subsequent readers will block at rmutex. a. All will be blocked at b. All will be blocked at 3 wsem rmutex c. All but one will be d. All but one will be blocked blocked at wsem at rmutex. 18. Suppose the reader code is completed as follows: wait(rmutex); rcount = rcount - 1; signal(rmutex); if (rcount == 0) signal(wsem); This "solution" is INCORRECT and can lead to a deadlock describe precisely how that deadlock can occur. Suppose the "last" reader sets rcount to 0, signals rmutex, and 4 then gets preempted. Suppose a new reader then arrives, increments rcount, and then blocks on wsem. When the "last" reader gets re-dispatched it will find rcount == 1 and not signal wsem. Thus, no process will ever be able to read or write again.