Operating Systems: A brief overview

This is part 3 /3
Read part 1 here and part 2/3 here.

Memory Management

In multi programming systems, what was considered large memory size 5 years ago, is obsolete today, what is considered large memory size today, is going to be obsolete in 5 years. So there is never going to be “enough memory”. Hence to optimally use the memory space available, we need memory management.

The Operating system allocates memory for running multiple programs. The OS will also need to move ports between the main memory and secondary memory.

Memory management requirements from an OS:

1. Relocation
   OS is responsible to load a process into any location in the main memory.
   The operating system should be able to relocate the process to a completely different section of main memory during it’s lifetime.
2. Protection
   The operating system should be the only entity allowed to access all of main memory.
   The process cannot access memory outside of its allocation.
3. Sharing
   Some processes may use the same code or data.
4. Logical Organization
   Having a pre-existing set of of modules, shared objects and dynamically linked libraries should be allowed to save memory.
5. Physical Organization
   The OS should be able to seamlessly map logical memory to physical memory.

Logical VS Physical Memory

CPU’s hardware memory management unit is responsible for converting logical address to physical address during runtime. Uses OFFSET

Partitioning Strategies

1. Fixed Partitioning

Main memory is divided into Static number of parts. Each process is allocated one part with size that is greater than or equal to the need of the process.
Problems:
Internal fragmentation (the extra space inside the partitions that is left is wasted)
Limit on the number of processes
In case of unequal partitioning — which partition to use?

2. Dynamic Partitioning

Partitions are created for exactly as much memory as the process requires.

Problems:
External Fragmentation (the spaces left in between the allocations is wasted)
Dynamic partitioning requires compact storage which is an expensive solution

How does OS fit the partitions?

i. Best Fit: — Finds the partition which is the closest to the size needed and allocate the same. This method causes internal fragmentation.
ii. First Fit — Allocates the first partition that fulfills the memory requirements. (NOTE: scans from the beginning of the memory for every allocation). This method minimizes the CPU time.
iii. Next Fit — Allocates the next partition that fulfills the memory requirements. (NOTE: scanning starts from the previously allocated partition)

3. Buddy System

img source: https://media.geeksforgeeks.org/wp-content/uploads/Capture-34.png

Buddy system, is a compromise between fixed and dynamic partitioning. The remainder memory is divided by 2 in each iteration until a best / least fit is found. This strategy makes the structure of the OS much simpler and is used by LINUX.

Problem:
This method causes both external and internal fragmentation.

4. Paging

In paging, the memory is broken down into small equal sized frames, like video reels. The OS takes advantage of the fact that RAM has an access time of O(1) for any memory location.

First, the program is divided into pages which are in turn stored in the non continuous frames created. The operating system then records frame number for each pages in a page map table which is in turn stored in the PCB.

The hardware’s MMU (Memory Management Unit) needs to be able to query the Page Map Table, hence the format of the Page Map Table has to be agreed upon before hand.

Benefits of Paging:

• No extended fragmentation
• Very minimal internal fragmentation
• Easy protection
• Easy relocation
• Easy sharing

Problems with Paging:

• Converting the logical to physical address
• Dealing with very large processes

To calculate PAGE: the standard method is to use bit shifts since it is given that pages are always in multiple of 2s.

To calculate OFFSET: the standard method is to use XOR.

Physical Address 
        = lookupInPMT(logicalAdress/pageSize) 
        *pageSize
        +(logicalAddress%pageSize)

5. Segmentation

Segmentation is very similar to paging, except the fact that in segmentation, the frames created are of unequal sizes. This makes the process less prone to fragmentation, even-though converting logical to physical address becomes more complex in segmentation.

Virtual Memory

Virtual Memory always assumes paging / segmentation is valid on the system. For an application to run, all memory doesn’t always need to be in the main memory. Hence we swap pages of the process onto the hard drive to free up extra space.

Any running program has 2 types of memory sets:

i. Resident Set — The processes in the main memory.
ii. Working Set — The process actually in use at the time.

We know that Working set ⊆Resident set. Now Page Faults occur when the (process from working set) != (process in the resident set)

Benefits of Page Faults:

• It creates an illusion of having more memory than what exists.
• Can remove unused pages (flash screen, cached memory)
• More processes can run in the system leading to a better performance.

This was part 3 of my 3 part series on Operating systems. 
Part 1 dealt with understanding computers, defining and understanding OS, kernels, multi programming, processes and its states. 
Part 2 will cover topics like context switching, threads, mutual exclusion, semaphores and deadlocks.
Other topics that you is look into:
Lookup problem, Replacement policies, get more resources here.