Deadlocks in Operating System: Necessary Conditions for Deadlock

 

Deadlocks:

 

In a multiprogramming environment several processes may compete for finite number of resources.

 

A process request resources, if the resources are not available at that time then process enters a wait state.

 

Waiting processes may never again change state because the resources that they have requested are held by other waiting processes. This situation is called a deadlock.

 

System Model:

 

A system consists of finite number of resources to be distributed among a number of competing processes. 

 

The resources are partitioned into several types each of which consists of some number of identical instances. Memory space, CPU cycles, files and I/O devices are examples of resource types.

 

Under the normal mode of operation a process may utilise resource in only the following sequence:

 

1.    Request: If request cannot be granted immediately, for example resource is being used by another process then the requesting process must wait until it can acquire the resource.

2.    Use: The process can operate on the resource for example if the resource is a printer the process can print on the printer.

3.    Release: The process releases the resource.

 

The request and release of resources are system calls. A system table records whether each resource is free or allocated and if resource is allocated to which process. If a process request resource that is currently allocated to another process it can be added to queue of processes waiting for this resource.

 

A set of processes is in a deadlock state when every process in the set is waiting for an event that can be caused only by another process in the set. The resources may be either physical resource (example printers, tape drives, memory space and CPU cycles) or logical resources (example files, semaphore and monitors).

 

 

 

Deadlock Characterization:

 

In a deadlock, processes never finish executing and system resources are tied up preventing other jobs from starting.

 

Necessary Conditions for Deadlock:

 

A deadlock situation can arise if the following four conditions hold simultaneously in a system:

 

1.    Mutual exclusion: At least one resource must be held in a non-shareable mode that is only one process at a time can use the resource. If another process request that resource the requesting process must be delayed until the resource has been released.

2.    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 processes.

3.    No pre-emption: Resources cannot be pre-empted i.e. a resource can be released only voluntarily by the process holding it after that process has completed its task.

4.    Circular wait: A set {P₀, P₁, P₂,..., P_n} of waiting processes must exist such that P₀ is a waiting for a resource that is held by P₁, P₁ is waiting for a resource that is held by P₂, …, P_{n -1} is a waiting for a resource that is held by P_n  and P_n  is waiting for a resource that is held by P₀.

Differences between Source Program and Object Program (Source Program vs. Object Program)

 

Source Program vs. Object Program:

Source Program	Object Program
A human readable program written by a programmer.	A machine executable program created after compiling a source program.
The programmer writes the source program.	A compiler generates an object program using one or more source files as an input.
Source program is human readable.	Object program is machine readable.
It is written in higher level languages.	It is usually written in lower level languages.

Differences between Compiler and Interpreter (Compiler vs. Interpreter)

 Compiler vs. Interpreter :

Compiler	Interpreter
Compiler works on the complete program at once. It takes the entire program as input.	Interpreter works line-by-line. It takes one statement at a time as input.
Compiler generates intermediate code, called the object code or machine code.	Interpreter does not generate Intermediate object code or machine code.
Compiler executes conditional control statements (like if-else and switch-case) and logical constructs faster than interpreter.	Interpreter executes conditional control statements at a much slower speed.
Compiled programs take more memory because the entire object code has to reside in memory.	Interpreter does not generate intermediate object code. As a result, interpreted programs are more memory efficient.
Compile once and run anytime. Compiled program does not need to be compiled every time.	Interpreted programs are interpreted line-by-line every time they are run.
Errors are reported after the entire program is checked for syntactical and other errors.	Error is reported as soon as the first error is encountered. Rest of the program will not be checked until the existing error is removed.
A compiled language is more difficult to debug.	Debugging is easy because an interpreter stops and reports error as it encounters them.
Compiler does not allow a program to run until it is completely error-free.	Interpreter runs the program from first line and stops execution only if it encounters an error.
Compiled languages are more efficient but difficult to debug.	Interpreted languages are less efficient but easier to debug. This makes such languages an ideal choice for new students.
Examples of programming languages that use compilers: C, C++, COBOL	Examples of programming languages that use interpreters: BASIC, Visual Basic, Python, Ruby, PHP, Perl, MATLAB, Lisp

3 Types of Translator Programs: Assembler - Compiler and Interpreter

 

Assembler:

o   A computer can directly execute only machine language programs that use numbers for representing instructions and storage locations.

