GATE 2013

OPERATING SYSTEM QUESTION AND ANSWERS

Other Operting System Questions

1 What is a process?
Answer: A program in execution.

2 What is a PCB?
Answer: Process control block. It contains various data structures.

3 List some of the queues on a typical system.
Answer: Ready, run, I/O.

4 How are these queues typically implemented?
Answer: FIFO queues, trees, linked-lists.

5 How many device queues are there on a system?
Answer: One for each device.

6 What does the long-term scheduler do?
Answer: Determines which jobs belong in the current mix of running/waiting jobs.

7 What does the short-term scheduler do?
Answer: Determines which of the current jobs should run in the next CPU burst.

8 Which scheduler must work very fast in order not to waste significant CPU time? Which
can be slow?
Answer: Fast: short-term. Slow: long-term.

9 What is the “degree of multiprogramming?”
Answer: Number of jobs in the current mix of running/waiting jobs.

10 When is the long-term scheduler invoked?
Answer: When a job is completed, or when the degree of multiprogramming hasn’t yet
been reached.

11 True/False: The long-term scheduler selects a group of I/O-bound jobs or a group of CPUbound
programs for subsequent activity. Explain.
Answer: False. It selects a mix of jobs for efficient machine utilization.

12 What is time sharing? What kind of scheduling does it involve?
Answer: Time sharing is many users interactively using a system “simultaneously;” each
user gets a share of CPU-time, after other users have gotten their share. It uses mediumterm
scheduling, such as round-robin for the foreground. Background can use a different
scheduling technique.

13 Explain the meaning of: “time sharing depends on negative feedback of the users for
speedy operation.”
Answer: Users who are impatient with the long response time will log off, resulting in
fewer users on the system, with faster response time.

14 What is swapping?
Answer: Copying a process out of memory onto a fast disk or drum, to allow space for
other active processes; it will be copied back into memory when space is ample.

15 What is a context switch?
Answer: The time needed to switch from one job to another.

16 Describe five implementations of the create-new-process mechanism.
Answer:
a. Parent continues executing.
b. Parent stops executing until children are done.
c. Parent and children share all variables.
d. Children share only a subset of parent’s variables.
e. Parents and children share no common resources.

17 Describe the producer/consumer problem.
Answer: The consumer can’t be allowed to use a result until the producer has created
that result, and the producer can’t be allowed to create results if the buffers are all full.

18 Give examples of producer/consumer pairs.
Answer: compiler/linker, linker/loader, card-reader/line-printer

19 How do you implement a circular array?
Answer: Using mod arithmetic, like in clocks.
Note: Several students have said by using linked lists; not so, authors replace the circular
array with a linked list.

20 How do you determine if the buffers (or arrays) are all full in circular arrays?
Answer: If the input-pointer is one less than the output-pointer in mod arithmetic.

21 How do you determine if the buffers (or arrays) are all empty?
Answer: If the input-pointer equals output-pointer.



1.Describe two approaches to off-line processing.
Answer:
a. Data is read from cards onto magnetic tapes, which are in turn mounted manually
on the main system. Printer output from the main system is saved on magnetic tape,
which is then mounted manually on a tape reader attached to a line printer.
b. Data is read from cards ontomagnetic tapes. But the tapes are not removed from their
drives. Instead, a small computer reads them and sends the information to the main
system. Similarly with output.
Review Questions 7
Note: Main difference here is that data was manually exchanged between main computer
and off-line system.


2. What is device independence?
Answer: The feature of systems that allows one input device to be replaced by another
without changes in the users’ programs. Similarly with output. Thus, an old model card
reader can be replaced with a new model; the old device driver programs are replaced by
new ones; user programs need not be changed (though they may need to be relinked).
Note: Many students respond that it is the ability to use different devices. This is false.
You can write a FORTRAN II program to read cards and print to a line printer, two different
devices; yet this does not imply device independence.


3. What were the advantages of off-line operations?
Answer:
a. Main computer no longer constrained by speed of card reader.
b. Application programs used logical I/O devices instead of physical I/O devices; programs
didn’t have to be rewritten when new I/O devices replaced old ones.


4. How have disk systems helped solved problems inherent in off-line systems?
Answer: Off-line systems use magnetic tape. The system cannot read data from one end
of the tape while the card reader writes data on the other end; it takes about 5 minutes to
rewind the tape fully. With disks, it takes only milliseconds to alternate from the portion
of the disk used for input and the portion for output.


5. What is spooling?
Answer: An acronym for “Simultaneous Peripheral Operation On-Line.” It uses the disk
as a large buffer for outputting data to line printers and other devices (like microfilm). It
can also be used for input, but is generally used for output. Its main use is to prevent
two users from alternately printing lines to the line printer on the same page, getting their
output completely mixed together. It also helps in reducing idle time and overlapped I/O
and CPU.


6. How do I/O-bound and CPU-bound programs differ?
Answer:
In I/O-bound programs, the CPU remains idle much of the time.
In CPU-bound programs, the I/O processor remains idle.
Note: I/O is never “faster” than CPU.


7. What is multiprogramming?
Answer: In multiprogramming, several programs are in memory concurrently; the system
switches among the programs for efficient processing, and minimal idle time.
Note: Many students claim multiprogramming “always” keeps CPU and I/O devices busy;
this is false; what is the computer to do at 3 AM Sunday morning, when there’s no job to
run?


8. Define batch systems in terms of interaction.
Answer: They are essentially devoid of interaction between user and program. All problems
must be anticipated, and can’t be corrected on-line.




1 What is a critical section?
Answer: A section of code that only one process at a time can be executing.


2 What is the critical-section problem?
Answer: To design an algorithm that allows at most one process into the critical section
at a time, without deadlock.

3 Why have critical sections of programs, as defined by authors?
Answer: To allow no more than one process in at a time.

4 List the constraints Dijkstra placed on solutions to the critical-section problem.
Answer:
a. Simultaneous execution is equivalent to sequential execution in unknown order.
b. Speeds of the processes are independent of each other.
c. A process in noncritical section can’t prevent other processes fromentering the critical
section.
d. Selection of admitting one process into critical section can’t be indefinitely postponed.

5 What three requirements must a solution to the critical-section problem satisfy?
Answer: Mutual exclusion, progress, bounded waiting.

6 What variable is common between the two processes in algorithm 1?
Answer: turn. Note that i and j are not variables.

7 What is wrong with algorithm 1?
Answer: Since algorithm 1 requires strict alternation of processes in the execution of the
critical section it does not satisfy the progress requirement.

8 What variable(s) is/are common between the two processes in algorithm 2?
Answer: A two-element boolean flag array.

9 What is wrong with algorithm 2? How do you prove it?
Answer: Violates the progress requirement (see page 168).

10 What variables are used in algorithm 3, which are common to both processes?
Answer: A two-element boolean array flag and turn.

11 What does execute “atomically” mean?
Answer: Executed as a group, with no context switches possible until all of the statements
in the group are completed.

12 Define the wait-(postpone) operation, wait(S).
Answer: While semaphore is nonpositive, wait; when semaphore becomes positive, subtract
one and exit.

13 Define the wakeup operation signal(S).
Answer: Add 1 to the semaphore.

14 Suppose we want to execute the statements S1, S2, and S3 in sequence, but that S2 has to be
executed exclusively for one process at a time. Write the code needed using semaphores.
Answer: Assume Q = 1 initially. S1; wait(Q); S2; signal(Q); S3