Process

From StudyWiki

Contents 1 Overview 2 Process Life Cycle 2.1 Process Creation 2.2 Three State Model 2.2.1 Process State Queues 3 Concurrent Processes 4 The Dispatcher 5 Process Scheduling 5.1 Low Level Scheduling Algorithms 5.1.1 First Come First Served 5.1.2 Shortest Remaining Time 5.1.3 Shortest Job First 5.1.4 Round Robin

Overview

Process

an instance of a computer program that is being sequentially executed by a computer system that has the ability to run several computer programs concurrently.

A computer program itself is just a passive collection of instructions, while a process is the actual execution of those instructions

• a program is the code a programmer writes
• a process is a program in execution
  • an instance of a program along with its data
• there may be several copies of the same program running simultaneously
  • e.g. several different processes
  • they may share program code
    • shared code shouldn't be changes during execution
  • different processes require different data areas
• the OS stores information about each process in a process control block (PCB), or process descriptor

Process Life Cycle

Process Creation

• created by a user via a command
  • when a user initiates a program, OS creates a PCB data structure to represent the execution of this program
  • OS also allocates resources for the process
  • process consists of machine code in memory and PCB
• created by user process (spawning a process)
  • process that creates a new process is called the parent, while the created process is called the child
• the child can also create new processes, forming a tree of processes

Three State Model

• A process can be in 3 main states:

  Ready

  Ready to run, but waiting for the CPU

  Running

  Actually running on the CPU

  Blocked

  waiting for an I/O operation to complete

Process State Queues

• a process is in exactly 1 state at any time
• can be only one process in the running state per processor
• there may be a queue of processes in the running state
• there may be several queues of processes in the blocked state
  • each represents one resource for which processes in that queue are waiting.

Concurrent Processes

• each CPU can only execute 1 instruction at a time
• CPU continues executing 1 process until
  • the process issues and I/O request by a system call
  • or an interrupt occurs e.g. timeout event
• both cause CPU execution to jump into the OS
  • the code handling the I/O oe the interrupt handler
• this allows the OS to take control
  • and, if necessary, switch the CPU to other processes

The Dispatcher

• following I/O system call or interrupt handling
• control is pass to the dispatcher, or low level scheduler
• the dispatcher then:
  1. decides if the current process is still the most appropriate to run
     • if yes, return control to it
     • otherwise:
  2. save state of current process in the PCB
  3. retrieve the state of the most suitable process
  4. transfer control to the newly selected process, at the point indicated by the restored program counter
• action of storing the state of current and (re)starting another progress is called a context change

Process Scheduling

• OS determines optimal sequence and timing of assigning CPU to processes, called scheduling
• objectives of scheduling
  • maximise system throughput
  • be fair to all users
  • provide tolerable response
• criteria for scheduling
  • user-assigned priority
  • job class: batch, online, or real-time
  • resource required (expected runtime) or used to date
• waiting time to date

• there are 3 levels of scheduling

  1. High Level Scheduling

     Decide whether to admit a new job into the system

     Medium Level Scheduling

     Concerns decision to temporarily remove a process from or reintroduce a process into the system

     Low Level Scheduling

     Decide which process in the ready state should run

Low Level Scheduling Algorithms

• 2 scheduling policies

  • Non Pre-emptive

    allow processes to run until complete or incurring an I/O wait

    Pre-emptive

    allow processes to be interrupted and replaced be other processes

• Major scheduling algorithms:
  • Non Pre-emptive
    • First Come First Served (FCFS)
    • Shortest Job First (SJF)
  • Pre-emptive
    • Shortest Remaining Time (SRT)
    • Round Robin (RR)

First Come First Served

• assigns CPU to process that is ready first
• Favours long jobs
• to be fair, the ratio of waiting time/run-time should be about the same for each process

Job	Estimated Run (a)	Waiting (b)	Ratio (b/a) !
1	2	0
2	60	2
3	1	62
4	3	63
5	50	66

Shortest Remaining Time

• selects job with shortest estimated remaining time
• during the run of a process, if a new job arrives whose run time is shorter than the remaining run-time of current process, it will be pre-empted to allow the new job to start
• Favours short jobs
• long jobs may be starved
• needs to measure elapsed run-time

Shortest Job First

• selects job with shortest estimated run time
• favours short jobs
• long jobs may be starved by arrival of short jobs

Job	Estimated Run (a)	Waiting (b)	Ratio (b/a) !
3	1	0
1	2	1
4	3	3
5	50	6
2	60	56

Round Robin

• Assigns CPU to each process in turn with fixed time quantum, typically 10-20ms
• if a process runs over its quantum, it is interrupted - a timeout - and returned to the back of the queue
• Pre-emptive and heavy overhead due to context switches.