Category: Operating System

Segmentation in OS | Practice Problems

Operating System

Segmentation in OS-

 

Before you go through this article, make sure that you have gone through the previous article on Segmentation in OS.

 

We have discussed-

  • Like Paging, Segmentation is another non-contiguous memory allocation technique.
  • Segmentation divides the process into meaningful segments.
  • Segment table stores the information about each segment of the process.

 

In this article, we will discuss a practice problem based on segmentation.

 

PRACTICE PROBLEM BASED ON SEGMENTATION-

 

Problem-

 

Consider the following segment table-

 

Segment No. Base Length
0 1219 700
1 2300 14
2 90 100
3 1327 580
4 1952 96

 

Which of the following logical address will produce trap addressing error?

  1. 0, 430
  2. 1, 11
  3. 2, 100
  4. 3, 425
  5. 4, 95

 

Calculate the physical address if no trap is produced.

 

Solution-

 

In a segmentation scheme, the generated logical address consists of two parts-

  1. Segment Number
  2. Segment Offset

 

We know-

  • Segment Offset must always lie in the range [0, limit-1].
  • If segment offset becomes greater than or equal to the limit of segment, then trap addressing error is produced.

 

Option-A: 0, 430-

 

Here,

  • Segment Number = 0
  • Segment Offset = 430

 

We have,

  • In the segment table, limit of segment-0 is 700.
  • Thus, segment offset must always lie in the range = [0, 700-1] = [0, 699]

 

Now,

  • Since generated segment offset lies in the above range, so request generated is valid.
  • Therefore, no trap will be produced.
  • Physical Address = 1219 + 430 = 1649

 

Option-B: 1, 11-

 

Here,

  • Segment Number = 1
  • Segment Offset = 11

 

We have,

  • In the segment table, limit of segment-1 is 14.
  • Thus, segment offset must always lie in the range = [0, 14-1] = [0, 13]

 

Now,

  • Since generated segment offset lies in the above range, so request generated is valid.
  • Therefore, no trap will be produced.
  • Physical Address = 2300 + 11 = 2311

 

Option-C: 2, 100-

 

Here,

  • Segment Number = 2
  • Segment Offset = 100

 

We have,

  • In the segment table, limit of segment-2 is 100.
  • Thus, segment offset must always lie in the range = [0, 100-1] = [0, 99]

 

Now,

  • Since generated segment offset does not lie in the above range, so request generated is invalid.
  • Therefore, trap will be produced.

 

Option-D: 3, 425-

 

Here,

  • Segment Number = 3
  • Segment Offset = 425

 

We have,

  • In the segment table, limit of segment-3 is 580.
  • Thus, segment offset must always lie in the range = [0, 580-1] = [0, 579]

 

Now,

  • Since generated segment offset lies in the above range, so request generated is valid.
  • Therefore, no trap will be produced.
  • Physical Address = 1327 + 425 = 1752

 

Option-E: 4, 95-

 

Here,

  • Segment Number = 4
  • Segment Offset = 95

 

We have,

  • In the segment table, limit of segment-4 is 96.
  • Thus, segment offset must always lie in the range = [0, 96-1] = [0, 95]

 

Now,

  • Since generated segment offset lies in the above range, so request generated is valid.
  • Therefore, no trap will be produced.
  • Physical Address = 1952 + 95 = 2047

 

Thus, Option-(C) is correct.

 

To watch video solution and practice other problems,

Watch this Video Lecture

 

Next Article- Segmented Paging in OS

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Segmentation in OS | Segmentation and Paging

Operating System

Non-Contiguous Memory Allocation-

 

Before you go through this article, make sure that you have gone through the previous article on Non-Contiguous Memory Allocation.

 

We have discussed-

  • Non-contiguous memory allocation is a memory allocation technique.
  • It allows to store parts of a single process in a non-contiguous fashion.

 

Techniques-

 

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

 

 

In this article, we will discuss about Segmentation.

 

Segmentation-

 

  • Like Paging, Segmentation is another non-contiguous memory allocation technique.
  • In segmentation, process is not divided blindly into fixed size pages.
  • Rather, the process is divided into modules for better visualization.

 

Characteristics-

 

  • Segmentation is a variable size partitioning scheme.
  • In segmentation, secondary memory and main memory are divided into partitions of unequal size.
  • The size of partitions depend on the length of modules.
  • The partitions of secondary memory are called as segments.

 

Example-

 

Consider a program is divided into 5 segments as-

 

 

Segment Table-

 

  • Segment table is a table that stores the information about each segment of the process.
  • It has two columns.
  • First column stores the size or length of the segment.
  • Second column stores the base address or starting address of the segment in the main memory.
  • Segment table is stored as a separate segment in the main memory.
  • Segment table base register (STBR) stores the base address of the segment table.

 

