## Computer Network | Hamming Code

Hamming code is a set of error-correction codes that can be used to detect and correct the errors that can occur when the data is moved or stored from the sender to the receiver. It is technique developed by R.W. Hamming for error correction.

Redundant bits –

Redundant bits are extra binary bits that are generated and added to the information-carrying bits of data transfer to ensure that no bits were lost during the data transfer.
The number of redundant bits can be calculated using the following formula:

```2^r ≥ m + r + 1
where, r = redundant bit, m = data bit```

Suppose the number of data bits is 7, then the number of redundant bits can be calculated using:
= 2^4 ≥ 7 + 4 + 1
Thus, the number of redundant bits= 4

Parity bits –
A parity bit is a bit appended to a data of binary bits to ensure that the total number of 1’s in the data are even or odd. Parity bits are used for error detection. There are two types of parity bits:

1. Even parity bit:
In the case of even parity, for a given set of bits, the number of 1’s are counted. If that count is odd, the parity bit value is set to 1, making the total count of occurrences of 1’s an even number. If the total number of 1’s in a given set of bits is already even, the parity bit’s value is 0.
2. Odd Parity bit –
In the case of odd parity, for a given set of bits, the number of 1’s are counted. If that count is even, the parity bit value is set to 1, making the total count of occurrences of 1’s an odd number. If the total number of 1’s in a given set of bits is already odd, the parity bit’s value is 0.

General Algorithm of Hamming code –
The Hamming Code is simply the use of extra parity bits to allow the identification of an error.

1. Write the bit positions starting from 1 in binary form (1, 10, 11, 100, etc).
2. All the bit positions that are a power of 2 are marked as parity bits (1, 2, 4, 8, etc).
3. All the other bit positions are marked as data bits.
4. Each data bit is included in a unique set of parity bits, as determined its bit position in binary form.
a. Parity bit 1 covers all the bits positions whose binary representation includes a 1 in the least significant
position (1, 3, 5, 7, 9, 11, etc).
b. Parity bit 2 covers all the bits positions whose binary representation includes a 1 in the second position from
the least significant bit (2, 3, 6, 7, 10, 11, etc).
c. Parity bit 4 covers all the bits positions whose binary representation includes a 1 in the third position from
the least significant bit (4–7, 12–15, 20–23, etc).
d. Parity bit 8 covers all the bits positions whose binary representation includes a 1 in the fourth position from
the least significant bit bits (8–15, 24–31, 40–47, etc).
e. In general each parity bit covers all bits where the bitwise AND of the parity position and the bit position is
non-zero.
5. Since we check for even parity set a parity bit to 1 if the total number of ones in the positions it checks is
odd.
6. Set a parity bit to 0 if the total number of ones in the positions it checks is even.

Determining the position of redundant bits –
These redundancy bits are placed at the positions which correspond to the power of 2.
As in the above example:

1. The number of data bits = 7
2. The number of redundant bits = 4
3. The total number of bits = 11
4. The redundant bits are placed at positions corresponding to power of 2- 1, 2, 4, and 8

Suppose the data to be transmitted is 1011001, the bits will be placed as follows:

Determining the Parity bits –

1. R1 bit is calculated using parity check at all the bits positions whose binary representation includes a 1 in the least significant position.

R1: bits 1, 3, 5, 7, 9, 11

To find the redundant bit R1, we check for even parity. Since the total number of 1’s in all the bit positions corresponding to R1 is an even number the value of R1 (parity bit’s value) = 0

2. R2 bit is calculated using parity check at all the bits positions whose binary representation includes a 1 in the second position from the least significant bit.

R2: bits 2,3,6,7,10,11

To find the redundant bit R2, we check for even parity. Since the total number of 1’s in all the bit positions corresponding to R2 is an odd number the value of R2(parity bit’s value)=1

3. R4 bit is calculated using parity check at all the bits positions whose binary representation includes a 1 in the third position from the least significant bit.

R4: bits 4, 5, 6, 7

To find the redundant bit R4, we check for even parity. Since the total number of 1’s in all the bit positions corresponding to R4 is an odd number the value of R4(parity bit’s value) = 1

4. R8 bit is calculated using parity check at all the bits positions whose binary representation includes a 1 in the fourth position from the least significant bit.

