Process Management
A process is a program in execution. The distinction is that a program is a static bit of code; the process is the instance of that program being executed. For example, if the same program is running twice, the program will be loaded into memory once, but it will have two processes - one for each instance of the program.
The operating system maintains information about all the processes in the process control block (PCB). The contains information such as the process’s unique ID, the current state of the process (explained in a moment), the program counter, pointers to allocated memory space and resources, CPU time used so far, and estimated time to completion.
The process can be in any one of three five, starting (while it is being loaded) running (if it is currently using the processor), runnable (if it is ready to be executed and is just waiting for the processor to become available), suspended (if it is waiting for I/O and could not execute even if the processor was free) and terminated.
Processes may form parent-child relationships, if a process spawns a child process, then these two processes may (or may not) share all or some of their information. A child process will execute concurrently with its parent and the parent will not complete until all of its children have - although a parent may choose to abort its children.
Threads are paths of execution within a process. For example, the same code may have two sections being executed simultaneously. One process may have many threads, which are stored in the thread control block (TCB) which stores information very much like the PCB. An operating system which allows multithreading (i.e. more than one thread-perprocess) allows the programmer to create programs which can have two or more parts executing concurrently. This is more efficient than spawning a new process because threads share address space and therefore require less resources than new processes, threads are also able to share their code, data and operating system resource allocation with other threads in their process.
Support for threads may come from the user (programmer) level or at kernel level by the OS. The relationship between user threads and kernel threads may be:
- one to one: each user thread exists as a kernel thread
- many to one: many user threads exist through one kernel thread
- many to many: multiplexes many user threads to an equal or smaller number of kernel threads.
Sharing Information between Processes
An independent process is said to be one which shares none of its data, and thus cannot be affected by the execution of any other process, a cooperating process however shares some of its data or communicates with other processes .
Inter-Process Communication (IPC)
A mechanism is required to synchronise the actions of two processes and to allow them to communicate. Once this has been established, processes can send messages to each other using send(message) and receive(message) functions.
Direct Communication
If a process names another process explicitly then it can establish a communication link with it which may be uni-directional or bi-directional, processes can send messages to each other using send(P, message)(send message to process P) and receive(Q, message) (receive message from process Q) functions.
Indirect Communication (Ports)
In this framework, messages are sent through unique "ports" (much like ports in networks) - if two processes share a port then they can communicate with each other. Many processes may use one port, so more than two processes can be communicating with each other. Commands will exist to connect to a port, send and receive through a port and disconnect from a port.
Resource Scheduling
In a single processor system, only one process can run at a time; any others must wait until the CPU is free.
(Operating System Concepts", Silberschatz)
Processes generally migrate between three different queues:
- Job Queue (All the processes in the system)
- Ready Queue (All the processes which are ready to execute)
- Device Queue (All the processes waiting for I/O devices to finish)
The Operating System must manage these queues, selecting the best item from the queues to execute next, this job is performed by schedulers. There is a long-term scheduler, which selects which items to place in the ready queue, and a short-term scheduler which selects which item from the ready queue should be executed next. Additionally, there may be a medium-term scheduler which moves items in and out of the ready queue depending on their status.
The CPU may switch from one process to another without completing it, this is known as context-shifting and it carries a time overhead since data from the process must be stored in memory as it is placed back in one of the queues. The process of context-shifting is performed by the dispatcher, which is responsible for taking the process selected by the scheduler and switching it onto the processor, the dispatcher will take time to complete this, this delay is known as the dispatcher latency. When a process uses a resource is known as a burst, so a CPU burst would be a process executing for some time, and an IO burst would be a process making use of an IO device. The "Burst-Cycle" is the switching a process between CPU bursts and IO bursts until it has completed execution.
Scheduling Algorithms
A scheduler will want to consider the following aspects when making a decision about which process to execute next:
- CPU Utilisation (the processor should be kept as busy as possible)
- Throughput (the number of processes which complete in a unit of time)
- Turnaround Time (the time taken for a process to complete)
- Waiting Time (the total time a process has spent in the queue)
- Response Time (the time from when the process was submitted, to when it first produces response)
A Gantt diagram can be used to show the times processes executed for, examples of Gantt diagrams are shown with the different scheduling algorithms described below.
First Come First Served (FCFS)
This method of scheduling means that the first process to request the processor gets it until it finished execution. This is simple to implement (just requires the use of a FIFO queue) but the average time for a process to complete may, or indeed may not be long. It can result in a convoy effect where a lot of quick processes are held back by one slow process at the front of the queue.
Shortest Job First (SJF)
This method associates processes with the length of their next CPU burst, the process with the shortest time is executed next. It is not pre-emptive, so once a burst is started it cannot be stopped, which can give rise to the problem of predicting how long a burst will take. This system is optimal for giving the lowest average waiting time.
Shortest Remaining Time First (SRTF)
Also known as pre-emptive SJF this method is very similar to SJF except that if a new process enters the queue with a burst time less than the remaining time of the current burst, then the current burst will be switched out in favour of the new process.
Priority Scheduling
With this system each process is given a priority, usually idenitified by an integer value. The process with the highest priority is executed each time. This ensures in a real time system the user can execute important tasks while less important ones are lowered in priority.
This can result in starvation though, where a process of low priority never actually executes as it is always superceeded by other higher priority bursts. The solution to this is to age a process, where after a fixed amount of time in the ready queue a process's priority is automatically promoted to ensure it does get executed in the end.
Round Robin
In Round Robin scheduling processor time is shared between process, making it ideal for time sharing systems. The processor goes through all the processes in the ready queue in turn allowing to execute for upto one 'time quantum', if it does not complete in this time the process is put back at the end of the queue until it does complete.
If there are n processes, and a time quantum is q, then each process must wait no longer than 
time units to complete.
Multilevel Queue (MLQ)
With multilevel queuing, the ready queue is partitioned into two or more queues. Processes are permanently assigned to one of the queues depending on their type (i.e. foreground/background tasks)
Each queue can then have its own scheduling algorithm, (i.e. foreground might be RR and background FCFS), there is then scheduling between the queues, normally by a fixed priority preemptive scheduling. However in some cases the queues are scheduled by time slice sharing.T
A Multilevel Feedback Queue (MLFQ) is like multilevel queuing, however rather than being permanently assigned to a queue a process may be promoted or demoted to a higher priority queue if it meets certain criteria. This can be used to prevent starvation in the queue by ageing processes, and to move CPU-greedy or particularly long tasks to low level queues.
More Complicated Systems
Multiprocessor Systems
- Asymmetric Multiprocessor Systems. This is where one processor is designated as master, and executes exclusively operating system code and delegates other work to slave processors.
- Symmetric Multiprocessor Systems. In this system all processors are equal, and can be used by any process. Although, one processor must be started first to set up the environment for all the processors, this is known as the interprocessor interrupt.
These methods can have issues such as how to share operating system code, and coherence between the two processor's caches of memory.
Multicomputer Systems
In this setup, workload is distributed over many seperate machines each with their own cache, main memory and operating system. The network passes processes to the computers and receives data back from them.
References:
- Janet Lavery - Durham University Computer Systems, Operating Systems Lecture 1, 2007
- Janet Lavery - Durham University Computer Systems, Operating Systems Lecture 3, 2007
- Janet Lavery - Durham University Computer Systems, Operating Systems Lecture 4, 2007
- Janet Lavery - Durham University Computer Systems, Operating Systems Lecture 5, 2007
- Janet Lavery - Durham University Computer Systems, Operating Systems Lecture 10, 2007
- Operating System Concepts, Silberschatz
- A2 Computing Revision - Paul Nicholls - http://resources.r9paul.org/ASA2/Computing/A2ComputingRevision.pdf