Operating System Chapterwise Notes of Galvin:Virtual Memory

Pages>> 1 2 3 4 5 6 7 8
Here we are giving chapter wise notes of operating system based on operating system concepts by galvin

Virtual Memory

q) how virtual memory is different from other memory management techniques?
a) it allows the execution of the process that need not be comletely in memory.

q) what are its advantages?
a) the process may be larger than the physical memory.allows processes to easily share files and address space.

note:- entire program is not needed always, onlysometimes:-
1) code that handles exceptions.
2) arrays ,lists,tables are often allocated more memory, than actually needed.

benefits of keeping in memory only the required instructins and data:-
1) more programs can be there in memory, more cpu uilization and throughput.
2) less I/O required to load or swap the processes.

note:- systems that support virtual memory, donot bother programmer to design overlays.

q) what is key concept behind virtual memory?
a) demand paging. demand segmentation can also be used, but segment replacement algorithms are very complex as they have variable sizes.

note:- here we can use pager instead of swapper.now a process needs to be in memory ,before its execution starts.but now instead of bringing all pages into memory, pager does not bring a page unless it is required.in begining pager makes a guess,which pages will be used and loads only those pages into memory, thus decreasing the swap time, and memory needed.

q) how we modify page table to know that which pages are in memory and which are not?
a) help of valid-invalid bit is taken.if a bit is valid, it means it is in logical address space and also is present in memory, if its invalid , it means either the page in not a valid logical address or right now its on disk and not in memory.

note:- page table entry for page on disk , contains invalid bit, or address of page on disk.

q) what is page - fault trap?
a) access to page that is currently not in memory is called page-fault.mapping hardware then sends trap to the o.s.

q) what is pure demand paging?
a) this concept says that never bring a page into memory until it is required.a process could start with no page in the memory.

q) what is swap space?
a) the portion of disk that contains the pages not in memory.

note:- if a page fault occurs when fetching a instruction , it needs to be fetched again. if page fault occurs when fetching an operand, then fetch and decode of instruction need to be done again.

note:-trying to increase degree of multiprogramming can increase the page fault rate.

q) what is modify/dirty bit?
a) when a page fault occurs and no free frame is there, we need to swap out a victim page and bring in the desired page.this takes double time to service page fault ie swapin+swapout. to reduce it we use modify bit.it is attached to each frame in physical memory. if frame is modified it is set. in this case it needs to be written back to memory. but if not changed only we swap in desired page overwritting it.read only pages help a lot in reducing the page fault service time, if they are the victims.

q) what do frame allocation algorithms do?
a) decide how many frames are to be allocated to a process.it also has a lot of affect on the page fault rate.

q) what is refernce string?
a) the string of memory references is called reference string.

q) how to implement FIFO page replacement algorithm?
a) way1) with each page in memory associate the time, when it came in, then remove the oldest page.
way2) make a FIFO queue of pages and remove 1 at the head.

q) what is belady's anomaly?
a) FIFO(some others are also there) suffers from belady's anomaly. here the number of page faults increase even with allocation of more frames to the process.

note:- of all the page replacement algorithms OPR has least page fault, though not practically possible.

q) what is logic of OPR?
a) remove the page that will not be used for the longest period of time.

q) what is logic of LRU?
a) here the page that has not been used for a long period of time is replaced. it is approximation to OPR.with each page its time of last use is attached.

q) implementation of LRU?
a) 1) counters:- with each page we have time-of-use field and we add to cpu a clock or counter, which is incremented for each memory reference.contents are copied to the referenced page.here we need to search page with least count. here we write to memory, and also counter is to be maintained to prevent overflow.

2) stack:- stack of page numbers. a page when referenced is moved to the top of stack.tail pointer points to LRU page easy to implement using doubly linked list.

note:- OPT and LRU donot suffer from belady's anomaly.

q) what are stack algorithms?
a) these never exhibit belady's anomaly.these are algorithms for which the set of pages in memory for n frames is always the subset of set of pages for n+1 frames.

note:- these algorithms slow down the process execution as for each memory reference , there is a need to update the timer or stack structures.

q) what are referenece bits?
a) its a technique used to assist LRU. with each page we associate a reference bit.initially all bits are cleared to 0 by O.s when it is referenced the hardware sets it to 1. so we can know which pages have been used and which have not been.

q) what additional feature added to reference bit?
a) now with each page a byte is attached ie 8 bits.it stores history.every interval(set by hardware), the refernce bit is set to high order bit, and all other bits are moved 1 postion right. smallest number is LRU.if same value FIFO is used.

q) what is 2nd chance alghorithm?
a) here only 1 refrence bit is used. if page is to be replaced it's reference bit is examined.if 0 it is replaced.if not, then it gets a 2nd chance ie bit is cleared and arrival time is set to current time, and moves further. it can also be implemented using the circular queue,where page with 0 reference bit is searched. if all are set, it acts as FIFO.

note:- we can also enhance the 2nd chance algorithm by using modify bit also along with. now we get 3 classes here:-
(0,0),(0,1),(1,0),(1,1).
case 1 : neither recently used nor modified- best page to replaced.
case 2 : not recently used but modified - not quite as good, page need to be written out on the disk before replacement
case 3 : recently used but not modified - probably will be used again soon
case 4 : recently used and modified - probably will be used again soon.

q) what are counting based page replacement algorithms?
a) here for each page , count the number of refernces made to it.
2 types are there:-
1) LFU:- page with low count is removed.
disadvantage:- a page that was used heavily in begining, but not needed now remains in memory.

2) MFU:-it argues that page with small count has just been brought in , and yet to be used.

note:- the minimum number of frames to be allocated to a process is also determined by the instruction -set architecture.ie enough pages must be there that the single instruction can reference.

note:- limit has been put on the levels of indirection to support virtual memory in context of minimum number of frames to be allocated to a process.

q) what is meant by equal allocation?
a) if we have m free frames and n processese, give each process m/n frames.

q) what is proportional allocation?
a) here we allocate number of frames to each process as s(i)/S *m; where S is total sum of virtual memory for each process. s(i) virtual memory for individual.

note:- we also need to consider the priority of the process while allocating frames rather than size.

q) what is global replacement and local replacement?
a) global replacement allows to select replacement frame from all frames even allocated to other processes.local replacement requires each process select replacement frame from its own set of allocated frames.

note:- higher priority process can select replacement frame from its own set or from lower proirity processes.

q) what is disadvantage of global page replacement?
a) a process cannot control its page faults.

note:- if number of frames allocated to a process fall below the minimum required by computer architecture, then process need to be swapped out completely.

q) what is thrashing?
a) its high paging activity, where process spend more time paging than execution.

note:- thrashing occurs because of over multiprogramming and global replacment.all processes are in pager device queue than ready queue.

q) how to prevent thrashing?
a) by allocating the process the number of frames it need. for this we use the locality model of process execution.

q) what is locality?
a)it is set of pages that are used together.program structure defines locality. eg:- a procedure its instructions,variables global variables form a locality.

note:- if fewer frames than its locality are assigned then the process will thrash.

Pages>> 1 2 3 4 5 6 7 8