Example of FCFS CPU Scheduling algorithm

 Evaluate FCFS CPU Scheduling algorithm for given Problem Problem and Average Turn Around Time and Average Response Time  

Process	P1	P2	P3	P4
Process Time	24	3	5	6

Given:

• Processes:
  • P1: Burst Time = 24 ms
  • P2: Burst Time = 3 ms
  • P3: Burst Time = 5 ms
  • P4: Burst Time = 6 ms
• Assumption: All processes arrive at the same time (0 ms), as no specific arrival time is provided.

Step 1: Process Execution Order

In FCFS scheduling, processes are executed in the order they arrive. Since all processes are assumed to arrive at the same time, they will be executed in the order they are listed.

Order of Execution:
P1 → P2 → P3 → P4

Step 2: Calculate Completion Time (CT), Turnaround Time (TAT), and Response Time (RT)

• Completion Time (CT): The time at which each process completes its execution.
• Turnaround Time (TAT): The total time taken from arrival to completion of a process. $$\text{TAT} = \text{Completion Time (CT)} - \text{Arrival Time (AT)}$$
  
• Response Time (RT): The time from the arrival of the process until it starts executing. Since in FCFS, a process starts execution immediately when the CPU is available, the response time is the same as the waiting time. $$\text{RT} = \text{Start Time} - \text{Arrival Time (AT)}$$
  

Execution and Calculations

Process	Burst Time (BT)	Start Time (ST)	Completion Time (CT)	Turnaround Time (TAT)	Response Time (RT)
P1	24 ms	0 ms	24 ms	24 ms	0 ms
P2	3 ms	24 ms	27 ms	27 ms	24 ms
P3	5 ms	27 ms	32 ms	32 ms	27 ms
P4	6 ms	32 ms	38 ms	38 ms	32 ms

Step 3: Average Turnaround Time and Average Response Time

• Average Turnaround Time (TAT):

  $$\text{Average TAT} = \frac{24 + 27 + 32 + 38}{4} = 30.25 \text{ ms}$$

• Average Response Time (RT):

  $$\text{Average RT} = \frac{0 + 24 + 27 + 32}{4} = 20.75 \text{ ms}$$

• Order of Execution: P1, P2, P3, P4
• Average Turnaround Time: 30.25 ms
• Average Response Time: 20.75 ms

Example on SJF CPU Scheduling algorithm

Evaluate SJF CPU Scheduling algorithm for given Problem , Find Average Turn Around Time and Average Response Time  

Process	P1	P2	P3	P4
Process Time	8	4	9	5
Arrival Time	0	1	2	3

Given:

• Processes:
  • P1: Burst Time = 8 ms, Arrival Time = 0 ms
  • P2: Burst Time = 4 ms, Arrival Time = 1 ms
  • P3: Burst Time = 9 ms, Arrival Time = 2 ms
  • P4: Burst Time = 5 ms, Arrival Time = 3 ms

Step 1: Process Execution Order

The SJF algorithm selects the process with the shortest burst time that has arrived and is ready to execute. If two processes have the same burst time, the one that arrived earlier is selected.

Order of Execution:

1. P1 arrives at 0 ms, and it starts execution immediately since it's the only process available.
2. P2 arrives at 1 ms and has the shortest burst time after P1 finishes.
3. P4 arrives at 3 ms and has the shortest burst time after P2 finishes.
4. P3 arrives at 2 ms but has the longest burst time, so it is executed last.

Step 2: Completion Time (CT), Turnaround Time (TAT), and Response Time (RT)

• Completion Time (CT): The time at which each process completes its execution.
• Turnaround Time (TAT): The total time taken from arrival to completion of a process. $$\text{TAT} = \text{Completion Time (CT)} - \text{Arrival Time (AT)}$$
• Response Time (RT): The time from the arrival of the process until it starts executing. $$\text{RT} = \text{Start Time} - \text{Arrival Time (AT)}$$

Execution and Calculations

Process	Arrival Time (AT)	Burst Time (BT)	Start Time (ST)	Completion Time (CT)	Turnaround Time (TAT)	Response Time (RT)
P1	0 ms	8 ms	0 ms	8 ms	8 ms	0 ms
P2	1 ms	4 ms	8 ms	12 ms	11 ms	7 ms
P4	3 ms	5 ms	12 ms	17 ms	14 ms	9 ms
P3	2 ms	9 ms	17 ms	26 ms	24 ms	15 ms

Step 3: Average Turnaround Time and Average Response Time

• Average Turnaround Time (TAT):

  $$\text{Average TAT} = \frac{8 + 11 + 14 + 24}{4} = 14.25 \text{ ms}$$
  

