Test 2
Operating Systems and Networking
Fall 2013
October 22, 2013
Answer only five questions from below
1. List three degrees of awareness between processes. Why is ‘process-awareness’ an important issue in designing efficient schemes for interprocess communication?
Ans. A process could be in three stages of awareness with regard to its knowledge of other processes. These are: (a) in contention or competition mode, (b) indirectly aware of each other, and (c) directly aware of each other. The means of communication would be predicated by their ability to sense each other. In (c), they could use mailboxes or similar construct to communicate, in (b) they would most likely use shared objects, and in (a) they would contend for their resources via locks.
2. What is a critical section for a process? What is a busy waiting with regard to an entry into a process’s critical section? Is buys waiting always less efficient (in terms of using processor time) than a blocking wait? Explain.
Ans. A CS is the section of a code that includes the explicit use of sharable resource(s) to carry out some specific action. Busy waiting is the process of checking repeatedly the availability of a specific critical resource by acquiring the CPU. Since it wastes CPU time, it is generally frowned upon; however, if the amount of waiting is extremely small, one could allow busy-waiting in some cases.
3. What are the two most widely used models of interprocess communications? What are their strengths and weaknesses?
Ans. Two models are: (a) Using semaphores, and (b) using message passing
Pros and cons of (a): Semaphores are easy to use. However they are error prone.
Pros and cons of (b): Message passing is straightforward via mailboxes particularly for small messages. Time wasted for large messages, and security issues are two of its weaknesses.
4. The following code attempts to portray a producer/consumer problem below for an infinite buffer case. For some reason, it doesn’t work. Rewrite the code so that it can ruin properly with appropriate environment setting.
producer() { consumer() {
while (true) { while (true) {
produce(item); wait(producer);
insert(item, buffer); item=delete(buffer);
signal(consumer); consume(item);
} }
Ans. Producer() { consumer () {
while (true) { while (true) {
produce(item); wait(full);
wait(empty); wait(buffer);
wait(buffer); item=delete(Buffer);
insert(item, Buffer); signal(buffer);
signal(buffer); signal(empty);
signal(full); consume(item);
} }
With the global shared variables: semaphore buffer = 1; semaphore empty = n (a high value);
Semaphore full=0; item Buffer [n]; ..
5. Indicate a solution scheme for n-Readers/Writers problem using Petri Net. We assume one or more readers (with a maximum of n readers) may read a shared object concurrently so long as there is no writing. Similarly, writer processes may share the object for writing; however, only one writer process at a time can be in its critical section. You must label each transition and place approriately.
6. Draw a Petri Net that shows two processes in a deadlock state labeling each place and transition appropriately.
7. Consider the deadlock situation that can happen in the dinning philosophers’ problem where the philosophers obtain the chopsticks one at a time. Discuss how the four necessary conditions for deadlock indeed hold in this setting. Discuss how one can avoid deadlocks by eliminating any of the four conditions.
Ans. Mutual Exclusion: When chopsticks are not shared. (To deny this share the chopsticks)
Hold & Wait: One chopstick at a time is picked up (To deny this both chopsticks must be picked up simultaneously) No Preemption (No one can ‘order’ others to return single chopstick (To deny this, one should have the capability to do so. Design one that is appropriate).
Circular waiting: Everyone has a single chopstick. ( To deny this, ask one to return one’s single chopstick back to the table).
8. Although a state of ‘starvation’ and that of a ‘deadlock’ are apparently very similar, they are very different. Indicate, why! How does one detect the two states?
Ans. Starvation is always due to lower process priority compared to those of others participating. Deadlock is something else that does not deal with priority. Eventually one might come out from a starved state, but from a deadlock embrace one cannot come out on one’s own. Define deadlock now. Detecting starving processes is difficult, but deadlock detection is easier. One could use circular wait check to detect deadlock.
9. The following processes join the CPU queue to run. Their arrival times and the CPU times are posted below.
Processes / Arrival time / CPU timeA / 0 / 10
B / 2 / 6
C / 3 / 1
D / 5 / 3
(a) Using FCFS CPU scheduling,
▪ Draw the Gantt chart (time chart)
▪ Find the minimum schedule length
▪ Find the average Turnaround time
▪ Find the average Queuing time
(b) Same as (a), but the schedule discipline is Shortest Process Next.
10. Most round-robin schedulers use a fixed sized quantum. Give an argument in favor of small quantum. Now give an argument in favor of large quantum. Are there any for which both are reasonable?
Ans. Small quantum size favors shorter jobs. Large quantum size favors larger jobs particularly if context-switching time is a costly event. Both are reasonable to adopt when jobs are in interactive modes (doing I/O) and are of mostly same size.
[Bonus] True, or False! Each correct answer earns three points.
a. A deadlock state occurs whenever a process is unable to release its request for a resource after use. F.
b. Non-blocking Receive will return either with a message or without a message. T
c. Hold and Wait condition can be prevented by requiring that a process gets all its resources at one time. T
d. Banker’s algorithm to avoid deadlock is unrealistic. T
e. In a multilevel feedback queue system, I/O bound processes tend to populate the bottom lower priority queues. F