Operating systems CPU scheduling algorithms notes

What is CPU scheduling?

CPU scheduling is the process of determining which process in the ready state should be allocated CPU time. It aims to maximize CPU utilization and minimize response time.

True or False: CPU scheduling is only for multitasking operating systems.

False. While it's crucial for multitasking, even single-task systems use scheduling to manage processes effectively.

Define 'context switch'.

A context switch is the process of storing the state of a currently running process and loading the state of another process. It allows multiple processes to share the CPU.

What is a 'ready queue'?

A ready queue is a data structure that holds all processes that are ready to execute but are waiting for CPU allocation. It allows the scheduler to manage processes efficiently.

Fill in the blank: The goal of CPU scheduling is to maximize ___ and minimize ___.

Throughput; turnaround time

List two factors influencing CPU scheduling.

- Process priority - Process burst time

What are 'burst time' and 'waiting time'?

Burst time is the total time a process needs on the CPU. Waiting time is the total time a process spends waiting in the ready queue before being executed.

Cause → Effect: High priority assigned to a process.

Effect: The process receives more CPU time compared to lower-priority processes.

Comparison: Preemptive vs Non-preemptive scheduling.

Preemptive allows interruption of running processes; Non-preemptive does not. Preemptive enhances responsiveness, while Non-preemptive avoids context switching overhead.

What is 'turnaround time'?

Turnaround time is the total time taken from submission to completion of a process. It includes waiting and execution times.

Define 'throughput'.

Throughput is the number of processes completed in a given time frame, often expressed as processes per second.

What is 'starvation' in scheduling?

Starvation occurs when a process waits indefinitely for CPU time, often due to lower priority compared to other processes.

True or False: All scheduling algorithms provide the same performance.

False. Different algorithms can lead to varying performance metrics, such as response time and CPU utilization.

What is a scheduling algorithm?

A scheduling algorithm determines the order in which processes access the CPU. Common types include First-Come, First-Served (FCFS) and Round Robin (RR).

Example: Calculate turnaround time.

Process A: Arrival Time = 0, Burst Time = 5, Completion Time = 10. Turnaround Time = Completion Time - Arrival Time = 10 - 0 = 10.

What does 'response time' measure?

Response time measures the time from process submission to the first response, crucial for interactive systems.

What is preemptive scheduling?

Preemptive scheduling allows the CPU to interrupt a currently running process to give CPU time to another process.

Example of a preemptive scheduling algorithm?

Round Robin is a common preemptive scheduling algorithm that allocates a fixed time slice to each process.

True or False: Preemptive scheduling can lead to resource starvation.

True. If a process is frequently preempted, it may suffer from starvation, being unable to complete its execution.

How does Round Robin handle processes?

Processes are assigned a time quantum. After that time elapses, the CPU is preempted and given to the next process in the queue.

Compare preemptive and non-preemptive scheduling.

Preemptive: Can interrupt processes. Non-preemptive: Processes run to completion without interruption.

What is Multilevel Queue Scheduling?

This algorithm divides the ready queue into several separate queues based on priority, each with its own scheduling algorithm.

Fill in the blank: Preemptive scheduling is crucial for ____ systems.

real-time systems, where timely responses are critical.

What happens in Shortest Remaining Time First?

The CPU is allocated to the process with the least remaining time, allowing preemption for shorter tasks.

Describe the effect of time quantum size.

A small time quantum increases context switching and overhead. A large time quantum can lead to longer wait times.

True or False: Preemptive scheduling improves responsiveness.

True. Processes can be allocated CPU time quickly, enhancing overall system responsiveness.

Example of Starvation in preemptive scheduling?

A low-priority process may be continuously preempted by higher-priority processes, delaying its execution indefinitely.

What is the role of priority in preemptive scheduling?

Processes with higher priority can preempt lower-priority processes, ensuring that critical tasks receive timely CPU access.

How does a process enter the ready queue?

When a process is created or becomes runnable, it is added to the ready queue, awaiting CPU allocation.

What is Context Switching?

The process of saving the state of a currently running process and loading the state of the next process to run.

True or False: Preemptive scheduling always leads to better performance.

False. While it improves responsiveness, it can increase context switching overhead, potentially degrading performance.

What is the primary benefit of preemptive scheduling?

It allows high-priority processes to execute promptly, improving system responsiveness and efficiency.

What is Non-Preemptive Scheduling?

Non-preemptive scheduling allows a running process to complete its execution without interruption. Once CPU allocation is given, it won't be taken away until the process finishes.

Advantages of Non-Preemptive Scheduling?

- Simplicity of implementation - Reduced context switching - Predictable process behavior

True or False: Non-preemptive scheduling is more responsive than preemptive scheduling.

