CS21004 - Operating Systems

Name the five-state process model

New, Ready, Running, Blocked, Exit

List the primary process states managed by the Kernel. 

Running, Ready, Blocked, Ready Suspend, Blocked Suspend, Terminated 

In a single core processor how many processes can run at once?

One

What happens in the suspend state?

A process is temporarily removed from the main memory and stored in secondary storage, allowing the system to allocate memory for other processes. It can be resumed later.

When does a process need to go into the suspend state?

When there is not enough RAM available

Where is virtual memory useful?

When swapping processes

What is needed to get out of blocked suspend?

RAM and to become unblocked

What is needed to get out of ready suspend?

RAM (only)

What should processes not share?

Resources

What is recommended for threads but not processes?

Switching

Why is process switching not recommended?

It is relatively slow as it is a kernel-mode operation

How are CPU resources allocated?

With priority scheduling

Name 8 process scheduling algorithms

First-Come First-Served, Shortest Job First/Next, Round Robin, Priority Scheduling, Multilevel Queue Scheduling, Multilevel Feedback Queue, Lottery Scheduling, Earliest Deadline First

Describe First-Come First-Served (FCFS)

Processes are executed in the order they arrive

Advantage of First-Come First-Served (FCFS)

Simple to implement

Disadvantage of First-Come First-Served (FCFS)

Can lead to long waiting times if a long process is scheduled first (the "convoy effect")

Describe Shortest Job First/Next (SJF/SJN)

The OS selects the process with the shortest estimated execution time

Advantage of Shortest Job First/Next (SJF/SJN)

Minimises average waiting time

Disadvantage of Shortest Job First/Next (SJF/SJN)

Requires knowing/estimating process lengths and can lead to starvation of longer processes

Describe Round Robin (RR)

Each process is assigned a fixed time slice (quantum). After its time expires, the process is preempted, and the next one in the queue is run

Advantage of Round Robin

Ensures all processes get CPU time, improving fairness and responsiveness

Disadvantage of Round Robin

Inefficiency due to frequent context switching if the time quantum is too small

Describe Priority Scheduling

Each process is assigned a priority, and the OS runs the highest-priority next

Advantage of Priority Scheduling

Allows important tasks to be completed first

Disadvantage of Priority Scheduling

Lower-priority processes may experience starvation. Solutions like aging (increasing a process’ priority over time) help prevent this

Describe Multilevel Queue Scheduling

Processes are divided into different queues based on characteristics (e.g. foreground, background). Each queue may have a different scheduling algorithm

Advantage of Multilevel Queue Scheduling

Customisable for different types of processes

Disadvantages of Multilevel Queue Scheduling

Complex to implement and balance

Describe Multilevel Feedback Queue

Similar to multilevel queue scheduling but processes can move between queues based on their behaviour and time spent waiting

Advantage of Multilevel Feedback Queue

Dynamically adjusts to the needs of processes, balancing between CPU-bound and I/O-bound tasks

Disadvantage of Multilevel Feedback Queue

Complex to configure and manage

Describe Shortest Remaining Time (SRT)

A preemptive version of SJF. The OS runs the process with the shortest remaining time to completion, preempting if a shorter job arrives

Advantage of Shortest Remaining Time (SRT)

Minimises the average time to complete processes

Disadvantages of Shortest Remaining Time (SRT)

Requires knowing/estimating the remaining execution time (can result in frequent context switching)

Describe Lottery Scheduling

Each process is given a certain number of tickets and the OS randomly selects a ticket to decide which process to run

Advantage of Lottery Scheduling

Provides probabilistic fairness and allows for flexible allocation of resources

Disadvantage of Lottery Scheduling

Randomness may cause some unpredictability in process scheduling

Describe Earliest Deadline First (EDF)

Processes are scheduled based on their deadlines, with the earliest deadline getting the highest priority

Advantage of Earliest Deadline First (EDF)

Ideal for real-time systems where meeting deadlines is critical

Disadvantage of Earliest Deadline First

Can be difficult to predict or manage system load when many processes have close deadlines

What does the "New" process state mean?

The process is not yet added to the system

What does the "Ready" process state mean?

The process is available to be executed by the processor

What does the "Blocked" process state mean?

The process is fully in main memory but waiting for something (e.g. I/O)

What does the "Suspended" process state mean?

The process is partially in secondary memory

What does the "Blocked Suspended" state mean?

The process is suspended and waiting for something

What does the "Ready Suspended" state mean?

The process is suspended but otherwise ready to execute

What should scheduling balance between?

User-oriented criteria and system-oriented criteria

What are examples of user-oriented scheduling criteria?

Low response times and meeting event deadlines

What should a scheduling mechanism be in terms of cost?

