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 Computer Science 422/622 Test 1 - Feb 20,1996 Name________________________ 1. 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. Dispatch | ---------------------|--------------------- | b. Suspend_Self | ---------------------|--------------------- | c. Preempt | ---------------------|--------------------- 2. Both of the following attempts at a software solution to the mutual exclusion problem has one of the fundamental failures that we discussed in class. Provide the name of the failure and describe the precise sequence of events that could lead to its occurrence. a. 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; Problem: How it might occur: b. 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; Problem: How it occurs: 3. Answer the following T or F. ___ a. The number of processes in the "Running" state can never exceed the number of processors in the computer system. ___ b. A process that did a tremendous amount of computation and very little I/O would typically spend more time in the "Blocked" state than one which did a large amount of I/O and a small amount of computation. ___ c. A process could never enter the "Ready" state more times than it entered the "Blocked" state. ___ d. A process could never be dispatched while in the Swapped-Out-Ready state. 4. We identified some hardware elements that were more-or-less mandatory prerequistes to being able to build a robust OS. Two of these were a hardware interrupt capability and a timer capable of generating interrupts. What were the other two? 1 - 2 - 5. For each of the following identify if it is primarily a hardware function (H), and OS function O, or the responsibility of the application program (A). ___ a. Save the Stack Pointer of a process to be prempted in the process's PCB. ___ b. Determine if an interrupt should occur when the execution of each machine instruction completes. ___ c. Determine which process should be swapped out when memory is overcommitted. ___ d. Push the IP and Flags registers onto the stack at the instant an application process is interrupted. 6. Suppose 2 processes are to be run and EACH ONE requires 10 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? 7. Suppose an application program enters and infinite loop. Which of the following best describes the mechanism used by the OS to regain control from the looping application. a. A timer interrupt causes a b. The OS periodically tests transfer of control to the applications for looping OS. conditions. c. The application is responsible d. None of the above applies. for periodically signalling the OS that all is well. 8. 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? 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. 9. Answer the following T or F: ___ a. A semaphore that has the value 0 always has at least one suspended process. ___ b. A semaphore that has at least one suspended process always has the value 0. ___ c. A signal operation on a semaphore that has a positive value at the time of the signal always causes the value of the semaphore to be incremented. ___ d. A wait operation on a semaphore with a non-empty wait queue never changes the value of the semaphore. 10. Consider the following function "testit" which could conceivably be run either as two threads or as two processes static int a; | thr_create(0,0, testit, 0) | if (fork() == 0) void testit( | thr_create(0,0, testit, 1) | testit(0) int b) | | if (fork() == 0) { | | testit(1) int c; | | -------------------------------------------------------------- variable | thread | process a | | |-----------------------------|---------------- b | | |-----------------------------|---------------- c | | |-----------------------------|---------------- Fill in the above table using the words "private" or "shared" depending on whether the variable is a private copy or a shared copy in the multi-thread and multi-process environments. 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 removed which of the following BEST describes the result in a multiprocessor system: (Note:these are NOT the same statements as on the quiz). a. it would no longer work b. it would still work correctly correctly and but it would but it would be slower. be faster. c. it still work correctly and it would be faster. 12. 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. be faster. c. it still work correctly and it would be faster. 13. Suppose that the instruction [5.1] STI ;turn ints back on were inserted after statement [5] The result would be that a. The system would work b. The system would work worse better because the amount because multiple processes of disabled int code would might mistakenly be allowed be reduced. to hold the lock at the same time. c. The system would work worse d. The system would work worse if priority scheduling were because of both b. and c. in use because a low priority process might be preempted while holding the lock. 14. 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) 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. Any time to buffer was either 4. Anytime regardless of the full or empty. state of the buffer. c. 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. Only when multiple producers or consumers exist. 15.a. We described a semaphore as a data structure consisting of three components.. Fill them with a comment describing the function of each. (Hint: all three are used in part b). struct semtype { }; b. Using your data structure above, fill in an implementation of the signal system call. You may assume the existence of functions setlock(int *lock) and unlock(int *lock) and call them as needed. void signal(struct semtype *sem) { } Computer Science 422/622 Test 1 - Feb 21 1995 Name________________________ 1. Each of the following attempts at a software solution to the mutual exclusion problem has a fundamental problem (e.g., not safe, deadlock prone, livelock prone, strict alternation of turns). Identify each problem and explain precisely how it could occur. a. Process 1 Process 2 [1] p1using = TRUE; p2using = TRUE; [2] while (p2using == TRUE); while (p1using == TRUE); [3] -- critical section --- -- critical section --- [4] p1using = FALSE; p2using = FALSE; Problem: How it occurs: b. Process 1 Process 2 [1] RETRY: RETRY: [2] p1using = TRUE; p2using = TRUE; [3] if (p2using == TRUE) if (p1using == TRUE) [4] { p1using = FALSE; { p2using = FALSE; [5] goto RETRY; } goto RETRY; } [6] -- critical section --- -- critical section --- [7] p1using = FALSE; p2using = FALSE; Problem: How it occurs: c. Process 1 Process 2 [1] while (p2using == TRUE); while (p1using == TRUE); [2] p1using = TRUE; p2using = TRUE; [3] -- critical section --- -- critical section --- [4] p1using = FALSE; p2using = FALSE; Problem: How it occurs: 2. Which of the following is not a DISADVANTAGE of the use of Dekker's algorithm. a. It uses busy waiting. b. It won't work on a multiprocessor. c. It won't work for more than d. It is complicated to program two processes. and therefore easy to program incorrectly. 3. Consider the following code segment from a bounded buffer producer consumer problem; Producer Consumer wait(slot); wait(item); wait(mutex); 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. Circle ALL conditions under which the wait(mutex) in the PRODUCER is necessary: 1. One producer and one consumer. 3. One producer and two consumers. 2. Two producers and one consumer. b. If multiple producers and consumers all use the same mutex semaphore and the producer code interchanged the order of its waits, a deadlock could occur. Could THIS deadlock occur 1. Only when the buffer was 2. Only when the buffer empty. was full. 3. Anytime regardless of the state of the buffer. c. 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. Only when multiple producers or consumers exist. 4. Answer the following questions T or F: ___ a. A process can never be dispatched while in a swapped out state. ___ b. It is generally more desirable to swap out processes that are suspended than processes that are ready to run. ___ 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. ___ d. A process should be swapped out each time it is suspended to wait for the completion of a disk i/o operation. 5. Answer the following T or F (considering waits and signal to be atomic operations... i.e. don't consider transient states that might exist while a wait or signal is being executed.) ___ a. A semaphore that has the value 1 never has a blocked process. ___ 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). ___ c. A semaphore that has at least one suspended process always has the value 0. ___ 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. ___ e. 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 6. If statements [4] and [5] were removed which of the following BEST describes the result in a multiprocessor system: (Note:these are NOT the same statements as on the quiz). a. it would no longer work b. it would still work correctly correctly and but it would but it would be slower. be faster. c. it still work correctly and it would be faster. 7. 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. be faster. c. it still work correctly and it would be faster. 8. Suppose that the instruction [5.1] STI ;turn ints back on were inserted after statement [5] The result would be that a. The system would work b. The system would work worse better because the amount because multiple processes of disabled int code would might mistakenly be allowed be reduced. to hold the lock at the same time. c. The system would work worse d. The system would work worse if priority scheduling were because of both b. and c. in use because a low priority process might be preempted while holding the lock. 9. 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. Dispatch | ---------------------|--------------------- | b. Suspend_Self | ---------------------|--------------------- | c. Preempt | ---------------------|--------------------- | d. Unsuspend | | 10. Consider the following solution to the readers and writers problem (assume semaphores are FIFO). reader: writer: wait(wsem); wait(wsem); read; write; signal(wsem); signal(wsem); a. Will this solution let either readers or writers starve. If so, who starves and how does it happen. b. Is this solution safe. That is, does it ensure that when a writer is writing no other writer can write and no reader can read. c. What is the principal disadvantage of this solution when compared with the solution described in class. 11. Suppose an application program gets into an infinite loop. Identify the answer which best decribes the mechanism used by the OS to be able to preempt the looping program. a. Each application is required b. The OS activates the SIG_INT to periodically call the OS manager associated with each to ensure all is well. application. c. A timer interrupt occurs. d. Each process periodically requests a change from the RUN to the READY state. a. What data elements were part of the semaphore structure that we described in our implementation of wait(). struct semtype { }; b. Write an implementation of the signal() operation on a counting semaphore.. You may assume that you have a correctly functioning setlock() and rlselock() lock management functions available to you. void signal( struct semtype *sem) { Computer Science 422/622 Test 1 - Feb 22 1993 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. Dispatch | ---------------------|--------------------- | b. Suspend_Self | ---------------------|--------------------- | c. Preempt | ---------------------|--------------------- | d. Unsuspend | | 2. Both of the following attempts at a software solution to the mutual exclusion problem has a fundamental problem.. For both cases identify the problem and describe the sequence of events that could lead to its occurrence: a. Process 1 Process 2 p1using = TRUE; p2using = TRUE; while (p2using == TRUE); while (p1using == TRUE); -- critical section --- -- critical section --- p1using = FALSE; p2using = FALSE; Problem: How it occurs: b. Process 1 Process 2 while (p2using == TRUE); while (p1using == TRUE); p1using = TRUE; p2using = TRUE; -- critical section --- -- critical section --- p1using = FALSE; p2using = FALSE; Problem: How it occurs: 3. Which ONE of the following is NOT a disadvantage of using Dekker's algorithm in application code. a. It is based on busy waiting. b. It is not safe on a multi processor system. c. It can't be easily extended d. It requires that processes if more than two processes have access to each others require mutex. data. 4. Answer the following questions T or F: ___ a. The swapper or medium term scheduler is a non-preemptive scheduler. ___ b. A process can never be dispatched while in a swapped out state. ___ c. It is generally more desirable to swap out processes that are suspended than processes that are ready to run. ___ d. A process can never be swapped out while in a Ready to Run state. ___ e. A process should be swapped out each time it is suspended to wait for the completion of a disk i/o operation. 5. Answer the following T or F: ___ a. A semaphore that has the value 0 always has at least one suspended process. ___ 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). ___ c. A semaphore that has at least one suspended process always has the value 0. ___ 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. 6. a. Write a pseudo-code implementation of the signal operation on a counting semaphore.. Include all necessary steps to ensure required mutual exclusion on single and multi cpu systems. (Don't worry about EFFICIENT acquisition of locks here). signal(sem) struct semtype *sem; { b. Is the order of lock acquisition and interrupt disabling important or irrelevant? c. Is the order of lock release and interrupt enabling important or irrelevant? d. Can the use of TS locks be safely eliminated from a single processor version of your solution. e. Can the use of disabling be safely eliminated from a multiprocessor version of your solution. 7. Consider the following solution to the producer consumer problem: PRODUCER: CONSUMER: while (1) while (1) { { wait(mutex) wait(numitems) wait(numslots) wait(mutex) produce consume signal(mutex) signal(mutex) signal(numitems) signal(numslots) } } a. Can the above solution deadlock? If so, explain exactly how, if not explain why not. b. Would reversing the order of either of the signals produce a potential for deadlock? If so, explain exactly how the deadlock could occur. c. Circle ALL conditions under which the wait(mutex) in the CONSUMER is necessary: 1. 1 producer and 1 consumer. 2. 1 producer and 2 consumers. 3. 2 producers and 1 consumer. 4. 2 producers and 2 consumers. 8. Consider the following solution to the readers and writers problem (assume semaphores are FIFO). reader: writer: wait(wsem); wait(wsem); read; write; signal(wsem); signal(wsem); a. Will this solution let either readers or writers starve. If so, who starves and how does it happen. b. Is this solution safe. That is, does it ensure that when a writer is writing no other writer can write and no reader can read. c. What is the principal disadvantage of this solution when compared with the solution described. 9. Select the one response from each of the three following rows which best characterizes how a message passing system should be configured in order to best emuluate counting semaphores. a1. Non blocking sends xor a2. Blocking sends b1. Non blocking receives xor b2. Blocking receives c1. Direct naming xor c2. Indirect naming. 10. When message passing is used to emulate a counting semaphore exactly how does the message passing system represent the current value of the counting semaphore. I can't seem to locate this year's test1.. Here is a similar one from last year. I will try to find it at home tonight. Computer Science 422/622 Test 1 - Feb 19 1992 Name________________________ 1. Each of the following attempts at a software solution to the mutual exclusion problem has a fundamental problem (e.g., not safe). Identify each problem. a. Process 1 Process 2 p1intending = TRUE; p2intending = TRUE; while (p2intending == TRUE); while (p1intending == TRUE); -- critical section --- -- critical section --- p1intending = FALSE; p2intending = FALSE; --> b. Process 1 Process 2 RETRY: RETRY: p1intending = TRUE; p2intending = TRUE; if (p2intending == TRUE) if (p1intending == TRUE) { p1intending = FALSE; { p2intending = FALSE; goto RETRY; } goto RETRY; } --> c. Process 1 Process 2 while (p2intending == TRUE); while (p1intending == TRUE); p1intending = TRUE; p2intending = TRUE; -- critical section --- -- critical section --- p1intending = FALSE; p2intending = FALSE; --> 2. Identify the two hardware items needed to implement the most simple form of multitasking: a. b. 3. The number of processes actually executing instructions on a computer system at any instant in time is limited: a. 1 b. The number of CPU's in the system. c. The maximum number of d. The number of processes processes the OS can support. currently in memory. 4. The rate at which an OS such as Unix dispatches and blocks or preempts processes on a system like hubcap is closest to: a. Once a day b. Once an hour. c. Once a minute d. Many times per second. 5. Answer the following T or F. ___ a. The number of processes in the "Ready to Run" state can never exceed the number of processors in the computer system. ___ b. A process that did a tremendous amount of computation and very little I/O would typically spend more time in the "Blocked" state than one which did a large amount of I/O and a small amount of computation. ___ c. A process could never enter the "Ready" state more times than it entered the "Blocked" state. ___ d. Dekker's algorithm is a safe way for two processes to ensure multual exclusion on a multiprocessor system. 6. It is generally not a good idea to swap out a process unless it will remain swapped out for at least: a. Several hours b. Several minutes c. Several seconds d. Several milliseconds. 7. When a process is suspended waiting for a single disk I/O to complete: a. It would typically be b. It would typically be swapped swapped out and in out and in once. several times. c. It would typically not be swapped out at all. 8. In a well-tuned multi-user system a process is typically: a. Swapped more often than b. Dispatched more often than swapped. dispatched. c. Swapped and dispatched about the same. 9. When a process must be swapped out, it is better to choose: a. A ready process b. A suspended process. c. A process that is not d. A process that has not been using much memory. dispatched since last swapped in. 10. Answer the following T or F ___ a. A semaphore that has a positive value never has any process waiting on it. ___ b. Waiting on a semaphore that has a value of zero may or may not cause a process to be blocked. ___ c. Signalling a semaphore that has a value of 0 always causes a process to become unblocked. ___ d. Signalling a semaphore that has a positive value will always cause the value to be incremented. 11. Answer the following T or F ___ a. A process is put in the Suspended (Blocked) state while attempting to acquire a test and set lock. ___ b. In a multiprocessor implementation of wait, the lock that protects the semaphore will be held (=1) while an application processes through a critical section. ___ c. Performing a wait operation before entering a critical section guarantees that a process will not be preempted before it leaves the critical section. 12. a. In a multiprocessor system describe exactly what problem can be caused by failure to disable interrupts before acquiring a test and set lock. b. How (if at all) would your answer change for a single processor system. 13. In a producer-consumer problem the use of a mutual exclusion semaphore is necessary a. Never b. Always c. Only if there is exactly d. If there are multiple producers one producer and one consumer or consumers. 14. The producer-consumer problem can deadlock if waits are placed in the wrong order in the following case(s) a. Producers use a different b. Producers and consumers mutex semaphores than use the same mutex semaphore consumers. c. In either case a or b. d. Never. 15. The producer-consumer problem can deadlock if signals are placed in the wrong order in the following case(s) a. Producers use a different b. Producers and consumers mutex semaphores than use the same mutex semaphore consumers. c. In either case a or b. d. Never. 15. Consider the following solution to the producer consumer problem: PRODUCER: CONSUMER: while (1) while (1) { { wait(numslots) wait(mutex) wait(mutex) wait(numitems) produce consume signal(mutex) signal(numslots) signal(numitems) signal(mutex) } } Can the above solution deadlock? If so, explain exactly how, if not explain why not. Consider the solution to the readers and writers problem shown on the next page: 16. The solution is best characterized as: a. FCFS b. Reader priority c. Writer priority. d. LCFS 17. The processes waiting on the semaphore "wsem" could include: a. Multiple readers and b. Multiple readers but at most multiple writers. one writer c. At most one reader but d. At most one reader and one multiple writers. writer. 18. Suppose multiple writers were waiting to write and there were NO waiting readers. A reader that arrived at this point would: a. Pass the waiting writers b. Read as soon as the last writer and read as soon as the in queue at the time of the active writer finished. readers arrival finished. c. Be passed in the queue by any writers arriving after the reader. 19. The processes waiting on the semaphore "s" could include: a. Multiple readers and b. Multiple readers but at most multiple writers. one writer c. At most one reader but d. None of the above. multiple writers.