Computer Architecture and Organization
CIS · Quiz · Spring 26
Paper 2 of 2By N.M. Nayem -Ul-Islam (2)Switch
Paper 2 of 2
Read the questions as text
Read off the PDF by AI, so it may have mistakes. The PDF is the original.
QUIZ 2
1. In direct mapping, each block of main memory maps to:
A. Any cache line
B. A specific line in cache
C. A set of cache lines
D. A random cache line
Answer: B
2. Fully associative mapping allows a block to be placed in:
A. Only one cache line
B. Some specific lines
C. Any cache line
D. Alternate lines
Answer: C
3. Set-associative mapping is a combination of:
A. Direct and fully associative
B. Direct and random
C. Fully associative and random
D. Tag and index mapping
Answer: A
4. In direct-mapped cache, the address is divided into:
A. Tag + Index + Offset
B. Tag + Offset
C. Set + Offset
D. Index + Offset
Answer: A
5. In fully associative mapping, the address is divided into:
A. Tag + Index + Offset
B. Tag + Offset
C. Index + Tag
D. Offset only
Answer: B
6. Direct mapping suffers from:
A. High complexity
B. High cost
C. Conflict misses
D. No misses
Answer: C
7. Least complex cache mapping technique:
A. Direct mapping
B. Associative mapping
C. Set-associative mapping
D. Random mapping
Answer: A
8. In a 4-way set associative cache, each block maps to:
A. 4 possible sets
B. Exactly one set
C. 4 possible lines inside one set
D. Any line in cache
Answer: C
9. Which mapping technique requires comparators for each line?
A. Direct
B. Set-associative
C. Fully associative
D. All of these
Answer: C
10. Main drawback of fully associative cache:
A. Slow
B. Complex and expensive
C. Low hit rate
D. Poor performance
Answer: B
11. Replacement policies apply to which cache mapping?
A. Direct
B. Associative
C. Set-associative
D. B and C
Answer: D
12. LRU replacement stands for:
A. Least Recently Updated
B. Last Recently Used
C. Least Recently Used
D. Last Reset Unit
Answer: C
13. Which mapping is least prone to conflict misses?
A. Direct
B. Set associative
C. Fully associative
D. Direct or set
Answer: C
14. Direct mapping requires comparing:
A. Only one tag
B. All tags
C. Tags of a set
D. No tags
Answer: A
15. Hit ratio increases with:
A. Small block size
B. Optimal mapping
C. Frequent misses
D. Low spatial locality
Answer: B
16. In set associative mapping, the number of sets equals:
A. Cache size / block size
B. Cache lines / ways
C. Tag size
D. Total memory blocks
Answer: B
17. A 2-way set-associative cache means:
A. Two sets
B. Two lines per set
C. Two levels of cache
D. Two indexes
Answer: B
18. Which mapping gives the best performance usually?
A. Direct
B. Fully associative
C. Set associative
D. Depends on cache size
Answer: C
19. Cache memory is closer to:
A. CPU
B. RAM
C. Hard disk
D. I/O devices
Answer: A
20. Cache block is also called:
A. Set
B. Line
C. Page
D. Word
Answer: B
21. Fully associative lookup is performed using:
A. Hashing
B. Content Addressable Memory (CAM)
C. Direct table lookup
D. Paging
Answer: B
22. In direct mapping, conflict miss occurs when:
A. Many blocks map to the same cache line
B. Cache is full
C. Data not present in main memory
D. Address offset overflows
Answer: A
23. Replacement not needed in direct mapping because:
A. Only one target line exists
B. Cache is infinite
C. No misses occur
D. Data always fits
Answer: A
24. The most flexible mapping scheme is:
A. Direct
B. Fully associative
C. Set associative
D. Fully direct
Answer: B
25. A mapping with fewer sets but more lines in each set is:
A. Direct
B. 2-way associative
C. k-way set associative
D. Fully associative
Answer: D
26. Miss penalty refers to:
A. Time to remove data
B. Time to access RAM after a miss
C. Time to store in cache
D. Time to replace LRU
Answer: B
27. The main problem with large block size:
A. Conflict miss
B. Longer hit time
C. Compulsory miss reduction
D. Less spatial locality
Answer: B
28. In set associative mapping, tags are compared:
A. Serially
B. In parallel
C. Randomly
D. Never
Answer: B
29. Thrashing in cache is most common in:
A. Direct
B. Fully associative
C. Set associative
D. Multilevel cache
Answer: A
30. Temporal locality means:
A. Nearby memory accesses
B. Same memory accessed repeatedly
C. Sequential data
D. Random access
Answer: B
31. Spatial locality means:
A. Repeated access
B. Accessing nearby addresses
C. Large gaps in memory
D. Undefined patterns
Answer: B
32. A tag field is used to:
A. Identify set
B. Identify main memory block
C. Identify line size
D. Select a replacement policy
Answer: B
33. In direct mapping, the index identifies:
A. Memory block
B. Cache line
C. Set
D. CPU core
Answer: B
34. Which mapping uses the smallest tag size?
A. Direct
B. Fully associative
C. Set associative
D. All equal
Answer: A
35. Cache hit means:
A. Data present in RAM
B. Data present in cache
C. Incorrect data
D. Cache full
Answer: B
36. Cache miss due to first access is called:
A. Capacity miss
B. Conflict miss
C. Cold/compulsory miss
D. Coherence miss
Answer: C
37. Capacity misses are caused by:
A. Limited cache size
B. Many blocks mapping to one line
C. New process
D. Tag mismatch
Answer: A
38. A 32 KB cache with 64B block has how many lines?
A. 512
B. 1024
C. 256
D. 64
Answer: A
(32 KB = 32768 B -> 32768 / 64 = 512)
39. If it's an 8-way set associative cache with 512 lines, sets =
A. 512
B. 64
C. 8
D. 128
Answer: B
(512 / 8 = 64 sets)
40. Replacement needed when:
A. Cache empty
B. Cache hit
C. Cache miss and set is full
D. Data is dirty
Answer: C
41. Write-back cache means:
A. Data written to RAM immediately
B. Data written to RAM only on replacement
C. Never written
D. Write ignored
Answer: B
42. Write-through cache means:
A. CPU writes only to cache
B. CPU writes to both cache and RAM
C. RAM writes ignored
D. Always slower
Answer: B
43. Tag comparison occurs during:
A. Hit only
B. Miss only
C. Both hit and miss checking
D. Replacement only
Answer: C
44. Least recently used block is removed in:
A. FIFO
B. LRU
C. LFU
D. Random
Answer: B
45. Index bits depend on:
A. Number of sets
B. Block size
C. Tag size
D. Total memory size
Answer: A
46. Offset bits depend on:
A. Memory size
B. Cache size
C. Block size
D. Set size
Answer: C
47. A 16-word block needs how many offset bits?
A. 2
B. 3
C. 4
D. 5
Answer: C
(16 = 2^4 -> 4 bits)
48. CAM is used in:
A. Direct cache
B. Set associative
C. Fully associative
D. Both B and C
Answer: D
49. Conflict miss is eliminated in:
A. Direct mapping
B. 2-way set associative
C. Fully associative
D. FIFO strategy
Answer: C
50. Best mapping for high-speed small caches:
A. Direct
B. Fully associative
C. 4-8 way set associative
D. Random
Answer: C
Replacement Algorithm
1. FIFO page replacement removes the page that is:
A. Least recently used
B. Most recently used
C. First inserted into memory
D. Last inserted into memory
Answer: C
2. FIFO stands for:
A. First in First out
B. Fast in Fast out
C. First instruction First out
D. File in File out
Answer: A
3. FIFO can be implemented using:
A. Stack
B. Queue
C. Hash table
D. Tree
Answer: B
4. FIFO page replacement is based on:
A. Time of arrival
B. Frequency of use
C. Future predictions
D. Recent usage
Answer: A
5. FIFO page replacement may lead to:
A. Belady's anomaly
B. Stack property
C. Optimal behavior
D. Least page faults
Answer: A
6. Belady's anomaly occurs when:
A. Increasing frames reduces page faults
B. Increasing frames increases page faults
C. Frames are constant
D. Page faults never occur
Answer: B
7. FIFO replacement does not consider:
A. How frequently a page is used
B. How recently a page is used
C. The order pages were loaded
D. Temporal locality
Answer: C
8. FIFO is considered:
A. Easiest to implement
B. Most optimal
C. Most complex
D. Most accurate
Answer: A
9. The data structure used in FIFO maintains pages in:
A. Ascending order
B. Arrival order
C. Access frequency
D. Least recent access
Answer: B
10. FIFO algorithm may remove:
A. Most recently added page
B. Least frequently used page
C. A heavily used page
D. The page used farthest in future
Answer: C
11. FIFO is mainly affected by:
A. Temporal locality
B. Spatial locality
C. Order of page arrivals
D. Logical address size
Answer: C
12. FIFO replacement algorithm belongs to:
A. Stack algorithms
B. Non-stack algorithms
C. Predictive algorithms
D. Adaptive algorithms
Answer: B
(Stack algorithms do not suffer from Belady's anomaly; FIFO does.)
13. In FIFO, when a page fault occurs and memory is full:
A. Random page is replaced
B. Most recently used page is replaced
C. First loaded page is replaced
D. Least frequently used is replaced
Answer: C
14. FIFO replacement ignores:
A. Page age
B. Page arrival time
C. Order of insertion
D. Page usage pattern
Answer: D
15. If pages enter memory in sequence A -> B -> C -> D, and FIFO must replace, the page removed first is:
A. A
B. B
C. C
D. D
Answer: A
16. FIFO is prone to:
A. High computational cost
B. Removing useful pages
C. Always optimal performance
D. Never replacing old pages
Answer: B
17. The number of page faults in FIFO generally:
A. Always decreases with more frames
B. Always increases with more frames
C. Can increase or decrease
D. Remains constant
Answer: C
18. FIFO uses which principle?
A. LRU
B. MRU
C. FCFS
D. Optimal
Answer: C
(First-Come, First-Served order)
19. When frames = 1, FIFO behaves like:
A. LRU
B. Optimal
C. No replacement algorithm
D. All algorithms behave the same
Answer: D
20. FIFO is often used as a baseline for comparison because:
A. It gives the lowest page faults
B. Simple and predictable behavior
C. It uses future prediction
D. It is the fastest algorithm
Answer: B
21. LIFO page replacement removes the page that is:
A. First inserted
B. Least recently used
C. Last inserted
D. Least frequently used
Answer: C
22. LIFO stands for:
A. Least In First Out
B. Last In First Out
C. Last Input First Out
D. Least Important First Out
Answer: B
23. LIFO page replacement can be implemented using:
A. Queue
B. Stack
C. Hash table
D. Priority queue
Answer: B
24. LIFO replacement tends to remove the page that was:
A. Used most recently
B. Used least recently
C. Used most frequently
D. Loaded earliest
Answer: A
25. LIFO is not preferred in practice because:
A. Difficult to implement
B. High number of page faults
C. Requires too much extra hardware
D. Illegal in modern OS
Answer: B
26. LIFO often discards the page that:
A. Will not be used soon
B. Will be used immediately
C. Has the lowest frequency
D. Has the longest arrival time
Answer: B
27. Which data structure best represents LIFO behavior?
A. Queue
B. Tree
C. Stack
D. Linked list
Answer: C
28. LIFO suffers from:
A. Belady's anomaly
B. High hit ratio
C. Stack property
D. Minimal page faults
Answer: A
29. LIFO is rarely used because it:
A. Does not track usage pattern
B. Tracks future use
C. Requires expensive hardware
D. Perfectly predicts access order
Answer: A
30. LIFO is most similar to which caching behavior?
A. FIFO
B. MRU (Most Recently Used)
C. LRU (Least Recently Used)
D. LFU (Least Frequently Used)
Answer: B
31. The Optimal page replacement algorithm replaces the page that:
A. Was least recently used
B. Will not be used for the longest time in the future
C. Was most frequently used
D. Was loaded first
Answer: B
32. The Optimal algorithm is also known as:
A. Belady's algorithm
B. Future knowledge algorithm
C. Clairvoyant algorithm
D. All of the above
Answer: D
33. Optimal page replacement is primarily used for:
A. Real execution
B. Simulation and benchmarking
C. Hardware page tables
D. TLB updates
Answer: B
34. Why is Optimal replacement not used in real systems?
A. Too slow for modern CPUs
B. Requires knowledge of future references
C. Requires expensive hardware
D. Not accurate
Answer: B
35. Optimal algorithm guarantees:
A. Maximum page faults
B. Minimum page faults
C. Zero page faults
D. Same faults as FIFO
Answer: B
36. Which algorithm is commonly compared against Optimal?
A. FIFO B. LIFO C. LRU D. All of these
Answer: D
37. Optimal page replacement never suffers from:
A. Thrashing
B. Belady's anomaly
C. Page faults
D. Cache misses
Answer: B
38. Belady's anomaly refers to:
A. Page faults decrease with more frames
B. Page faults increase with more frames
C. Optimal always performs worst
D. TLB misses increase
Answer: B
39. Optimal algorithm is considered a:
A. Stack algorithm
B. Queue algorithm
C. Random algorithm
D. Clock algorithm
Answer: A
40. Optimal algorithm chooses the page whose:
A. Last use is recent
B. Next use is farthest
C. Next use is closest
D. Arrival time is earliest
Answer: B
41. The main purpose of Optimal algorithm is to:
A. Reduce CPU usage
B. Measure theoretical performance limits
C. Allocate physical memory
D. Improve disk scheduling
Answer: B
42. Optimal algorithm requires analysis of:
A. Past reference behavior
B. Future reference string
C. Current memory usage only
D. Timestamps
Answer: B
43. Which page replacement algorithm tries to imitate Optimal?
A. FIFO
B. LRU
C. LIFO
D. Random
Answer: B
44. In Optimal algorithm, if two pages have unknown future references:
A. Replace the first one
B. Replace any one of them
C. Replace the last one
D. Replace the one with oldest arrival time
Answer: B
45. Which characteristic does Optimal share with LRU?
A. Stack property
B. Queue-like behavior
C. Belady anomaly
D. Removing MRU pages
Answer: A
46. What is the biggest drawback of Optimal algorithm?
A. Low accuracy
B. Requires large memory
C. Cannot be implemented in real time
D. Needs page locking
Answer: C
47. Optimal algorithm is ideal but:
A. Too complex to implement
B. Impossible without future access knowledge
C. Too slow for hardware
D. Gives inconsistent results
Answer: B
48. Optimal algorithm ensures that:
A. Page fault count is minimal for any input
B. FIFO never beats it
C. LRU always beats it
D. It behaves exactly like MRU
Answer: A
49. Optimal is used in operating system textbooks to:
A. Show real-world OS behavior
B. Provide a performance bound
C. Demonstrate FIFO anomalies
D. Implement page tables
Answer: B
50. Which property makes Optimal immune to Belady's anomaly?
A. It uses arrival time
B. It is a stack algorithm
C. It is FIFO-based
D. It uses random selection
Answer: B
Short Questions
1. What is cache memory mapping?
Answer: The method used to determine where a block of main memory is placed in the cache.
2. Name the three types of cache mapping.
Answer: In any cache line.
3. What is an advantage of fully associative mapping?
Answer: Very low conflict misses.
4. What is a drawback of fully associative mapping?
Answer: It is expensive and complex to implement.
5. What is set-associative mapping?
Answer: Cache is divided into sets, and a block can go into any line within its assigned set.
6. What is a "k-way set-associative" cache?
Answer: A cache where each set contains k lines.
7. Which mapping technique offers the best balance between cost and performance?
Answer: Set-associative mapping.
8. What is a cache line?
Answer: A fixed-size block of data stored in the cache.
9. What is the purpose of the tag field in a cache address?
Answer: To identify which memory block is stored in a cache line.
10. What is an index field in cache addressing?
Answer: [Figure: diagram illustrating cache addressing and tag directory]