For the above illustration, consider the segment table is-

 

 

Here,

  • Limit indicates the length or size of the segment.
  • Base indicates the base address or starting address of the segment in the main memory.

 

In accordance to the above segment table, the segments are stored in the main memory as-

 

 

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-

  1. Segment Number
  2. Segment Offset

 

 

  • Segment Number specifies the specific segment of the process from which CPU wants to read the data.
  • Segment Offset specifies the specific word in the segment that CPU wants to read.

 

Step-02:

 

  • For the generated segment number, corresponding entry is located in the segment table.
  • Then, segment offset is compared with the limit (size) of the segment.

 

Now, two cases are possible-

 

Case-01: Segment Offset >= Limit

 

  • If segment offset is found to be greater than or equal to the limit, a trap is generated.

 

Case-02: Segment Offset < Limit

 

  • If segment offset is found to be smaller than the limit, then request is treated as a valid request.
  • The segment offset must always lie in the range [0, limit-1],
  • Then, segment offset is added with the base address of the segment.
  • The result obtained after addition is the address of the memory location storing the required word.

 

Diagram-

 

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

 

 

Advantages-

 

The advantages of segmentation are-

  • It allows to divide the program into modules which provides better visualization.
  • Segment table consumes less space as compared to Page Table in paging.
  • It solves the problem of internal fragmentation.

 

Disadvantages-

 

The disadvantages of segmentation are-

  • There is an overhead of maintaining a segment table for each process.
  • The time taken to fetch the instruction increases since now two memory accesses are required.
  • Segments of unequal size are not suited for swapping.
  • It suffers from external fragmentation as the free space gets broken down into smaller pieces with the processes being loaded and removed from the main memory.

 

To gain better understanding about Segmentation,

Watch this Video Lecture

 

Next Article- Practice Problems On Segmentation

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Page Replacement Algorithms | Important Results

Operating System

Page Replacement Algorithms-

 

Before you go through this article, make sure that you have gone through the previous article on Page Replacement Algorithms.

 

We have discussed-

  • When a page fault occurs, the required page has to be brought from the secondary memory.
  • If all the frames of main memory are already occupied, then a page has to be replaced.
  • Page replacement algorithms help to decide which page should be replaced.

 

In this article, we will discuss some important results.

 

Important Results-

 

Result-01: For a Reference String Consisting Of Repeated Sequence Of Page Numbers-

 

For such a reference string,

  • Optimal page replacement algorithm replaces the most recently used page to minimize the page faults.
  • This is because most recently page will be required after the longest time.
  • Thus, Optimal page replacement algorithm acts as Most Recently Used (MRU) page replacement algorithm.

 

In other words,

  • MRU page replacement algorithm will behave as Optimal page replacement algorithm.
  • MRU page replacement algorithm gives the optimal performance.

 

Example-

 

Consider the following reference string consisting of a repeated sequence of page numbers-

1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6

 

Here,

  • Both Optimal and MRU page replacement algorithm replaces the most recently used page.
  • Most recently used page will be required after the longest time.
  • Hence, both these algorithms give the optimal performance.

 

 

Total number of page faults occurred = 12

 

NOTES-

 

Note-01:

 

  • These are the minimum number of page faults that are possible.
  • If any other page replacement algorithm is used, it will surely give rise to more number of page faults.
  • FIFO and LRU page replacement algorithm give rise to 24 number of page faults.

 

Note-02:

 

  • CPU may generate such a reference string when executing loops.
  • This is because while executing loops, same set of instructions have to be executed again and again.

 

Note-03:

 

  • Principle of locality states that the next reference would be most probably from the most recently used pages.
  • Here, the behavior of Optimal page replacement algorithm contradicts with the principle of locality.
  • Here, Optimal algorithm replaces the most recently used page to give the optimal performance.
  • So, from here we can infer that principle of locality does not hold true in certain scenarios.

 

Result-02: For a Reference String Where First Half String Is a Mirror Image Of Other Half-

 

For such a reference string,

  • Optimal page replacement algorithm replaces the least recently used page or firstly arrived page to minimize page faults.
  • This is because such a page will be required after the longest time.
  • Thus, Optimal page replacement algorithm acts as LRU and FIFO page replacement algorithm.

 

In other words,

  • LRU and FIFO page replacement algorithm will behave as Optimal page replacement algorithm.
  • LRU and FIFO page replacement algorithm gives the optimal performance.

 

Example-

 

Consider the following reference string where first half string is a mirror image of other half string-

1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1

 

Here,

  • Optimal, LRU and FIFO page replacement algorithms replaces the least recently used or firstly arrived page.
  • Least recently used or firstly arrived page will be required after the longest time.
  • Hence, all these algorithms give the optimal performance.

 

 

