In computer memory management, paging is a technique used by operating systems to manage virtual memory. Paging is a method of dividing a computer’s memory into smaller sections called pages, which can be swapped in and out of physical memory as needed. The page table is a data structure used by the operating system to keep track of which pages are currently in memory and which are not. Paging the page table is a technique used to reduce the overhead of page table access by breaking the page table into smaller pages.

Purpose of Paging the Page Table

The page table is used by the operating system to map virtual memory addresses to physical memory addresses. The page table can become quite large, particularly on systems with a large amount of memory. Paging the page table involves breaking the page table into smaller pages, which can be loaded into physical memory as needed. This reduces the overhead of page table access and allows the operating system to manage memory more efficiently.

Page Faults and Replacement Algorithms

Page faults occur when a process tries to access a page that is not currently in memory. When this happens, the operating system must load the required page from disk into physical memory. Replacement algorithms are used by the operating system to determine which pages should be swapped out of memory when new pages need to be loaded. Two commonly used replacement algorithms are the Least Recently Used (LRU) and First-In, First-Out (FIFO) algorithms.

Consider the following page reference string: 1,2,3,4,5,1,2,3,4,5 for a memory with three frames. We will use this reference string to illustrate how the LRU and FIFO algorithms work.

LRU Algorithm

The LRU algorithm replaces the page that has not been accessed for the longest period of time. In our example, the LRU algorithm works as follows:

  1. Load page 1 into frame 1. Page faults = 1
  2. Load page 2 into frame 2. Page faults = 2
  3. Load page 3 into frame 3. Page faults = 3
  4. Load page 4, replace page 1. Page faults = 4
  5. Load page 5, replace page 2. Page faults = 5
  6. Load page 1, replace page 3. Page faults = 6
  7. Load page 2, replace page 4. Page faults = 7
  8. Load page 3, replace page 5. Page faults = 8
  9. Load page 4, replace page 1. Page faults = 9
  10. Load page 5, replace page 2. Page faults = 10

Therefore, the LRU algorithm would have 10 page faults for the given reference string.

FIFO Algorithm

The FIFO algorithm replaces the page that has been in memory for the longest period of time. In our example, the FIFO algorithm works as follows:

  1. Load page 1 into frame 1. Page faults = 1
  2. Load page 2 into frame 2. Page faults = 2
  3. Load page 3 into frame 3. Page faults = 3
  4. Load page 4, replace page 1. Page faults = 4
  5. Load page 5, replace page 2. Page faults = 5
  6. Load page 1, replace page 3. Page faults = 6
  7. Load page 2, replace page 4. Page faults = 7
  8. Load page 3, replace page 5. Page faults = 8
  9. Load page 4, replace page 1. Page faults = 9
  10. Load page 5, replace page 2.

OS-2022

Q-1.

(a) Write are the functions of operating systems? write a note on multi programmed operating systems ?

(b) Distinguish between client server and peer to peer model of distributed systems .

Q-2.

(a) With a Neat Sketch, Describe the services that an Operating System provides to users, processes and other systems.

(b) What is meant by Storage Structure? Discuss Storage Hierarchy.

(c) Write the Advantages and Disadvantages of using the same system call interface for manipulating both Files and Devices.

Q-3.

(a) What are the criteria for evaluating the CPU scheduling algorithms? Why do we need it?

(b) Define process. Explain various steps involved in change of a process state with process state neat transition diagram.

Q-4.

(a) What is synchronization? Explain how semaphores can be used to deal with n-process critical problem.

(b) Define a thread. Give the benefits of multithreading. What resources are used when a thread is created?

Q-5.

(a) How dose deadlock avoidance differ from deadlock prevention? Write about deadlock avoidance algorithm in detail.

(b) Different between external fragmentation and internal fragmentation. How to solve the fragmentation using paging?

Q-6.

(a) What is the purpose of paging the page table? Consider the following page reference string 1,2,3,4,5,1,2,3,4,5 for a memory with three frames. How many page faults would LRU and FIFO replacement algorithm?

(b) What are the disadvantages of single contiguous memory allocation? Explain.

Q-7.

(a) Briefly explain about single-level, two-level and three Structured directories.

(b) What is disk scheduling? Explain the C-SCAN scheduling by giving an example.

Q-8.

(a) Interrupt and spooling.

(b) UNIX file system.

(c) Program and system threats.