Info-Grade

 The thread is a lightweight process that means one single program can be divided into small threads which will execute concurrently for fast execution of task. We can say that thread is a sub process of a process.

A thread is an independent path of execution within a program. Many thread can run concurrently within a program. Every threads in Java is created and controlled by the java.lang thread class. A java program can have many threads, and these threads can run currently, either synchronously or asynchronously.

 - Threads are lightweight compared to process.

Difference between thread and process

Process	Thread
- A Process is an instance of a program. It contains a threads.	- Threads are the parts of process. It cannot contain a process.
- Process run in its separate.	- Thread run in shared memory spaces.
- Process is controlled by the operating system.	- Threads a re controlled by programmer in a program.
- Processes are independent.	- Threads are dependent.
- New processes require duplication of the parent process.	- New threads are easily created.
- Process require more time for context switching as they are more heavy.	- Threads require less time for context switching as they are lighter then process.
- Process require more resources then threads.	- Threads generally need less resources than process.
- Process require more time for termination.	- Threads require less time for termination.

 Life cycle of threads

 

New
The thread is in new state if you create an instance of thread class but before the invocation of start() method.

Runnable
A thread in the runnable state is executing the Java virtual machine but it may be waiting for other resources from the operating system such as processor.

Running
The thread is in running state if the thread scheduler has selected it.

Blocked (Non Runnable)
It is the state when the thread is still alive, but is currently not eligible to run.

Terminated
A thread is in terminated or dead state when its run() method exists.

• One way to avoid race conditions is not to allow two processes to be in their critical sections at the same time. 
• Critical section is the part of the process that accesses a shared variable. 
• That is, we need a mechanism of mutual exclusion. Mutual exclusion is the way of ensuring that one process, while using the shared variable, does not allow another process to access that variable.

Process 

Now, the main point of this part is to consider how an operating system deals with processes when we allow many to run. To achieve true parallelism we must have multiprocessor system when n processors can execute n programs simultaneously. True parallelism cannot be achieved with singl CPU. In single processor CPU switched from one process to another process rapidly. In 1 sec CPU can serve 100's of processes giving the illusion of parallelism to a user which is called pseudo-parallelism. 

Threads 

Difference between Process and Threads

Thread	Process
- Threads are lightweight	- Processes are heavyweight
- Threads are runs in address space of processes	- Processes have their own address space
- Threads shares files and other data	- Processes do not share files and other data
- Thread switching is faster	- Process switching is slower
Threads are easy to create and destroy	Process are difficult to create and destroy

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 into wait state. Waiting processes may never again change state, because the resources they have requested are held by other waiting processes. This situation is called a deadlock. System is deadlocked if there is a set of processes such that every process in the set is waiting for another process in the set.

Example 1
System has 2 disk drives.
P1 and P2 each hold one disk drive and each needs another one.

Example 2
- Porcess A makes a request to use the scanner
- Porcess A given the scanner
- Process B request thee CD writer
- Process B given the CD writer
- Now a requrest the CD writer
- A is denied permission until B releases the CD writer
- Also now B ask for the scanner
- Result is DEADLOCK !!

Necessary conditions for deadlock/Deadlock Characterization

A deadlock can arise if the following four conditions hold simultaneously (Necessary Condition).
1. Mutual exclusion: 
Only one process at time can use the resource.
.
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 preemption: 
A resource can be released only voluntarily by the process holding it, after that process has completed its task.

4. Circular wait:
A set {P0, P1, …, Pn} of waiting processes must exist such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.

Deadlocks Handling

Mainly there are four methods of handling deadlock
1. Deadlock avoidance 
To avoid deadlocks the system dynamically considers every request and decides whether it is safe to grant it at this point. The system requires additional prior information regarding the overal potential use of each resource for each process. 

2. Deadlock Prevention 
It means that we design such a system where there is no chance of having a deadlock. The goal is to ensure that at least one of the Coffman's necessary conditions for deadlock can never hold. Deadlock can be prevented deadlocks by constraining how request for resources can be made in the system and how they are handled.

