HOME    >    IB    >    COMPUTER FUNDAMENTALS
NEXT PAGE >
INTERUPT HANDLING

COMPUTER FUNDAMENTALS | OPERATING SYSTEMS

DESIGNED FOR IB EXAMINATIONS
OBJECTIVES
A1.3.3 Compare different approaches to scheduling.
• Managing the execution of processes by allocating CPU time to optimize system performance
• First-come first-served, round robin, multilevel queue scheduling, priority scheduling​
  • LEARN
  • TERMINOLOGY
  • QUESTIONS
  • FLASHCARDS
  • WORKBOOK
<
>

SECTION 1 | MANAGING THE EXECUTION OF PROCESSES

An operating system uses CPU scheduling to manage the execution of processes by deciding how processor time is allocated. Because a computer typically runs many processes at the same time, the CPU must be shared efficiently to optimize overall system performance.

Purpose of CPU Scheduling
The CPU can only execute one process at a time. CPU scheduling ensures that:
  • Multiple processes can make progress
  • The system remains responsive to user input
  • Hardware resources are used efficiently

By carefully allocating CPU time, the operating system creates the illusion that many programs are running simultaneously.

How CPU Time Is Allocated
The operating system divides CPU time among active processes. This is usually achieved by:
  • Selecting a process from a ready queue
  • Allowing it to run for a short period of time
  • Suspending it and switching to another process if needed

This rapid switching between processes is known as context switching and is fundamental to multitasking systems.

Optimising System Performance
When allocating CPU time, the operating system aims to optimize performance according to several criteria:
  • Responsiveness: Interactive systems must respond quickly to user actions, such as typing or clicking.
  • Throughput: The number of processes completed in a given period of time should be maximized, especially in batch systems.
  • Fairness: All processes should receive a reasonable share of CPU time, preventing starvation.
  • CPU Utilisation: The processor should be kept as busy as possible without overloading the system.

Different systems may prioritize these goals differently. For example, a desktop computer emphasizes responsiveness, while a server may prioritize throughput.

Role of Scheduling Algorithms
To manage CPU time effectively, operating systems use scheduling algorithms. Each algorithm follows specific rules to decide which process runs next and for how long. The choice of scheduling approach has a significant impact on system performance, user experience, and fairness.

Managing the execution of processes through CPU scheduling is essential for efficient multitasking. By allocating CPU time carefully, the operating system optimizes performance and ensures smooth and reliable system operation.

Why does an operating system allocate CPU time between processes?

A. To store files and folders efficiently.
B. To allow multiple processes to run fairly and optimize system performance.
C. To translate programs into machine code.
D. To manage hardware device connections.

SECTION 2 | FIRST COME FIRST SERVED

First-Come, First-Served (FCFS) is one of the simplest CPU scheduling algorithms used by operating systems. As its name suggests, processes are executed in the order in which they arrive in the ready queue.

How FCFS Scheduling Works
When a process becomes ready to run, it is placed at the end of a queue. The CPU selects the process at the front of the queue and allows it to run until it completes or blocks (for example, waiting for input/output).

Key characteristics of FCFS scheduling:
  • Processes are executed strictly in arrival order
  • Once a process starts running, it keeps the CPU until it finishes or is blocked
  • There is no pre-emption (the OS does not forcibly remove a running process from the CPU)

Advantages of FCFS
FCFS has several benefits:
  • Simplicity: Easy to understand and implement
  • Fairness in Order: Processes are treated equally based on arrival time
  • Low Overhead: Minimal scheduling decisions reduce system overhead

Disadvantages of FCFS
Despite its simplicity, FCFS has notable drawbacks:
  • Poor Responsiveness: Short, interactive processes may be forced to wait behind long-running processes
  • Convoy Effect: A long CPU-bound process can delay many shorter processes, reducing overall system performance
  • Inefficient CPU Utilization: The system may appear slow, especially in interactive environments

When FCFS Is Appropriate
FCFS is best suited to simple batch processing systems where:
  • Processes have similar execution times
  • Responsiveness is not critical
  • Implementation simplicity is a priority

First-Come, First-Served scheduling is straightforward and predictable, but it is generally unsuitable for modern interactive systems that require fast response times.

Which statement correctly describes First-Come, First-Served scheduling?

A. The process with the highest priority always runs first.
B. Processes run in arrival order and are not pre-empted.
C. Each process is given a fixed time slice.
D. Processes are placed into multiple queues.

SECTION 3 | ROUND ROBIN

Round Robin is a pre-emptive CPU scheduling algorithm designed to improve fairness and responsiveness in multitasking and time-sharing systems. Each process is given a small, fixed amount of CPU time, known as a time slice or quantum.

How Round Robin Scheduling Works
All ready processes are placed in a queue. The operating system selects the process at the front of the queue and allows it to run for one time slice:
  • If the process finishes before the time slice expires, it leaves the system.
  • If the process does not finish, it is pre-empted and moved to the back of the queue.
  • The next process in the queue is then given CPU time.

This cycle repeats continuously, giving each process regular access to the CPU.

