Operating System Design

National Institute of Technology Rourkela

Year 2010 Question Paper Solution

Question 1a: Which of the following scheduling could result in starvation? Justify.

  • FCFS
  • SJF
  • RR

Ans 1a: Shortest job to completion first (SJC) running a workload with many short jobs can starve long running software.

Priority scheduling suffers from starvation because a low priority process can indefinitely wait because of high priority processes that are continuously input to the system.

Question 1b: Consider a system running ten I/O bound tasks and one CPU bound task. Assume that the I/o bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the context switching overhead is 0.1 millisecond and that all processes are long running tasks. What is CPU utilization for a Round Robin scheduler when:

  • The time quantum is 1 millisecond
  • The time quantum is 10 millisecond

Ans 1b: The time quantum is 1 millisecond: Irrespective of which process is scheduled, the scheduler incurs a 0.1 millisecond context-switching cost for every context-switch. This results in a CPU utilization of 1/1.1*100=91%

The Time quantum is 10 milliseconds: The I/O bound tasks incur a context switch after using up only 1 millisecond of the time quantum. The time required to cycle through all the processes is therefore 10*1.1+10.1(as each I/O bound task executes for 1 millisecond and then  incur the context switch task, whereas the CPU-bound task executes for 10 milliseconds before incurring a context switch). The CPU unitization is therefore 20/21*100=94%

Question 1c: Although two processes may be associated with the same program, they are nevertheless considered two separate execution sequences. Explain Why?

Ans 1c: We emphasize that a program by itself is not a process; a program is a passive entity, while a process is an active entity. It is known that two processes may be associated with the same program; they are nevertheless considered two separate execution sequences. For instance, several users may be running different copies of the mail program, or the same user may invoke many copies of the editor program. Each of this is a separate process, and although text sections are equivalent, the data section varies. It is also common to have a process that spawns (call another process) many process as it runs.

Question 1d: Define the following terms

  • Race Condition
  • Context Switch
  • Safe sequence of execution

Ans 1d: Race Condition: A race condition occurs when two threads access a shared variable at the same time. The first thread reads the variable, and the second thread reads the same value from the variable. Then the first thread and second thread perform their operations on the value, and they race to see which thread can write the value last to the shared variable. The value of the thread that writes its value last is preserved, because the thread is writing over the value that the previous thread wrote.

Context Switch:

Safe Sequence of Execution:


Question 2: Define and explain a solution of the 3rd Readers-Writers problem using semaphores, where the readers and writers are given priorities.

Ans 2: semaphore mutex = 1;                 // Controls access to the reader count

semaphore db = 1;                    // Controls access to the database

int reader_count;                    // The number of reading processes accessing the data




  while (TRUE) {                     // loop forever

     down(&mutex);                          // gain access to reader_count

     reader_count = reader_count + 1;       // increment the reader_count

     if (reader_count == 1)

         down(&db);                         // if this is the first process to read the database,

                                            // a down on db is executed to prevent access to the

                                            // database by a writing process

     up(&mutex);                            // allow other processes to access reader_count

     read_db();                             // read the database

     down(&mutex);                          // gain access to reader_count

     reader_count = reader_count - 1;       // decrement reader_count

     if (reader_count == 0)

         up(&db);                           // if there are no more processes reading from the

                                            // database, allow writing process to access the data

     up(&mutex);                            // allow other processes to access reader_countuse_data();

                                            // use the data read from the database (non-critical)





  while (TRUE) {                     // loop forever

     create_data();                         // create data to enter into database (non-critical)

     down(&db);                             // gain access to the database

     write_db();                            // write information to the database

     up(&db);                               // release exclusive access to the database


Question 3a: Suppose that a scheduling algorithm favours that process that have used the least processor time in the recent past. Why will this algorithm favour I/O bound processes and yet not permanently starve CPU bound processes? Explain

 Ans 3a: It will favor the I/O-bound programs because of the relatively short CPU burst request by them; however, the CPU-bound programs will not starve because the I/O-bound programs will relinquish the CPU relatively often to do their I/O.



Question 3b: How does the wait () and signal () operations associated with monitors differ from the corresponding operations defined for semaphores?

 Ans 3a: A wait operation atomically decrements the value associated with a semaphore. If two wait operations are executed on a semaphore when its value is 1, if the two operations are not performed atomically, then it is possible that both operations might proceed to decrement the semaphore.

Question 4b: Answer the following question using Banker’s Algorithm:

  • Is the System in a safe state?
  • If a request from process P1 arrives for (0,4,2,0) can the request be granted immediately?

 Ans 3a:

  • Is the system in a safe state? Yes. With Available being equal to (1,5, 2, 0), either process P0 or P3 could run. Once process P3 runs, it releases its resources which allow all other existing processes to run.
  • If a request from process P1 arrives for (0,4,2,0), can the request be granted immediately? Yes it can. This results in the value of Available being (1, 1, 0, 0).One ordering of processes that can finish is P0, P2, P3, P1, and P4.


Question 5: Write short note on

  • Inter process communication
  • Multi-processor CPU scheduling.

 Ans 5a:

  • Inter process communication: In computing, inter-process communication (IPC) is a set of methods for the exchange of data among multiple threads in one or more processes. Processes may be running on one or more computers connected by a network. IPC methods are divided into methods for message passing, synchronization, shared memory, and remote procedure calls (RPC). The method of IPC used may vary based on the bandwidth and latency of communication between the threads, and the type of data being communicated.
  • Multi-processor CPU scheduling: In computer science, multiprocessor scheduling is an NP-hard optimization problem. The problem statement is: "Given a set J of jobs where job ji has length li and a number of processors m, what is the minimum possible time required to schedule all jobs in J on m processors such that none overlap?" The applications of this problem are numerous, but are, as suggested by the name of the problem, most strongly associated with the scheduling of computational tasks in a multiprocessor environment. The multiprocessor scheduling problem is a generalization of the optimization version of the number partitioning problem, which considers the case of partitioning a set of numbers (jobs) into two equal sets (processors). For a review of multiprocessor scheduling problems see chapter "Parallel Tasks" in



Post Your Comment Below


G+ BikesOnrent.in