R8: bit 8,9,10,11

To find the redundant bit R8, we check for even parity. Since the total number of 1’s in all the bit positions corresponding to R8 is an even number the value of R8(parity bit’s value)=0.

Thus, the data transferred is:

Error detection and correction –
Suppose in the above example the 6th bit is changed from 0 to 1 during data transmission, then it gives new parity values in the binary number:

The bits give the binary number as 0110 whose decimal representation is 6. Thus, the bit 6 contains an error. To correct the error the 6th bit is changed from 1 to 0.

### Description:

We help you polish your skills and get ready for the job, whether you are a fresh college graduate or a working professional.

We also get you connected with the right companies worldwide based on your skills and preferences, and do everything needed to make sure you get your dream job.

How many times were you frustrated while looking out for a good collection of programming/algorithm/interview questions? What did you expect and what did you get? This portal has been created to provide well written, well thought and well explained solutions for selected questions.

You can use this cheat-sheet which I personally use!

You can learn more from us on Facebook, Twitter, and Instagram.

## Line Configuration in Computer Networks

A network is two or more devices connected through a link. A link is a communication pathway that transfer data from one device to another. Devices can be a computer, printer or any other device that is capable to send and receive data. For visualization purpose, imagine any link as a line drawn between two points.
For communication to occur, two devices must be connected in some way to the same link at the same time. There are two possible types of connections:

1. Point-to-Point Connection
2. Multipoint Connection

Point-to-Point Connection :

1. A point-to-point connection provides a dedicated link between two devices.
2. The entire capacity of the link is reserved for transmission between those two devices.
3. Most point-to-point connections use a actual length of wire or cable to connect the two end, but other options such as microwave or satellite links are also possible.
4. Point to point network topology is considered to be one of the easiest and most conventional network
topologies.
5. It is also the simplest to establish and understand.

Example: Point-to-Point connection between remote control and Television for changing the channels.

Multipoint Connection :

1. It is also called Multidrop configuration. In this connection two or more devices share a single link.
2. More than two devices share the link that is the capacity of the channel is shared now. With shared capacity, there can be two possibilities in a Multipoint Line configuration:

Spatial Sharing: If several devices can share the link simultaneously, its called Spatially shared line configuration.
Temporal (Time) Sharing: If users must take turns using the link , then its called Temporally shared or Time Shared Line configuration.

We help you polish your skills and get ready for the job, whether you are a fresh college graduate or a working professional.

We also get you connected with the right companies worldwide based on your skills and preferences, and do everything needed to make sure you get your dream job.

How many times were you frustrated while looking out for a good collection of programming/algorithm/interview questions? What did you expect and what did you get? This portal has been created to provide well written, well thought and well explained solutions for selected questions.

Come and start learning at http://www.techcodebit.com

You can learn more from us on Facebook, Twitter, and Instagram.

## Basics of Computer Networking

Open system:
A system which is connected to the network and is ready for communication.

Closed system:
A system which is not connected to the network and can’t be communicated with.

Computer Network:
It is the interconnection of multiple devices, generally termed as Hosts connected using multiple paths for the purpose of sending/receiving data or media.
There are also multiple devices or mediums which helps in the communication between two different devices which are known as Network devices. Ex: Router, Switch, Hub, Bridge.

The layout pattern using which devices are interconnected is called as network topology. Such as Bus, Star, Mesh, Ring, Daisy chain.

OSI:
OSI stands for Open Systems Interconnection. It is a reference model that specifies standards for communications protocols and also the functionalities of each layer.

Protocol:
Protocol is the set of rules or algorthims which define the way how two entities can communicate across the network and there exists different protocol defined at each layer of OSI model. Few of such protocols are TCP, IP, UDP, ARP, DHCP, FTP and so on.

UNIQUE IDENTIFIERS OF NETWORK
Host name:
Each device in the network is associated with a unique device name known as Hostname.
Type “hostname” in the command prompt and press ‘Enter’, this displays the hostname of your machine.

IP Address (Internet Protocol address):
Also know as Logical Address, is the network address of the system across the network.
To identify each device in the world-wide web, Internet Assigned Numbers Authority (IANA) assigns IPV4 (Version 4) address as unique identifier for each device on the Internet.
Length of the IP address is : 32-bits. (Hence we have 2³² ip addresses available.)
Type “ipconfig” in the command prompt and press ‘Enter’, this gives us the IP address of the device.

