ch5 - basic

Question 1

What CPU Scheduler do?

Answer 1

The CPU scheduler selects a process from the processes in the ready queue, and allocates a CPU core to it

the scheduler is defined by the ordering of that queue

Question 2

When CPU scheduling decisions may take place?

Answer 2

CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates

Question 3

When scheduling scheme is nonpreemptive?

Answer 3

When scheduling takes place only under circumstances 1 and 4, the scheduling scheme is nonpreemptive.

A process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates

Question 4

What is the meaning of nonpreemptive scheduling?

Answer 4

Under Nonpreemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases it either by terminating or by switching to the waiting state.

Question 4

What is a problem with preemptive scheduling?

Answer 4

Preemptive scheduling can result in race conditions when data are shared among several processes.

Question 5

can nonpreemtive scheduling result in race condition?

Answer 5

NO

That’s because the scheduler don’t interrupt the process, so it makes all the changes it should do to the shared data before switching to another process

Question 6

What is a dispatcher?

Answer 6

Dispatcher module gives control of the CPU to the process selected by the CPU scheduler; this involves:
1. Switching context
2. Switching to user mode
3. Jumping to the proper location in the user program to restart that program

Question 7

What is dispatch latency?

Answer 7

Dispatch latency – time it takes for the dispatcher to stop one process and start another running

Question 9

What are scheduling Criteria?

Answer 9

1. CPU utilization – keep the CPU as busy as possible
2. Throughput – # of processes that complete their execution per time unit
3. Turnaround time – amount of time to execute a particular process
4. Waiting time – amount of time a process has been waiting in the ready queue
5. Response time – amount of time it takes from when a request was submitted until the first response is produced.

Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time

Question 9

How First- Come, First-Served (FCFS) Scheduling works?

Answer 9

The processes are chosen according to their arrival time
a normal queue

Question 10

What is convoy effect?
When it happens?

Answer 10

Convoy effect - short process behind long process
might happen in FCFS scheduling algorithm

Question 11

How Shortest-Job-First (SJF) Scheduling works?

Answer 11

Associate with each process the length of its next CPU burst
Use these lengths to schedule the process with the shortest time

Question 12

Is SJF optimal in terms of waiting time?

Answer 12

SJF is optimal – gives minimum average waiting time for a given set of processes

Question 13

What is the preemptive version of SJF called?

Answer 13

Preemptive version called shortest-remaining-time-first

Question 14

How do we determine the length of the next CPU burst?

Answer 14

Could ask the user or estimate

Question 15

Use SJF to determine the order of these processes and the average waiting time

Process Burst Time
P1————6
P2————8
P3————7
P4————3

Answer 15

0-3sec: P4
3sec-9sec: P1
9sec-16sec: P3
16sec-24sec: P2

average waiting time = (3 + 16 + 9 + 0) / 4 = 7

Question 16

What is the best estimate for the next CPU burst length based on?

Answer 16

It should be similar to the previous one.

Question 17

Which process is chosen when using estimated CPU bursts for scheduling?

Answer 17

The process with the shortest predicted next CPU burst.

Question 18

What method is used to estimate the next CPU burst length?

Answer 18

Exponential averaging based on previous CPU burst lengths.

Question 19

What does tₙ represent?

Answer 19

The actual length of the nth CPU burst.

Question 20

What does τₙ₊₁ represent?

Answer 20

The predicted value for the next CPU burst.

Question 21

What is the range of α in exponential averaging?

Answer 21

0 ≤ α ≤ 1.

Question 22

What is the formula for predicting the next CPU burst length?

Answer 22

τₙ₊₁ = α * tₙ + (1 - α) * τₙ.

Question 23

What value is α commonly set to?

Answer 23

½ or 0.5

Question 24

What does alpha = 0 mean in Exponential Averaging? what about alpha = 1?

Answer 24

if alpha = 0 history does not count (only the very first prediction) if alpha = 1 Only the actual last CPU burst counts

Question 25

What is Shortest Remaining Time First Scheduling?

Answer 25

Preemptive version of SJN Whenever a new process arrives in the ready queue, the decision on which process to schedule next is redone using the SJN algorithm.

Question 26