3. Deadlock Detection and Recovery 
We can allow the system to enter a deadlock state, detect it and recover - If a system does not employ either a deadlock prevention or a deadlock avoidance algorithm, then a deadlock situation may occur. In this environment, the system can provide an algorithm that examines the state of the system to determine whether a deadlock has occurred and an algorithm to recover from the deadlock.

4.  Ignore the Problem (Ostrich Algorithm) : 
We can ignore the deadlock problem altogether. If the deadlock occurs, the system will stop functioning and will need to be restarted manually. This approach is used in systems in which deadlocks occur infrequently and if it is not a life critical system. This method is cheaper than other methods. This solution is used by most operating systems, including UNIX.

Deadlock Prevention 

If we simulate deadlock with a table which is standing on its four legs then we can also simulate four legs with the four conditions which when occurs simultaneously, cause the deadlock.

However, if we break one of the legs of the table then the table will fall definitely. The same happens with deadlock, if we can be able to violate one of the four necessary conditions and don't let them occur together then we can prevent the deadlock.

Deadlock prevention methods are given below
1. Attack mutual Exclusion
Must hold only for non-sharable resources. Sharable resources, on the other hand, do not require mutually exclusive access, and thus cannot be involved in a deadlock.

2. Attack Hold and Wait
Ensure that whenever a process requests a resource, it does not hold any other resources. Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none. There is a drawback of low resource utilization in this method.

3. Attack No Preemption
If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are preempted (or released). If a process requests some resources and if they are not available, we check whether they are allocated to some other process that is waiting for additional resources. If so, we preempt the desired resources from the waiting process and allocate them to the requesting process.

4. Attack Circular Wait
One way to ensure that circular wait never holds is to Impose a total ordering of all resource types, and require that each process requests resources in an increasing or decreasing order of enumeration.

Deadlock Avoidance 

Traditional memory stores data at a specific address and "recalls" that data later if the address is specified. Instead of an address, associative memory can recall data if a small portion of the data itself is specified.


Associative memory is often referred to as content. Addressable memory (CAM). In associative memory, any stored items can be accessed by using the contends of item. Items are stored in an associative memory have two field format, key and data.
Associative searching is based on simultaneous matching of key to be searched with stored key associated with each line of data.



The following diagram shows the block representation of an associative memory.

The functional registers like the argument register A and key register K each have n bits, are for each bit of a word. The match register m consist of M bits, one for each memory word.

Pipeline hazards are situations that prevent the next instruction in the instruction stream from executing during its designated clock cycles. In another word, any condition that causes a stall in the pipeline operations can be called a hazard. There are mainly three types of hazards, they are:

1. Data Hazards 
2. Structural Hazards
3. Control Hazards 

Data Hazards
It arises when instructions depend on the result of previous instruction but the previous instruction is not available yet.

Structural Hazards:
They arise when there are resource conflicts that prevents hardware to execute simultaneous execution of instruction. For e.g. Lets say the hardware has a register file which has a limitation of only one read or write in a cycle. If there is an instruction that needs to read from this register file while another instruction needs to write to this register file, only one can execute because of conflict.

Control Hazards
These hazards arise as a result of any type of branch instruction. Till the branch is completely executed. The branch is completely executed, the stream of following instructions will not be known completely.

Reduced instruction set computer (RISC).
 The main characteristics of RISC pipeline is to use an efficient instructions pipeline. In case of RISC pipeline, the instruction pipeline can be implemented with only two or three segments where segments 1 fetches the instructions from the memory.

Segment 2 executes the instruction in the ALU, and segment 3 may be used to store the results of the ALU operation in a particular register.

Parallel processing systems are designed to speed up the execution of programs by dividing the program into multiple fragments and processing these fragments simultaneously such systems are known as tightly coupled systems.


Parallel computing is an evolution of serial computing where the jobs are broken into discrete parts that can be executed currently. Each part is further broken down to a series of instructions. Instructions from each part execute simultaneously on different CPU's.


Parallel systems are more difficult to program than computers with a single processor because the architecture of parallel computers varies accordingly and the processes of multiple CPU's must be co-ordinates and synchronized.

