HOME

Top 10 List of Week 05

1.Virtual Memory
Virtual memory is a storage allocation scheme in which secondary memory can be addressed as though it were part of main memory. The addresses a program may use to reference memory are distinguished from the addresses the memory system uses to identify physical storage sites, and program generated addresses are translated automatically to the corresponding machine addresses. The size of virtual storage is limited by the addressing scheme of the computer system and amount of secondary memory is available not by the actual number of the main storage locations. It is a technique that is implemented using both hardware and software. It maps memory addresses used by a program, called virtual addresses, into physical addresses in computer memory.

1. Demand Pagging
   Demand pagging is the process of loading the page into memory on demand (whenever page fault occurs). The process includes the following steps:
   

   If CPU try to refer a page that is currently not available in the main memory, it generates an interrupt indicating memory access fault.
   The OS puts the interrupted process in a blocking state. For the execution to proceed the OS must bring the required page into the memory.
   The OS will search for the required page in the logical address space.
   The required page will be brought from logical address space to physical address space. The page replacement algorithms are used for the decision making of replacing the page in physical address space.
   The page table will updated accordingly.
   The signal will be sent to the CPU to continue the program execution and it will place the process back into ready state.
   

2. Copy on Write
   Copy on Write or simply COW is a resource management technique. One of its main use is in the implementation of the fork system call in which it shares the virtual memory(pages) of the OS. In UNIX like OS, fork() system call creates a duplicate process of the parent process which is called as the child process. The idea behind a copy-on-write is that when a parent process creates a child process then both of these processes initially will share the same pages in memory and these shared pages will be marked as copy-on-write which means that if any of these processes will try to modify the shared pages then only a copy of these pages will be created and the modifications will be done on the copy of pages by that process and thus not affecting the other process.
   

3. 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. Since actual physical memory is much smaller than virtual memory, page faults happen. In case of page fault, Operating System might have to replace one of the existing pages with the newly needed page. Different page replacement algorithms suggest different ways to decide which page to replace.
   

4. Page Replacement
   

   First In First Out (FIFO) : the operating system keeps track of all pages in the memory in a queue, the oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.
   Optimal Page replacement : pages are replaced which would not be used for the longest duration of time in the future.
   Least Recently Used : page will be replaced which is least recently used.
   

5. Frame Allocation
   An important aspect of operating systems, virtual memory is implemented using demand paging. Demand paging necessitates the development of a page-replacement algorithm and a frame allocation algorithm. Frame allocation algorithms are used if you have multiple processes; it helps decide how many frames to allocate to each process. The two algorithms commonly used to allocate frames to a process are:
   

   Equal allocation: In a system with x frames and y processes, each process gets equal number of frames, i.e. x/y.
   Proportional allocation: Frames are allocated to each process according to the process size.
   The number of frames allocated to a process can also dynamically change depending on whether you have used global replacement or local replacement for replacing pages in case of a page fault.
   Local replacement: When a process needs a page which is not in the memory, it can bring in the new page and allocate it a frame from its own set of allocated frames only.
   Global replacement: When a process needs a page which is not in the memory, it can bring in the new page and allocate it a frame from the set of all frames, even if that frame is currently allocated to some other process; that is, one process can take a frame from another.
   

6. Thrashing
   Thrashing is a condition or a situation when the system is spending a major portion of its time in servicing the page faults, but the actual processing done is very negligible. The basic concept involved is that if a process is allocated too few frames, then there will be too many and too frequent page faults. As a result, no useful work would be done by the CPU and the CPU utilisation would fall drastically. The long-term scheduler would then try to improve the CPU utilisation by loading some more processes into the memory thereby increasing the degree of multiprogramming. This would result in a further decrease in the CPU utilization triggering a chained reaction of higher page faults followed by an increase in the degree of multiprogramming, called Thrashing.
   

7. Allocating Kernel Memory
   

   Buddy allocation system : a larger memory block is divided into small parts to satisfy the request. This algorithm is used to give best fit. The two smaller parts of block are of equal size and called as buddies. In the same manner one of the two buddies will further divide into smaller parts until the request is fulfilled. Benefit of this technique is that the two buddies can combine to form the block of larger size according to the memory request.
   Slab Allocation : eliminates fragmentation caused by allocations and deallocations. This method is used to retain allocated memory that contains a data object of a certain type for reuse upon subsequent allocations of objects of the same type. In slab allocation memory chunks suitable to fit data objects of certain type or size are preallocated. Cache does not free the space immediately after use although it keeps track of data which are required frequently so that whenever request is made the data will reach very fast.
   

8. Prepaging
   In demand paging, that page is brought to the main memory which is actually demanded during the execution of the process. But, in pre-paging pages other than the demanded by the CPU are also brought in. The OS guesses in advance which page the process will require and pre-loads them into the memory. It saves time when large contiguous structures are used. Consider an example where the process requests consecutive addresses. So, in such cases, the operating system can guess the next pages. And, if the guesses are right, fewer page faults will occur and the effective memory access time will increase.
   

9. Translation Lookaside Buffer (TLB)
   Translation Lookaside Buffer (TLB) is a special cache used to keep track of recently used transactions. TLB contains page table entries that have been most recently used. Given a virtual address, the processor examines the TLB if a page table entry is present (TLB hit), the frame number is retrieved and the real address is formed. If a page table entry is not found in the TLB (TLB miss), the page number is used as index while processing page table. TLB first checks if the page is already in main memory, if not in main memory a page fault is issued then the TLB is updated to include the new page entry.