CS2106: Lecture 3 - Process Scheduling

Questions from Archi

- In a multi core archi, does each core have its own scheduler

A: There is one for each core. Lab2 will build it.

- If we use a code that does not import any lib, is path D still use

e.g int main() {return 0;}

(Ref to diagram)

A: Not all syscall have to been in the code so setting up will still use path D.

Some implied lib calls happen in intitalise.

- Conceptually there would be multiple block queues for the different event right

A: For diff event types some structures might be more suitable than others

We can have multiple queues for different things

Concurrent execution

- Virtual or physical parellism

Its an illusion of paralleism even thou we have only one single core

If there is one core, there is only one truly running process but they can take turns. While one is waiting, the other is running.

This is the concurrency.

Physical:
The concurrency is happening in hardware. (Parallelism in hardware)

- Multi core 

- Multi context in hardware

Scheduling policies are not really related to parallelism

Insert slide 5

This is an example of concurrent execution on a single core.

Time Slicing

There is performance impact but there is no correctness problem

-> This is make sure by the OS

-> The OS have a short period of time to save the context and to restore (take a ss) before the scheduler pick another process

- The os then pull out the context of the other process

- This is called context switch: Switching the context of one process and saving the other

Context Switch

1. Process A decided to switch

2. The OS save the state into PCB

3. Meanwhile, the scheduler is invoke to select another process

4. The process p1 continues and when it is done (interrupt)

5. It saves its context and reload the previous Process A

Do we need to keep the PCB structure updated at all time

-> no

It is a hassle to update everything, register is involved

We only save stuff into memory when something (interrupt) happens

Multitasking OS

Each process queue for OS.

One CPU: Time slice

Multi: Scheduler decides which Core for which processes

Scheduling

It is a part of the OS that makes the scheduling decisions

The scheduler will select and pick a few processes to run on the CPU.

How to select?

Multiple ways to allocate:

Influence by process environment -> Scheduling algo

Process Behavior

CPU: 

- Computation

- Number crunching

IO:
- Request and receiving service from io devices

- IO bound process spend majority of its time here.

IO usually waits slower than processors.

The prog that usually change between the two modes, the scheduler must know what kind of process it is (IO/CPU boound) to make different policies for each of the processes

Processing environment

Batch processing

Just submit the job to. No interaction required and no need to be responsive

This job is very easy to schedule

Interactive

- With active user interacting with system

- Must be responsive, consistent in response time

- e.g Microsoft word (when we type something,we do not want to wait for a few seconds before seeing the word)
It does not do anything until you press something. (IO intensive)
While it is waiting, it is block. [There are some systems that are interactive but not IO intensive]

Real time processing

Have a deadline

Task are usually periodic

Task in RTP Is usually superior.

Criterias for algo

- Fair

Must have a shared time for CPU

No starvation

- Balance

All parts of the computing system should be utilized

We do not want to have a bottleneck in the system

When to perform scheduling

- Non preemptive

Scheduler cannot decide when to kick you out of the CPU until you give up volunterrily

(Usual for batch systems)

- Preemptive

Usually periodic

When do we call the scheduler?
When a process is finish/block, another process is to be picked.

1. Scheduler is trigger (OS take over)

2. If context switch:

Context of running is save and place into queue (ready or block)

3. Scheudler use its algo to pick process p

4. Set up context for p

5. Run process p

Batch Processing

Criteria:

- Throughput: Number of tasks finish per unit line

- Turnaround time: Total wall clock time taken, related to waiting time for CPU

- CPU utilization: Percentage of time when CPU is working on task

FCFS

- The first process in the queue is served first

- No starvation (every process is guaranteed time and the queue is always decreasing)

-  NO priority

Problems:

- If there is a long task infront, the waiting task behind will have to wait time(A) to finish.

It will be better if we reorder the time to shortest to longest. (But this might cause a problem)

SJF

- Select the task with the shortest total CPU time

Problem:

- We do not know how long it takes to finish

- We can use Exponential Avg 

Predn+1 = aActualn + (1- a) predn

Actualn = the most recent CPU time consumed

Predictedn = the past history of CPU time consumed

a = Weight placed on recent event or past history

Predictedn+1 = latest prediction

This equation is use to predict the CPU time taken for the incoming task

