AOS 3

Policy

The ordering of which processes to run

Policy scheduling assumptions

1. All procceses have the same runtime

2. All processes arrive at the same time

3. The processes only use the cpu, not io, gpu, display to screen

4. We know the runtime ahead of time

Turnaround time

The time it takes for a process to arrive and execute

Throughput

The number of processes that can be executed

Fairness

How equally the cpu is shared between the processes

Responsiveness

The time between arrival and getting scheduled

FIFO scheduling

The first process to arrive is the first one to be executed

Shortest job first (SJF) policy

Whichever job has the shorted execution time, will get priority. Has good turnaround and responsiveness

Preemption

A feature of scheduling algorithms that allows the cpu to context switch out the current process and switch in another one for a short time.

Shortest Job Time Completion (Policy)

Uses preemption so any processes that show up that have a shorter ttc will be executed after context switching out the current process.

Completely fair scheduler

The linux task scheduler. Uses a heap to store processes, sorted by virtual runtime. Whichever has the least runtime will be run first.

Virtual Runtime

How much a process runs vs how much it is supposed to run. The calculation is complicated by accounting for the priority of the process, how much time it ran, how many different processes are competing for runtime. The VR is always being recomputed.

Linux Categories of Processes

Other, Batch, Idle

Batch Process

Computation bound process which needs to run without interruption as much as possible so that it can finish.

Idle process

The tag for processes that are running in the background and not doing too much.

Thread

Has its own instruction pointer, its own stack, and its own set of registers. This is different from a process.

What context switch is cheaper, thread or process?

The thread is cheaper since it is smaller.

Data race

When different processes are trying to do something in a certain order and they operate out of order.