It should be “cheap” (i.e., efficient) to implement

Why should a scheduling mechanism favour short jobs?

To improve response time

Why should a scheduling mechanism favour I/O-bound jobs?

To achieve good I/O device utilisation and better interactive performance

What should a scheduling mechanism determine about a job?

The nature of the job, and it should schedule it accordingly

What kinds of tasks are typically high priority?

System-critical tasks and real-time events

Give examples of high-priority processes.

Interrupt servicing, I/O operations, security monitoring, audio/video playback, and user interface tasks

What kinds of tasks are medium priority?

Regular user applications

Give examples of medium-priority processes.

Word processors, web browsers, and background data synchronisation

Give examples of low-priority processes.

System maintenance (e.g., disk defragmentation, file indexing) and large data backups

What is pre-emption in process scheduling?

When a high-priority process arrives while a lower-priority one is running, the lower-priority process is paused so the higher-priority process can execute

How does a multilevel queue scheduler decide which process to run?

It checks the highest-priority queue first

What are the base priority values in Windows?

Threads have base priority values from 1 to 31 - values 16-31 are reserved for real-time threads.

Who can change process priorities in Windows?

The user (with sufficient permissions) or the operating system

What are the scheduling priority ranges in Linux?

Real-time priorities: 0-99, static priorities 100-139

What is the range of niceness values in Linux?

-20 (highest priority) to +19 (lowest priority)

What do niceness values represent?

User-configurable hints that affect how much CPU time a process gets.

What does CFS stand for in Linux scheduling?

Completely Fair Scheduler

What is priority inversion?

A situation where a high-priority task is indirectly blocked by a low-priority task holding a resource, while a medium-priority task runs in between

Why does priority inversion happen?

A low-priority task holds a resource needed by a high-priority task, and a medium-priority task preempts the low-priority one

Why is it called "priority inversion"?

Because the priority order is effectively reversed (lower-priority tasks run before higher-priority ones)

What is priority inheritance?

The low-priority task temporarily inherits the high-priority task’s priority until it releases the shared resource

What are other solutions to priority inversion?

Priority ceiling protocols and reducing the length of critical sections

What is the arrival time?

The time in which a process arrives in the system

What is the burst/execution time?

The amount of CPU time a process needs to finish its current CPU work unit or job

What is the completion time?

Clock time when a job finishes

What is the turnaround time (formula)?

Completion time - Arrival time

What is the waiting time (formula)?

Turnaround time - Burst time

What is the response time?

The time from arrival until the first job is scheduled on the CPU (first run)

What is throughput?

The number of jobs completed per unit time

What is the advantage of short turnaround time?

Batch completion

What is the advantage of short response time?

Interactivity

What is the advantage of high throughput?

System capacity

What is preemption?

The OS interrupting (pausing) a running task and switching the CPU to another task with the intention to resume the first later

What are the benefits of preemption?

It enables time-sharing and priority-driven scheduling

Name 3 methods to mitigate starvation

Aging, hybrid policies, limit preemption depth

What is aging?

Gradually increasing priority (of effective weight) of waiting jobs

What are hybrid policies?

Giving long jobs guaranteed CPU slices before preemption

What is an example of limit preemption depth?

Only preempting if the remaining time difference is large

What does Windows do when a thread completes I/O and becomes runnable?

Windows temporarily boosts the thread’s dynamic priority so it can run immediately, helping it finish quickly and improving system responsiveness

What does Jain’s fairness index measure?

The equality of resource allocation among n processes with allocations x1, . . . , xn.

What are the worst and best values for Jain’s fairness index?

1/n (worst), 1 (perfect fairness)

What is the Dijkstra's Banker's Algorithm?

A deadlock avoidance algorithm used in operating systems to manage resource allocation safely

What is a safe state?

When a system can allocate resources to each process in such a way that all processes can complete without leading to deadlock

Why is system in a safe space important?

It guarantees that there exists a sequence of process execution that allows all processes to finish

What are inconsistencies known as?

Race condition

How to prevent race conditions?

Synchronisation mechanisms like locks, semaphores, and monitors are used

What does mutual exclusion do?

It prevents multiple processes or threads from accessing a shared resource simultaneously

What does a semaphore do?

Controls access to a shared resource by multiple processes or threads

Name the 2 types of semaphores

Binary and counting

How do you calculate the need matrix?

Max - Allocation

How can we tell if deadlock is possible using D Bankers algorithm?

If the need matrix is greater than the available matrix

What are the advantages of the Banker's Algorithm (5)?

Prevents deadlock by keeping the system in a safe state, allows efficient and fair resource allocation, prevents starvation, is flexible for different resource types and systems, and is conceptually simple to understand and implement