False. Non-preemptive scheduling can lead to longer wait times for other processes, making it less responsive.

Example of Non-Preemptive Scheduling Algorithm?

First-Come, First-Served (FCFS) is a classic example, where processes are executed in the order they arrive.

What is First-Come, First-Served (FCFS)?

A non-preemptive scheduling algorithm where the first process that arrives is the first to be executed until completion.

How does FCFS handle process completion?

Processes are completed in the order of their arrival. For example, if Process A arrives before Process B, A will finish before B.

What is Shortest Job Next (SJN)?

SJN, or Shortest Job First (SJF), is a non-preemptive algorithm that selects the process with the smallest execution time next.

Comparison: FCFS vs SJN?

FCFS is simpler but can lead to longer average wait times. SJN can minimize waiting time but requires knowledge of process lengths.

What happens in Non-Preemptive Round Robin?

Non-preemptive Round Robin does not exist. Round Robin is inherently preemptive since it allocates time slices.

True or False: Non-preemptive scheduling is suitable for batch processing.

True. Non-preemptive scheduling works well in environments where tasks are predictable, such as batch processing.

What is Priority Scheduling?

In Priority Scheduling, processes are assigned priorities, and the one with the highest priority is executed first. Non-preemptive levels ensure a running process isn't interrupted.

Cause → Effect: Low priority in Non-Preemptive Scheduling?

Processes with low priority may experience starvation as high-priority processes continue to execute.

Fill in the blank: Non-preemptive scheduling is less effective in environments with __________ processes.

interactive processes.

What is the ideal scenario for Non-Preemptive Scheduling?

Best for systems with long, non-interactive jobs where predictability and minimal context switching are desired.

Example of process wait in Non-Preemptive Scheduling?

If Process A takes 10 seconds and Process B takes 3 seconds, B must wait 10 seconds before execution starts.

True or False: Non-preemptive algorithms always maximize CPU utilization.

False. They can lead to lower CPU utilization during long wait times for lower priority processes.

Multilevel Queue Scheduling

This algorithm divides the ready queue into multiple queues, each with different priority levels. - Examples: foreground and background processes.

True or False: Round Robin is suitable for real-time systems.

False. Round Robin does not guarantee timely execution, which is crucial for real-time systems.

What is the purpose of Feedback Scheduling?

Feedback Scheduling dynamically adjusts the priority of processes based on their behavior and execution time, helping to optimize CPU usage.

First-Come, First-Served vs. Shortest Job First

First-Come, First-Served (FCFS) serves processes in the order they arrive, while Shortest Job First (SJF) prioritizes the shortest tasks. - SJF minimizes waiting time.

What is Lottery Scheduling?

Lottery Scheduling assigns tickets to processes; the CPU is allocated to a randomly selected ticket holder, promoting fairness in resource allocation.

True or False: Priority Scheduling can lead to starvation.

True. Lower-priority processes may wait indefinitely if higher-priority processes continually arrive.

What are Real-Time Scheduling Algorithms?

These algorithms ensure processes meet strict timing constraints. - Examples: Rate Monotonic Scheduling, Earliest Deadline First.

Compare Static vs. Dynamic Priority Scheduling.

Static priority does not change, while dynamic priority can adjust based on process behavior or system load, improving responsiveness.

Fill in the blank: In _____ Scheduling, I/O-bound processes get higher priority.

Multilevel Feedback Queue. This helps improve overall system responsiveness.

What is the main goal of Fair Share Scheduling?

To allocate CPU time fairly among users or groups, ensuring that all have equitable access to resources.

Cause → Effect: High-priority aging.

Cause: Continuous arrival of high-priority processes. Effect: Low-priority processes may starve and not execute.

What is the key concept behind Weighted Fair Queuing?

Weighted Fair Queuing allows processes to share bandwidth fairly based on assigned weights, ensuring efficient network resource allocation.

True or False: Earliest Deadline First is optimal for periodic tasks.

True. It can guarantee the timely execution of periodic tasks if the total utilization is below a certain threshold.

What is the advantage of using Hybrid Scheduling?

Hybrid Scheduling combines multiple algorithms to capitalize on their strengths, improving overall system performance and responsiveness.

Example: Calculate wait time in SJF scheduling.

Processes: P1 (2ms), P2 (4ms), P3 (1ms). Wait times: P1 = 0, P2 = 2, P3 = 6. Average wait = 2ms.

What is the purpose of Completely Fair Scheduler?

The Completely Fair Scheduler (CFS) aims to allocate CPU time fairly among all processes by using a time-sharing mechanism. - Operates based on virtual runtime. - Balances responsiveness and throughput. - Suitable for desktop and server environments.