Transcript Process - Likho Pao

Process
• Program (Passive Entity) is a sequence of instructions, written to
perform a specified task on a computer. A computer
requires
programs
to
function,
typically
executing
the program's instructions in a central processor. Program stores in
secondary memory.
• A process (active entity) is a program or an instance of a computer
program that is being executed. It contains the program code and
its current activity. Depending on the operating system (OS),
a process may be made up of multiple threads of execution that
execute instructions concurrently.
“Program under execution or when program in main memory or
running program”
Process State
•
•
•
•
•
New (Job Queue or HDD): The process is being created.
Running (Processor): Instructions are being executed.
Waiting (device queue): The process is waiting for some event to occur (such as an
I/O completion or reception of a signal).
Ready (Ready Queue or Main Memory): The process is waiting to be assigned to a
processor.
Terminated: The process has finished execution.
Schedulers
• Long term scheduler or job scheduler: HDD to
Main memory (between new state and ready state)
• Short term scheduler or CPU scheduler or
Dispature: main memory to CPU (between Ready
state and running state)
• Medium term scheduler
Long term scheduler
• It is also called job scheduler. Long term scheduler
determines which programs are admitted to the system for
processing.
• Job scheduler selects processes from the queue and loads
them into memory for execution. Process loads into the
memory for CPU scheduling.
• The primary objective of the job scheduler is to controls the
degree of multiprogramming. If the degree of
multiprogramming is stable, then the average rate of
process creation must be equal to the average departure
rate of processes leaving the system.
• Example any person waits for friends means not decided a
time where this process will be completed.
Short term scheduler
• It is also called CPU scheduler. Main objective is increasing system
performance in accordance with the chosen set of criteria. It is the change
of ready state to running state of the process. CPU scheduler selects
process among the processes that are ready to execute and allocates CPU
to one of them.
• Short term scheduler also known as dispatcher, execute most frequently
and makes the fine grained decision of which process to execute next.
Short term scheduler is faster than long term scheduler.
• The dispatcher is the module that give control of the CPU to process
selected by short term scheduler . This function involves
– Switching context
– Switching to user mode
– Jumping to the proper location in the user program to restart the program
• the time it takes for the dispatcher to stop one process and start another
running is known as the dispatch latency.
Medium term scheduler
• Medium term scheduling is part of the swapping. It
removes the processes from the memory. It reduces
the degree of multiprogramming. The medium term
scheduler is in-charge of handling the swapped outprocesses.
Difference
Process Control Block
• Each process is represented
in the operating system by a
process control block (PCB)
also called a task control
block. PCB is the data
structure used by the
operating system. Operating
system
groups
all
information that needs
about particular process.
Context Switch
• Switching the CPU to another process requires saving the state of
the old process and loading the saved state for the new process.
This task is known as a context switch. The context of a process is
represented in the PCB of a process.
• A context switch is the mechanism to store and restore the state or
context of a CPU in Process Control block so that a process
execution can be resumed from the same point at a later time.
• Using this technique a context switcher enables multiple processes
to share a single CPU. Context switching is an essential part of a
multitasking operating system features.
• When the scheduler switches the CPU from executing one process
to execute another, the context switcher saves the content of all
processor registers for the process being removed from the CPU, in
its process descriptor. The context of a process is represented in the
process control block of a process.
Context Switching
Context Switching
•
•
•
•
•
•
•
When the process is switched, the following
information is stored.
Program Counter
Scheduling Information
Base and limit register value
Currently used register
Changed State
I/O State
Accounting
Process Scheduling
• The process scheduling is the activity of the process
manager that handles the removal of the running
process from the CPU and the selection of another
process on the basis of a particular strategy.
• Process scheduling is an essential part of a
Multiprogramming operating system. Such operating
systems allow more than one process to be loaded into
the executable memory at a time and loaded process
shares the CPU using time multiplexing.
• CPU schedule two type of process
• CPU Bounded
• I/O bounded process
CPU-I/O Burst cycle
• The success of CPU scheduling
depends on the following observed
property of processes: Process
execution consists of a cycle of CPU
execution and I/O wait. Processes
alternate between these two states.
Process execution begins with a CPU
burst. That is followed by an I/O
burst, then another CPU burst, then
another I/O burst, and so on.
• Eventually, the last CPU burst will
end with a system request to
terminate execution, rather than
with another I/O burst.
Scheduling Algorithms
CPU scheduling deals with the problem of deciding which
of the processes in the ready queue is to be allocated
the CPU.
– First Come First Serve (FCFS) Scheduling
– Shortest-Job-First (SJF) Scheduling
• Nonpreemptive SJF
• Preemptive SJF
– Priority Scheduling
• Nonpreemptive priority
• Preemptive priority
– Round Robin(RR) Scheduling
– Multilevel Queue Scheduling
Scheduling Criteria
• CPU utilization – To keep the CPU as busy as possible.
– Lightly loaded system 40% busy
– Heavily loaded system 90% busy
• Throughput – Number of processes that complete their execution per
time unit.
• Turnaround time – Amount of time to execute a particular process; which
is the interval from time of submission of a process to the time of
completion (includes the sum of periods spent waiting to get into memory,
waiting in ready queue, executing on the CPU, and doing I/O).
• Waiting time – Sum of the periods spent waiting in the ready queue.
• Response time – The time from the submission of a request until the first
response is produced (i.e., the amount of time it takes to start responding,
but not the time that it takes to output that response).
Optimization Criteria
•
•
•
•
•
•
Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time
For interactive systems (such as time-sharing systems),
some analysts suggest that minimizing the variance in the
response time is more important than minimizing the
average response time. A system with reasonable and
predictable response time may be considered more
desirable than a system that is faster on the average, but is
highly variable. However, little work has been done on CPUscheduling algorithms to minimize variance.
•
FCFS:
– The process that requests the CPU first is allocated the CPU first.
– Implementation is based on FIFO queue.
– When a process enters the ready queue, its PCB is linked onto the tail of the
queue. When the CPU is free, it is allocated to the process at the head of the
queue.
– The FCFS algorithm is nonpreemptive (i.e., the CPU keeps the process until either
terminating or requesting I/O).
•
SJF
– Nonpreemptive– once CPU given to the process it cannot be preempted until completes
its CPU burst.
• Under nonpreemptive scheduling, once the CPU has been allocated to a process,
the process keeps the CPU until it releases the CPU either by terminating or by
switching to the waiting state. This scheduling method is used by the Microsoft
Windows 3.1 and by the Apple Macintosh operating systems.
– Preemptive – if a new process arrives with CPU burst length less than remaining time of
current executing process, preempt. This scheme is known as the Shortest-RemainingTime-First (SRTF).
– If two processes have the same length next CPU burst, FCFS scheduling is used.
– SJF is optimal – gives minimum average waiting time for a given set of processes.
Priority Scheduling
• A priority number (integer) is associated with each process.
• The CPU is allocated to the process with the highest priority (smallest
integer ≡ highest priority).
• Equal priority processes are scheduled in FCFS.
• Priority can be either preemptive or nonpreemptive.
• A preemptive priority will preempt the CPU if the newly arrived process is
higher than the priority of the currently running process.
• A nonpreemptive priority will simply put the new highest priority process
at the head of the ready queue.
• Problem ≡ Starvation (indefinite blocking) – low priority processes may
never execute.
• Solution ≡ Aging – as time progresses increase the priority of the process,
so eventually the process will become the highest priority and will gain the
CPU (i.e., the more time is spending a process in ready queue waiting, its
priority becomes higher and higher)
RR
• The Round Robin is designed for time sharing systems.
• The RR is similar to FCFS, but preemption is added to switch between
processes.
• Each process gets a small unit of CPU time (time quantum or time slice ),
usually 10-100 milliseconds. After this time has elapsed, the process is
preempted and added to the end of the ready queue (ready queue treated
as a circular queue) . That is, after the time slice is expired an interrupt will
occur and a context switch.
• If there are n processes in the ready queue and the time quantum is q,
then each process gets 1/n of the CPU time in chunks of at most q time
units at once. No process waits more than (n-1)q time units.
• The performance of RR depends on the size of the time slice q :
– If q very large (infinite) ⇒ FIFO
– If q very small ⇒ RR is called processor sharing, and context switch increases.
So, q must be large with respect to context switch, otherwise overhead is too
high.
• The performance of the RR algorithm depends heavily on the
size of the time quantum. At one extreme, if the time
quantum is very large (infinite), the RR policy is the same as
the FCFS policy.
• If the time quantum is very small (say 1 microsecond), the RR
approach is called processor sharing, and appears (in theory)
to the users as though each of n processes has its own
processor running at 1/n the speed of the real processor.
• This approach was used in Control Data Corporation (CDC)
hardware to implement 10 peripheral processors with only
one set of hardware and 10 sets of registers.
• Turnaround time depend on time quantum. (it will be larger
with respect to context switching)
problems
• FCFS: Convoy effect
• There is a convoy effect, as all the other processes wait for
the one big process to get off the CPU. This effect results in
lower CPU and device utilization than might be possible if
the shorter processes were allowed to go first.
• Priority schduling: Aging
– Aging is a technique of gradually increasing the
priority of processes that wait in the system for a
long time.
Multilevel Queue Scheduling
• Multi-level queue scheduling algorithm is used in scenarios where
the processes can be classified into groups based on property like
process type, CPU time, IO access, memory size, etc. One general
classification of the processes is foreground processes and
background processes.
• A multilevel queue-scheduling algorithm partitions the ready
queue into several separate queues. The processes are permanently
assigned to one queue, generally based on some property of the
process, such as memory size, process priority, or process type. Each
queue has its own scheduling algorithm.
• For example, separate queues might be used for foreground
(interactive) and background (batch) processes. The foreground
queue might be scheduled by an RR algorithm, while the
background queue is scheduled by an FCFS algorithm.
• an example of a multilevel
queue-scheduling algorithm
with five queues:
1. System processes
2. Interactive processes
3. Interactive editing
processes
4. Batch processes
5. Student processes
Multilevel Feedback Queue Scheduling
• Normally, in a multilevel queue-scheduling algorithm,
processes are permanently assigned to a queue on
entry to the system. Processes do not move between
queues (problem).
• If there are separate queues for foreground and
background processes, for example, processes do not
move from one queue to the other, since processes do
not change their foreground or background nature.
• This setup has the advantage of low scheduling
overhead, but the disadvantage of being inflexible.
• Multilevel feedback queue scheduling, however,
allows a process to move between queues. The
idea is to separate processes with different CPUburst characteristics.
• If a process uses too much CPU time, it will be
moved to a lower-priority queue. This scheme
leaves I/O-bound and interactive processes in the
higher-priority queues. Similarly, a process that
waits too long in a lower priority queue may be
moved to a higher-priority queue. This form of
aging prevents starvation.
• In general, a multilevel feedback
queue scheduler is defined by the
following parameters:
• The number of queues
• The scheduling algorithm for each
queue
• The method used to determine
when to upgrade a process to a
higher priority queue
• The method used to determine
when to demote a process to a
lower-priority queue
• The method used to determine
which queue a process will enter
when that process needs service
Process creation (Fork())
• Fork() is a system call which is required to
create process in linux.
• User can create replication of current running
process using fork().