Paging

Paging is a memory management scheme that permits physical address space of a process to be non contiguous. 

In paging, physical memory is partitioned into fixed size blocks called FRAMES and logical memory is partitioned into block of same size called PAGES. The size of page is equal to frame size. Every CPU generated address is now divided into two parts 

i. Page Number (p): Used as an index into page table. 

ii. Offset

In paging, it is not necessary for a free frame to be contiguous. It can be allocated to a process that needs it. Thus there is no external fragmentation and there is no need for compaction.

Page table contain address of each page in physical memory. That is page table contain frame number in which page is available.  The base address plus page offset gives physical memory address. 

To provide memory protection, page table consists of additional bit known as valid or invalid bit. The bit is set to valid if page is in logical address space and is valid. It is set to invalid if page is not in the logical address space. Valid and Invalid bit is set by OS for each page. 

When a process arrives, its size in pages is examined. Each page of process needs one frame. Process of n pages requires that n frames are available. If frame is available, first page is loaded into one of the available frame and entry of frame number is made in the page table. The next page is now loaded and entry is made in page table. The process is repeated for all the pages of the process. 

<diagram>

In addition to page table, OS maintains a frame table. Frame table has one entry for each frame indicating whether it is free or allocated. If frame is allocated, frame table stores process name and its page number. 

Structure of Page Table

Some the methods to structuring the page table is as follows

1. Hierarchical Paging: In a 32 bit logical address space and page size of 4 KB (212), page table consist of 232/212 entries. The page table becomes very large. One solution is to divide the page table into smaller pieces. When we divide page table in two parts it is called two-level paging algorithm.  The table is also known as forward mapped page table because address obtained by moving for outer page to inner page.

In a 32 bit logical address space and page size 4KB (212), 12 bits consist off set. The remaining 20 bits page number is divided into two parts:  p1=10 bits for page number and p2=10 bits for offset. P1 is index number of outer page table and p2 is displacement of outer page table.

<diagram1>

2. Hashed Page Tables: In hashed page tables the hash value is the page number. Each entry in a hash table contains a linked list of elements that hash to same location. Each element consist of three parts

i. Logical page number

ii. Value of mapped page frame

iii. A pointer to next element of linked list

The logical page number is compared with the field 1 of first element in the linked list. If there is a match, the corresponding frame number present in field 2 is used to form the desired physical address. If no match, next entries are searched. 

Hashed Page Table

3. Inverted Page tables: An inverted page table has one entry for each frame of memory.  Each entry consist of logical address of the page and the information of a process to which the page belongs; i.e. process id. It means there is only one page table is in the system.  

Here, logical address consist of three parts

i. Process Id

ii. Page Number 

iii. Offset

The inverted page table is sorted by physical address but searching is done on logical address. When memory reference occurs, page table is searched for a match. If match is found at position x, then the physical address is (x,offset). If no match is found, an illegal address is accessed. 

Functions of Operating System

PROCESS MANAGEMENT

• A process is defined as a program in execution. 
• It is more than program code.

 

To accomplish its task, a process needs certain resources like CPU time, memory files and I/O devices and as a process executes it changes its states. Each process may be in one of the following stages

• New: The process is being created.
• Running: Instruction are being executed.
• Waiting: Waiting for some resource like memory, I/O , CPU time etc.
• Ready: Process is in main memory and waiting to be assigned to CPU.
• Terminate: The process finished execution.

An Operating System performs the following activities for processor management.

• Creating and deleting both user and system processes.
• Suspending and resuming processes.
• Provide mechanisms for process synchronization.
• Provide mechanism for process communication.

MEMORY MANAGEMENT

Main Memory is an array of addressable words or bytes that is quickly accessible. Main Memory is repository of quickly accessible data shared by CPU and I/O devices. Main Memory is volatile. Main memory is only storage device that CPU is able to address and access directly. For a program to be executed, it must be loaded into main memory. To improve CPU utilization and speed up computer response time, we keep several programs in memory.

The operating system is responsible for following activities in connection with the memory management

• Keeping track of which part of memory are currently being used and by whom
• Deciding which processes are to be loaded into memory
• Allocating and deallocating memory space as needed
• Swap IN and Swap OUT of processes
• Managing the sharing of memory between process

FILE MANAGEMENT

A file is a collection of related information defined by the user. The files are organized into directories and sub-directories. These files resides permanently on secondary storage . All the secondary storage device have different characteristic in terms of physical organization, storage capacity, access methods and data transfer rate etc. Therefore File Management is one of the most important function of an operating system.

The Operating System is responsible for the following activities for file management

• creating and deleting files
• creating and deleting directories.
• Supporting primitives for file and directories manipulation.
• Mapping file on to secondary storage.
• Backing up files on permanent storage media.

I/O MANAGEMENT

The two main jobs of computer are I/O and processing. The role of the operating system in computer I/O is to manage and control I/O operations. Because I/O devices vary widely in their function and speed, a variety of methods are needed to control them. These methods form the I/O sub-system.

The operating System is responsible for the following activities for I/O Management

• buffering: Stores data being transferred between two devices or between device and application. Reasons of Buffering: Cope with a speed mismatch between the producer and consumer. and Provide adaptions for devices that have different data transfer sizes.
  
• caching: Region of fast memory that holds copies of frequently used data.
  
• spooling:.Is a buffer that holds output for a device such as printer
  
• A general device driver interface: a translator that takes input  consist of high level commands and gives output consists of low level hardware specific instructions that are used by hardware controller
  
• Drivers for specific hardware devices.

Only Device Driver know the complexities of the specific devices to which it is assigned.