Key Characteristics of Round Robin
  • Pre-emptive: The OS can interrupt a running process when its time slice ends.
  • Fair Allocation: Each process receives an equal share of CPU time.
  • Time-Sharing: Well suited to systems where many users or applications run concurrently.

Advantages of Round Robin
  • Good Responsiveness: Interactive applications remain responsive because no process can monopolize the CPU.
  • Fairness: All processes are treated equally regardless of execution time.
  • Predictable Behaviour: Each process is guaranteed CPU access within a known time frame.

Disadvantages of Round Robin
  • Context Switching Overhead: Frequent switching between processes can reduce efficiency.
Time Slice Selection:
  • If the time slice is too short, overhead increases.
  • If it is too long, the system behaves more like FCFS and becomes less responsive.

When Round Robin Is Appropriate
Round Robin is commonly used in:
  • Interactive systems
  • Multi-user operating systems
  • Time-sharing environments

Round Robin scheduling balances fairness and responsiveness by dividing CPU time into equal slices, making it well suited for modern interactive systems

Which statement correctly describes Round Robin scheduling?

A. Processes run until completion in arrival order.
B. The highest-priority process always runs first.
C. Each process gets a fixed time slice and is pre-empted if it does not finish.
D. Processes are assigned to permanent queues.

SECTION 4 | MULTI LEVEL QUEUE SCHEDULING

Multilevel Queue Scheduling is a CPU scheduling approach that organizes processes into multiple separate queues based on their characteristics. Each queue is assigned its own scheduling policy, allowing the operating system to manage different types of processes more effectively.

How Multilevel Queue Scheduling Works
Processes are permanently assigned to a specific queue when they enter the system. The queue a process belongs to is typically determined by factors such as:
  • Process type (system, interactive, batch)
  • Priority level
  • Resource requirements
Each queue may use a different scheduling algorithm. For example:
  • Foreground (interactive) processes may use Round Robin
  • Background (batch) processes may use FCFS
The operating system decides which queue gets access to the CPU, often based on queue priority.

CPU Allocation Between Queues
There are two common approaches:
  • Fixed Priority Scheduling:
    Higher-priority queues are always served before lower-priority queues.
  • Time Sharing Between Queues:
    Each queue is given a fixed portion of CPU time.
Advantages of Multilevel Queue Scheduling
  • Efficient Management: Different types of processes are handled according to their needs.
  • Improved Responsiveness: Interactive processes can be prioritized.
  • Clear Separation: System and user processes can be isolated logically.
Disadvantages of Multilevel Queue Scheduling
  • Inflexibility: Processes cannot move between queues.
  • Risk of Starvation: Lower-priority queues may receive little or no CPU time.

When Multilevel Queue Scheduling Is Appropriate
This approach is suitable for systems where processes can be clearly categorised and where fixed priorities are acceptable.

Multilevel queue scheduling improves performance by separating processes into queues with different scheduling strategies, but it can be unfair if lower-priority queues are neglected.

Which statement correctly describes multilevel queue scheduling?

A. Processes move between queues based on their CPU usage.
B. All processes share the CPU equally.
C. Processes are permanently assigned to queues with different scheduling policies.
D. Processes run strictly in order of arrival.

SECTION 5 | PRIORITY LEVEL SCHEDULING

Priority scheduling is a CPU scheduling approach in which each process is assigned a priority level, and the CPU is allocated to the process with the highest priority. This allows the operating system to ensure that important tasks receive CPU time before less critical ones.

How Priority Scheduling Works
Each process is given a numerical priority value when it enters the system. The scheduler then:
  • Selects the highest-priority process from the ready queue
  • Allocates CPU time to that process
  • Chooses the next highest-priority process when the CPU becomes available
Priority scheduling can be:
  • Non-pre-emptive: A running process keeps the CPU until it finishes or blocks
  • Pre-emptive: A running process can be interrupted if a higher-priority process arrives

​Advantages of Priority Scheduling
  • Supports Critical Tasks: Important system or real-time processes can be prioritized
  • Flexible: Can be combined with other scheduling algorithms
  • Efficient for Mixed Workloads: Useful when some tasks are more time-sensitive than others
Disadvantages of Priority Scheduling
  • Starvation: Low-priority processes may never get CPU time if high-priority processes keep arriving
  • Priority Inversion: A low-priority process may block a higher-priority one by holding a required resource
To reduce these problems, operating systems may use techniques such as aging, where a process’s priority increases the longer it waits.

When Priority Scheduling Is Appropriate
Priority scheduling is commonly used in:
  • Real-time systems
  • Systems with critical background services
  • Environments where tasks have clearly defined importance levels

Priority scheduling improves responsiveness for important processes but must be carefully managed to ensure fairness.

Which statement correctly describes priority scheduling?