• Average Response Time (RT):

  $$\text{Average RT} = \frac{0 + 7 + 9 + 15}{4} = 7.75 \text{ ms}$$
  

• Order of Execution: P1, P2, P4, P3
• Average Turnaround Time: 14.25 ms
• Average Response Time: 7.75 ms

Examples of Round Robin CPU Scheduling algorithm

 Evaluate Round Robin  CPU Scheduling algorithm for given Problem Time slice =3 ms.

Process	P1	P2	P3	P4
Process Time	10	5	18	6
Arrival Time	5	3	0	4

Given:

• Time Slice (Quantum): 3 ms
• Processes:
  • P1: Burst Time = 10 ms, Arrival Time = 5 ms
  • P2: Burst Time = 5 ms, Arrival Time = 3 ms
  • P3: Burst Time = 18 ms, Arrival Time = 0 ms
  • P4: Burst Time = 6 ms, Arrival Time = 4 ms

Step 1: Order of Execution

We will simulate the round-robin scheduling process:

1. Process Arrival:

   • P3 arrives at time 0 ms. Burst Time = 18 ms
   • P2 arrives at time 3 ms. Burst Time = 5 ms
   • P4 arrives at time 4 ms. Burst Time = 6 ms
   • P1 arrives at time 5 ms. Burst Time = 10 ms

2. Time Chart: We will execute each process for up to 3 ms (time slice) in a round-robin manner, continuing until all processes are completed.

   Time (ms)	Process Executed	Remaining Time of Process
   0 - 3	P3	P3 (15 ms left)
   3 - 6	P2	P2 (2 ms left)
   6 - 9	P4	P4 (3 ms left)
   9 - 12	P1	P1 (7 ms left)
   12 - 15	P3	P3 (12 ms left)
   15 - 17	P2	P2 (0 ms, completed)
   17 - 20	P4	P4 (0 ms, completed)
   20 - 23	P1	P1 (4 ms left)
   23 - 26	P3	P3 (9 ms left)
   26 - 29	P1	P1 (1 ms left)
   29 - 32	P3	P3 (6 ms left)
   32 - 33	P1	P1 (0 ms, completed)
   33 - 36	P3	P3 (3 ms left)
   36 - 39	P3	P3 (0 ms, completed)

Step 2: Calculate Completion Time, Turnaround Time, and Waiting Time

Completion Time (CT): The time at which each process completes execution.

Turnaround Time (TAT): The total time taken from arrival to completion of a process.
$\text{TAT} = \text{Completion Time} - \text{Arrival Time}$

Waiting Time (WT): The total time the process spends waiting in the ready queue.
$\text{WT} = \text{Turnaround Time} - \text{Burst Time}$

Process	Arrival Time (AT)	Burst Time (BT)	Completion Time (CT)	Turnaround Time (TAT)	Waiting Time (WT)
P1	5 ms	10 ms	33 ms	28 ms	18 ms
P2	3 ms	5 ms	17 ms	14 ms	9 ms
P3	0 ms	18 ms	39 ms	39 ms	21 ms
P4	4 ms	6 ms	20 ms	16 ms	10 ms

Step 3: Summary of Metrics

Step 3: Summary of Metrics

• Average Turnaround Time (TAT): $$\text{Average TAT} = \frac{28 + 14 + 39 + 16}{4} = 24.25 \text{ ms}$$
  
• Average Waiting Time (WT): $$\text{Average WT} = \frac{18 + 9 + 21 + 10}{4} = 14.5 \text{ ms}$$
  

• Completion Order: P2, P4, P1, P3
• Average Turnaround Time: 24.25 ms
• Average Waiting Time: 14.5 ms

==========================================================================

Consider 3 processes P1, P2 and P3, which require 5, 7 and 4 time units and arrive at time 0, 1 and 3. Draw the Gant chart, process completion sequence and average waiting time for. Round robin scheduling with CPU quantum of 2 time units.

Given:

• Processes:
  • P1: Burst Time = 5 ms, Arrival Time = 0 ms
  • P2: Burst Time = 7 ms, Arrival Time = 1 ms
  • P3: Burst Time = 4 ms, Arrival Time = 3 ms
• Time Quantum: 2 ms

Step 1: Gantt Chart

1. Initial State:

   • P1 arrives at 0 ms.
   • P2 arrives at 1 ms.
   • P3 arrives at 3 ms.