MAC Address (Media Access Control address):
Also known as physical address, is the unique identifier of each host and is associated with the NIC (Network Interface Card).
MAC address is assigned to the NIC at the time of manufacturing.
Length of the MAC address is : 12-digit/ 6 bytes/ 48 bits
Type “ipconfig/all” in the command prompt and press ‘Enter’, this gives us the MAC address.

Port:
Port can be referred as logical channel through which data can be sent/received to an application. Any host may have multiple applications running, and each of this application is identified using the port number on which they are running on.
Port number is a 16-bit integer, hence we have 2¹⁶ ports available which are categorized as shown below:

Number of ports: 65,536
Range: 0–65535
Type “netstat -a” in the command prompt and press ‘Enter’, this lists all the ports being used.

Socket:
The unique combination of IP address and Port number together are termed as Socket.

Few more concepts
DNS Server:
DNS stands for Domain Name system.
DNS is basically a server which translate web addresses or URL (ex: www.google.com) into their corresponding IP addresses. We don’t have to remember all the IP addresses of each and every website.
The command ‘nslookup’ gives you the IP address of the domain you are looking for. This also provides the information of our DNS Server.

ARP:
ARP stands for Address Resolution Protocol.
It is used to convert the IP address to its corresponding Physical Address(i.e.MAC Address).
ARP is used by the Data Link Layer to identify the MAC address of the Receiver’s machine.
RARP:
RARP stands for Reverse Address Resolution Protocol.
As the name suggest, it provides the IP address of the a device given physical address as input. But RARP has become obsolete since the time DHCP has come into picture.

We help you polish your skills and get ready for the job, whether you are a fresh college graduate or a working professional.
We also get you connected with the right companies worldwide based on your skills and preferences, and do everything needed to make sure you get your dream job.

How many times were you frustrated while looking out for a good collection of programming/algorithm/interview questions? What did you expect and what did you get? This portal has been created to provide well written, well thought and well explained solutions for selected questions.
Come and start learning at http://www.techcodebit.com

You can learn more from us on Facebook, Twitter, and Instagram.

## Virtual Memory | Operating System

Virtual Memory is a storage allocation scheme in which secondary memory can be addressed as though it were part of main memory. The addresses a program may use to reference memory are distinguished from the addresses the memory system uses to identify physical storage sites, and program generated addresses are translated automatically to the corresponding machine addresses.
The size of virtual storage is limited by the addressing scheme of the computer system and amount of secondary memory is available not by the actual number of the main storage locations.

It is a technique that is implemented using both hardware and software. It maps memory addresses used by a program, called virtual addresses, into physical addresses in computer memory.

1. All memory references within a process are logical addresses that are dynamically translated into physical addresses at run time. This means that a process can be swapped in and out of main memory such that it occupies different places in main memory at different times during the course of execution.
2. A process may be broken into number of pieces and these pieces need not be continuously located in the main memory during execution. The combination of dynamic run-time addres translation and use of page or segment table permits this.

If these characteristics are present then, it is not necessary that all the pages or segments are present in the main memory during execution. This means that the required pages need to be loaded into memory whenever required. Virtual memory is implemented using Demand Paging or Demand Segmentation.

Demand Paging :
The process of loading the page into memory on demand (whenever page fault occurs) is known as demand paging.
The process includes the following steps :

1. If CPU try to refer a page that is currently not available in the main memory, it generates an interrupt indicating memory access fault.
2. The OS puts the interrupted process in a blocking state. For the execution to proceed the OS must bring the required page into the memory.
3. The OS will search for the required page in the logical address space.
4. The required page will be brought from logical address space to physical address space. The page replacement algorithms are used for the decision making of replacing the page in physical address space.
5. The page table will updated accordingly.
6. The signal will be sent to the CPU to continue the program execution and it will place the process back into ready state.

Hence whenever a page fault occurs these steps are followed by the operating system and the required page is brought into memory.

Advantages :

