CS2106: Lecture 3 - Process Scheduling

- 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

- 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

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

Each process queue for OS.

One CPU: Time slice

Multi: Scheduler decides which Core for which processes

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

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

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

This job is very easy to schedule

- 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]

Have a deadline

Task are usually periodic

Task in RTP Is usually superior.

- 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

- 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

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

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

- 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)

- 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

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

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

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

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

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

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.