2. Execution Sequence:

   • Time 0 - 2: P1 executes (Remaining Burst Time: P1 = 3 ms).
   • Time 2 - 4: P2 executes (Remaining Burst Time: P2 = 5 ms).
   • Time 4 - 6: P3 executes (Remaining Burst Time: P3 = 2 ms).
   • Time 6 - 8: P1 executes (Remaining Burst Time: P1 = 1 ms).
   • Time 8 - 10: P2 executes (Remaining Burst Time: P2 = 3 ms).
   • Time 10 - 12: P3 executes (Remaining Burst Time: P3 = 0 ms, completed).
   • Time 12 - 14: P1 executes (Remaining Burst Time: P1 = 0 ms, completed).
   • Time 14 - 16: P2 executes (Remaining Burst Time: P2 = 1 ms).
   • Time 16 - 17: P2 completes (Remaining Burst Time: P2 = 0 ms).

Gantt Chart:

Step 2: Completion Time (CT), Turnaround Time (TAT), and Waiting Time (WT)

Completion Time (CT): The time at which each process completes its execution.

Turnaround Time (TAT): The total time taken from arrival to completion. $\text{TAT} = \text{Completion Time (CT)} - \text{Arrival Time (AT)}$

Waiting Time (WT): The total time a process spends waiting in the ready queue. $\text{WT} = \text{Turnaround Time (TAT)} - \text{Burst Time (BT)}$

Process	Arrival Time (AT)	Burst Time (BT)	Completion Time (CT)	Turnaround Time (TAT)	Waiting Time (WT)
P1	0 ms	5 ms	14 ms	14 ms	9 ms
P2	1 ms	7 ms	17 ms	16 ms	9 ms
P3	3 ms	4 ms	12 ms	9 ms	5 ms

Step 3: Average Waiting Time

• Average Waiting Time (WT): $$\text{Average WT} = \frac{9 + 9 + 5}{3} = 7.67 \text{ ms}$$
  

• Completion Time (CT): P1 = 14 ms, P2 = 17 ms, P3 = 12 ms

• Average Turnaround Time (TAT): 13 ms

• Average Waiting Time (WT): 7.67 ms

Operating Systems MCQ Unit-3

 The critical section problem is primarily concerned with:

a) Process creation

b) Memory management

c) Process synchronization

d) Deadlock prevention

Which of the following conditions must be satisfied to solve the critical section problem?

a) Mutual Exclusion, Progress, Bounded Waiting

b) Mutual Exclusion, Deadlock, Fairness

c) Progress, Fairness, Memory Management

d) Mutual Exclusion, Paging, Swapping

The principle of mutual exclusion ensures that:

a) Multiple processes can enter their critical sections simultaneously

b) Only one process is allowed to execute in its critical section at a time

c) Processes execute independently without synchronization

d) No process enters the critical section

A mutex lock is used to:

a) Allow multiple processes to enter the critical section

b) Protect a critical section by ensuring mutual exclusion

c) Switch between user and kernel modes

d) Handle memory allocation dynamically

If a process holds a mutex lock, and another process tries to acquire it:

a) The other process will proceed immediately

b) The other process will be blocked until the lock is released

c) Both processes will enter the critical section

d) The lock will be shared between the processes

Which of the following problems can occur if a mutex lock is not used properly?

a) Deadlock

b) Starvation

c) Race Condition

d) All of the above

The Dining Philosophers problem is an example of:

a) Deadlock

b) Starvation

c) Mutual Exclusion

d) All of the above

In the Producer-Consumer problem, the buffer is used to:

a) Store processes

b) Store resources

c) Store items produced by the producer before they are consumed by the consumer

d) Store memory allocation information

In the Readers-Writers problem, a writer is allowed to write if:

a) No other process is writing

b) No process is reading or writing

c) At least one reader is reading

d) Another writer is writing

Which of the following is a solution to prevent deadlock in the Dining Philosophers problem?

a) Allowing at most 3 philosophers to sit at the table at the same time

b) Using semaphores to restrict the number of philosophers that can pick up forks

c) Allowing philosophers to eat in turns

d) Avoiding the use of shared resources

Operating Systems MCQ Unit- 2

 

A process in execution is called:

a) Program

b) Task

c) Thread

d) Job

The Process Control Block (PCB) does NOT contain:

a) Process State

b) Program Counter

c) Memory Management Information

d) I/O Devices List

Which of the following is NOT a possible state for a process?

a) New

b) Ready

c) Running

d) Exited

A process that is terminated but still available in the process table is called:

a) Orphan

b) Zombie

c) Suspended

d) Blocked

Which of the following is a CPU scheduling algorithm?

a) Round Robin

b) Least Recently Used

c) First-In-First-Out

d) Quick Sort

In pre-emptive scheduling, the CPU can be taken away from a process:

a) Only when the process finishes

b) Only if a process requests I/O

c) By the operating system to allocate to another process

d) None of the above

The turnaround time of a process is defined as:

a) Time taken to complete the execution of a process

b) Time taken to load the process into the CPU

c) Time taken for a process to move from ready to running state

d) Time taken to block a process

In which of the following scheduling algorithms is the waiting time for a process minimized?

