Part 2 Chapter 3: Processes and Process Management

Preemptive Scheduling

The CPU can be taken away from a running process before it’s done.

The current executing process has no choice but to change from Running state to the Ready State and go back to the Ready Queue.

1. A more higher-priority process arrives

2. Time slice is up. The process that is executing has exceeded its limit

In what ways does Preemptive Scheduling occurs?

Non-preemptive Scheduling

The CPU cannot be taken away from the process. The process is allowed to complete its current CPU burst.

The currently executing process terminates

When does the only time a process can be assigned to another process in Non-preemptive Scheduling?

• CPU Utilization - keep the CPU busy as possible

• Throughput - maximizing the amount of work done by the CPU

• Turnaround Time - minimizing the amount of time it takes to execute a process

• Response Time - minimizing the time between the submission of a request and the start of the system’s first response (not the final output)

• Waiting Time - minimizing the total time a process had to spend inside the ready queue

What are the performance criteria a good scheduler should follow?

First-Come, First-Served Algorithm (FCFS)

The process that arrives in the ready queue first gets to use the CPU first.

It follows the First-In, First-Out rule (FIFO).

It is non-preemptive scheduling algorithm

Milliseconds

All values for arrival time and CPU burst time are measure in _____.

Its simplicity.

The CPU Scheduler doesn’t waste time picking the next process, it just picks the first in line.

What is the main advantage of the FCFS Scheduling algorithm?

It yields a high average waiting time since it favors CPU-bound processes.

CPU-bound processes (long tasks) take a long time to finish, so I/O bound processes (short tasks) get stuck waiting behind.

What is the main advantage of the FCFS Scheduling Algorithm?

Convoy Effect

A long process makes a bunch of smaller processes wait.

Shortest Process First Algorithm

The process with the shortest CPU burst time is the one that will be executed first.

I/O bound processes are given a higher priority than CPU-bound processes.

SPF favors I/O-bound processes because they tend to have short bursts. This keeps the queue small and waiting times lower than FCFS.

What is the advantage of the SPF?

1. It is impossible to determine the exact CPU burst of each processes.
   
   We guess based on past behavior (exponential averaging)
   
   

2. Long CPU-bound processes keep getting pushed back forever (Starvation)

What are the main advantage of the SPF?

Shortest Remaining Time First Algorithm

The preemptive version of SPF.

If a shorter process arrives, it can interrupt the running process

• It is the most optimal among all the CPU Scheduling Algorithms

• Processes with very large CPU burst time will be preempted once a short process enters the queue

What is the main advantage of the Shortest Remaining Time First Algorithm

• Aside from not knowing the exact CPU burst time of a process, there is now the additional burden of having to track the remaining burst time of a CPU process

• More context switches as compared to the two previous algorithms

What is the main disadvantage of Shortest Remaining Time First (SRTF)?

Round Robin Algorithm

Preemptive version of the FCFS algorithm.

Each process is given a time limit (time slice or time quantum) to execute at the CPU.

Once the time slice expires, the running process goes back to the ready queue.

It is the only CPU Scheduling Algorithm that guarantees that each process gets its fair share of the CPU.

Response time is its priority.

What is the main advantage of Round Robin?

If the length of the time quantum is wrong, the performance of the RR is affected.

If the time quantum is too small, there will be too much context switch.

If the time quantum is too large, then the performance becomes similar to that of the FCFS Algorithm.

What is the main disadvantage of Round Robin?

Priority Scheduling

May be non-preemptive or preemptive.

Every process is given a priority number.

The waiting time of high-priority process are minimized.

What’s the main advantage of Priority Scheduling?

There is a possibility that processes with very low priorities may be denied the use of CPU especially if high-priority processes kept on entering the Ready Queue. (Starvation)

What is the main disadvantage of Priority Scheduling?

Aging can be utilized by the operating system where the priority of a process gradually increases the longer it stay in the ready queue.

How to solve the problem of Starvation?

Multilevel Feedback Queue

It determines the behavior pattern of a process and thus schedule its execution appropriately.

It utilizes several ready queue, wherein each queue will have a different priority.

1. All processes enter the highest priority queue

2. If a process completes its execution within the given time slice, it leaves the network.

3. If not, it will move to the next lower-priority queue. But the lower-priority queue will only start if the highest-priority queue is empty.

How does Multilevel Feedback Queue Algorithm works?

Concurrency

The execution of two or more independent processes at the same time period.

1. A process creates a child process using the fork system call.

2. After calling fork () , the child gets its own memory space, but it starts as an exact copy of the parent.

3. At this point, both the parent and child are running the same program, independently!

How UNIX creates a new process?

1. Unique ID

2. State (New, Ready, Running, Blocked,Terminated)

3. CPU Registers

4. Scheduling Priority

5. Control Blocks (Thread Control Block)

6. Competing for CPU Time

7. Independent Execution

What’s the similarities between a Thread and a Process?

1. Memory Space - share’s memory with the process

2. Information Stored - Threads don’t need as much info because they inherit it from their process

3. Shared Resources - Threads inside a process share these resources.

4. Control - Threads inside the same process can control each other freely

5. Changes & Effects - If the main thread changes or is terminated, all other threads in the process are affected.

What’s the differences between a Thread and a Process?

• Creating a thread is easier because it doesn’t need a separate memory space—it just shares the memory of its process.

• Context switching (switching between running tasks) is quicker for threads because they store less information.

• Since threads share the same memory, they can easily access each other's data.

• Threads can be assigned to specific tasks inside a program (e.g., one thread handles input, another handles calculations, etc.).
  🔹 This makes programs more efficient since they can work on multiple things at the same time.

What are the advantages of using Threads over Process?

• Since all threads share the same memory, two (or more) threads might try to modify the same variable at the same time.

• Since threads of the same process are equals, they can affect each other directly.

What are the disadvantages of Threads over Processes?