Mumbai University > Computer Engineering > Sem 3 > Data Structures

Marks: 10M

Year: May 2016

1. From lots of application of linked list, one of the application of linked list is Frame Management.
2. This interesting application of linked lists is found in the way some systems support virtual memory.
3. Virtual memory is a mapping of address space that allows a process to execute without being completely in physical memory, the real memory of the system. One advantage of this is that a process can make use of an address space that is much larger than that which the physical memory of the system would allow otherwise. Another advantage is that multiple processes can share the memory of the system while running concurrently.
4. A process running in virtual memory deals with virtual addresses. These are addresses that seem like physical addresses to the process, but that the system must translate before using. Address translation takes place using a page table and is fast due to dedicated hardware. Each process has its own page table that maps pages of its virtual address space to frames in physical memory. When a process references a particular virtual address, the appropriate entry in its page table is inspected to determine in which physical frame the page resides. When a process references a virtual address not yet in a frame, a page fault occurs and a frame is allocated in physical memory.
5. The below example addresses the management of frames that has just been described. For this, two functions are presented; alloc_fiame and free_fmme. The alloc_fiame and free_frame functions employ a linked list to maintain the frames that are available to be allocated.
6. The alloc_frame function retrieves the number of a free frame from a list of available frames. Given a specific page, this number is placed in the page table to indicate in which physical frame the page is to reside. The free_frame function accepts a frame number and places it back into the list of available frames once a page has been removed from physical memory. Both functions assume that before either is called, the operating system has inserted into the list all frames that it wishes to make available. The example for circular lists later in this chapter addresses what happens when allot frame is called and the list is empty. A linked list is a good way to manage frames because frame allocation involves frequent insertions and deletions, and these operations are performed at the head of the list. The runtime complexity of both alloc_fiame and free_frame is O(1) because the two functions simply call list_rem_next and list_ins_next respectively, which are both O(1) operations.