o   Hence an assembly language program must be converted or translated into its equivalent machine language program before it can be executed on the computer.

o   This translation is done with the help of a translator program called assembler.

o   Assembler is system software supplied by computer manufacturers.

o   It translates an assembly language program into its equivalent machine language program.

o   It is so called because in addition to translating it also assembles the machine language program in main memory of the computer and makes it ready for execution.

o   As the figure shows the input to the assembler is assembly language program often referred as a source program and its output is the machine language program often referred as object program.

o   The assembler translates each assembly language instruction into an equivalent machine language instruction. There is a one to one correspondence between the assembly language instructions of a source program and the machine language instructions of its equivalent object program.

o   During the process of translation of a source program into its equivalent object program by the assembler the source program is not under execution. It is only converted into a form that can be executed by the computer.

Compiler:

o   A computer can execute only machine language programs directly.

o   Hence a high level language program must be converted on translated into its equivalent machine language program before it can be executed on a computer.

o   This translation is done with the help of a translator program called compiler.

o   Hence a compiler is a translator program that translates a high-level language program into its equivalent machine language program.

o   As the figure shows input to the compiler is the high level language program often referred as a source program and its output is the machine language program referred as object program.

 

o   Since high level language instructions are micro instructions, the compiler translates each high level language instruction into a set of machine language instructions rather than a single machine language instruction.

o   Hence there is a one-to-many correspondence between high level language instructions of a source program and machine language instructions of its equivalent object program.

o   A compiler can translate only those source programs that have been returned in the language for which the compiler is meant.

o   Compilers are large programs residing permanently on secondary storage.

o   To translate a source program, the compiler and the source program are loaded first from secondary storage into main memory of the computer.

 

o   The compiler being a program is then executed with the source program as its input data.

o   It generates the equivalent object program as its output is saved in a file on secondary storage.

o   To execute the program the object program is loaded from secondary storage into main memory and executed.

o   In addition to translate in high level language instructions into machine language instructions, compilers also detect and indicate certain type of errors in source programs automatically. These errors are referred as syntax errors and are of following types:

1.     Illegal characters

2.     Illegal combination of characters

3.     Improper sequencing of instructions

4.     Use of undefined variable names

o   A compiler however cannot detect logic errors. It can detect grammatical or syntax errors only in the source program.

Interpreter:

o   Interpreter is another type of translator used to translate high level language program into its equivalent machine language program.

o   It takes one statement of the high level language program, translate it into machine language instructions and then execute the resulting machine language instructions immediately.

o   This is different from a compiler that really translates the entire source program into an object program and its not involved in its execution.

o   The input to an interpreter is a source program button like a compiler its output is the result of program execution instead of an object program.

o   After compilation of a source program, the result in object program is a saved permanently for future use and is used every time the program is to be executed. Hence repeated compilation is not necessary for repeated execution of a program. However in case of an interpreter since no object program is saved for future use repeated interpretation of a program is necessary for its repeated execution.

o   As compared to compilers, interpreters are easier to write because they are less complex programs than compilers. They also require less memory space for execution than compiler require.

o   The main advantage of interpreter over compiler is that syntax error in a program statement is detected and brought to the attention of the programmer as soon as the program statement is interpreted. This allows the programmer to make corrections during interactive program development. Therefore and operators make it easier and faster to correct programs.

o   The main disadvantage of interpreters over compilers is that they are slower than compiler when running a finished program.  This is because each statement is translated every time it is executed from the source program.  In case of compiler, each statement is translated only once and saved in the object program. The saved object program can be executed many times whenever needed and no translation of any statement is required during the execution of the program. As the interpreter does not produce an object program it must perform the translation process each time a program is executed.

o   Assemblers, compilers and interpreters are also referred as a language processors since they are used for processing language instructions. 

 

Instruction Formats (Zero, One, Two and Three Address Instruction):

• Computer perform task on the basis of instruction provided. An instruction in computer comprises of groups called fields.
• These fields contain different information as for computers everything is in 0 and 1.
• So, each field has different significance on the basis of which a CPU decides what to perform.
• The most common fields are:

1. Operation field: This specifies the operation to be performed like addition.
2. Address field: contain the location of operand, i.e., register or memory location.
3. Mode field: This specifies how operand is to be founded.

