Processes and Scheduler

Introduction

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

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

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

Each level provide functionality to upper level and uses the functionality provided by the lower level.

An example of OS structured on levels is Dijkstra’s THE operative system.

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

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

All the modern multitasking operative systems support concurrency.

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

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

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

A concurrent system has essentially two ways for the processes to interact with each other:

1. Competition: using common resources that can’t be used at the same time (scanners, printers, …)
2. 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

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

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

The OS component that choose which process to load into memory (and assign CPU) is called scheduler.

Scheduling Types

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

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

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

Long term

Decide which processes to load into memory. This level of scheduler is absent in time-sharing systems.

Medium term

Can execute swapping to change the number of processes loaded into memory.

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

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

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

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

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

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.