Podcast Beta
Questions and Answers
What is the implementation of FIFO in cache replacement based on?
What is the basis of replacement in the Least Frequently Used (LFU) algorithm?
What is the purpose of the counter associated with each line in the LFU algorithm?
What happens when a block that is resident in the cache is to be replaced and has not been altered?
Signup and view all the answers
What is the disadvantage of the Write Through policy?
Signup and view all the answers
What is the purpose of the dirty bit in the Write Back policy?
Signup and view all the answers
Which of the following is NOT a replacement algorithm?
Signup and view all the answers
What is the main difference between the Write Through and Write Back policies?
Signup and view all the answers
Why do we need Replacement Algorithms?
Signup and view all the answers
Which Replacement Algorithm replaces the block that has been in the cache longest with no reference to it?
Signup and view all the answers
What is the main assumption behind the Least Recently Used (LRU) Replacement Algorithm?
Signup and view all the answers
What is the main advantage of implementing the Least Recently Used (LRU) Replacement Algorithm?
Signup and view all the answers
How is the Least Recently Used (LRU) Replacement Algorithm implemented in a two-way set associative cache?
Signup and view all the answers
How is the Least Recently Used (LRU) Replacement Algorithm implemented in a fully set associative cache?
Signup and view all the answers
Which Replacement Algorithm replaces the block that has been in the cache longest?
Signup and view all the answers
What is the main difference between the Least Recently Used (LRU) and First in First out (FIFO) Replacement Algorithms?
Signup and view all the answers
Study Notes
Replacement Algorithms
- Replacement algorithms are needed because there must be a mechanism to replace existing blocks when a new block is brought into a filled cache.
- In direct mapping, there is only one possible line for any particular block, and no choice is possible.
- In associative and set associative techniques, a replacement algorithm is needed.
Least Recently Used (LRU)
- LRU replaces the block in the set that has been in the cache longest with no reference to it.
- This is because recently used memory locations are more likely to be referenced in the future.
- In two-way set associative, LRU is implemented using a USE bit, which is set to 1 when a line is referenced and 0 when the other line in the set is referenced.
- In fully set associative, LRU is implemented using a separate list of indexes to all the lines in the cache, where the line at the back of the list is used for replacement.
First In First Out (FIFO)
- FIFO replaces the block in the set that has been in the cache longest.
- FIFO implementation involves maintaining a queue or list of cache lines, where the cache line at the front of the queue represents the oldest block in the cache.
Least Frequently Used (LFU)
- LFU replaces the block in the set that has experienced the fewest references.
- LFU can be implemented by associating a counter with each line.
Random
- Random replaces a line at random from among the candidate lines.
Write Policy
- When a block that is resident in the cache is to be replaced, there are two cases to consider:
- Case 1: If the old block in the cache has not been altered, then it may be overwritten with a new block without first writing out the old block.
- Case 2: If at least one write operation has been performed on a word in that line of the cache, then main memory must be updated by writing the line of cache out to the block of memory before bringing in the new block.
Write Through
- Write through: all write operations are made to main memory as well as cache immediately.
- Disadvantage: The processor always slows down to main memory speed.
Write Back
- Write Back: write operations are written in the main memory before replacing if and only if the control bit (dirty bit) is set.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Learn about replacement algorithms and write strategy in computer organization. Understand why these algorithms are needed and how they work in different caching scenarios.