Total number of page faults occurred = 14

 

  • These are the minimum number of page faults that are possible.
  • If any other page replacement algorithm is used, it will surely give rise to more number of page faults.

 

Remember-

 

  • Optimal page replacement algorithm always gives the best performance in every scenario.
  • This is because it foresees the future and takes the form of an algorithm which gives the best performance in that scenario.

 

Next Article- Segmentation in OS

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Belady’s Anomaly | Page Fault | Paging

Operating System

Page Fault in OS-

 

Before you go through this article, make sure that you have gone through the previous article on Page Fault in OS.

 

We have discussed-

  • When a page fault occurs, the required page has to be brought from the secondary memory.
  • If all the frames of main memory are already occupied, then a page has to be replaced.
  • Page Replacement Algorithms help to decide which page should be replaced.

 

Effect of Increasing Number of Frames-

 

  • The number of page faults should either decrease or remain constant on increasing the number of frames in main memory.
  • But sometimes the unusual behavior is observed.
  • Sometimes, on increasing the number of frames in main memory, the number of page faults also increase.

 

Belady’s Anomaly-

 

Belady’s Anomaly is the phenomenon of increasing the number of page faults on increasing the number of frames in main memory.

 

Following page replacement algorithms suffer from Belady’s Anomaly-

  • FIFO Page Replacement Algorithm
  • Random Page Replacement Algorithm
  • Second Chance Algorithm

 

NOTE-

 

In the above discussion,

  • “Algorithms suffer from Belady’s Anomaly” does not mean that always the number of page faults will increase on increasing the number of frames in main memory.
  • This unusual behavior is observed only sometimes.

 

Reason Behind Belady’s Anomaly-

 

  • An algorithm suffers from Belady’s Anomaly if and only if it does not follow stack property.
  • Algorithms that follow stack property are called as stack based algorithms.
  • Stack based algorithms do not suffer from Belady’s Anomaly.
  • This is because these algorithms assign priority to a page for replacement that is independent of the number of frames in the main memory.

 

Examples-

 

Following page replacement algorithms are stack based algorithms-

  1. LRU Page Replacement Algorithm
  2. Optimal Page Replacement Algorithm

Hence, they do not suffer from Belady’s Anomaly.

 

Stack Property-

 

Consider-

  • Initially, we had ‘m’ number of frames in the main memory.
  • Now, the number of frames in the main memory is increased to ‘m+1’.

 

According to stack property-

  • At each stage, the set of pages that were present in the main memory when number of frames is ‘m’ will be compulsorily present in the corresponding stages in main memory when the number of frames is increased to ‘m+1’.

 

The following illustrations explain it clearly.

 

Illustration-01: For Optimal Page Replacement Algorithm-

 

Consider the reference string is-

0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4

 

Now, observe the following two cases-

 

Case-01: When frame size = 3

 

 

Number of page faults = 7

 

Case-02: When frame size = 4

 

 

Number of page faults = 6

 

From here, we can observe-

  • At all the stages in case-02, main memory compulsorily contains the set of pages that are present in the corresponding stages in case-01.
  • Thus, optimal page replacement algorithm follows the stack property.
  • Hence, it does not suffer from Belady’s Anomaly.
  • As a proof, number of page faults decrease when the number of frames is increased from 3 to 4.

 

Illustration-02: For LRU Page Replacement Algorithm-

 

Consider the reference string is-

0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4

 

Now, observe the following two cases-

 

Case-01: When frame size = 3

 

 

Number of page faults = 10

 

Case-02: When frame size = 4

 

 

Number of page faults = 8

 

From here, we can observe-

  • At all the stages in case-02, main memory compulsorily contains the set of pages that are present in the corresponding stages in case-01.
  • Thus, LRU page replacement algorithm follows the stack property.
  • Hence, it does not suffer from Belady’s Anomaly.
  • As a proof, number of page faults decrease when the number of frames is increased from 3 to 4.

 

Illustration-03: For FIFO Page Replacement Algorithm-

 

Consider the reference string is-

0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4

 

Now, observe the following two cases-

 

Case-01: When frame size = 3

 

 

Number of page faults = 9

 

Case-02: When frame size = 4

 

 

Number of page faults = 10

 

From here, we can observe-

  • At stage-07 and stage-08 in case-02, main memory does not contain the set of pages that are present in the corresponding stages in case-01.
  • Thus, FIFO page replacement algorithm does not follow the stack property.
  • Hence, it suffers from Belady’s Anomaly.
  • As a proof, number of page faults increase when the number of frames is increased from 3 to 4.

 

NOTE-

 

In the above illustration,

  • FIFO Page Replacement Algorithm suffers from Belady’s Anomaly.
  • It would be wrong to say that “FIFO Page Replacement Algorithm always suffer from Belady’s Anomaly”.

 