The scheduler will use the results of this equation to scheduler the job accordingly to SJF.

Last week from archi

1. Copy one write approach to forks which only copies memory when necessary, why is there a need for clone which only copy specific.

Fork is a lib call while clone is the underlying sys call.

Copy on write is a perf optimization for data that is shared.

Do we want to share everything with the child?

Clone have a better flexibility to allow us to select which part of the memory to share with the child.

IT does not matter if its copy on write

2. How does child process know if its should read from own pcb or parents using the copy on write optimization?

PCB is part of the OS context of a process. The process do not know about it but the OS does. This is abstraction.

3. In what case we use wait and sleep

wait -> Process to  finish 

Sleep -> wait for a set amt of time

Q4. Do we create a new process ID for the child process when we fork or do we defer that to when there is a write (according to the copy then write)

Fork returns different values to child and parent

To parent = id of child

To child = 0

We always create the process ID first

Q5. Is the PCB stored in memory? And does it contain or does it point to the heap stack data and text.

The PCB are stored in OS memory and its only accessible to kernel.

It is stored in kernel memory which is smaller than memory.

So it cannot store all the actual data but contains the information required to access the memory.

(Does not have to be pointers)

Q6 When do we get segmentation fault?

When the program generation an address that does not belong to the program.

Q7 When the process/program encounters a page fault (accessing mem that has not been allocated), Does the process become blocked instead of terminated since it can restart from that particular instruction?

This is a different type of fault. It is not segmentation (Memory managment topic in week 9)

Q8 Some C string literals are read onlu

char * S = "hello"

C treats it as immutable

SRT

Shortest time remaining : Select job with the shortest remaining time or the expectation

How is this different with SJF?
- The order of process is different

- When a new process enter, it will be different

- This is preemptive variant of SJF

Provides good service for short job even when it arrives late.

Interactive environment

Response time: Time between request and response by system

Predictability: Variation in response time, less variation -> More predictable

Preemptive scheduling algo are use to ensure good response time

-> Scheduler needs to run preiodically

keep track of time and to ensure each process have its own set of time to run

How do we make sure the scheduler takes over the CPU periodically?

-> timer interrupt = base on hardware clock

Terminology: Timer and time quantum

Interval of timer interrupt

Os scheduler is triggered every timer interrupt

Typical values (1ms to 10ms)

Time quantum

Execution duration given to a process

Could be constant or variable among the process

Must be multiples of interval of timer interrupt

Large range of values (5ms to 100ns)

Scheduling Algo:

1. Round Robin

Pick the first task from queue and run till

- a fixed time slice

- Task gives up

- Task blocks

Notes:

It is preemptive of FCFS

Guarantee the time before the task to get CPU (n-1)q

Choice of time quantum duration isimport:

big: Better CPU util but more waiting time 

samll: Bigger CPU util but shorter waiting time  [More context switch]

2. Priority based

Some process are  more important than others

Assign a priority value to asll task

There is preemptive and non premptive

Problem:

Low priority may starve.

High priority process keep hogging the CPU

Worse in pre-emptive:

- Preemptive ensure that each job get fix amount of time quantum so if a low pirority job waited so long just for a short amount of time, the prob will become worse

Sol:

Decrease priority each time it gets a chance to run

However, it is difficult to control the exact amount of CPU time given to a process using priority

Priority inversion

If a process use a resource and was lock due to it not finishing it and another high priority task come in needing the same resource.

The next process (not the high priority one) gets to execute because of the first process not finishing it yet/

3. Multi level feedback queue

Determine what time of process it is and classify it.

Adaptive.: Learn the process behavior automatically

Seeks to minimize:

- RT for interactive and IO bound process

- Turnaround time

For different priority, there are different algo running.

If a job utilize its time slice, the priority is reduce

There are different queue for differenet priority processes.

4. Lottery scheduling

Give out lottery tickets to processes for various system resource.

When scheduling decision is needed:

Lottery ticket is chosen randomly among eligible tickets

Winner is granted resource

For each TQ, each TQ have a lottery tickets. We are bias towards some proceess due to the priority. (Give more tickets to that process)

Responsive:
A new created process can participate in the next lottery/

Provides a decent level of control:
A process can be give Y lottery tickets, it can distribute to its child process.