Operating System | Gate Vidyalay

Category: Operating System

Paging | Memory Management | Operating System

Operating System

Non-Contiguous Memory Allocation-

Non-contiguous memory allocation is a memory allocation technique.
It allows to store parts of a single process in a non-contiguous fashion.
Thus, different parts of the same process can be stored at different places in the main memory.

Techniques-

There are two popular techniques used for non-contiguous memory allocation-

Paging
Segmentation

In this article, we will discuss about Paging.

Learn about Segmentation.

Paging-

Paging is a fixed size partitioning scheme.
In paging, secondary memory and main memory are divided into equal fixed size partitions.
The partitions of secondary memory are called as pages.
The partitions of main memory are called as frames.

Each process is divided into parts where size of each part is same as page size.
The size of the last part may be less than the page size.
The pages of process are stored in the frames of main memory depending upon their availability.

Example-

Consider a process is divided into 4 pages P₀, P₁, P₂ and P₃.
Depending upon the availability, these pages may be stored in the main memory frames in a non-contiguous fashion as shown-

Also Read- Contiguous Memory Allocation

Translating Logical Address into Physical Address-

CPU always generates a logical address.
A physical address is needed to access the main memory.

Following steps are followed to translate logical address into physical address-

Step-01:

CPU generates a logical address consisting of two parts-

Page Number
Page Offset

Page Number specifies the specific page of the process from which CPU wants to read the data.
Page Offset specifies the specific word on the page that CPU wants to read.

Step-02:

For the page number generated by the CPU,

Page Table provides the corresponding frame number (base address of the frame) where that page is stored in the main memory.

Step-03:

The frame number combined with the page offset forms the required physical address.

Frame number specifies the specific frame where the required page is stored.
Page Offset specifies the specific word that has to be read from that page.

Diagram-

The following diagram illustrates the above steps of translating logical address into physical address-

Advantages-

The advantages of paging are-

It allows to store parts of a single process in a non-contiguous fashion.
It solves the problem of external fragmentation.

Disadvantages-

The disadvantages of paging are-

It suffers from internal fragmentation.
There is an overhead of maintaining a page table for each process.
The time taken to fetch the instruction increases since now two memory accesses are required.

To gain better understanding about Paging,

Watch this Video Lecture

Next Article- Page Table | Page Table Entry

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

C-LOOK Algorithm | Disk Scheduling Algorithms

Operating System

Disk Scheduling Algorithms-

Before you go through this article, make sure that you have gone through the previous article on Disk Scheduling.

We have discussed-

Disk scheduling algorithms are used to schedule multiple requests for accessing the disk.
The purpose of disk scheduling algorithms is to reduce the total seek time.

Various disk scheduling algorithms are-

In this article, we will discuss about C-LOOK Disk Scheduling Algorithm.

C-LOOK Disk Scheduling Algorithm-

Circular-LOOK Algorithm is an improved version of the LOOK Algorithm.
Head starts from the first request at one end of the disk and moves towards the last request at the other end servicing all the requests in between.
After reaching the last request at the other end, head reverses its direction.
It then returns to the first request at the starting end without servicing any request in between.
The same process repeats.

Also Read- SCAN Disk Scheduling Algorithm

Advantages-

It does not causes the head to move till the ends of the disk when there are no requests to be serviced.
It reduces the waiting time for the cylinders just visited by the head.
It provides better performance as compared to LOOK Algorithm.
It does not lead to starvation.
It provides low variance in response time and waiting time.

Disadvantages-

There is an overhead of finding the end requests.

Also Read- C-SCAN Disk Scheduling Algorithm

PRACTICE PROBLEMS BASED ON C-LOOK DISK SCHEDULING ALGORITHM-

Problem-01:

Consider a disk queue with requests for I/O to blocks on cylinders 98, 183, 41, 122, 14, 124, 65, 67. The C-LOOK scheduling algorithm is used. The head is initially at cylinder number 53 moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from 0 to 199. The total head movement (in number of cylinders) incurred while servicing these requests is _______.

