Processes and Scheduler
Introduction
Section titled “Introduction”Terminology
Section titled “Terminology”Process term is informally used to indicate an executing program.
A program is a passive entity which implements an algorithm (in a given programming language). It describes the steps to take to archive the wanted result.
A process is an active entity which represent the execution of the given steps.
Operative System
Section titled “Operative System”Before talking about how the process abstraction works and how the scheduler helps the OS to manage their resources, let’s talk about the different types of operative systems.
The operative system is usually represented by different levels.
The operative system can be made up with different structures.
Monolithic Structure
Section titled “Monolithic Structure”The operative system is made up by a single module containing all the procedures.
The best advantage is efficiency, because of a low cost in terms of interaction between the various operative system components.
The worst disadvantages are the difficulty of maintenance, extensibility, portability and reliability.
Levels Structure
Section titled “Levels Structure”Each level provide functionality to upper level and uses the functionality provided by the lower level.
| Level | Functionality |
|---|---|
| 5 | Operator |
| 4 | User programs |
| 3 | I/O Management |
| 2 | Process to console communication |
| 1 | Memory management |
| 0 | Process allocation and multiprogramming |
An example of OS structured on levels is Dijkstra’s THE operative system.
Micro Kernel Structure
Section titled “Micro Kernel Structure”Kernel only contains main functionality. Everything else is moved to user mode.
Kernel provides process abstraction and manage both synchronous and asynchronous interrupts.
Concurrent Systems
Section titled “Concurrent Systems”All the modern operative systems are able to perform many tasks at the same time. It means that all the given tasks are assigned and executed by different processes in the same instant of time. To each process, a fully dedicated tiny virtual CPU is assigned. A concurrent system is then achieved.
Multitasking
Section titled “Multitasking”All the modern multitasking operative systems support concurrency.
Process Management
Section titled “Process Management”By introducing the concept of process, the OS complexity increase. It must provide the ways for a process to (be):
- Created (UNIX’s
fork()syscall) - Terminated (UNIX’s
kill()syscall) - Suspended and restored (while accessing I/O)
- Synchronized (UNIX’s signals)
- Communicate (Inter Process Communication methods)
- Avoid errors
Process Stages
Section titled “Process Stages”
A process is active when it’s executing on the CPU. It moves (suspends) to blocked status when it has to wait for a certain event (such as an I/O operation, a message to receive, …).
In the case of a mono-processor CPU, a system can have many active processes but only one executing process in a given instant of time.
Let’s add all the remaining stages is with a more comprehensive schema:
- IDLE: Starting state
- READY: Ready to be executed
- RUNNING: Executing
- WAITING: Wait for an event to continue
- SWAPPED: Process’ image copied on disk
- TERMINATED: Ended
- ZOMBIE: Ended but partially present in memory
Please Note: ready and waiting processes are managed into queue structures.
Process Control Block
Section titled “Process Control Block”Process descriptor, better known as Process Control Block, is a data structure holding all the information that distinguish the process.
The most important are:
- PID: Process IDentifier
- Status: Idle, Ready, Running, …
- Program Counter
- Table of Opened Files
- Scheduling: priority, pointers to processes queues, …
- Memory Management: page tables, limit registers, …
- I/O Devices: assigned I/O devices
Synchronization
Section titled “Synchronization”A concurrent system has essentially two ways for the processes to interact with each other:
- Competition: using common resources that can’t be used at the same time (scanners, printers, …)
- Cooperation: executing a common task by exchanging messages on common resources
If the interaction between processes goes wrong, the OS faces interferences. Solutions of those issues depends on the model the processes rely on.
Local environment model
Section titled “Local environment model”Different processes can communicate only by exchanging messages using interprocess communication methods (IPC) like pipes.
No memory is shared.
An example of local environment model is UNIX.
Global environment model
Section titled “Global environment model”Different processes (called threads), can communicate by using a shared memory area. An example of global environment model is Java’s multithreading.
Synchronization primitives to avoid interferences are semaphores and monitor.
Scheduler
Section titled “Scheduler”The OS component that choose which process to load into memory (and assign CPU) is called scheduler.
Scheduling Types
Section titled “Scheduling Types”Non-preemptive
Section titled “Non-preemptive”Also known as cooperative scheduling. A process in RUNNING state continues to use CPU until it autonomously decide to free the resource.
Preemptive
Section titled “Preemptive”A process in RUNNING state can lose CPU access even if it could have continued to run. All the modern systems uses preemptive scheduling to allow a better resources’ management.
Context Switching
Section titled “Context Switching”A mechanism that literally allow the switch of context from a process P0 (that have to free up CPU) and a process P1 that should start using the CPU.
It saves P0 status into its descriptor and load P1 form the process’ descriptor.
Scheduling Levels
Section titled “Scheduling Levels”Long term
Section titled “Long term”Decide which processes to load into memory. This level of scheduler is absent in time-sharing systems.
Medium term
Section titled “Medium term”Can execute swapping to change the number of processes loaded into memory.
Short term
Section titled “Short term”Decide to which process, from READY queue, assign CPU and for how much time the process can hold CPU (scheduling algorithms). It also triggers the context switching.
Scheduling Algorithms
Section titled “Scheduling Algorithms”It ia s short term scheduling that realize a certain policy to choose which process to assign PU from READY ones.
Different policies aim to improve different parameters based on the context in which the operative system is used (server farm, laptop computer, embedded device, …).
Some important parameters are:
- percentage of CPU usage
- throughput (number of processes completed in a given time)
- response time
- fairness
First Come First Served
Section titled “First Come First Served”FCFS policy assign CPU to processes in the order they get to the system. They’re managed into a FIFO queue. Scheduling type is non-preemptive.
Mean waiting time is quite high due to non-preemption: this policy doesn’t allow good performances. It is widely diffuse in batch systems.
Shortest Job First
Section titled “Shortest Job First”SJF policy assign CPU to the process that executes in the lowest time. This implies that the system must know in advance processes’ characteristics.
Round Robin
Section titled “Round Robin”This policy was born for time-sharing systems. Processes’ READY queue is managed with a FIFO. CPU is assigned to each process for a fixed period of time.
If a process P0 does not terminate in the given time, CPU is reassigned to the subsequent process P1 and P0 is placed back in the READY queue.
The fixed period of time must be sufficiently greater than context switching time to avoid loose in CPU productivity.
Priority Policy
Section titled “Priority Policy”Starting from Round Robin, this policy introduce many queues of processes based on their priority level.
Priority can be static (fixed based on process’ characteristics) or dynamic (change during time). Static priority can lead to starvation issue: a process with low priority could never get access to CPU since it’s overcome by processes with higher priority.
Dynamic priority disadvantage CPU bound processes, avoid starvation and advantage I/O bound processes to help the user perform the tasks he needs.