Unit I
Introduction to the Operating System
After pressing the main switch of a computer, a process called booting takes place automatically. Such things can perform automatically through a master control program of a computer, which is known as operating system.
There is no universally accepted definition of O/S. but its acts as a mediator between the system user and the hardware i.e. peripherals of the system. The main objective of an O/S is to provide an environment/ platform on which user can execute their programs in convenient and efficient manner.
It is a resource allocator of a system i.e. without getting the resources from the O/S the particular process can not execute/perform its task. So O/S can manage CPU timing, memory space, storage space, I/O devices etc. So, it is a manager/supervisor/executive of a system. It is also used to prove the security over the system. Therefore we can define an O/S as the followings:
• It is a master control program
• It is an environment variables
• It is a resource allocator
• It is a supervisor of the system
• It is a manager of the system
• It is a executive of the system
• It is a inspector of the system
• It is a security center
Basically operating system performs the following tasks:
• Provide user interface
• Job management
• Task management
• Process management
• Device management
• Providing security
1.1 Types/services of an Operating System:
MS-Dos, Windows 3x/95/98/2000/XP/NT, UNIX, Linux, Mac O/S, OS2 are the example of the operating system. The earliest operating system was developed in the late 1960’s to manage tape drive. Later in the mid 1960, it became essential parts of a system i.e. personal computer which is based upon timesharing, multi-threading, multitasking concepts.
Depending upon the working principal of an O/S we can categories it to many other different types/systems. They are:
i). Simple batch system
ii). Personal computer
iii). Time sharing system
iv). Parallel system
v). Distributed system
vi). Real time system
a) Batch System(Simple & multi programmed):
As we known device management is one of the main task of an O/S. Early computers were used card reader and tape drive as an I/O device, and line printer, is the most common output devices. So user can't directly interact with the system. In this situation user must be waited some time to get the result/output. It means, there is a delay between job submission and completion which is known as turn-around-time.
During the execution time, CPU became idle because the speed of the CUP and I/O devices are not same. To overcome this problem, simple batch system used SPOOLING (Simultaneous Peripheral Operation On-Lining) concept (1965 - 1980).
According to this concept, firstly O/S collects all the data/tasks/process/jobs from the input devices and save it to the disk. After this O/S would load as many as job into the memory one after another until the available memory could accommodate. Then the CPU is switching from one task to another and executes them. This situation i.e. after adding the SPOOLING concepts to the Simple Batch System became multiprogramming.
Following are the block diagram of this concept:
b) Time Sharing System:
In general term, it refers the allocation of a time between more then one job. It is a logical extension of multiprogramming. Typically, there are many jobs in job pool wants to execute at a time but CUP can't handle more then one job at a time. In this situation CPU can share the time slice between them equally. The main objects of this system are to provide interactive use of the system at a reasonable cost i.e. time sharing allows users to share the computer and its resources simultaneously.
c) Parallel system:
In this system, there are more than one CPU which shares the same bus, memory and I/O it is also known as multiprocessor system. In this one acts as a master processor and another became slave. The master processor handled the task first and allocates to the slave t perform some task. In general practices, we did not use this system. The main objective of this system is to increase reliability. In symmetric multiprocessing each processor runs an identical copies of an O/S i.e. separately runs the system by sharing the resources.
d) Distributed System:
This is a new concept over there the processor doesn't share this memory i.e. each processor contains its own local memory. The connecting mechanism like telephone line, high speed bus was used to connect different individual system to share the resources. But in networking environment different protocols are used to do so. To achieve following objectives we can use this system:
i. Resource sharing
ii. Computation speedup
iii. Reliability
iv. Communication
e) Real time system:
This system is used when rigid time requirements have been placed. It means with in a defined time constraints the CPU must execute that task. Mainly it is used to create flight simulator of the aircraft, scientific application, some major scientific equipments etc.
In this system sensors are used to bring the data. It has well defined fixed time constraints, within that time frame processing must be done. Depending upon the working principle of the system we can categories this system into two different categories. They are:
i). Hard real time:
In this within a given time frame the critical tasks must be executed. Such types of guarantees were providing by the system. So time is a rigid factor over here. Aeronautical engineers, scientific researchers were uses this system.
ii). Soft real time:
It can set the priority over the critical task. On the basis of its priority the will be perform. So after analyzing the condition we can set the priority to the processes. Hospital, metrological equipments are the example of this.
Unit II
Process concept
(the
was put here)
to be here)
was put here)
It is a primary mechanism for defining and managing the execution of the program under the control of an OS. Process is a dynamic concept that refers to a program in execution undergoing a frequent state and attribute changes. On the other hand an executable program is a static process that may give to one or more process. As we know a process is a unit of work in program i.e. A process is more then the program code. It also includes the current activity as represented by the value of the program counter and the contents of the processors registers. A process generally also includes the process stack, containing temporary data and a data section containing global variables.(The cursor was here, and I expected the
to be here)
1.1 Process state:
A process is a unit of work in program. During the program execution/process execution it changed the state. Those states of the process are also known as the current activity of the process. Following are the different process state and the transition diagram process:
• New
• Ready
• Waiting
• Running
• Termination
1.2 Process control block:
Process name
Process ID / state
Process counter
CPU registers
CPU scheduling
Memory mgt.
IO management
Accounting inf.
Processes
Each process is represented in an OS by a PCB which is known as a task control block. When ever a process created, an OS creates a corresponding process control block, serve as its runtime description during the life time of the process. Information stored in PCB and the block diagram of this is as follows.
• Process name and id
• Priority
• State of the process
• Memory management
• IO status
• File management
• A register save area
• Accounting information of a process.
1.3 Process scheduling
The objective of multiprogramming is to have some processes running at all times, to maximize the CPU utilization and the objective of the time sharing is to switch the CPU among processes so frequently that users can interact with each program while it is running. It means OS is responsible for selecting the right process to the CPU. To do so different CPU scheduling algorithms are used.
1.4 Scheduling queues:
After creating the process it will directly enter into the job queue, which is a part of a main memory and they are ready to execute but they are waiting for the resources. At that time such process list is known as the ready queue. Once the process is allocated to the CPU and is executing, one of the several event occur. Mainly following are those events:
• Process could create new sub process and wait for tits termination.
• Process could issue an IO request and then be placed in an IO queue.
• Process could be removed forcibly from the CPU as a result of an interruption and be put back in the ready queue.
Following are the common representation for the discussion of process scheduling is a queuing diagram.
1.5 Process synchronization:
In typical terminology, a synchronizations is the matching of timing between the components (H/W) of the computer so that all are coordinated i.e. Join together. For instance, operations performed by the o/s are generally synchronized i.e. to internal system clock.
But in case of process synchronization it is done by the CPU however CPU can execute more tan one process at a time but d time sharing system arise to synchronize between them . There are two different types of process they are
a). Independent process: The concurrent process executes in the CPU may be either independent or cooperating process. A process is independent if it can’t affect or it can’t be affected by the other process executes in the CPU clearly any process that doesn’t share any data with any other process is independent process.
b). Co-operating process: On the other hand, a process is co-operating process if it can affect or it can be affected by the other process executing in the system. Clearly any process that shares data with other process is d cooperating process. There are several reasons for providing an environment that allows process co-operations. They are:
Information sharing: Since several users may be interested in the same piece of information (for instance a shared file). We must provide an environment to allow concurrent access to these types of resources.
Computation speedup: If we want a particular task to run faster we must break it into sub task, each of which will be executing in parallel with other.
Convenience: Even an individual uses may have task to work on at a time. For instanced user may be editing, printing, compiling in parallel.
1.6 Inter-process communication:
The ability of one process to communicate with another in a multitasking environment by using piping, semaphores, shared memory, queues, mailbox, message system mechanism is known as inter process communication. Basically it is used to achieve process synchronization. As same the cooperating process we can also achieve this with in a process by dividing it into the different functions, modules, procedures etc. Following are the some terms associates with the IPC.
• Message passing system: It is a mechanism that the use of computer and the data communication equipment to convey messages from one location to another by using email, voice mail, fax etc. In this we have to know the following logical questions:
How are the links established?
Can a link be associated with more then two processes, functions, modules, procedure etc?
What is the capacity of a link?
What is the size of message?
Is there an acknowledgement signal generates?
• Naming: It is mechanisms that refers or identify a process which wants to communicate with other by using direct and indirect communication.
1. Direct communication: if processes P1 and P2 want to communicate, they must send messages to and receive messages from each other. In direct communication, the processes must explicitly name the sender and the recipient processes. In this send and receive mechanisms are defined as follows:
Send (P1, message): send a message to process P1.
Receive (P2, message): receive a message from process P2.
Receive (ID, message): receive a message from any process but it contains the process ID.
At that time each and every processes need to know the other’s identity to communicate which is responsible to generate an acknowledgement signal from the both sides.
2. Indirect communication: in this mechanism, the messages are sent to and received from the different mailboxes or ports which have a unique identity. Communication can be established by using the mailbox identity numbers which is shared by more then one processes. So the send and receive mechanisms are defined as follows:
Send (A, message): send a message to mailbox A.
Receive (A, message): receive a message from mailbox A.
At this time an operating system is responsible for the following operation on behalf of processes:
To create a new mailbox
To send and receive message through the mailbox
To delete the mailbox.
• Buffering: it is temporary locations i.e. Queue on which the message can exchange whenever the communication can be direct or indirect. Such temporary queue can be implemented in following three ways:
Zero capacity: it means there is no any message in the waiting queue.
Bounded capacity: the capacity of the queue has finite length. If the queue is full the sender must delayed until the space is available.
• Unbounded capacity: it has a queue with infinite length, so the number of messages can wait in it but the sender never wait.
1.7 The critical section problem
It is a region on which the process shares the data, updating the table, changing the common variable’s, waiting for files, waiting for I/O is known as critical sections. Each and every process has its critical region, section which has a segment of code on which such types of operations are performed. When one process is in its critical section, no other process is to be entered to its critical section. So at a time only one process can enter into the critical section.
Therefore each process has a segment of code called critical section in which the process may be changing common variables, updating tables, waiting a file etc. Typically, when one process is in its critical section, no other is to be allowed to execute in its critical section and when processes access shared data, the mutual exclusion is to be in forced. That is when an executing process leaves its critical section, and then only the other process waiting to enter its own critical section should be allowed to proceed. So each process must request permission to enter its critical section. The section of code implementing this request is the entry section. The critical section may be followed by an exit section. The remaining code is the reminder section. By analyzing this we can draw a following general structure of the critical section in a form of algorithm.
Do {
Entry section
Critical section
Exit section
Reminder section
} while (1)
A solution to the critical section problem must satisfy the following three requirements:
Mutual exclusion: if a process is executing in its critical section, then no other process can be executing in the critical section.
Progress: if no process is executing in its critical section and their exists some processes that wish to enter their critical section then only those processes that are not executing in their reminder section can participate in the critical section.
Bounded waiting: there exists a bound on the number of times that other processes are allowed to enter their critical section, after a process has made a request to enter its critical section and before that request is granted.
1.8 Classical problems of synchronization:
Mainly there are four different problems arise in the process synchronization. They are:
Producer, consumer problem
Producer, consumer with a bounded buffer problem
Producer, consumer problem with an unbounded buffer problem
Reader, writer problem
(i). Producer, consumer problem:
Even a set of cooperating process, some of which produce data items to be consumed by other process which is behaves like a consumer, with possible disparity between production and consumption rate. Processes often trend to behave as a mixture of two rather then having a pure consumer or a pure producer.
(ii). Producer, consumer with a bounded buffer problem:
The main problem in bounded buffer is that both consumer and producer may be stop in certain circumstances. A consumer may acquire only produces item and must wait when no items are available.
Producer on the other hand, may produce items only when there are empty buffer otherwise new arrival might overwrite the item produces earlier which is still waiting for the consumption. At any particular time the shared global buffer may be empty. In other case a producer may also be kept on waiting when the buffer is full.
(iii). Producer, consumer with an unbounded buffer problem:
In the first attempt to solve the producer/ consumer problem, we assure that a buffer of unbounded capacity is set a side to smooth the speed difference between producer and consumer. Obviously after the system is initialed a producer must be the first process to run in order to produce the first item. For the point of consumer process may run whenever there is more than one item in the buffer produced but yet being consumed given the unbounded buffer produce may run at any time without any restriction.
(iv). Reader, writer problem:
Reader and writer is a classical problem is concurrent process is using the shared global data is being accessed by more than one process. The processed are categories depending on the user of the resources as either read or in write mode. A reader never modifies a shared data structure. Where as a writer may both read and write into it. A number of reader may use the shared data structure concurrently because no matter how they enter leaved the process but writer on the other hand must be granted exclusive access to the data i.e. they can’t be interleaved satisfy with either read or write.
In a set of co-operating process, a producer process produces information that is consumed by a consumer process. To allow producer and consumer processes to run concurrently, we must have available a buffer of items that can be filled by the producer and emptied by the consumer. Sometimes a producer can produce one item while the consumer is consuming another item. At that situation, the producer and consumer must be synchronized, so that the consumer doesn’t try to consume an item that has not yet been produced. So the consumer must wait until an item is produced. Therefore a buffer plays a vital role over here. In the producer consumer relationship with the unbounded buffer, the consumer may have to wait for new items, but the producer can always produce new items. On the other hand, in the producer consumer relationship with the bounded buffer, the consumer must wait if the buffer is empty and the producer must wait if the buffer is full. In this, size of the buffer is fixed. Following algorithm suggest us the typical producer-consumer relationships.
1.9 Monitor:
Semaphore provides a powerful and flexible tool for enforcing mutual exclusion and for cooperation process. It is difficult to produce a correct program by using semaphore. The difficulty is that waits and signal operation may be scattered through out a program and it is not easy to see the overall affect of this operations by semaphore.
So the monitor is a programming language construct that provides equivalent functionalities as that of semaphore and that is easier to control. The monitor construct has been implemented in the number of programming language more recently they have been implemented in the program library. Following are the block diagram of the monitor.
Generally following are the some characteristics of the monitor.
The local data variables are accessible only by the monitor procedure and not by any other external procedure.
A process enters the monitor by invoking one of the procedures.
Only one process can able to execute in the monitor at a time. Any other process that has invoked the monitor is suspended while waiting for the monitor became available. Os the data variables in the monitor can be acceded by only one process at a time. Thus a shared data structure can be protected by placing each in a monitor.
1.10 Semaphore:
It is a synchronization tool used to generalize the more complex problems. It is a protected integer variable whose value can be altered and accessed only by the operations P and V after its initialization. So the initialization of the semaphore variables is known as the semaphore initialization. The variable only can alter and accessed through its two standard atomic transactions i.e. P and V. a semaphore is an integer variables apart from its initialization. It access only through two standard atomic operations i.e. “P” for wait and “V” for signal. To transmit a signal by semaphore, then the process should execute the preemptive signal.
To receive the signal by the semaphore is a process executing the preemptive wait, if the corresponding signal is not yet be transmitted the processes is suspended until the transmission take place. Generally there are two process/operations of semaphore:
“P” operation with semaphore (S):
If (S>0) then
S=S-1
Else (wait on S)
“V” operation with semaphore (S):
If (one or more process are waiting on S) then
(Let one of these processes proceed)
Else (S=S+1)
So, semaphore is implemented as the nucleus of the OS where process state switching is controlled.
Unit III
CPU scheduling
The main purpose of the multi-user/multitasking OS is, to increase the CPU utilization i.e. To reduce the idleness timing of the CPU. To do so we have to use time sharing system on behalf of CPU scheduling, that time sharing system is a type of OS as well as a type of a CPU scheduling algorithm. So the management or allocation of the CPU timing to the different processes/tasks/jobs refers a CPU scheduling which handles or executes more then one task at a time by switching the CPU between them.
1.1 CPU Schedulers:
A process of migrates the CPU from one task to another by using the various scheduling queues throughout the lifetime of the process is known as scheduler. So the scheduler selects from among the processes in memory that are ready to execute and allocates the CPU to one of them, which is the main task of the short term scheduler. Following are the different terms related to the scheduler:
• Long term scheduler: it is responsible for loading the different processes into the memory to execute.
• Short term scheduling: it is also performing such tasks but it will load the particular task to the CPU which is ready to execute.
• IO bound: it spends more CPU time to take/collects an IO request from the IO devices rather then doing the execution i.e. It spends more time to the users.
• CPU bound: it gives more time to compute the requests rather then giving more time to the users.
• Context switch: multitasking feature can be achieved only when the CPU switched to another process from the first one. At that time OS requires to save the state of the old one and load the new process to execute which is done buy the context switch.
• Preemptive scheduling: a scheduling is said to be preemptive if the job can be taken away from the CPU. To make preemptive effective more then one process must be kept in the main storage so that the next process is ready for the execution.
• Non-preemptive: a scheduling is known as non preemptive if once a process has been entered into the CPU, we can’t take away that particular process until and unless completing its whole task.
• Dispatcher: It is the module that gives control of the CPU to the process selected by the short term scheduler.
1.2 Scheduling criteria:
Different CPU scheduling algorithms have different properties and may favor one class of processes over another. In choosing which algorithm is better to use in a particular situation of the various algorithms. It means many criteria have been suggested for computing CPU scheduling algorithm. Following are the some criteria that are used to determine of the best algorithm.
• CPU utilization: we want to keep CPU as busy as possible. It varies from 0 to 100 %. In real system it varies from 40 to 90 % i.e. 90% for heavily loaded system. To achieve this we need to supply a proper device and so on.
• Turn around time: the interval from the time of submission of a process to the time of completion is the turn around time. It is a sum of the periods spends waiting to get into the CPU and waiting in the ready queue for executing and doing IO.
• Throughput: it is the one measure of work is the number of processes that are completed per time unit.
• Waiting time: the CPU scheduling algorithm doesn’t affect the amount of time during which a process execute nor does IO, it affects only the amount of time that a process spends waiting in a ready queue. So it is the sum of the periods spent waiting in the ready queue.
• Response time: in an i9nteractive system, it is not a best creation. It is another measure is the time from submission of a request until the first response is produce. This measure called response time i.e. the amount of time it takes to start responding nut not the time that is takes to output that response.
1.3 CPU scheduling algorithms:
CPU scheduling deals with the problem of deciding of the processes in the ready queue which one to be allocated the CPU. There are many more scheduling algorithms to do so. Following are the some important algorithm with its short descriptions:
• First come first served scheduling: The process that requests the CPU first allocated the CPU is known as FCFS. It is non preemptive types of scheduling manage by the FIFO queue. When a process enters the ready queue, its PCB is linked onto the tail of the queue and then when the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue. Following are the simple example of this scheduling:
Process B_time
P1 24 MS
P2 12 MS
P3 4 MS
Soln: On the basis of FCFS method we can create the following Gantt chart:
WT for P1=0
WT for P2=24
WT for P3=36
So, AWT=WT for (P1+P2+P3)/3=
60/3=20 MS
TAT for P1=24
TAT for P2=36
TAT for P3=40
So, ATAT=TAT for (P1+P2+P3)/3= 100/3=33.33 MS
• Shortest job first scheduling: it is a preemptive scheduling in which the waiting process with the smallest estimated burst time (to complete) is run next. It reduces the average waiting time over FCFS. Following are the simple example of this scheduling:
Process B_time
P1 24 MS
P2 12 MS
P3 4 MS
Soln: On the basis of SJF method we can create the following Gantt chart:
WT for P1=16
WT for P2=4
WT for P3=0
So, AWT=WT for (P1+P2+P3)/3=
20/3=6.66 MS
TAT for P1=40
TAT for P2=16
TAT for P3=4
So, ATAT=TAT for (P1+P2+P3)/3=
60/3=20 MS
• Priority scheduling: it can be either preemptive or non preemptive. A priority is associated with each process, and the CPU is allocated to the process with the highest priority, while the priority equals, the processes are scheduled in FCFS basis. Zero is the highest priority. Following are the simple example of this scheduling:
Pr_ss Priority B_time
P1 0 24 MS
P2 1 12 MS
P3 2 4 MS
Soln: On the basis of PS method we can create the following Gantt chart:
WT for P1=0
WT for P2=24
WT for P3=36
So, AWT=WT for (P1+P2+P3)/3=60/3= 20ms
TAT for P1=24
TAT for P2=36
TAT for P3=40
So, ATAT=TAT for (P1+P2+P3)/3= 100/3=33.33 MS
• Round Robin scheduling: it is specially designed for the time sharing systems. It is similar to the FCFS scheduling but preemption is needed to switch between processes. A smallest unit of time called slice/quantum is used to switch the CPU from one task to another. So a cycle can be form to complete the task with in different attempts. Following are the simple example of this scheduling:
Process B_time
P1 24 MS
P2 12 MS
P3 4 MS
Soln,
On the basis of RR method we can create the following Gantt chart, with 5 MS of time slice:
WT for P1=0+14+24+31=69
WT for P2=5+19+29=53
WT for P3=10
TAT for P1=40
TAT for P2=31
TAT for P3=14
So, AWT= WT for (P1+P2+P3)/3= 32/3=44 MS So, ATAT= TAT for (P1+P2+P3)/3= 85/3=28.33
• Multilevel queue scheduling: it allows different algorithms to be used for various classes of processes. The most common is the foreground/interactive queue which uses a RR scheduling and the background batch queue which uses FCFS scheduling but foreground have a highest priority. So each queue has its own scheduling mechanism. In addition, there must be a scheduling between the queues which is commonly implemented as a fixed priority preemptive scheduling. Following are the block diagram of this:
• Multilevel feedback queue scheduling: in multilevel queue scheduling, processes do not move between the queues but in the multilevel feedback queue scheduling, however, allows a process to move between the queues. 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 may be moved to a higher-priority queue. In this fashion the processes executes from the different queues by using the different scheduling algorithms.
Unit IV
Deadlocks
In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources, if the resources are not available at that time; the process enters a wait state. It may happen that waiting process will never again change its state because the resources they have requested are held by other waiting process. This situation is known as deadlock.
1.1 Deadlock characterization:
Deadlock is a situation on which CPU can not respond to the processes. In this situation the utilization of the CPU can be either 0% or 100%. So a deadlock situation can arise if the following four conditions hold simultaneously in a system i.e. if an operating system could not manage/maintain one of the following conditions the system automatically enter into the deadlock situation which is the deadlock characteristics or necessary conditions for the deadlocks.
Mutual exclusion:
At least one resource must be held in a non-sharable mode; i.e. only one process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released. So, other processes have to wait in a ready queue/waiting queue until and unless the previous process will not complete its full execution.
Hold and wait:
A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other process. So, to send the request for the extra resources for executing a particular process, it must collect the minimum resources first.
Circular wait:
There are a set of processes wants to use the resources that is held by the other process i.e. P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, P2 is waiting for a resource that is held by P3 and so on. It means Pn is the process that is requested the resource and that resource is held by any other process.
No preemption:
Resources cannot be preempted i.e. a resource can be released only voluntarily by the process holding it, after that process has completed its task. So without completing its full execution we can not preempted the resources from there.
1.2 Methods for handling deadlocks:
Principally there are three different methods for handling deadlocks. They are:
A protocol is used to prevent or avoid deadlocks, which ensures the system never enter into the deadlock state.
Once the system enters into the deadlocks state, we should detect it and recover the data and system from the deadlock successfully.
Uses such types of an operating system which never entered into a deadlock such as Linux, UNIX etc. So ignore the problem altogether and pretend that deadlocks never occur in the system.
To ensure that the deadlocks never occur in a system, we have to use either a deadlock prevention or deadlock avoidance scheme.
On the other hand, if a system doesn’t ensure that a deadlock will never occur we need to provide an algorithm that examines the state of the system to determine whether a deadlock has occur and an algorithm to recover form the deadlock. Therefore we need to use deadlock detection and deadlock recovery scheme.
(a). Deadlock prevention:
Deadlock prevention is a set of methods for ensuring that at least one of the necessary conditions can not hold. By ensuring that at least one of these conditions cannot hold, we can prevent the occurrence of a deadlock. These methods prevent deadlocks by constraining how requests for resources can be made i.e. how the resources will be allocated to the particular process for execution. So following are the three different ways to prevent our system entered into a deadlock condition.
Each and every process must request all its necessary resources at once and not proceed the execution with out getting/collecting full resources.
If any process holds a certain resources, they can’t request another one without realizing it. After releasing that one they have to send the request at a time/combinely.
If there are multiple instance of the resource on a system, only one can use the single process i.e. that process can’t send the request to that another instances of the same resources.
But we have to analyze following four different necessary condition of the deadlock in-terms of deadlock prevention. That ensure the system never occur a deadlock.
Mutual exclusion:
In the system if we have sharable resources there are a no chances to occur deadlock because a process never needs to wait for the shareable resource. But in case of non sharable resources we need to use this concepts i.e. at least one process can use this resource at a time and others must be wait in a job pool. Read only files are the good example of the sharable resource and the printer is the example of the non sharable resource.
Hold and wait:
According to this concept, whenever a process requests a resource, it doesn’t hold any other resources. It means a process allows sending a request for the process only when the process has none i.e. it must release all the resources that is currently allocated before it can request any additional resources. We need to face the following disadvantages to use such types of protocol. They are:
(a). Resource utilization: The utilization of the resource may be reduce/low, since many of the resources may be allocated but unused for a long period.
(b). Starvation: A process that needs generally usable resources may have to wait indefinitely because at least one of the resources that it needs is always allocated to some other process.
No preemption:
No preemption condition is that there is no preemption of resources that have already been allocated. In this, if a process requests some resources, firstly we need to check whether they are available or not. If they are available, allocate them but if they are not available, we need to check whether they are allocated to some other process that is waiting for the additional resources or not. If so, we preempt the desired resources from the waiting process and allocate them to the requesting process. But if the resources are not either available of held by a waiting process, the requesting process must wait in a ready queue/job pool. During this waiting period, some of its resources may be preempted if other process requests them.
Circular wait:
According to this concept a process holds at least one resources being requested by the next process and so on. So we need to break the circular chain of the processes as well as the resources to prevent from the deadlock.
(b). Deadlock avoidance:
By applying different preventive measure, we can prevent the deadlock from our system but there is a chance for low device utilization and reduce system throughput. For this purpose deadlock avoidance is an alternative mechanism. According to this concepts system must be provides additional information about how resources are to be requested. It is the simplest and most useful model. It requires that each process declare the maximum number of resources of each type that it may need. It means operating system provides advance additional information about the process and the resources i.e. which resources are needed for completing the particular task.
So, for displaying proper information of each process about the maximum number of resources of each type that may be requested. It is possible to construct an algorithm that ensures the system will never enter a deadlock state which defines the deadlock avoidance approach i.e. algorithm.
A deadlock avoidance algorithm dynamically examines the resource allocation state to ensure that they can never be a circular wait condition. The resource allocation state is defined by the number of available and allocated resources and the maximum demands of the processes. For this purpose we need to examine the state of the process. Following are the process state:
(a). Safe state: A state is safe if the system can allocate resources to each process. So a safe state is not a deadlock state.
(b). Unsafe state: Whenever a system can not provide the necessary resources the process that processes falls in an unsafe state. So a deadlock state is an unsafe state but not all unsafe states are deadlock i.e. unsafe state may lead to a deadlock. In this the operating system can’t prevent processes from requesting resources such that a deadlock occurs.
(c). Deadlock detection:
After applying different deadlock prevention and avoidance mechanism if we can not ensure that our system will not entered into a deadlock situation we need to implement deadlock detection and the recovery scheme/algorithm. Indeed the deadlocks occur into the system that we need to find out where is the deadlock and under which circumstances the deadlock arises into the system. So, we can not separate the deadlock detection and the recovery system. In this situation we need to implement the following scheme to detect and recover the system from the deadlock.
Apply the deadlock detecting algorithm to determine the state and the condition for the deadlock and find out where is the deadlock occur.
Apply an algorithm to recover our system from the deadlock.
So, deadlock detection algorithms have to use under the following situation.
If all resources have a single instance, we need to define an algorithm that uses a variant of the resource allocation graph.
If a resource has several instances, then an algorithm describes the next applicable processes.
(d). Recovery from deadlock:
Indeed the deadlock occurs into a system we need to implement deadlock detection algorithm to find out the deadlock and so on. But our main motive is to recover the system from the deadlock. We can use different scheme to do so. By applying manual as well as automatic techniques we can recover our data successfully. To do automatically we need to implement some precaution during the installation of an operating system, then only we can recover more then 80% of our information after recovery from the deadlock otherwise we can't achieve such amount of our data. This is done manually only.
Following are the two different manual ways to recover our system from the deadlock.
(a). Process termination:
According to this concept, we need to terminate abnormally (aborted) the processes which are responsible for entering our system into a deadlock. So we use one of the following methods to eliminate deadlocks by aborting a process but aborting a process may not easy because it is not a right solution i.e. economic one.
(i). Abort all deadlocked processes until and unless the deadlock cycle is not break but at a great expanse because such processes takes a long time to compute and so on.
(ii). Abort one process at a time until the deadlock cycle is not eliminated.
(b). Resource preemption:
To eliminate deadlocks using resource preemption methods, we need to preempt some resources from the processes and allocate such resources to other processes until the deadlock cycle is not broken. Following three issues are needed to be address to recover our system from the deadlock by using this resource preempted method.
(i). Selecting a victim:
To achieve cost effectiveness and more data, we need to select which resources and which processes are to be preempted? So we must check the permission about the processes as well as resources preemption.
(ii). Rollback:
After preempted the resources from the processes it can't continue its execution and it became an unsafe state. At that time we need to restart the process execution.
(iii). Starvation:
According to this concept we need to ensure and preempt the resources only when the processes will not demand such resources later.
Unit V
Memory management
In uni-programming environment system is divided into two parts: one for operating systems and another for the programs currently being executed. On the other hand, in multiprogramming system, users parts of the memory are further being subdivided to accommodate process i.e. Multi-processes. This is done by the operating system dynamically which is known as storage / memory management.
To improve of its response to its users, the computer must keep several processes in memory. Selection of a memory management scheme for a specific system depends on many factors, especially on the hardware configurations of the system.
As we know, memory is a large array of words or bites, each with its own address. The CPU fetches instructions from memory according to the value of the program counter. These instructions may cause additional loading from and storing to specific memory address.
1.1 Logical Vs physical address space:
An address generated by the CPU is commonly referred to a logical address, whereas an address seen by the memory unit is commonly referred to a physical address. It means that the user never sees the real physical addresses. The compile time and load time address binding schemes result in an environment where the logical and physical addresses are the same. However the execution time address-binding scheme results in an environment where the logical and physical address differs.
The set of all logical address generated by a program is referred to as a logical address space; the set of all physical addresses corresponding to these logical addresses is referred to as a physical address space. Thus in execution time, address binding scheme logical and physical address spaces differ. The runtime mapping from virtual to physical addresses is done by the memory-management unit (MMU), which is a hardware device. The memory mapping hardware converts logical addresses into physical address and vice versa.
1.2 Swapping:
A process needs to be in the memory to be executed. A process however can be swapped temporarily out of memory to a backing store and then brought back into the memory for continued execution. A variant of this swapping policy is used for priority based scheduling algorithms. If a high priority process arrives and wants service, the memory manager can swap out the lower priority process so that it can load and execute the higher priority process. When the higher priority process finishes, the lower priority process can be swapped back in and continued this variant of swapping is known as roll-out, roll-in.
Normally, a process that will swap out will be swapped back into the same location. Swapping requires a backing store. The backing store is commonly a fast risk. It must be large enough to accommodate copies of all memory images for all users and must provide direct access to the memory images. The system maintains a ready queue consisting of all process whose memory images are on the backing store or in memory and are ready to run.
1.3 Contiguous allocation
In this each program has to occupy a single contiguous block of storage location. In non-contiguous storage allocation a program is divided into several blocks or segments that they may be placed through out main memory in pieces. Not necessarily adjacent to one another. It is more difficult to control non-contiguous storage allocation. The benefit is that if main storage has many small holes available instead of single large hole, then the operating system can often load and execute a program otherwise need to wait.
As we know programs are limited size to the amount of main storage but it is possible to run program larger then the main storage using the concept of overlays. If a particular program section is not needed for the duration of program execution when another section of the program may be brought in from the secondary storage to occupy the storage used by the program that is no longer needed. Overlays give the programmer to extend limited main storage but manual overlays structure can be difficult to modify.
1.4 Paging:
The problem of external fragmentation has two solutions. The first one is compaction, which changes the allocation of memory to make free space contiguous and hence useful to users programs. Another one is paging, which permit a program’s memory to be non contiguous, this allowing a program to be allocated to physical memory wherever it is available. Physical memory is broken into fixed sized blocks called frames.
Logical memory is broken into blocks of the same size called pages. In this every address is divided into two pates i.e. Page number and page offset, where, the page number is used as a index into a page table and page offset is a displacement with a page at which the reference address is loaded. It means every address generated by the CPU is divided into two parts. They are:
# Page number (P)
# Page offset (D)
In this, the page table contains the base address of each page in physical memory. This base address combined with the page offset to define the physical memory address. In figure “f” is denoted to the base address.
A special memory management unit (MMU) performs the address translation i.e. from virtual (logical) to physical.
1.5 Segmentation:
An alternative way, in which, the user program and its associated data are divided into a number of segment. In this case the program number and an offset. It is not required that all segment of all programs being of the same length. As with paging a logical address using segmentation consists of two parts:
-Segment number
-Segment offset.
Because of the use of unequal size to dynamic partition, the difference compare with dynamic partition is that with segmentation. A program may occupy more then one partition and those partitions need not be contagious. Segmentation eliminates internal fragmentation. But like dynamic fragmentation, however because a process is broken up into a number of small pieces the external should be less. Paging is that invisible to the program which as segmentation operating system usually visible to the programmer.
1.5.1 Characteristics of the segmentation:
Following are the some characteristic of the segmentation.
1. Main memory is not being partition.
2. Program segments specified by the programmer to the compiler i.e. the decision is made by the programmer.
3. External fragmentation is present in the segmentation.
4. Operating system must maintain a segment for each process by showing the limit and base.
5. Operating system must maintain a list of free holes or partition in the main memory.
6. All the segment of a process must be in main memory for the process to run unless overlays are used.
1.5.2 Combined approach of segmentation and paging:
Both segmentation and paging scheme is combined to improve their efficiency. In a combined system, a user’s address space is broken up into a number of segments at the discretion of the programmer. Each segment is in turn broken up into a number of fixed size pages, which are equal in length to a main memory frame. If a segment is less than a one page from the systems point of view, the segment offset is viewed as a page number and page offset for a page within the specified segments.
It suggests a structure support to combination of paging and segmentation. Associated with each process in a segment table and a number of page table one per process segment. When a particular process is running a register holds the starting address of hr segment table for hat process. Presented with a virtual address the processor uses the segment number portion to index into the process segment table to fid the page table for the virtual address is used to index the page table and lookup the corresponding frame number. This combined with the offset portion of the virtual address to produce the desired real address.
Unit VI
Virtual Memory:
The key to the virtual storage concept is disassociating the address referenced in a running process from the addresses available in primary storage. The addresses referenced by a running process are called virtual address. The addresses available in primary storage are called real address. Even through processes reference only virtual addresses they must be mapped into real addresses or – process executes.
Dynamic address translation (DAI) mechanisms convert virtual addresses to real address as a process executes. The system exhibits the property that the address contiguous in a processes virtual address space need not be contiguous in real storage. This is called artificial contiguity.
1.1 Demand Paging:
It is the convention wisdom that a process pages should be loaded on demand. No page should be brought from secondary to primary storage until a running process explicitly references it. There are several reasons for the appeal of this strategy. They are:
i) Computability results:
Specifically the haul ting problem, it tells us that the path of execution a program will take can’t be accurately predicted. Therefore any attempt to preload pages in anticipation of their use might result, the wrong page being loaded.
ii) Demand paging:
It guarantees that the only pages brought to main storage are those actually needed by the processes.
iii) Pure demand paging:
There is a possibility that the management scheme could execute with no page fault i.e. It never bring a page into memory until it is required. This is known as pure demand paging.
1.1.1 Performance of Demand paging:
Demand paging can have a significant effect on the performance of a computer system. If there are no page faults the effective access time will be equal to the normal memory access time. For most computer system now ranges from 10 to 200 mono sec. If a page fault occurs, the time faults as address to effective access time is then effective access time = (1-P) x ma + p x page fault time. Where, Ma = memory address, P is probability of a page fault (O≤ P ≤ 1), we would accept P to be close to zero i.e. with few page fault. There are three major components of the page fault services time.
i) Time taken to swap in the page
ii) Time taken to service the page fault interrupt.
iii) Time taken to restart the process.
1.2 Page replacement:
Every operating system has its own unique replacement scheme. Any page replacement algorithm should aim to attaining lowest page fault rate. Assumption: running it on a particular string of memory response and computing the number of page fault evaluate every algorithm. Random number can generate reference string artificially by the address of each memory reference.
1.2.1 Page replacement algorithm
There are many different page replacement algorithms. Probably every operating system has its own unique replacement scheme. We have to select those algorithm schemes which one can perform this job with the lowest page fault rate. We evaluate an algorithm by running it on a particular string of memory references and computing the number of page faults. The string of memory references in known as reference string. Mainly they are three different types’ replacement algorithms. They are
i) FIFO algorithm:
It is a simplest algorithm associates with each page the time when that page was brought into memory. When a page must be replaced, the oldest page is chosen. FIFO queue is creating to holds all pages in memory. The page is replaced at the head of the queue. When a page is brought into memory, we insert it at the tail of the queue. To illustrate the page replacement algorithms we shall use the following reference string for memory with three frames.
Reference string: 70120304230321201701Page fault: 3 frames
Sol.
70120304230321201701
ii) Optimal algorithm:
An optimal page replacement algorithm has the lowest page fault rate of all algorithms. An optimal page replacement algorithm exists and has been called OPT or MIN. So we can simply say that replace the page that will not be used for the longest period of time. Consider the following reference string i.e. for a memory with 3 frames.
Reference string: 70120304230321201701Page fault: 3 frames
Sol.
70120304230321201701
iii) LRU algorithm:
If we use recent past as an approximation of the near future, then we will replace the page that has not been used for the longest period of time. This approach is the least recently used algorithm. LRU replacement associates with each page the time of the page’s last use. When a page must be replaced LRU chooses that page that has not been used for the longest period of time. Consider the following reference string with respect to a memory with three frames.
Reference string: 70120304230321201701Page fault: 3 frames
Sol.
70120304230321201701
1.3 Frame allocations
A different problem arises when demand paging is combined with multiprogramming. Multiprogramming puts two or more processes in memory at the same time. The problem is to allocate the fixed a mount of free memory among various process. We can’t allocate more then total number of available frames. There must also be a minimum number of frames, which can be allocated for every process. Now we decide that the minimum number of frames per user process should define by the architecture while the maximum number is defined by the amount of available physical memory.
Other important factors in the way that frames are allocated to the various processes in page replacement. With multiply processes computing for frames, we can classify page replacement algorithms into two different categories. They are global replacement and local replacement.
# Global replacement allows a process a select a replacement frame from the set of all frames even if that frame is currently allocated to some other processes; one process can take a frame from another.
# Local replacement requires that each process select from only its own set of allocated frames.
1.4 Thrashing:
Any process, which doesn’t have enough frames, will quickly lead to page fault. If there is maximum number of page fault, it will decrease the CPU performances, because CPU wills not doing the process execution i.e. CPU is busy for page replacement and demand paging rather then the compilation. At this point, it must replace some page however, since all into pages are in active use, it must replace a page that will be needed again right away. Due to this a page fault arises again, again and again. This very high paging activity is known as thrashing i.e. When CPU utilization is decrease; we have to face the problem of thrashing. Following are the block diagram of thrashing.
A process is threshing if it is spending more time paging then executing. So thrashing leads to poor performance of the system. The CPU scheduler seep the decreasing CPU utilization & increases the degree of multiprogramming as a request. Her new process tries to get started by taking pages from running processes, causing more page faults & a longer queue for the paging device. As a result, CPU utilization drop even further, & the CPU scheduler try to increase the degree of multiprogramming even more. That is, the page fault rate increased & thrashing occur serially. No work is getting done, because the processes are spending their max time in replacing the page rather than the proper executing. Following are the solution of this:
1) Locating model of program execution.
2) Working set model of program execution.
3) Page fault frequency strategies.
1.5. Other consideration:
The selection of a replacement algorithm &allocation policy is the major decisions to make for a paging system. There is much other consideration as well. Same of them are:
1). Pre paging
2). Page size
1.6 Demand segmentation:
As we know, there are limited no of resources in the systems. Although demand paging is generally considered the most efficient virtual memory system a significant amount of hardware is required to implement it. When this hardware is lacking less efficient means are sometimes devised to provide virtual memory. A space in point is demand segmentation.
![Microsoft Highlights Start Button in New Windows 8.1 Ad [Video]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uKkUCitmQKBA_g5CKWDOt5DGSA8-Xi52DQZQ_kxwWGPVZycQwrcg_NczyWlr6KEJcfPzhKIV__7_m-sbq3tqeJ5GSKssELWRsmSr4dsA=w100)
1 Comments
thanx........ very good notes
ReplyDeletesir you people are very great to share with us that type notes
amanullah from karak kpk pakistan
khattakamanullah70@gmail.com