• More processes may be maintained in the main memory: Because we are going to load only some of the pages of any particular process, there is room for more processes. This leads to more efficient utilization of the processor because it is more likely that at least one of the more numerous processes will be in the ready state at any particular time.
• A process may be larger than all of main memory: One of the most fundamental restrictions in programming is lifted. A process larger than the main memory can be executed because of demand paging. The OS itself loads pages of a process in main memory as required.
• It allows greater multiprogramming levels by using less of the available (primary) memory for each process.

Page Fault Service Time :
The time taken to service the page fault is called as page fault service time. The page fault service time includes the time taken to perform all the above six steps.

```Let Main memory access time is: m
Page fault service time is: s
Page fault rate is : p
Then, Effective memory access time = (p*s) + (1-p)*m```

Swapping:

Swapping a process out means removing all of its pages from memory, or marking them so that they will be removed by the normal page replacement process. Suspending a process ensures that it is not runnable while it is swapped out. At some later time, the system swaps back the process from the secondary storage to main memory. When a process is busy swapping pages in and out then this situation is called thrashing.

Thrashing :

At any given time, only few pages of any process are in main memory and therefore more processes can be maintained in memory. Furthermore time is saved because unused pages are not swapped in and out of memory. However, the OS must be clever about how it manages this scheme. In the steady state practically, all of main memory will be occupied with process’s pages, so that the processor and OS has direct access to as many processes as possible. Thus when the OS brings one page in, it must throw another out. If it throws out a page just before it is used, then it will just have to get that page again almost immediately. Too much of this leads to a condition called Thrashing. The system spends most of its time swapping pages rather than executing instructions. So a good page replacement algorithm is required.

In the given diagram, initial degree of multi programming upto some extent of point(lamda), the CPU utilization is very high and the system resources are utilized 100%. But if we further increase the degree of multi programming the CPU utilization will drastically fall down and the system will spent more time only in the page replacement and the time taken to complete the execution of the process will increase. This situation in the system is called as thrashing.

Causes of Thrashing :

1. High degree of multiprogramming : If the number of processes keeps on increasing in the memory than number of frames allocated to each process will be decreased. So, less number of frames will be available to each process. Due to this, page fault will occur more frequently and more CPU time will be wasted in just swapping in and out of pages and the utilization will keep on decreasing.
2. For example:
Let free frames = 400
Case 1: Number of process = 100
Then, each process will get 4 frames.
3. Case 2: Number of process = 400
Each process will get 1 frame.
Case 2 is a condition of thrashing, as the number of processes are increased,frames per process are decreased. Hence CPU time will be consumed in just swapping pages.
4. Lacks of Frames:If a process has less number of frames then less pages of that process will be able to reside in memory and hence more frequent swapping in and out will be required. This may lead to thrashing. Hence sufficient amount of frames must be allocated to each process in order to prevent thrashing.

Recovery of Thrashing :

• Do not allow the system to go into thrashing by instructing the long term scheduler not to bring the processes into memory after the threshold.
• If the system is already in thrashing then instruct the mid term schedular to suspend some of the processes so that we can recover the system from thrashing.

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

## Operating Systems | Segmentation

A Memory Management technique in which memory is divided into variable sized chunks which can be allocated to processes. Each chunk is called a Segment.

A table stores the information about all such segments and is called Segment Table.

Segment Table: It maps two dimensional Logical address into one dimensional Physical address.

It’s each table entry has

• Base Address: It contains the starting physical address where the segments reside in memory.
• Limit: It specifies the length of the segment.

Translation of Two dimensional Logical Address to one dimensional Physical Address.

Address generated by the CPU is divided into:

• Segment number (s): Number of bits required to represent the segment.
• Segment offset (d): Number of bits required to represent the size of the segment.

Advantages of Segmentation:

• No Internal fragmentation.
• Segment Table consumes less space in comparison to Page table in paging.

Disadvantage of Segmentation:

• As processes are loaded and removed from the memory, the free memory space is broken into little pieces, causing External fragmentation.

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

## Operating System | Page Replacement Algorithms

In a operating systems that use paging for memory management, page replacement algorithm are needed to decide which page needed to be replaced when new page comes in. Whenever a new page is referred and not present in memory, page fault occurs and Operating System replaces one of the existing pages with newly needed page. Different page replacement algorithms suggest different ways to decide which page to replace. The target for all algorithms is to reduce number of page faults.