a) First-Come, First-Served (FCFS)

b) Shortest Job Next (SJN)

c) Round Robin (RR)

d) Priority Scheduling

The fork() system call is used to:

a) Terminate a process

b) Create a new process

c) Execute a new program

d) Bring a process to the foreground

What happens to the parent process when the child process is terminated?

a) The parent process also terminates

b) The parent process must terminate the child

c) The parent process receives a SIGCHLD signal

d) The parent process is suspended until the child terminates

Operating Systems MCQ Unit-1

 

Which of the following is not considered a system service?

a) Process Management

b) Memory Management

c) User Authentication

d) Text Editing

System services are typically provided by the:

a) Hardware

b) User Applications

c) Operating System

d) None of the above

Which of the following is an example of a system call?

a) printf()

b) fork()

c) scanf()

d) strlen()

System calls provide an interface between:

a) User and Hardware

b) User and System Programs

c) User and Kernel

d) Hardware and Kernel

Which of the following is NOT a system program?

a) File Management Utilities

b) Compilers

c) Text Editors

d) Web Browsers

System programs are designed to:

a) Allow user interaction with hardware directly

b) Facilitate development of user applications

c) Manage system resources

d) Execute system calls directly

The layered approach to system structure implies:

a) Each layer is independent of others

b) Lower layers provide services to upper layers

c) Upper layers control the lower layers directly

d) All layers operate simultaneously

In a microkernel system structure, most of the operating system functions are:

a) Located in the kernel

b) Implemented in user space

c) Not present

d) Controlled by hardware

During the system boot process, the first program that is typically loaded is:

a) Bootloader

b) Operating System

c) BIOS/UEFI

d) Kernel

Which of the following steps occurs first during the system boot process?

a) Loading the Kernel

b) Loading the Bootloader

c) Power-On Self Test (POST)

d) Initializing System Services

Question Bank Operating Systems

 

Operating System Question Bank

Unit-1

1. Define Operating System and explain the various types of Operating Systems?

2. Explain Operating System Structures?

3. Explain the different functions of an operating system and discuss the various services provided by an operating system.

4. Explain about the dual mode operation in OS with a neat block diagram.

5. What is operating system? Explain multiprogramming and time sharing systems.

6. Explain briefly concept of virtual machines

7. Write the differences between monolithic kernel and microkernel.

8. Explain briefly system calls with examples.

9. Explain different operations performed by the operating system.

10. Explain different types of system calls with suitable example.

11. What are the functionalities of Operating Systems? Explain in detail

12. Explain difference between Multitasking and Multi Programming?

13. Explain briefly User and Operating System Interface

Unit-2

1. Define Process? Explain process State diagram? Explain about process schedulers?

2. Consider 3 processes P1, P2 and P3, which require 5, 7 and 4 time units and arrive at time 0, 1 and 3. Draw the Gant chart, process completion sequence and average waiting time for. i) Round robin scheduling with CPU quantum of 2 time units. ii) FCFS.

3. Explain CPU Scheduling Algorithms with examples?

4. Explain about Scheduling Criteria.

5. Evaluate FCFS CPU Scheduling algorithm for given Problem Problem and Average Turn Around Time and Average Response Time  

Process	P1	P2	P3	P4
Process Time	24	3	5	6

6. Evaluate SJF CPU Scheduling algorithm for given Problem and Average Turn Around Time and Average Response Time  

Process	P1	P2	P3	P4
Process Time	8	4	9	5
Arrival Time	0	1	2	3

7. Evaluate Round CPU Scheduling algorithm for given Problem Time slice =3 ms.

Process	P1	P2	P3	P4
Process Time	10	5	18	6
Arrival Time	5	3	0	4

8. Explain in detail Inter Process Communication? 

9. With a neat sketch explain process state diagram.

10.  Write the difference between user level thread and kernel level thread?            

11. What are the criteria for evaluating the CPU scheduling algorithm?      

12. What is a process? Explain Process Control Block.

Unit-3

1. What is critical section problem? Explain with example?   

2. What is Semaphore? Explain producer consumer problem using semaphore?      

3. Define process synchronization and explain any one method of synchronization?           

4. What is Monitor? Explain with any example using monitor?        

5. Explain the solution for Dining-Philosophers Problem    

6. What are the methods for handling deadlock.  

7. Write about deadlock and starvation?

8. Explain about Deadlock Avoidance?     

9. Explain how recovery from deadlock? 

10. Explain Dead lock detection (Banker’s Algorithm) with Example?           

11. Write about Deadlock Prevention Methods?  

12. What is synchronization? What are the different synchronization mechanisms? Explain in detail.

13. Discuss about the following   

A)           Semaphore        

B)           Monitor