A. Processes run strictly in arrival order.
B. All processes receive equal CPU time.
C. The process with the highest priority is selected to use the CPU.
D. Processes are fixed into different queues permanently.
CPU Scheduling | The operating system process of deciding which process uses the CPU and for how long.
Process | A program that is currently loaded into memory and being executed by the CPU.
Ready Queue | A list of processes that are ready to use the CPU but are waiting for their turn.
Context Switching | The process of saving the state of a running process and loading the state of another process so the CPU can switch between them.
System Performance | A measure of how efficiently a computer system operates, including responsiveness, throughput, and CPU utilization.
Responsiveness | How quickly a system responds to user input or requests.
Throughput | The number of processes completed by the system in a given period of time.
Fairness | Ensuring that all processes receive an appropriate share of CPU time without starvation.
First-Come, First-Served (FCFS) | A non-pre-emptive scheduling algorithm where processes are executed in the order they arrive.
Convoy Effect | A situation in FCFS scheduling where short processes are delayed by a long-running process.
Pre-emptive Scheduling | A scheduling approach where the operating system can interrupt a running process to give CPU time to another process.
Non-Pre-emptive Scheduling | A scheduling approach where a process keeps the CPU until it finishes or blocks.
Round Robin Scheduling | A pre-emptive scheduling algorithm where each process is given a fixed time slice in turn.
Time Slice (Quantum) | A fixed amount of CPU time allocated to a process before it may be pre-empted.
Multilevel Queue Scheduling | A scheduling method that divides processes into multiple fixed queues, each with its own scheduling policy.
Priority Scheduling | A scheduling approach where the CPU is allocated to the process with the highest priority.
Priority Level | A value assigned to a process that determines its importance relative to other processes.
Starvation | A situation where a process never receives CPU time because other processes are always scheduled first.
Aging | A technique used in priority scheduling where a process’s priority increases the longer it waits, reducing starvation.
Open-Ended Questions – Approaches to CPU Scheduling
  1. Explain why an operating system must allocate CPU time between multiple processes.
  2. Describe how CPU scheduling helps optimize overall system performance.
  3. Explain how First-Come, First-Served (FCFS) scheduling works and identify one advantage and one disadvantage.
  4. Describe the convoy effect and explain why it can reduce system performance.
  5. Explain how Round Robin scheduling allocates CPU time and why it is suitable for interactive systems.
  6. Discuss how the choice of time slice affects the performance of Round Robin scheduling.
  7. Describe how multilevel queue scheduling organizes processes and manages CPU allocation.
  8. Explain one advantage and one disadvantage of multilevel queue scheduling.
  9. Describe how priority scheduling works and explain why starvation can occur.
  10. Explain how aging can be used to reduce starvation in priority scheduling

Sample Answers

1) Explain why an operating system must allocate CPU time between multiple processes.

Because only one process can execute on the CPU at a time. The OS must decide which process runs next so that multiple programs can make progress and the system can support multitasking.

2) Describe how CPU scheduling helps optimize overall system performance.

Scheduling aims to keep the CPU busy (high utilization), complete more work over time (throughput), respond quickly to users (responsiveness), and share CPU time fairly so no process is neglected.

3) Explain how First-Come, First-Served (FCFS) scheduling works and identify one advantage and one disadvantage.

FCFS runs processes in the order they arrive in the ready queue and is non-pre-emptive. Advantage: simple and low overhead. Disadvantage: poor responsiveness because short jobs can be stuck behind long jobs.

4) Describe the convoy effect and explain why it can reduce system performance.

The convoy effect occurs when a long CPU-bound process runs first and causes many shorter processes to wait behind it. This increases waiting time and can make the system feel slow, reducing overall performance and responsiveness.

5) Explain how Round Robin scheduling allocates CPU time and why it is suitable for interactive systems.

Round Robin gives each process a fixed time slice. If it doesn’t finish, it is pre-empted and moved to the back of the queue. This prevents one process from monopolizing the CPU and improves responsiveness for interactive tasks.

6) Discuss how the choice of time slice affects the performance of Round Robin scheduling.

If the time slice is too small, context switching happens frequently and overhead increases. If it is too large, the system behaves more like FCFS and becomes less responsive. A balanced time slice reduces overhead while staying responsive.

7) Describe how multilevel queue scheduling organizes processes and manages CPU allocation.

Processes are placed into separate queues based on type (e.g., interactive vs batch) and usually stay in that queue. Each queue can use a different scheduling algorithm, and the OS allocates CPU time between queues using fixed priorities or time-sharing.

8) Explain one advantage and one disadvantage of multilevel queue scheduling.

Advantage: interactive processes can be prioritized to improve responsiveness. Disadvantage: lower-priority queues may suffer starvation if higher-priority queues dominate CPU time.

9) Describe how priority scheduling works and explain why starvation can occur.

Priority scheduling runs the highest-priority process first (pre-emptive or non-pre-emptive). Starvation can occur because low-priority processes may keep getting postponed if higher-priority processes continue to arrive.

10) Explain how aging can be used to reduce starvation in priority scheduling.

Aging gradually increases a process’s priority the longer it waits in the ready queue. Over time, this ensures even low-priority processes eventually become high enough priority to run.

COMING SOON
SUGGESTIONS
We would love to hear from you
SUBSCRIBE 
To enjoy more benefits
We hope you find this site useful. If you notice any errors or would like to contribute material then please contact us.