Page Fault — A page fault is a type of interrupt, raised by the hardware when a running program accesses a memory page that is mapped into the virtual address space, but not loaded in physical memory.

Page Replacement Algorithms :

• First In First Out (FIFO) –
This is the simplest page replacement algorithm. In this algorithm, operating system keeps track of all pages in the memory in a queue, oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.
• For example-1, consider page reference string 1, 3, 0, 3, 5, 6 and 3 page slots.
• Initially all slots are empty, so when 1, 3, 0 came they are allocated to the empty slots → 3 Page Faults.
when 3 comes, it is already in memory so → 0 Page Faults.
Then 5 comes, it is not available in memory so it replaces the oldest page slot i.e 1. →1 Page Fault.
Finally 6 comes, it is also not available in memory so it replaces the oldest page slot i.e 3 →1 Page Fault.
• Example-2, Let’s have a reference string: a, b, c, d, c, a, d, b, e, b, a, b, c, d and the size of the frame be 4.
• There are 9 page faults using FIFO algorithm.
• Belady’s anomaly — Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm. For example, if we consider reference string 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4 and 3 slots, we get 9 total page faults, but if we increase slots to 4, we get 10 page faults.
• Optimal Page replacement –
In this algorithm, pages are replaced which are not used for the longest duration of time in the future.
• Let us consider page reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 and 4 page slots.
• Initially all slots are empty, so when 7 0 1 2 are allocated to the empty slots → 4 Page faults
0 is already there so → 0 Page fault.
when 3 came it will take the place of 7 because it is not used for the longest duration of time in the future. →1 Page fault.
0 is already there so → 0 Page fault..
4 will takes place of 1 → 1 Page Fault.
• Now for the further page reference string → 0 Page fault because they are already available in the memory.
• Example-2, Let’s have a reference string: a, b, c, d, c, a, d, b, e, b, a, b, c, d and the size of the frame be 4.
• There are 6 page faults using optimal algorithm.
• Optimal page replacement is perfect, but not possible in practice as operating system cannot know future requests. The use of Optimal Page replacement is to set up a benchmark so that other replacement algorithms can be analyzed against it.
• Least Recently Used –
In this algorithm page will be replaced which is least recently used.
• Let say the page reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 . Initially we have 4 page slots empty.
Initially all slots are empty, so when 7 0 1 2 are allocated to the empty slots → 4 Page faults
0 is already their so → 0 Page fault.
when 3 came it will take the place of 7 because it is least recently used →1 Page fault
0 is already in memory so → 0 Page fault.
4 will takes place of 1 → 1 Page Fault
Now for the further page reference string → 0 Page fault because they are already available in the memory.
• Example-2, Let’s have a reference string: a, b, c, d, c, a, d, b, e, b, a, b, c, d and the size of the frame be 4.
• There are 7 page faults using LRU algorithm.

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

## Operating System | Memory Management |Partition Allocation Method

In operating system, following are four common memory management techniques.

```Single contiguous allocation:  Simplest allocation method used by MS-DOS.
All memory (except some reserved for OS) is available to
a process.```
`Partitioned allocation: Memory is divided in different blocks`
```Paged memory management: Memory is divided in fixed sized units called
page frames, used in virtual memory environment.```
```Segmented memory management: Memory is divided in different segments (a
segment is logical grouping of process' data or code)
In this management, allocated memory does'nt  have to
be contiguous.```

Most of the operating systems (for example Windows and Linux) use Segmentation with Paging. A process is divided in segments and individual segments have pages.

In Partition Allocation, when there are more than one partition freely available to accommodate a process’s request, a partition must be selected. To choose a particular partition, a partition allocation method is needed. A partition allocation method is considered better if it avoids internal fragmentation.

Below are the various partition allocation schemes :

```1. First Fit: In the first fit, partition is allocated which is first
sufficient from the top of Main Memory.```
```2. Best Fit  Allocate the process to the partition which is first
smallest sufficient partition among the free available partition.```
```3. Worst Fit  Allocate the process to the partition which is largest
sufficient among the freely available partitions available in
the main memory.```
```4. Next Fit Next fit is similar to the first fit but it will search
for the first sufficient partition from the last allocation point.```