Pipeline is the process of accumulating instruction from the process through a pipeline. It allows strong and executing instructions in an orderly process. It is also known as pipeling process.

Pipeline is a technique where multiple instructions are overlapped during execution. Pipeline is divided into stages and these stages are connected with one another to form a pipe like structure. Instructions entered from one end and exit from another end.

1. Arithmetic Pipeline 
2. Instruction Pipeline 

Here, A and B are significant digits of floating point number, while a and b are exponents.


Instruction Pipeline
In this a stream of instructions can be executed by overlapping fetch, decode and execute phases of an instruction cycle. This type of technique is used to increases the throughput of the computer system.

An instruction pipeline reads instruction from the memory while previous instructions are being executed in other segments of the pipeline. Thus we can execute multiple instructions simultaneously. The pipeline will be more efficient if the instruction cycle is divided into segment of equal duration.

The interconnection structure must support the following types of module

• Memory to processor : the CPU reads an instruction or data from memory
• Processor to memory : the CPU write data to memory 
• I/O to processor : the CPU reads data from the I/O device via the I/O module 
• Processor to I/O
• I/O to or from memory : An I/O module is allowed to change data directly with memory without going through the processor using DMA (Direct Memory Access) 

Address Line

• It is used to determine the source or destination of the data on the data bus. 
• For example : 
• The CPU puts the address of the desired word to be read from/or written to memory on the address lines. 
• The width of an system bus determine the maximum addressable memory
• The address lines are also used to address I/O ports. 

Control Lines

• Control lines are used to hold control signals to control the access and the use of data and address lines since these lines are shared by all components
• Control signals transmit command and timing information between system components. 
• Timing signal indicate the validity of data and address information 
• Command signals specifies the type of operations to be performed

Main operation of Bus 
If a module wishes to send data to another module it must do two things.

• Obtain the use of the bus
• Transfer data via the bus

Define arithmetic pipelining. Explain pipelining hazards with examples. 

1. Arithmetic Pipeline
2. Instruction Pipeline 

Arithmetic pipelines are usually found in most of the computers. They are used for floating point operations, multiplication of fixed point numbers etc.

1. Data Hazards
2. Control Hazards or instruction Hazards
3. Structural Hazards.

For the above sequence, the second instruction needs the value of ‘A’ computed in the first instruction. Thus the second instruction is said to depend on the first. In this situation data hazards is arises.  A data hazard is any condition in which either the source or the destination operands of an instruction are not available at the time expected in the pipeline.

Define memory hierarchy. Explain cache memory mapping functions with example. 

Cache Mapping
There are three different types of mapping used for the purpose of cache memory which are as follows:

1. Direct mapping
2. Associative mapping and 
3. Set-Associative mapping. 

Direct catch mapping

• The simplest way to determine cache locations in which store Memory blocks is direct Mapping technique.
• In this block J of the main memory maps on to block J modulo 128 of the cache. Thus main memory blocks 0,128,256,….is loaded into cache is stored at block 0. Block 1,129,257,….are stored at block 1 and so on.
• Placement of a block in the cache is determined from memory address. Memory address is divided into 3 fields, the lower 4-bits selects one of the 16 words in a block.
• When new block enters the cache, the 7-bit cache block field determines the cache positions in which this block must be stored.
• The higher order 5-bits of the memory address of the block are stored in 5 tag bits associated with its location in cache. They identify which of the 32 blocks that are mapped into this cache position are currently resident in the cache.
• It is easy to implement, but not Flexible

Micro programmed Control Unit:

• A control unit with its binary control values stored as words in memory is called as micro programmed control. Each word in the control memory contains micro instruction that specifies one or more micro operations for the system. A sequence of micro instructions constitutes a micro program.
• Micro programmed implementation is a software approach in contrast to the hardwired approach.
• It deals with various units of software but at the micro level i.e. micro-operation, micro-instruction, micro-program etc.
• Different key elements used for implementation of a control unit using micro programmed approach is shown in fig. below: