OS Processes: States, PCB & Scheduling

• Education is the most powerful weapon which you can use to change the world, according to Nelson Mandela.

Processes - Outline

• Processes Definition and Management are key to understanding OS operations.
• A consideration of the Process States Model, specifically the 5-state model.
• Process Control Block (PCB) details are of key importance.
• Process Scheduling is a core concept for process execution.
• Understanding Context Switch.
• Focus on Operations on Processes; Creation, Termination, and Inter-process Communication.

Learning Outcomes

• Need to define a Process, and a Process State.
• Be able to differentiate between a process and a thread.
• Understand multitasking and how it works.
• Be able to differentiate between the 5 states of a process and draw a state process diagram.
• Understanding the importance and architecture of PCB.
• Know the scheduling concept and draw a process scheduling diagram.
• Be able to differentiate between long-term, short-term and mid-term schedulers.
• Understand the concept and the importance of Context Switch.
• Know about the process operations; Creation, Termination and Inter-Process Communication.
• Learn the Producer-Consumer Model.

Process Definition and Management

• A program written in a high-level language such as C/C++/C#/Java/etc is transformed by a compiler.
• This transforms it into readable code by machine and loads into the operating system via computer memory
• Resources are allocated to enable Program Execution.

Process vs Thread

• A process can be thought of as a program in execution.
• A unit of execution within a process where a process can have one thread or more.

Multitasking

• During its lifetime, a process does a lot of I/O activity.
• This is especially true for I/O bound processes, but also applies to CPU bound processes.
• I/O is very slow compared to CPU.
• While a process waits for completion of some I/O activity, it is considered "idle".
• Other processes can then use the CPU during this time.
• The OS achieves multitasking by executing many processes with concurrency.
• Multitasking is similar to parallel computing but permits time-sharing the same hardware to many processes.

Chrome Browser as Multi-Process Architecture

• Google Chrome Browser is a multi-process application, with 3 types of processes.
• The Browser element manages the user interface and performs network I/O.
• A new browser process is created when Chrome is started and only one browser process is created.
• The Renderer processes render web pages, parse HTML and run Javascript code, etc.
• A new renderer is created for each website opened.
• The Plug-in creates a process for each type of plug-in, such as Adobe Flash Player, in use.
• Plugin processes contain the code for the plug-in and enables the plug-in to communicate with associated renderer processes and the browser process.
• Adobe Flash Player (Shockwave Flash) is computer software for content on the Adobe Flash platform.
• Flash Player is capable of viewing multimedia contents, executing applications, and streaming audio/video.

Process State

• The state of a process is defined by its current activity.

• When a process is executing, it changes from one state to another.

• Understand the processes’ state by asking, What is the process currently doing?

The 5 States of Process

• New: Process is being created.
• Running: Instructions are being executed.
• Waiting: Process is waiting for some events to occur, like I/O completion or signal reception.
• Ready: Process is waiting to be assigned to a processor.
• Terminated: Process has finished execution.

Diagram of Process State

• A new process is admitted and enters the ready state.
• From 'ready' an interrupt occurs bringing it to the 'running' state.
• A scheduler dispatch puts a process into 'waiting' for I/O, until the I/O event completes.
• From 'running' exit to terminated.

PCB: Process Control Block

• Each process is presented in the Operating System by a Process Control Block (PCB), also called Task Control Block.
• PCB is used to represent a particular process in the Operating System.
• Each PCB contains:
  • Process ID - an identifier for a particular process.
  • Process State - describes the current state of the process (e.g., New, Waiting).
  • Program Counter - the address of the next instruction that has to be executed by a particular process.
  • CPU Registers - informs the registers used by a particular process (index registers, stack pointer etc).
  • CPU Scheduling Information - provides priority for the processes, pointer to the scheduling queue.
  • Memory Management Information - the memory used by a particular process (related to a certain process).
  • Accounting Information - being used by the particular process such as CPU, time, memory.
  • I/O status Information - Represents the I/O devices assigned to a particular process.

PCB in Linux

• Linux maintains a doubly-linked list of the processes by the C structure task_struct.
• Each task_struct stores information such as process identifier (pid), state, scheduling information, parent, children, list of open files, and address space.

Process Scheduling

• The objective of multiprogramming is to have process running at all times, to maximize CPU utilisation.
• The objective of time sharing is to switch the CPU among processes frequently so that users can interact with each program while it's running.
• A process scheduler selects an available process (possibly from a set of several available processes) for program execution on the CPU to meet these two objectives.

Single Processor System

• For a single processor system, there will never be more than one running process.
• If there are more processes, the rest will have to wait until the CPU is free and can be rescheduled.

Scheduling Queues

• As processes enter the system, they are put into a job queue, which consists of all the processes in the system.
• The processes that are residing in the main memory and are ready and waiting to be executed are kept on a list called the ready queue.

Scheduler Types

• Long Term and Short Term schedulers.
• Often, in a batch system, more processes are submitted immediately, and processes are spooled to a mass-storage device (disk).
• The long-term or job scheduler selects processes from this pool and loads them into memory for execution.
• The short-term or CPU scheduler selects from processes ready to execute and allocates the CPU.
• The frequency of execution is the primary difference between these two schedulers.
  • a short-term scheduler must select a new process for the CPU frequently
  • a long-term scheduler executes infrequently.
• The long-term scheduler should select a good process mix of I/O-bound and CPU-bound processes.

Medium-Term Scheduler

• Medium-term scheduling is a part of swapping, removing processes from memory to reduce multiprogramming.
• The medium-term scheduler is in charge of handling swapped out-processes.
• A running process may be suspended if it makes an I/O request.

Context Switch

• Interrupts cause the operating system to change a CPU from its current task and to run a kernel routine.
• When an interrupt occurs, the system needs to save the current context of the process on the CPU so that it can restore that context.
• The context is represented in the PCB (Process Control Block) of the process.
• A context switch occurs when a CPU core switches from one process to another.
• The OS must save the context of the current process and load the context of the new process.
• A scheduler is a kernel component that decides and dispatches which processes to run after a context switch.
• The context must be saved and restored following an interrupt call.

Context Switch Performance

• Context Switch time is pure overhead, because the system does no useful work while switching.
• Its speed varies from machine to machine, depending on memory speed, the number of registers, and special instructions.
• Typical speeds are milliseconds.

Operation on Processes

• Key considerations for operations on processes are:
  • process creation
  • process termination
  • inter-process communication.

Process Creation

• A process may create several new processes via a create process-system call during execution.
• The creating process is called the parent process, while new processes are called the children of that process.
• Each of these processes may in turn create other processes, forming a tree of processes.
• Each process has a unique pid (process identifier) an integer.
• When a process creates a new process:
  • Parent continues to execute concurrently with its children.
  • Parent waits until some or all of its children have terminated.
  • Children may have all the resources that the parent possesses.
  • Children may have a part of the resources that the parent has.
  • The child is a duplicate of the parent process with the same data.
  • The child can have a new program loaded in it.

Process control

• UNIX programs can use system calls like fork(), exec() , exit() and wait().
• fork() creates new process as an image of the parent.
• exec() is used after fork() to replace the process image with a new program.
• exit() terminates the process with an exit status.
• wait()is used by parent to wait for a child to terminate.
• Windows systems user CreateProcess - the system call directly specifies the command and child info, where the parent wait.
• Windows does not support fork().

Process Termination

• Call invokes exit() system.
• Parent catches the process by invoking the wait() function.
• When process terminates, OS deallocates all resources.
• PCB remains in memory until parent calls wait - until then the process is a zombie process.
• The parent might terminate a child process.
• The kernel might "kill" a process under severe circumstances.
• Other terminate reasons could include division by zero or access violation, etc.
• The user might abort the process.

Inter-Process Communication (IPC)

• Processes that execute concurrently in the Operating System may be independent or cooperating.
• Independent processes don’t affect or get affected by other processes.
• Cooperate processes may affect or be affected by other running processes
• IPC occurs with cooperating processes, for:
  • Information Sharing
  • Computation Speed Up
  • Convenience

Types of Communication

• Shared Memory - region of memory shared by cooperating process to exchange information.
• Message Passing - messages exchanged between the operating processes.
• Pipes- a shared file where one process writes and another reads (Unidirectional).
• Sockets - processes communicating over a network via pair of sockets, identified by IP address concatenated with port number.

Producer-Consumer Model

• A process management model where:
  • Producer produces items.
  • Consumer receives or 'consumes' items.
  • Use of buffering.
• Applications print files by copying them into some folder - a spooler process takes the files and sends them one by one to the printer

IPC: Shared Memory

• Memory needs to be accessible by Process A, Process B and there is Shared Memory between processes.

Shared Memory: Consumer-Producer Model

• Memory area is accessible by collaborating processes and organized as a cyclic buffer.

POSIX Shared Memory

• Processes have separate address spaces, so OS provides ways to allocate shared memory (POSIX Shared Memory: i.e. mmap) for different processes.
• The shared memory works only for IPC same host is possible or between processes across network.
• When many processes access shared data concurrently, synchronization is an important issue.
• The buffer is created and managed by user processes explicitly, as a circular buffer data structure, accessible by both processes.

IPC: Message Passing

• There can be Direct and Indirect Link.
• Using send(pid, msg), recv(pid, msg); Or. send(mbox, msg), recv(mbox, msg).
• Processes synchronize using Send/Receive primitives - mechanism for synchronization.
• Direct link - the other process explicitly specified (send/receive).
• Indirect link - messages exchanged via mailbox, where Processes do not know each other in advance.
• Send() and Recv() calls can be either blocking (synchronous) or non-blocking.
• Synchronous calls are a synchronization method which can be called rendez-vous.

Message Passing

• Code implementation example:

/* Consumer's main loop */
Message next_consumed;
while(true) {
    recv(producer, next_consumed)
    /* consume the item... */
}
/* Producer's main loop */
Message next_produced;
while(true) {
    /* produce an item... */
    send(consumer, next_produced)
}

Characteristics of Shared Memory and Message Passing

• Shared Memory:
  • System calls required only to establish shared memory regions.
  • Once shared memory is established, routine memory accesses occur, without kernel assistance.
• Message Passing:
  • Typically use system calls and kernel intervention(time-consuming).
  • Useful for exchanging smaller amounts of data.
  • Easier to implement in a distributed system than shared memory.
  • With several processing cores, message passing provides better performance than shared memory.

Operation on Processes IPC: Pipes

• A pipe is similar to having an intermediate file, where one process writes, and another process reads.
• The pipe exists in main memory, so it is faster than disk access.
• The system calls to read and write to/from a pipe are the same for accessing files ie: READ(fd, ...), WRITE(fd, ...).
• Two type of pipes:
  • Ordinary pipe in UNIX (Anonymous pipes in Windows) by a parent to communicate.
  • Named pipe (FIFO) accessible by any process, (unidirectional but can create 2 pipes).
  • IPC Using Pipe in Command Line Interface (CLI).

Pipes in command line interface

• CLI users can “redirect” the input and output of a program from and to a file and create "pipe” between two programs.
• The redirector ">" redirects the output of program or command into another file.
• Example: ifconfig > conf.txt will send the output to conf.txt
• The pipe symbol permits to create a pipe.
• Example: 'ifconfig | grep “192”' - the output is executed by grep "192"
• Descriptor fd[0] is for reading & fd[1] is for writing, so information into fd[1] is readable into fd[0] through pipes.