HOME

Top 10 List of Week 05

1. The Need of Virtual Memory
   Computer has a finite amount of RAM. So memory can run out, especially when running multiple programs at the same time. Virtual memory makes it possible to compensate for a computer’s physical memory shortages by temporarily transferring data from RAM to disk storage. With VM, a system can load larger programs or multiple programs running at the same time - operating as if it has infinite memory.

2. VM Advantages and Disadvantages
   Advantages: fast (when only one segment of program is required for its execution), help implement multiprogramming environment and also allows to run more application at once, fit many large programs into small programs, data sharing between memory, and more.
   Disadvantages: the main disadvantage is that it slows down the computer because the data has to be mapped between virtual and physical memory.
   The guru99 link above compares the advantages vs disadvantages in a clear manner.

3. Memory Fragmentation
   I will give you an example case which was explained by Gary. If you try to run 2 programs, 1 bit for the first and the other bit for the second program, but the the first program exit. The second program will fill in the first program place but the second one could be smaller and has a memory gap left. For example, the third program comes in but can’t fit the gap and put in another bit. If this goes over and over, the gap could consume too much space because these tiny gaps. This called memory fragmentation. This is why paging and segmenting comes into play.

4. Paging and Segmentation
   How VMs are handled? There are two approaches: Paging and Segmentation. Paging divides memory into sections or paging files. When computer uses up its RAM, pages that aren’t in use are transferred to the section of hard drive designated for VM using a swap file. Meanwhile, segmentation divides VM into segments of different length. Similar concept with paging, segments not in use in memory can be moved to virtual memory on the hard drive. Some VM system combines both. The primary benefit is that memory is used more efficiently. With VM computer can run programs larger than physical memory without added cost or hardware. Frees application from managing shared memory, which can sometimes leads to accidental overwrite or accesing sensitive information

5. Virtual Space for Apps and MMU
   When app wants to access a particular address, there is a piece of hardware in CPU called MMU (memory management unit). It maps the virtual address that it runs on to an actual physical address in memory. Each app thinks it as the only app and can access all memories it is being given to. This is called as virtual address space, where memory is partitioned into different sets of addresses and allocated to different apps. Partitioning the memory is the job of the OS. If there are 2 apps where each one has 0 address, they refer to different location in physical address. This is what mapping is. Advantages:
   1. Each app is self contained. It doesn’t write over other app’s memory space because it has its own address space.
   2. It does not matter where the app is locationed in the memory because the MMU does the mapping between the virtual - physical addresses.
   3. The app does not have to be in one continuous block in the memory, it can be splitted up into different parts. And again, it is the job of MMU to map the vaddress into physical RAM.

6. Demand Paging
   The idea is that when a process is swapped in, its pages are not swapped in all at once. Instead, they are swapped in only when the process needs them, or you can say on-demand. This is called lazy swapper or pager. Deciding whether to keep pages in the main memory or secondary memory is difficult because we cannot say in advance. Thus, Demand Paging suggests keeping all pages of the frames in the secondary memory until they are required. In other words, it says that do not load any page in the main memory until it is required.

7. Page Fault
   A page fault happens when a running program accesses a memory page that is mapped into the virtual address space, but not loaded in physical memory. MMU will raise a page fault. It goes back to kernel and say “hey i can’t find the address” which can happen for one of three reasons:
   a) App try to access addreess that is not allowed to access. The address memory has not been alocated.
   b) Lazy allocation: kernel say you can have that, but it won’t actually give you the Physical page of RAM until it start to write to it. The MMU will be reprogrammed and the whole thing will start again and the address is found on physical RAM.
   c) We used to use that memory but now it’s being swapped. the kernel will go and get that page from the compressed RAM (Z SWAP), uncompressed, put in physical memory, MMU reprogram, and the whole thing can resume.

8. Page Replacement Algorithms
   A page replacement algorithm is needed to decide which page needs to be replaced when new page comes in. There are some possible algoritms such as:
   First In First Out (FIFO) ; OS keeps track of all pages in the memory in a queue, the oldest page is in the front of the queue. The front page is selected for removal whenever a page needs to be replaced.
   Optimal Page replacement ; In this algorithm, pages are replaced which would not be used for the longest duration of time in the future.
   Least Recently Used; In this algorithm page will be replaced which is least recently used.
   And a lot more! This website (https://www.gatevidyalay.com/page-replacement-algorithms-page-fault/) explains deeper by giving a real example how the algorithm works on an array of numbers.

9. Address Translation
   The Physical Memory is divided into different pages. The page size is typically 4K. Using paging, 300 MB app only need 77000 entries in the look up table with 4 bytes per every entry. What happens when an app request something over virtual addres. MMU -> find which page is in -> redirect to address of page. What happen if the page is in the middle of the page? Here comes the address translation proccess. So the first 12 bits(offset) of VA is copied directly to PA, then the remaining 20 bits address is used as look up. The address is looked up in the page table -> Found -> Give the 20 bits of upper part. Then, the combination of the page address + offset of 12 bits -> actual address in RAM. This udacity video nicely explain the mapping virtual physical memory https://www.youtube.com/watch?v=c5TD8QyRJcA

10. Memory Cache (TLB)
    For one RAM access, the process that goes is; to access a virtual address, MMU access physical memory to access entry in the table. Then, MMU can start translating the virtual address to physical memory. Therefore, there is multiple RAM accesses happening for one RAM access inside the app. It can be 2 RAM access, 3 RAM access, etc and it makes the process SLOW!But how does the CPU design this better? Cache of recently looked up addresses with Translation Looked Aside Buffer (TLB). Whenever an address is translated, it goes to the cache. The next time the address is the needed it will look at TLB ( cache ) to look up the page size.