Which scheduling algorithm is *more optimal* than SJN for minimum **average waiting time** when pre‑emption is allowed?

Answer 26

SRT (Shortest Remaining Time)

Question 27

Why does **SRT** achieve a lower average waiting time than SJN?

Answer 27

It always runs the process with the **least remaining burst time** and can pre‑empt when a shorter job arrives, minimizing the time other processes wait.

Question 28

Is **SJN** pre‑emptive?

Answer 28

No — SJN (Shortest Job Next) is **non‑preemptive**.

Question 29

What key metric does **SRT** use to choose the next process?

Answer 29

**Remaining burst time**.

Question 30

On what basis does **SJN** pick the next process?

Answer 30

The **total burst time**; it chooses the shortest job among those already waiting.

Question 31

In the example P1(0,8 ms) P2(1,4 ms) P3(2,2 ms), what is the **average waiting time under SRT**?

Answer 31

≈ 2.33 ms

Question 32

In the same example, what is the **average waiting time under SJN**?

Answer 32

≈ 5.33 ms

Question 33

When should you prefer **SRT**?

Answer 33

When processes arrive at different times, pre‑emption is allowed, and you care about minimizing average waiting time.

Question 34

When might **SJN** be preferred over SRT?

Answer 34

When pre‑emption is not allowed or you need a simpler implementation.

Question 35

Which algorithm offers better **real‑time responsiveness**?

Answer 35

SRT — it can switch immediately to a shorter incoming job.

Question 36

Which algorithm is **simpler to implement**?

Answer 36

SJN.

Question 37

How the RR algorithm works?

Answer 37

Each process gets a small unit of CPU time (time quantum q), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.

Question 38

provide an upper bound to the waiting time of a process if using RR, given that there are n processes in the ready queue

Answer 38

If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units.

Question 39

Like what RR performs when q is small / large?

Answer 39

q large -> FIFO (FCFS) q small -> RR

Question 40

When is q too small?

Answer 40

If it's not large with respect to the context switch ## Footnote q must be large with respect to context switch, otherwise overhead is too high.

Question 41

is SJF a type of Priority Scheduling?

Answer 41

Yes! and the priority is the predicted next CPU burst time

Question 42

What's the problem with Priority Scheduling?

Answer 42

Starvation – low priority processes may never execute

Question 43

A solution to starvation problem in Priority Scheduling?

Answer 43

Aging – as time progresses increase the priority of the process

Question 44

How are Priority Scheduling and RR merged?

Answer 44

use RR for processes with the same priority

Question 45

What is Multilevel Queue in CPU scheduling?

Answer 45

The ready queue consists of multiple queues Multilevel queue scheduler defined by the following parameters: Number of queues Scheduling algorithms for each queue Method used to determine which queue a process will enter when that process needs service Scheduling among the queues

Question 46

What is Priority Scheduling in terms of Multilevel Queue?

Answer 46

Have separate queues for each priority. Schedule the process in the highest-priority queue!

Question 47

# True or False? When threads supported, threads scheduled, not processes

Answer 47

True

Question 48

What is Symmetric multiprocessing?

Answer 48

Symmetric multiprocessing (SMP) is where each processor is self scheduling.

Question 49

What is load balancer and what it does?

Answer 49

Load balancing attempts to keep workload evenly distributed

Question 50

What Push migration does?

Answer 50

Push migration – periodic task checks load on each processor, and if found pushes task from overloaded CPU to other CPUs

Question 51

What Pull migration does?

Answer 51

Pull migration – idle processors pulls waiting task from busy processor

Question 52

What are soft and hard affinities?

Answer 52

**Soft affinity** – the operating system attempts to keep a thread running on the same processor, but no guarantees. **Hard affinity** – allows a process to specify a set of processors it may run on.

Question 53

What is Interrupt latency?

Answer 53

Interrupt latency – time from arrival of interrupt to start of routine that services interrupt

Question 54

What is Dispatch latency ?

Answer 54

Dispatch latency – time for schedule to take current process off CPU and switch to another

Question 55

What is the conflict phase of dispatch latency

Answer 55

Conflict phase of dispatch latency: Preemption of any process running in kernel mode Release by low-priority process of resources needed by high-priority processes | (this a part of the dispatching process)