Is Best-Fit really best?
Although, best fit minimizes the wastage space, it consumes a lot of processor time for searching the block which is close to required size. Also, Best-fit may perform poorer than other algorithms in some cases.

## Deadlock Prevention And Avoidance

Deadlock Characteristics
Deadlock has following characteristics.

```Mutual Exclusion.
Hold and Wait.
No preemption.
Circular wait.```

Deadlock Prevention

We can prevent Deadlock by eliminating any of the above four condition.

Eliminate Mutual Exclusion
It is not possible to dis-satisfy the mutual exclusion because some resources, such as the tap drive and printer, are inherently non-shareable.

Eliminate Hold and wait
1. Allocate all required resources to the process before start of its execution, this way hold and wait condition is eliminated but it will lead to low device utilization. for example, if a process requires printer at a later time and we have allocated printer before the start of its execution printer will remained blocked till it has completed its execution.

2. Process will make new request for resources after releasing the current set of resources. This solution may lead to starvation.

Eliminate No Preemption
Preempt resources from process when resources required by other high priority process.

Eliminate Circular Wait
Each resource will be assigned with a numerical number. A process can request for the resources only in increasing order of numbering.
For Example, if P1 process is allocated R5 resources, now next time if P1 ask for R4, R3 lesser than R5 such request will not be granted, only request for resources more than R5 will be granted.

Deadlock Avoidance

Deadlock avoidance can be done with Banker’s Algorithm.

Banker’s Algorithm

Bankers’s Algorithm is resource allocation and deadlock avoidance algorithm which test all the request made by processes for resources, it check for safe state, if after granting request system remains in the safe state it allows the request and if their is no safe state it don’t allow the request made by the process.

Inputs to Banker’s Algorithm
1. Max need of resources by each process.
2. Currently allocated resources by each process.
3. Max free available resources in the system.

Request will only be granted under below condition.
1. If request made by process is less than equal to max need to that process.

2. If request made by process is less than equal to freely availbale resource in the system.

Example

```Total resources in system:
A B C D
6 5 7 6```
```Available system resources are:
A B C D
3 1 1 2```
```Processes (currently allocated resources):
A B C D
P1  1 2 2 1
P2  1 0 3 3
P3  1 2 1 0```
```Processes (maximum resources):
A B C D
P1  3 3 2 2
P2  1 2 3 4
P3  1 3 5 0```
```Need = maximum resources - currently allocated resources.
Processes (need resources):
A B C D
P1  2 1 0 1
P2  0 2 0 1
P3  0 1 4 0```

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

## Disk Scheduling Algorithms

Disk scheduling is is done by operating systems to schedule I/O requests arriving for disk. Disk scheduling is also known as I/O scheduling.

Disk scheduling is important because:

• Multiple I/O requests may arrive by different processes and only one I/O request can be served at a time by disk controller. Thus other I/O requests need to wait in waiting queue and need to be scheduled.
• Two or more request may be far from each other so can result in greater disk arm movement.
• Hard drives are one of the slowest parts of computer system and thus need to be accessed in an efficient manner.

There are many Disk Scheduling Algorithms but before discussing them let’s have a quick look at some of the important terms:

• Seek Time:Seek time is the time taken to locate the disk arm to a specified track where the data is to be read or write. So the disk scheduling algorithm that gives minimum average seek time is better.
• Rotational Latency: Rotational Latency is the time taken by the desired sector of disk to rotate into a position so that it can access the read/write heads. So the disk scheduling algorithm that gives minimum rotational latency is better.
• Transfer Time: Transfer time is the time to transfer the data. It depends on the rotating speed of the disk and number of bytes to be transferred.
• Disk Access Time: Disk Access Time is:
```Disk Access Time = Seek Time +
Rotational Latency +
Transfer Time```
• Disk Response Time: Response Time is the average of time spent by a request waiting to perform its I/O operation. Average Response time is the response time of the all requests. Variance Response Time is measure of how individual request are serviced with respect to average response time. So the disk scheduling algorithm that gives minimum variance response time is better.

Disk Scheduling Algorithms

1. FCFS: FCFS is the simplest of all the Disk Scheduling Algorithms. In FCFS, the requests are addressed in the order they arrive in the disk queue.