• An instruction is of various lengths depending upon the number of addresses it contains.
• On the basis of number of address instruction are classified as:

Zero Address Instructions:

• A stack based computer do not use address field in instruction. To evaluate an expression first it is converted to revere Polish Notation i.e. Post fix Notation.

One Address Instructions:

• This is used as an implied ACCUMULATOR register for data manipulation.
• One operand is in accumulator and other is in register or memory location.
• Implied means that the CPU already knows that one operand is in accumulator so there is no need to specify it.

 

opcode

operand/address of operand

mode

 

Two Address Instructions:

• This is common in commercial computers. Here two addresses can be specified in the instruction.
• Unlike earlier in one address instruction the result was stored in accumulator here result can be stored at different location rather than just accumulator, but require more number of bit to represent address.

 

opcode

Destination address

Source address

mode

 

Three Address Instructions:

• This has three address fields to specify a register or a memory location.
• Program created are much short in size but number of bits per instruction increase.
• These instructions make creation of program much easier but it does not mean that program will run much faster because now instruction only contain more information but each micro operation (changing content of register, loading address in address bus etc.) will be performed in one cycle only.

 

opcode

Destination address

Source address

Source address

mode

 

Computer Buses: Address Bus, Data Bus and Control Bus

Computer Buses:

According to computer architecture, a bus is defined as a system that transfers data between hardware components of a computer or between two separate computers.

System bus is a single bus that helps all major components of a computer to communicate with each other. It is made up of an address bus, data bus and a control bus. 

The data bus carries the data to be stored, while address bus carries the location to where it should be stored.

1.   Address Bus:

·         Address bus is a part of the computer system bus that is dedicated for specifying a physical address.

·         When the computer processor needs to read or write from or to the memory, it uses the address bus to specify the physical address of the individual memory block it needs to access (the actual data is sent along the data bus).

·         More correctly, when the processor wants to write some data to the memory, it will assert the write signal, set the write address on the address bus and put the data on to the data bus.

·         Similarly, when the processor wants to read some data residing in the memory, it will assert the read signal and set the read address on the address bus. After receiving this signal, the memory controller will get the data from the specific memory block (after checking the address bus to get the read address) and then it will place the data of the memory block on to the data bus.

·         The size of the memory that can be addressed by the system determines the width of the address bus and vice versa. For example, if the width of the address bus is 32 bits, the system can address 2^32 memory blocks (that is equal to 4GB memory space, given that one block holds 1 byte of data).

2.   Data Bus:

·         A data bus simply carries data. Typically, the same data bus is used for both read/write operations.

·         When it is a write operation, the processor will put the data (to be written) on to the data bus.

·         When it is the read operation, the memory controller will get the data from the specific memory block and put it in to the data bus.

·         The data bus consists of 8, 16, or 32 parallel lines.

·         The data bus is bidirectional bus, means the data can be transferred from CPU to main memory and vice versa.

·         The number of data lines used in the data bus is equal to the size of data word being written or read.

·         The data bus also connects the I/O ports and CPU. So, the CPU can write data to or read it from the memory or I/O ports.

 

3.   Control Bus:

 

·         A control bus is part of the system bus, used by CPUs for communicating with other devices within the computer.

·         The control bus carries commands from the CPU and returns status signals from the devices.

·         For example, if the data is being read or written to the device the appropriate line (read or write) will be active (logic one).

·         The number and type of lines in a control bus varies but there are basic lines common to all microprocessors, such as:

1. Read {\displaystyle {\overline {RD}}}(RD): A single line that when active (logic zero) indicates the device is being read by the CPU.
2. Write {\displaystyle {\overline {WR}}}(WR): A single line that when active (logic zero) indicates the device is being written by the CPU.
3. Byte enable (E): A group of lines that indicate the size of the data (8, 16, 32, 64 bytes).

·         The RD and WR signals of the control bus control the reading or writing of RAM, avoiding bus contention on the data bus. 

Differences between Address Bus and Data Bus:

Sr. No.	Address Bus	Data Bus
1	It is a computer bus which is used to specify physical address in memory.	This bus is used to transmit data among components.
2	It is unidirectional.	It is bidirectional.
3	Address bus helps to transfer memory addresses of data and IO.	Data bus helps to send and receive data.
4	The width determines amount of memory system can address.	The width determines data transfer rates.