Memory Management - 2 Flashcards
What is FIFO method in Swapping?
We choose to remove the last page who’s been swapped
What is NRU method in Swapping?
We choose to remove the page who’s not recently used
What is 2nd chance FIFO method?
We operate according to FIFO , but if the chosen page referenced bit is set, we clear it and move the page on top of the queue and keep searching.
What is the LRU swapping method?
- Replace pages that have been used least recently.*
- This can be implemented using bit table of n*n, where n is the number of pages.*
- Each time a page k is selected: row k is filled with 1’s, and column k is filled with zeros. This behaviour makes row k to have the greatest binary value.(because it has all ones except (k,k) but for all other j’s (j,k) is also zero). In addition, this set up does not change the order between previous set ups.*
What is the NFU Swapping method?
NFU - Not Frequently Used.
LRU approximatiom.
- we add a counter field to each page frame, which is updated with every clock tick. That is:*
- Divide the counter by 2(shift right) - maintain order.*
- Add reference bit from left(most significant)*
- Reset reference bit if it is set on.*
Why is it considered approximation?
There might happen to be two process with the same counter value, because within a tick clock there might be several accesses to pages. Therefore, it is only an approximation of LRU
What is so strange about Belady’s anomaly?
Generally as the number of frames available increases, the number of page faults will decrease.
But in the case of FIFO(First in first out) it might happen that more page frames, for the same referecnce string, will result in more page fault.
What is special about stack Algorithms?
Assume a process p, a memory which can hold m pages and a total of n virtual pages.
M(m,r): the set of virtual pages in memory after the r’th reference of p, given a memory of size m.
Stack algorithms satisfy the following rule:
For any p,m and reference string r, M(m,r) is a subset of M(m+1,r)
It is special because stack algorithm don’t suffer from Belady’s abnomaly.
Page Replacement in Multi-Programming:
Local or global algorithms?
does fair-share is good?
allocate according to process size?
- Local is better. When a page fault is raised on process p, the local algorithm searches for a swap a page which belong to p.*
- A global algoirthm is free to select any page, this results in more page faults.*
Fair share isn’t good because it doesn’t take into account the size of each process and how many times it has been used.
Allocation according to size is better, but there must be a minimum for a running process, not doing so results with very high page-fault rate.
What is Thrashing?
A process busy in swapping pages in and out.
- The degree of multiprogramming describes the maximum number of processes that a single-processor system can accommodate efficiently.*
- Do you remember the Thrashing Diagram? you should!*
- Increasing multiprogramming level initially increases CPU utilization.*
- Beyond some points, Thrashing sets in and multiprogramming level must be decreased.*
What is the locality model?
Locality: a set of pages that are actively used together.
Locality model: states that as a process executes, it shifts from one locatliy to another.
For instance, when we enter a function - we need a set of pages relevant to its execution.
What are the techniques to handle locality?
Working set model:
- based on the locality model*
- basic prinicipal: if we allocate enough frames to a process to accomodate its current locality, it will only fault whenever it moves to some new locality.*
- but if allocated frames are less than current locality, the process is bound to thrash.*
- The working set of a process is the set of pages used by A most recently memory references.*
- Note: A is predetermined.*
WS(t, A) -** denotes the working set at time **t
- How is the Effective Access Time time computed given the input:*
- page fault rate: p*
- memory access time: m*
- page-fault service time: l*
- Exercise: m = 100 nanosecs. l = 25 milsecs*
- In order to get an effective access time of 10% degradation in access time m. how much p needs to be?*
Effective Access Time: (1-p)*m + p*l
Answer:
- first, recall that nano = 10^-9. mili = 10^-3.*
- let’s change l from millisecs to nano. That is, multiply 25 by a factor of 10^6 - l = 25,000,000*10^-9*
- degradation of 10% in access time means 100+10 = 110 nanosecs.*
- we have (1-p)*100 + p*25,000,000 = 100-100p+25,000,000p = 110*
- 24999900p = 10 -> p = 10/24999900 = 4*10^-7*
- The working-set has a fixed parameter A.*
- what if A is too small? too big? what if A = infinity?*
Dt = sum of all |WS(t)| =** total size of all workings sets at time **t.
What if Dt>m? what can we do about it?
Too small:** will not compass en entire **locality
Too big: will encompass several localities
infinity: will encompass entire program
Dt>m: thrashing. to solve such a case, we can suspend one of the processes.
- How is the working-set implemented?*
- What’s the problem with counting A last references?*
- what a better alternative exist?*
- counting A last references is expensive.*
- Instead, we can use the clock ticks and the fact that the reference bits are updated by the hardware.*
Virtual time field is added to the process struct
- With each tick, update process virtual time and virtual time of referenced paging-table entries. Then, clear the R bit.*
- Page p’s age is the difference between the process’ virtual time and the time of p’s last reference.*
What’s the idea behind Working Set Clock: global version.
Same idea as WSClock algorithm but for pages held by all processes in memory.
Clock Tick: the algorithm uses;
parameter Tau
pages reference bits ,time of last reference [ref(frame)], and current “virtual times” of processes[Tp].
Replace page when:
R = 0 and Tp - ref(frame) > Tau
case no page satisfies R=0 we choose a dirty one
case no page is older than Tau we choose the oldest one.
Can you review all Page Replacement Algorithms?
How non-RAM-resident pages are stored on disk?
What may be the problem with allocating a fixed chunk on disk to a process, upon creation?
are there more alternative?
option 1 (static): allocate a fix chunk of the swap area to process upon creation, keep offset in PTE.
problem: memory requirements may change dramatically.
option 2: Reserve separate swap areas for text, data, stack, allow each to extend over multiple chunks.
option 3(dynamic): allocate swap space to a page when it is swapped out, de-allocate when back in.
Need to keep swap address for each page. why? in dynamic allocation, we should track the address for efficiency. every search might be very long because it might be placed anywhere in the file.
