PROCESS MANAGEMENT:
What is a Process?
Process memory is divided into four sections for efficient working :
-
The Text section is made up of the compiled program code, read in from non-volatile storage when the program is launched.
-
The Data section is made up of the global and static variables, allocated and initialized prior to executing the main.
-
The Heap is used for the dynamic memory allocation and is managed via calls to new, delete, malloc, free, etc.
-
The Stack is used for local variables. Space on the stack is reserved for local variables when they are declared.
States of Process:
Submit:
-
User submits a job and the system must
respond.
Hold:-
Job converted into machine-readable form, resources are not allocated. Job is normally inserted at the back of the ready queue (list). Job scheduler (OS) accesses the job and invokes memory management for allocation of memory, device management for allocation of device. If successful, it then invokes process management to place the process in queue.
Ready:-
Process is about to start computation
(Ready to run) if the processor is allocated.
Run:-
Processor is assigned and its program is
presently being executed.
Wait:-
Waiting for some events (I/O device).
Complete:-
Process has completed its computation and
all its assigned resources may be deallocated.
Process Control Block (PCB):-
1. OS groups all information that it needs about a particular process into a data structure called PCB.
2. Whenever a process is created, OS creates a corresponding PCB to serve as its run time description during the lifetime of process.
3. When the process terminates, its PCB is released to full of free cells from which new PCBs are drawn.
4. Information stored in PCB typically includes:-
4.1. PID (Process Identification)
4.2. Priority
4.3. State(Ready/Running/Suspend)
4.4. Hardware state(Processor/Register/Flag)
4.5. Scheduling information (To whom/when/how long)
4.6. Memory management information
4.7. I/O status (pending operations)
4.8. File Management (Open file access right)
4.9. Accounting Information.
Process Scheduling:-
1.
It refers to a set of policies
and mechanisms built into the OS that governs the order in which the work to be
done by the computer system.
2.
Scheduler is that part of OS
that is based on some algorithm, decides which process to run first when more
than one process are present. The algorithm is called Scheduling Algorithm.
Pre-emptive:-
The strategy of allowing processes that are
logically rumble should be suspended temporarily.
Non
Pre-emptive:-
Once the processor is allocated, the
process is allowed to run until it terminates or incurs on I/O wait i.e. it
cannot forcibly lose the process.
Priority-based Scheduling (Pre-emptive) :-
1. In principle, each process in the system
is assigned a priority level and the scheduler always chooses the highest
priority ready process, priority may be static or dynamic.
2. The initial values are assigned by the
user or the system at the time of process creation. The level of priority may
be determined on the basis of characteristics, resource requirements and run
time behavior of the process.
3. The common problem with priority based
scheduling is the possibility that low priority may be effectively locked out
by the higher priority one. In general, completion of a process within a finite
time of its creation can’t be guaranteed by the scheduling time – indefinite
blocking (starvation).
4. Remedy/ Aging priority: - The priority of
each process is gradually increased after the process spends certain amount of
time in the system. Eventually the older process attains the higher priority –
Event Driven Scheduling.
5. Event driven process consists of fixed or
dynamically varying priority to all process and scheduling the highest priority
ready process whenever a significant event occurs.
6. Priority based scheduling is used in hard
real time system.
7. SJF algorithm is a special case of
priority based scheduling. Equal priority processes are scheduled in FCFS
scheduling.
8. Priorities are generally from fixed range
of numbers which may be assigned in increasing or decreasing order.
Non-preemptive Scheduling is a CPU scheduling technique the process takes the resource (CPU time) and holds it till the process gets terminated or is pushed to the waiting state. No process is interrupted until it is completed, and after that processor switches to another process.
Algorithms that are based on non-preemptive Scheduling are non-preemptive priority, and shortest Job first.
Multilevel queue scheduling:-
1.One way to
implement complex scheduling is to clarify the workload according to its
characteristics and to maintain separate process queue service by the different
scheduler. (advantage)
2.It partitions
the ready queue into several separate queues. The processes are permanently
assigned to one queue.
3.Multilevel
queue scheduling may also impose the combined overhead of its constituent
scheduling discipline. (drawback)
Multilevel Queue Feedback Scheduling :-
1. It allows a process to move between
queues. The idea is to separate processes with different CPU bursts.
2. If a process uses too much CPU time,
it will be moved to a lower priority queue. Similarly, a process that waits too
long in a lower priority queue it may be moved to a higher priority queue –
This form of aging prevents starvation. It is defined by the following
parameters:-
2.1. Number of queues.
2.2. The scheduling algorithm for each
queue.
2.3. The method used to determine when to
upgrade a process to a higher priority queue.
2.4. The method used to determine when to
demote a process to a lower priority queue.
2.5. Method used to determine which queue a
process will enter when that process needs service.
Concurrent Process:-
If execution of
the last instruction of the first process is not completed before the first
instruction of the second process we say that processes arte concurrent
process. Here the total execution time is an overlapping time.
Interacting Process:-
These are the
processes which share the common resources.
Non Interacting Process:-
These are the
processes that do not share the common resources.
Process competition:-
Depending upon
the scheduling criteria a particular resource will be assigned to a particular
process.
Process Cooperation:-
Each process depends directly on data produced
by other members of the community.
Mutual Exclusion:-
No 2 process can
share the same resources at the same time. Total operation of a process can be
divided into 2 parts:-
a. Computation
with its own internal variable is called non critical region.
b. Computation
with shared variables is called critical region.
Achieving Mutual Exclusion by Busy Waiting:-
1. 2 concurrent
processes p & q are called cyclic i.e. every now and then they wish to
share resource R for a finite time but cannot use it at the same time.
2. Mutual
exclusion can be achieved with busy waiting. While 1 process is busy, by
updating shared resource in its critical region. No other process will enter in
its critical region – Waiting.
Synchronization among concurrent processes:-
1. No two
processes can be simultaneously in their critical region – Mutual exclusion.
2. When a
process wishes to enter its critical region, it will be enabled to do so within
a finite time.
3. No assumption
can be made about relative speeds of progress of the process.
4. A process
should not block indefinitely the progress of other process.
Process Cooperation:-
1. Process P
produces and sends a sequence of data.
2. Process C
receives and consumes data produces by P.
3. We call
process P as Producer, process C as Consumer and the problem is ‘Producer
Consumer Problem’.
4. Speeds of P
and C are independent, so situations may arise:-
4.1. Sender
Ready, Receiver Unready
4.2. Sender
Unready, Receiver Ready
5. Concept of
buffer was introduced to smooth speed variations between processes.
Inter Process Communication:-
IPC is subjected
to the following resource constraints:-
1. Sender cannot
exceed the buffer’s capacity (which is finite).
2. Receiver
cannot consume message faster than their producer i.e. Receiver cannot consume
message from an empty buffer.
Synchronization rule:-
1. If the sender
tries to put a message in a full buffer, the sender will be delayed until the
receiver has taken at least one message from full buffer.
2. If the
receiver tries to receive a message from empty buffer, receiver will be delayed
until the sender has put another message into empty buffer.
3. Messages are intended to be received as they
are sent (No loss, No permutation, No combination).
Two IPC Primitive:-
1. Sleep():-
It is a system
call that blocks/suspends a calling process until another process wakes it up.
2. Wakeup():-
It is a system
call to wake up another process.
Critical Section Problems:-
I.Producer
Consumer problem with Sleep() and Wakeup():-
Max: - Maximum
number of slots in the buffer.
Count: - Counts
the number of messages in the buffer at any instance.
Synchronization
rule with Sleep() and Wakeup():-
1. To produce a
message P will fist check if Count = Max, if so P will call Sleep(), if not P
will add an item and increase count by 1.
2. To consume a
message C will first check if Count = 0, if so it will call Sleep(), otherwise
it removes the page and decrements count by one.
3. Both P and C
also test if other processes are asleep, if so, it awakes the process.
Pseudo Code for Producer and Consumer:-
#define true 1
#define max 100
int count = 0;
Producer()
{
while(true)
{
Produce_Item()
{
//generate
message
if(Count
== Max)
//Is
buffer full?
Sleep();
Enter_Item()
{
//
put the item
Count++;
if(Count
== 1)
//Was
buffer empty?
Wakeup(Consumer);
}
}
}
}
Consumer()
{
while(true)
{
if(Count
== 0)
//Is
buffer empty?
Sleep();
Remove_Item(); //Remove item out of buffer
Count--;
if(Count == Max - 1)
//Was
buffer full?
Wakeup(Producer);
Consume_Item();
//Use
the message
}
}
II. Producer Consumer problem using message passing (Hardware Solution):-
1. This
system uses two primitives:-
a. Send(destination,
&message)
b. Receive(source,
&message)
2. It
is producer consumer problem with message passing technique and no shared
memory.
3. ssumptions:-
3.1. All messages
are of same size.
3.2. Messages
sent but not yet received are automatically buffered by OS.
4. Consider
a total of N messages analogous to the N slot.
5. The
consumer starts out by sending N empty messages to the producer, whenever the
producer has an item to give to the consumer; it takes an empty message from
the consumer and sends back a full one.
6. In
this way the total number of messages in the system remains constant in time,
so they can be stored in a given amount of memory.
7. If
producer works faster it will wait for an empty message from the consumer.
8. If
consumer works faster, the consumer will be blocked, waiting for a full one.
Pseudo Code:-
#define N 100
//no of slots in the buffer
Producer()
{
int
item;
message
m; // message buffer
while(true)
{
Produce_Item();
//generate item to put into buffer
Receive(Consumer,&m);
//wait
for an empty to arrive
Build_Message(&m,item);
//construct
a message to send
Send(Consumer,&m);
//Send
full message(item) to consumer
}
}
Consumer()
{
int
item i;
message
m; //message buffer
for(i
= 0; i < N; i++)
Send(Producer,&m);
//Send
N empties
while(true)
{
Receive(Producer,&m);
//Get
a full message
Extract_Item(&item,&m);
//Take
item out of message
Consume_Item(item);
//Utilise
the message
Send(Producer,&m);
//Send
back empty reply
}
}
III. Dining Philosopher Problem (IPC
classical problem):-
Problem Statement:-
1. 5 Philosophers are seated around a circular table.
In front of each philosopher has a plate of
slippery spaghetti.
2. Between each plate there is a fork, the spaghetti
is so slippery that a philosopher needs 2 forks at a time to eat it.
3. An algorithm has to be written for each philosopher
so that the philosophers never get stuck and can eat with maximum parallelism.
4. There are 3 states of a philosopher: - Thinking
(Past) , Eating (Present continuous), Hungry (She wishes to eat/future).
5. The life of a philosopher consists of alternate
periods of hungry, eating and thinking.
6. Fork is treated as critical region, take_fork(), put_fork(),
employ the semaphore variable
mutx.
7. A philosopher is successful to acquire 2 forks if
left neighbour and right neighbour are not eating, otherwise, it will go to
sleep().
8. After eating and put_fork() each philosopher awakes
up her left and right neighbour by taste(left) and taste(right).
9. Forks are implemented in the critical region.
Pseudo Code:-
#define true 1
#define n 5
#define left (i - 1) % n
#define right (i + 1) % n
#define thinking 0
#define hungry 1
#define eating 0
typedef int semaphore;
int state[n];
semaphore mutex = 1;
semaphore s[n];
philospher(int i)
{
while (true)
{
think();
take_fork(i); //aquire 2 forks or blocks!!!
eat();
put_fork(i); //put both forks back on the table!!!
}
}
take_fork(int i)
{
down(mutex); //enter
critical region
state[i] =
hungry; //shows intention of eating
taste(i); //try to
aqurire
up(mutex); //exit critical
region
down(s[i]);
}
put_fork(int i)
{
down(mutex); //enter
critical region
state[i] =
thinking; //finished eating
taste(left); //see if left neighbour can now eat
taste(right); //see if
right neighbour can now eat
up(mutex);
}
taste(int i)
{
if (state[i]
== hungry && state[left] != eating && state[right] != eating)
{
state[i]
= eating;
up(s[i]);
}
}
IV. Readers
and Writers problem:-
1. It
is an IPC problem, which models access to a database (computerized record
keeping system).
2. It
is acceptable to have multiple processes reading the database at the same time
but one process is writing (updating) the database, no other process may have
access to the database.
3. In
this solution, the first reader to get access to the database does a down on
the semaphore DB, subsequent readers increment a counter (RC).
4. As
readers leave, they decrement the counter and do an up operation on the
semaphore allowing a blocked writer (1) to get in.
5. Assumptions: The models to access DB, design is based on 3 assumptions.
5.1 Multiple
Processes (Readers) can read the DB at the same time.
5.2. Only
one writer at a time is allowed to get access to the database and no other
processes are allowed to get access to the database.
5.3 This
solution provides readers to get priority over writer.
5.4. RC –
Counts the no. of readers at any time.
Pseudo code:-
typedef int semaphore;
semaphore mutx = 1;// controlls access RC
semaphore db = 1; // controlls access to database
int rc = 0; // number of processes reading the
database
Readers()
{
while(true)
{
down(mutx);//get
exclusive access to rc
rc+=
1; // one more reader reads
if(rc
== 1)
down(db);//if
its first reader
up(mutx);
read_database(); read data in the database
down(mutx);//
leave database
rc-= 1;//one reader fewer now
if(rc == 0)
//if
this is last reader
up(db);
up(mutx);//release exclusive access to rc
use_read_data();// task in non critical region
}
}
Writer()
{
while(true)
{
prepare_data();//task
of non critical region
down(db);//get
exclusive access to database
write_database();//update the database
up(db);//release exclusive access
}
}
Content
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 content switch.
When does context switching happen?
1. When a high-priority process comes to a ready state (i.e. with higher priority than the running process)
2. An Interrupt occurs
3. User and kernel-mode switch (It is not necessary though)
4. Preemptive CPU scheduling used.
Context Switch vs Mode Switch
A
mode switch occurs when the CPU privilege level is changed, for example
when a system call is made or a fault occurs. The kernel works in more a
privileged mode than a standard user task. If a user process wants to access things that are only accessible to the kernel, a mode switch must
occur. The currently executing process need not be changed during a
mode switch.
A mode switch typically occurs for a process context switch to occur. Only the kernel can cause a context switch.
Schedulers:
There are 3 main schedulers of operating system:-
1. Long
term scheduler
2. Medium
term scheduler
3. Short
term scheduler
Long term
scheduler:
The function of the long term scheduler is to select
the jobs from the pool of jobs and load these jobs into main memory (ready
queue) of the computer, so the long term scheduler is also called job
scheduler.
Short term
scheduler:
The function of the short term scheduler is to select
a job from the ready queue and gives the control of the CPU to that process
with the help of dispatcher. Short term scheduler is also called CPU scheduler.
The method of selecting a process from the ready queue is depending on the CPU
scheduling algorithm.
Medium term
scheduler:
If a process requests an I/O in the middle of the
execution, then the process is removed from the main memory and loaded in the
ready queue. When the I/O operation is completed then the job is moved from
waiting queue to ready queue. These 2 jobs are performed by medium-term
scheduler.
QnA:
1. What
is the purpose of job scheduler?
Ans: It selects one job from many jobs submitted to
the system for execution.
2. What
is the purpose of dispatcher?
Ans: This allocates the processer for a particular
process.
3. What
is the duty of I/O scheduler?
Ans: I/O scheduler decides which device must be
allocated to which process.
4. What
do you mean by polling?
Ans: Polling is a technique
in which one system checks the status of another independent system.
5. Process vs Program
| Process | Program |
|---|---|
| The process is basically an instance of the computer program that is being executed. | A Program is basically a collection of instructions that mainly performs a specific task when executed by the computer. |
| A process has a shorter lifetime. | A Program has a longer lifetime. |
| A Process requires resources such as memory, CPU, Input-Output devices. | A Program is stored by hard-disk and does not require any resources. |
| A process has a dynamic instance of code and data | A Program has static code and static data. |
| Basically, a process is the running instance of the code. | On the other hand, the program is the executable code. |
Comments
Post a Comment