To gain better understanding about Belady’s Anomaly,

Watch this Video Lecture

 

Next Article- Page Replacement Algorithms Important Results

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Page Replacement Algorithms | Page Fault

Operating System

Page Fault in OS-

 

Before you go through this article, make sure that you have gone through the previous article on Page Fault in OS.

 

We have discussed-

  • A page fault occurs when a page referenced by the CPU is not found in the main memory.
  • The required page has to be brought from the secondary memory into the main memory.
  • A page has to be replaced if all the frames of main memory are already occupied.

 

Page Replacement-

 

Page replacement is a process of swapping out an existing page from the frame of a main memory and replacing it with the required page.

 

Page replacement is required when-

  • All the frames of main memory are already occupied.
  • Thus, a page has to be replaced to create a room for the required page.

 

Page Replacement Algorithms-

 

Page replacement algorithms help to decide which page must be swapped out from the main memory to create a room for the incoming page.

 

Various page replacement algorithms are-

 

 

  1. FIFO Page Replacement Algorithm
  2. LIFO Page Replacement Algorithm
  3. LRU Page Replacement Algorithm
  4. Optimal Page Replacement Algorithm
  5. Random Page Replacement Algorithm

 

A good page replacement algorithm is one that minimizes the number of page faults.

 

FIFO Page Replacement Algorithm-

 

  • As the name suggests, this algorithm works on the principle of “First in First out“.
  • It replaces the oldest page that has been present in the main memory for the longest time.
  • It is implemented by keeping track of all the pages in a queue.

 

LIFO Page Replacement Algorithm-

 

  • As the name suggests, this algorithm works on the principle of “Last in First out“.
  • It replaces the newest page that arrived at last in the main memory.
  • It is implemented by keeping track of all the pages in a stack.

 

NOTE

Only frame is used for page replacement during entire procedure after all the frames get occupied.

 

LRU Page Replacement Algorithm-

 

  • As the name suggests, this algorithm works on the principle of “Least Recently Used“.
  • It replaces the page that has not been referred by the CPU for the longest time.

 

Optimal Page Replacement Algorithm-

 

  • This algorithm replaces the page that will not be referred by the CPU in future for the longest time.
  • It is practically impossible to implement this algorithm.
  • This is because the pages that will not be used in future for the longest time can not be predicted.
  • However, it is the best known algorithm and gives the least number of page faults.
  • Hence, it is used as a performance measure criterion for other algorithms.

 

Random Page Replacement Algorithm-

 

  • As the name suggests, this algorithm randomly replaces any page.
  • So, this algorithm may behave like any other algorithm like FIFO, LIFO, LRU, Optimal etc.

 

PRACTICE PROBLEMS BASED ON PAGE REPLACEMENT ALGORITHMS-

 

Problem-01:

 

A system uses 3 page frames for storing process pages in main memory. It uses the First in First out (FIFO) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults  that will occur while processing the page reference string given below-

4 , 7, 6, 1, 7, 6, 1, 2, 7, 2

Also calculate the hit ratio and miss ratio.

 

Solution-

 

Total number of references = 10

 

 

From here,

Total number of page faults occurred = 6

 

Calculating Hit ratio-

 

Total number of page hits

= Total number of references – Total number of page misses or page faults

= 10 – 6

= 4

 

Thus, Hit ratio

= Total number of page hits / Total number of references

= 4 / 10

= 0.4 or 40%

 

Calculating Miss ratio-

 

Total number of page misses or page faults = 6

 

Thus, Miss ratio

= Total number of page misses / Total number of references

= 6 / 10

= 0.6 or 60%

 

Alternatively,

Miss ratio

= 1 – Hit ratio

= 1 – 0.4

= 0.6 or 60%

 

Problem-02:

 

A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults  that will occur while processing the page reference string given below-

4 , 7, 6, 1, 7, 6, 1, 2, 7, 2

Also calculate the hit ratio and miss ratio.

 

Solution-

 

Total number of references = 10

 

 

From here,

Total number of page faults occurred = 6

 

In the similar manner as above-

  • Hit ratio = 0.4 or 40%
  • Miss ratio = 0.6 or 60%

 

Problem-03:

 

A system uses 3 page frames for storing process pages in main memory. It uses the Optimal page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults  that will occur while processing the page reference string given below-

4 , 7, 6, 1, 7, 6, 1, 2, 7, 2

Also calculate the hit ratio and miss ratio.

 

Solution-

 

Total number of references = 10

 

 

From here,

Total number of page faults occurred = 5

 

In the similar manner as above-

  • Hit ratio = 0.5 or 50%
  • Miss ratio = 0.5 or 50%

 

To gain better understanding about Page Replacement Algorithms,

Watch this Video Lecture

 

Next Article- Practice Problems On Page Fault

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.