Solution-

Total head movements incurred while servicing these requests

= (65 – 53) + (67 – 65) + (98 – 67) + (122 – 98) + (124 – 122) + (183 – 124) + (183 – 14) + (41 – 14)

= 12 + 2 + 31 + 24 + 2 + 59 + 169 + 27

= 326

Alternatively,

Total head movements incurred while servicing these requests

= (183 – 53) + (183 – 14) + (41 – 14)

= 130 + 169 + 27

= 326

Problem-02:

Consider a disk queue with requests for I/O to blocks on cylinders 47, 38, 121, 191, 87, 11, 92, 10. The C-LOOK scheduling algorithm is used. The head is initially at cylinder number 63 moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from 0 to 199. The total head movement (in number of cylinders) incurred while servicing these requests is _______.

Solution-

Total head movements incurred while servicing these requests

= (87 – 63) + (92 – 87) + (121 – 92) + (191 – 121) + (191 – 10) + (11 – 10) + (38 – 11) + (47 – 38)

= 24 + 5 + 29 + 70 + 181 + 1 + 27 + 9

= 346

Alternatively,

Total head movements incurred while servicing these requests

= (191 – 63) + (191 – 10) + (47 – 10)

= 128 + 181 + 37

= 346

To gain better understanding about C-LOOK Disk Scheduling Algorithm,

Watch this Video Lecture

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

LOOK Algorithm | Disk Scheduling Algorithms

Operating System

Disk Scheduling Algorithms-

Before you go through this article, make sure that you have gone through the previous article on Disk Scheduling.

We have discussed-

Disk scheduling algorithms are used to schedule multiple requests for accessing the disk.
The purpose of disk scheduling algorithms is to reduce the total seek time.

Various disk scheduling algorithms are-

In this article, we will discuss about LOOK Disk Scheduling Algorithm.

LOOK Disk Scheduling Algorithm-

LOOK Algorithm is an improved version of the SCAN Algorithm.
Head starts from the first request at one end of the disk and moves towards the last request at the other end servicing all the requests in between.
After reaching the last request at the other end, head reverses its direction.
It then returns to the first request at the starting end servicing all the requests in between.
The same process repeats.

Also Read- C-SCAN Disk Scheduling Algorithm

NOTE-

The main difference between SCAN Algorithm and LOOK Algorithm is-

SCAN Algorithm scans all the cylinders of the disk starting from one end to the other end even if there are no requests at the ends.
LOOK Algorithm scans all the cylinders of the disk starting from the first request at one end to the last request at the other end.

Advantages-

It does not causes the head to move till the ends of the disk when there are no requests to be serviced.
It provides better performance as compared to SCAN Algorithm.
It does not lead to starvation.
It provides low variance in response time and waiting time.

Disadvantages-

There is an overhead of finding the end requests.
It causes long waiting time for the cylinders just visited by the head.

PRACTICE PROBLEM BASED ON LOOK DISK SCHEDULING ALGORITHM-

Problem-

Consider a disk queue with requests for I/O to blocks on cylinders 98, 183, 41, 122, 14, 124, 65, 67. The LOOK scheduling algorithm is used. The head is initially at cylinder number 53 moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from 0 to 199. The total head movement (in number of cylinders) incurred while servicing these requests is _______.

Solution-

Total head movements incurred while servicing these requests

= (65 – 53) + (67 – 65) + (98 – 67) + (122 – 98) + (124 – 122) + (183 – 124) + (183 – 41) + (41 – 14)

= 12 + 2 + 31 + 24 + 2 + 59 + 142 + 27

= 299

Alternatively,

Total head movements incurred while servicing these requests

= (183 – 53) + (183 – 14)

= 130 + 169

= 299

To gain better understanding about LOOK Disk Scheduling Algorithm,

Watch this Video Lecture

Next Article- C-LOOK Disk Scheduling Algorithm

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

C-SCAN Disk Scheduling | Disk Scheduling

Operating System

Disk Scheduling Algorithms-

Before you go through this article, make sure that you have gone through the previous article on Disk Scheduling.

We have discussed-

Disk scheduling algorithms are used to schedule multiple requests for accessing the disk.
The purpose of disk scheduling algorithms is to reduce the total seek time.

Various disk scheduling algorithms are-

In this article, we will discuss about C-SCAN Disk Scheduling Algorithm.

C-SCAN Disk Scheduling Algorithm-

Circular-SCAN Algorithm is an improved version of the SCAN Algorithm.
Head starts from one end of the disk and move towards the other end servicing all the requests in between.
After reaching the other end, head reverses its direction.
It then returns to the starting end without servicing any request in between.
The same process repeats.

Also Read- FCFS Disk Scheduling Algorithm

Advantages-

The waiting time for the cylinders just visited by the head is reduced as compared to the SCAN Algorithm.
It provides uniform waiting time.
It provides better response time.

Disadvantages-

It causes more seek movements as compared to SCAN Algorithm.
It causes the head to move till the end of the disk even if there are no requests to be serviced.

Also Read- SSTF Disk Scheduling Algorithm

PRACTICE PROBLEM BASED ON C-SCAN DISK SCHEDULING ALGORITHM-

Problem-

Consider a disk queue with requests for I/O to blocks on cylinders 98, 183, 41, 122, 14, 124, 65, 67. The C-SCAN scheduling algorithm is used. The head is initially at cylinder number 53 moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from 0 to 199. The total head movement (in number of cylinders) incurred while servicing these requests is _______.

Solution-

Total head movements incurred while servicing these requests

= (65 – 53) + (67 – 65) + (98 – 67) + (122 – 98) + (124 – 122) + (183 – 124) + (199 – 183) + (199 – 0) + (14 – 0) + (41 – 14)

= 12 + 2 + 31 + 24 + 2 + 59 + 16 + 199 + 14 + 27

= 386

Alternatively,

Total head movements incurred while servicing these requests

= (199 – 53) + (199 – 0) + (41 – 0)

= 146 + 199 + 41

= 386

To gain better understanding about C-SCAN Disk Scheduling Algorithm,

Watch this Video Lecture

Next Article- LOOK Disk Scheduling Algorithm

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

SCAN Algorithm | Disk Scheduling Algorithms

Operating System

Disk Scheduling Algorithms-

Before you go through this article, make sure that you have gone through the previous article on Disk Scheduling.

We have discussed-

Disk scheduling algorithms are used to schedule multiple requests for accessing the disk.
The purpose of disk scheduling algorithms is to reduce the total seek time.

Various disk scheduling algorithms are-

In this article, we will discuss about SCAN Disk Scheduling Algorithm.

SCAN Disk Scheduling Algorithm-

As the name suggests, this algorithm scans all the cylinders of the disk back and forth.
Head starts from one end of the disk and move towards the other end servicing all the requests in between.
After reaching the other end, head reverses its direction and move towards the starting end servicing all the requests in between.
The same process repeats.

NOTE-

SCAN Algorithm is also called as Elevator Algorithm.
This is because its working resembles the working of an elevator.

Also Read- FCFS Disk Scheduling Algorithm

Advantages-

It is simple, easy to understand and implement.
It does not lead to starvation.
It provides low variance in response time and waiting time.

Disadvantages-

It causes long waiting time for the cylinders just visited by the head.
It causes the head to move till the end of the disk even if there are no requests to be serviced.

Also Read- SSTF Disk Scheduling Algorithm

PRACTICE PROBLEM BASED ON SCAN DISK SCHEDULING ALGORITHM-

Problem-

Consider a disk queue with requests for I/O to blocks on cylinders 98, 183, 41, 122, 14, 124, 65, 67. The SCAN scheduling algorithm is used. The head is initially at cylinder number 53 moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from 0 to 199. The total head movement (in number of cylinders) incurred while servicing these requests is _______.