Compare the memory management of windows with linux

Introduction

In this term paper, I have explained important concepts of memory management and compared the memory management system of windows and Linux.

• The memory management system is one of the important parts of the operating system.
• Its basic function is to manage the memory hierarchy of RAM and secondary memory devices.
• There is always a need of more memory than physical memory. Memory management allows this to be done through the concept of virtual memory.
• Virtual memory can be many times larger than the physical memory.
• The most important task of memory management includes allocation and dealloacation of memory to the processes.

Memory management system provides:

1. Large Address Space
2. Protection
3. Memory Mapping
4. Physical Memory Allocation for Processes
5. Shared Virtual Memory.

Some Important Terms and Concepts

Logical and physical Address

• Logical address is generated by CPU and also called as virtual address.
• Physical address is the address seen by the Memory Unit.

Memory Management Unit

• It is a hardware that maps logical address to physical address.
• Value of relocation register is added to value generated by user process.

Paging

• The logical address space is divided into fixed size blocks called pages. The pages are located at different memory locations in the memory.
• Physical address space is divided into fixed size blocks called frames.
• Address translation is actually done by the MMU (Memory Management System) by using a page table as shown in the figure below.

MMU converts logical addresses to physical addresses that consist of a page frame number and an offset within that page.

Address Translation scheme

Logical address generated by the CPU is divided into two parts-

Page number (p) and page offset (d)

Page number- it contains base address of each page in physical memory.

Page offset- it defines physical address that is sent to memory unit.

Memory Protection

• A protection bit is associated with each frame.
• Valid-invalid bit is added to each entry in the page table.
• If bit is valid it means page is valid and is present in process’s logical address space
• If bit is invalid it means page is invalid and is not present in process’s logical address space.
• If the page is not present, it leads to generate page fault.

Virtual Memory

Virtual addresses are created by the CPU. We require mapping function to implement the concept of virtual memory. Mapping performs address translation, converting virtual address to physical address. Virtual address is the address used to refer a memory location and physical address is the actual memory location.

Memory Compaction

It is the technique of relocating all occupied areas of the memory to one end so as to get a large block of free memory space.

It can be done under three conditions-

1. As soon as process terminates.
2. When a new job cannot be loaded into memory due to fragmentation.
3. At fixed time intervals.

Comparison

1) Data structures

Windows

• Windows uses tree data structure.
• Each node of the tree is called Virtual Address Descriptors (VAD).
• VAD marks each node as free, committed or reserved.
• Committed nodes are those nodes that are currently being used.
• Free nodes are unused nodes.
• Reserved nodes cannot be used until reservation is lifted off.

Linux

• It uses linked list data structure.
• It maintains a list of vm_area_structs.
• This list is searched whenever a page is to be found.
• It also records the range of address, protection mode and the direction in which it grows (up or down).
• If number of entries becomes more than 32, Linux converts linked list into a tree.
• Linux uses data structure depending upon the situation.

2) Distribution of Process Address Space

Windows

• Windows on 32 bit x86 systems can access up to 4GB of physical memory.
• Windows allows each process to have its own 4GB logical address space by using paging.
• The upper 2GB is kept for windows kernel mode.
• The lower 2GB of the address space is reserved for user mode.

Linux

• 3GB of memory space is reserved for user mode
• 1GB is kept for Kernel mode.

3) Paging

Linux uses demand paging with no pre paging

• Linux do not swap the entire process instead uses a lazy swapper.
• It never swaps a page into the memory unless that page is needed.
• Instead of swapping in a whole process, the pager swaps only necessary pages into memory.
• It thus avoids reading pages that will not be used, this decreases swap time and amount of physical memory required.
• To distinguish between the pages that are in memory and are on the disk we use valid and non valid bits.
• If bit is valid it shows that the page is legal and is in the memory and if bit is set to invalid it indicates that it is on the disk.

Linux uses three level paging

Windows uses cluster demand paging

• Pages are brought in the memory when they are needed.
• Instead of bringing pages one by one, eight pages are brought in the memory simultaneously.
• It makes use of working set model.
• Working set is the amount of memory currently assigned to the process.
• It contains the pages that are in the main memory.
• Size of working set can be changed accordingly.

Windows uses Two Level Paging

4) Address structure

Linux

Linear address is broken into four parts:

• Global Directory.
• Middle Directory.
• Page Table
• Offset.

Windows

Address is divided into two parts:

• Page number
• Page offset

5) Page replacement

Linux uses LRU

• Least Recently Used Page Replacement Algorithm (L.R.U.)
• The page that is not used for a long period of time is selected as victim page and is replaced.
• Implemented in two ways- Counters and stack.
• In counters, each page table entry is associated with a time-of-use field. The page with smallest time value is replaced.
• In stack, the page at the bottom is removed and put on the top of the stack. Least recently used is always at the bottom of the stack.

Here is an example of LRU page replacement algorithm.

No. of page faults=12

Windows uses FIFO

• First in First out Page Replacement Algorithm (F.I.F.O.).
• The oldest page is chosen for replacement.
• It suffers from be lady’s anomaly.
• Page fault rate may increase when we increase number of frame.
• It has low performance.
• It has maximum number of page faults.

Here is an example of FIFO page replacement algorithm.

No. of page faults =155)

Windows divides virtual pages into four lists:-

• Modified Page List.
• Stand-by Page List.
• Free Page List.
• Zeroed Page List.

Pages that have been modified are in modified page list. After writing to disk they are stored in standby list. Pages that have not been modified go to stand by list. The modified page list is called dirty list and standby list is called clean list.

Linux divides the pages into four lists:-

• Active List.
• Inactive-dirty List.
• Inactive clean List.
• Free List.

Active pages are on the list 1. If some of the pages are not active, their age decreases and goes down to zero, which means it has to be removed.