CST-334 Week 4

 This week I learned more about managing free space in memory, more translation techniques using paging, and the different policies that determine when a page should be swapped out into disk. In memory, external fragmentation will cause free space to be chopped up into little pieces of different sizes. This may cause some requests to fail as there may be no space left to fit the request. To solve this problem, a free list data structure can be used to manage free space in the heap. A free list looks similar to a linked list data structure. Each node contains an address of where space is free and the length of that free space. When requesting in memory that may be smaller than what is available in a free chunk, the allocator will split a free chunk into two so it can satisfy the request. In the opposite case, when a chunk of memory is free, the allocator will coalesce free space. There are different strategies that are used for managing free space, best fit, worst-fit, and first-fit. Best-fit will search the free list for blocks just large enough to satisfy a request. Worst-fit will search the free list for the largest block to satisfy a request. Finally, first-fit will just allocate the first block large enough to satisfy a request.

Paging is a beneficial translation mechanism, as it causes minimal fragmentation in memory. However, paging contains additional overhead that can slow down translations. To solve this issue. The translation-lookaside buffer will create a cache of popular address translations (i.e. a temporal locality). When a VPN is cached, the PFN can be quickly found versus having to find the PFN from a page table.

Occasionally, there will not be enough memory in RAM (or maybe there is a running process that is not being utilized at the moment) and in these cases, it will be beneficial to move a page into disk. This is referred to as the swap space, as it is an area reserved for moving pages between memory and storage. To determine if a page is stored inside disk, a present bit is added the PTE. A 1 indicates the page is inside physical memory. and a 0 indicates a page is stored in disk.

There are different policies employed that determine when a page should be swapped out. These include, FIFO, LRU, and Belady. In the FIFO policy, the "oldest" element in cache will be evicted. In the LRU policy, the least-recently used element will be evicted. Finally, in the Belady policy, cache elements to be used furthest in the future will be evicted.

I think one of the easier topics for me this week was using the FIFO policy to determine which elements should be evicted. One of the harder ones to use was Belady as it can be a bit more difficult as there are more elements you have to keep track of. The Belady policy also raises some questions for me, as it does not seem very realistic to know what the future elements will be and I am curious what situations this policy will be useful for.