Advantages:

• Every request gets a fair chance
• No indefinite postponement

Disadvantages:

• Does not try to optimize seek time
• May not provide the best possible service
1. SSTF: In SSTF (Shortest Seek Time First), requests having shortest seek time are executed first. So, the seek time of every request is calculated in advance in queue and then they are scheduled according to their calculated seek time. As a result, the request near the disk arm will get executed first. SSTF is certainly an improvement over FCFS as it decreases the average response time and increases the throughput of system.

Advantages:

• Average Response Time decreases
• Throughput increases

Disadvantages:

• Overhead to calculate seek time in advance
• Can cause Starvation for a request if it has higher seek time as compared to incoming requests
• High variance of response time as SSTF favours only some requests
1. SCAN: In SCAN algorithm the disk arm moves into a particular direction and services the requests coming in its path and after reaching the end of disk, it reverses its direction and again services the request arriving in its path. So, this algorithm works like an elevator and hence also known as elevator algorithm. As a result, the requests at the midrange are serviced more and those arriving behind the disk arm will have to wait.

Advantages:

• High throughput
• Low variance of response time
• Average response time

Disadvantages:

• Long waiting time for requests for locations just visited by disk arm
1. CSCAN: In SCAN algorithm, the disk arm again scans the path that has been scanned, after reversing its direction. So, it may be possible that too many requests are waiting at the other end or there may be zero or few requests pending at the scanned area.

These situations are avoided in CSAN algorithm in which the disk arm instead of reversing its direction goes to the other end of the disk and starts servicing the requests from there. So, the disk arm moves in a circular fashion and this algorithm is also similar to SCAN algorithm and hence it is known as C-SCAN (Circular SCAN).

Advantages:

• Provides more uniform wait time compared to SCAN
1. LOOK: It is similar to the SCAN disk scheduling algorithm except the difference that the disk arm in spite of going to the end of the disk goes only to the last request to be serviced in front of the head and then reverses its direction from there only. Thus it prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.
2. CLOOK: As LOOK is similar to SCAN algorithm, in similar way, CLOOK is similar to CSCAN disk scheduling algorithm. In CLOOK, the disk arm inspite of going to the end goes only to the last request to be serviced in front of the head and then from there goes to the other end’s last request. Thus, it also prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.

Each algorithm is unique in its own way.Overall Performance depends on number and type of requests.

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

## Operating System | Paging

Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. This scheme permits the physical address space of a process to be non — contiguous.

• Logical Address or Virtual Address (represented in bits): An address generated by the CPU
• Logical Address Space or Virtual Address Space( represented in words or bytes): The set of all logical addresses generated by a program
• Physical Address (represented in bits): An address actually available on memory unit
• Physical Address Space (represented in words or bytes): The set of all physical addresses corresponding to the logical addresses

The mapping from virtual to physical address is done by the memory management unit (MMU) which is a hardware device and this mapping is known as paging technique.

• The Physical Address Space is conceptually divided into a number of fixed-size blocks, called frames.
• The Logical address Space is also splitted into fixed-size blocks, called pages.
• Page Size = Frame Size

Let us consider an example:

• Physical Address = 12 bits, then Physical Address Space = 4 K words
• Logical Address = 13 bits, then Logical Address Space = 8 K words
• Page size = frame size = 1 K words (assumption)

Address generated by CPU is divided into

• Page number(p): Number of bits required to represent the pages in Logical Address Space or Page number
• Page offset(d): Number of bits required to represent particular word in a page or page size of Logical Address Space or word number of a page or page offset.

Physical Address is divided into

• Frame number(f): Number of bits required to represent the frame of Physical Address Space or Frame number.
• Frame offset(d): Number of bits required to represent particular word in a frame or frame size of Physical Address Space or word number of a frame or frame offset.

The hardware implementation of page table can be done by using dedicated registers. But the usage of register for the page table is satisfactory only if page table is small. If page table contain large number of entries then we can use TLB(translation Look-aside buffer), a special, small, fast look up hardware cache.

• The TLB is associative, high speed memory.
• Each entry in TLB consists of two parts: a tag and a value.
• When this memory is used, then an item is compared with all tags simultaneously.If the item is found, then corresponding value is returned.

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide