Computer Organization: Replacement Algorithms

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the implementation of FIFO in cache replacement based on?

A queue or list of cache lines (correct)

A graph of cache lines

A tree of cache lines

A stack of cache lines

What is the basis of replacement in the Least Frequently Used (LFU) algorithm?

The block that has been used most frequently

The block that is at the front of the queue

The block that has experienced the fewest references (correct)

The block that has been in the cache for the longest time

What is the purpose of the counter associated with each line in the LFU algorithm?

To keep track of the number of times a block is accessed (correct)

To determine the oldest block in the cache

To implement the Random algorithm

To implement the FIFO algorithm

What happens when a block that is resident in the cache is to be replaced and has not been altered?

The old block is overwritten with a new block Signup and view all the answers

What is the disadvantage of the Write Through policy?

It slows down the processor Signup and view all the answers

What is the purpose of the dirty bit in the Write Back policy?

To indicate when a block is dirty and needs to be written back to main memory Signup and view all the answers

Which of the following is NOT a replacement algorithm?

Write Through Signup and view all the answers

What is the main difference between the Write Through and Write Back policies?

Write Through writes immediately, while Write Back writes when the block is replaced Signup and view all the answers

Why do we need Replacement Algorithms?

Because there should be a mechanism to replace existing blocks when a new block is brought into a filled cache. Signup and view all the answers

Which Replacement Algorithm replaces the block that has been in the cache longest with no reference to it?

Least Recently Used (LRU) Signup and view all the answers

What is the main assumption behind the Least Recently Used (LRU) Replacement Algorithm?

More recently used memory locations are more likely to be referenced in the future. Signup and view all the answers

What is the main advantage of implementing the Least Recently Used (LRU) Replacement Algorithm?

It increases the hit ratio. Signup and view all the answers

How is the Least Recently Used (LRU) Replacement Algorithm implemented in a two-way set associative cache?

Each line includes a USE bit that is set to 1 when the line is referenced, and the USE bit of the other line in that set is set to 0. Signup and view all the answers

How is the Least Recently Used (LRU) Replacement Algorithm implemented in a fully set associative cache?

The cache mechanism maintains a separate list of indexes to all the lines in the cache. Signup and view all the answers

Which Replacement Algorithm replaces the block that has been in the cache longest?

First in First out (FIFO) 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?

LRU replaces the block that has been in the cache longest with no reference to it, while FIFO replaces the block that has been in the cache longest. 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.

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.