Explain any one application of linked with an example

1views

written 6.2 years ago by

kaivanshah • 280

Linked list is used to implement Frame Management within Virtual memory.
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.
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. 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.
For Example of frame management consider two functions ; alloc_frame and free_frame. The alloc_frame and free_frame functions employ a linked list to maintain the frames that are available to be allocated.
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 function 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.

ADD COMMENT EDIT