Cache miss classification और metadata accounting
लक्ष्य, पूर्वज्ञान और conventions
स्पष्ट reference cache से compulsory/capacity/conflict misses पहचानें; tags, valid, dirty और दिए replacement bits सहित physical storage निकालें। पूर्वज्ञान: live cache-foundations तथा पाठ 07। Mapping फिर नहीं पढ़ाते और cache miss को OS page fault नहीं मानते।
Trace serial block reads का है; शुरू में caches खाली, हर miss पर allocation, prefetch/invalidation नहीं, block size समान। 3C reference, actual जितनी lines वाला fully associative LRU cache है। हर request पर reference update करें, actual hit पर भी। केवल actual misses classify करें।
1. तीन-step operational rule
हर actual miss पर:
- Block पहले कभी नहीं आया तो compulsory।
- पहले आया है तथा reference अभी भी miss करता है तो इस convention में capacity।
- पहले आया है, reference hit और actual miss है तो conflict।
Replacement तथा initial-state नियम जरूरी हैं। हर repeated miss conflict नहीं; केवल actual की current state से classification नहीं होता। वास्तविक systems में coherence, invalidation, prefetch या अलग replacement policies के लिए अधिक categories चाहिए हो सकती हैं। यहाँ stated textbook 3C reference convention है, हर वास्तविक miss के एक स्पष्ट physical कारण का दावा नहीं।
2. तीनों categories वाला उदाहरण
Actual: दो-line direct-mapped; block b→line b mod2। Reference: दो-line fully associative LRU। Reads 0,2,0,1,2।
- 0: actual miss; पहली बार→compulsory। Reference [0]।
- 2: actual miss, line0 में 0 हटता; पहली बार→compulsory। Reference oldest→newest [0,2]।
- 0: actual miss, 2 हटता; पहले देखा है। Reference hit होकर [2,0]→conflict।
- 1: actual line1 miss; पहली बार→compulsory। Reference 2 हटाकर [0,1]।
- 2: actual line0 miss; पहले देखा है। Reference भी miss करके 0 हटाता और [1,2] बनाता→इस convention में capacity।
Actual में पाँच misses: तीन compulsory, एक conflict, एक capacity। Reference में चार misses। यहाँ actual−reference misses=एक conflict क्योंकि actual कभी hit नहीं हुआ जब reference miss हुआ। पूरे paired trace की जाँच बिना यह subtraction generalize न करें।
3. हर request का paired classification सुरक्षित क्यों
उन्हीं caches पर 0,1,3,0 लें। Actual M,M,M,H: 0 line0 में रहता है, 1 तथा 3 line1 में बदलते हैं। Reference M,M,M,M: 0,1,3 के बाद LRU ने 0 निकाल दिया। आखिरी पर actual hit/reference miss है। Actual के तीन compulsory misses हैं, अन्य miss शून्य। कुल actual−reference=−1, जो conflict count नहीं हो सकता। Fully associative LRU की placement flexibility से हर trace में replacement decisions बेहतर होना जरूरी नहीं। इसलिए simultaneous state से actual misses classify करें, totals अंधाधुंध न घटाएँ।
4. Data capacity और physical bits
C bytes data, B bytes block, E ways, A-bit byte address। मानें कि C/B और (C/B)/E पूर्णांक हैं तथा block size B और set count S दो की घात हैं। Low-bit indexing में lines L=C/B, sets S=L/E, offset b=log2 B, index s=log2 S, tag t=A−s−b। ये storage गणना के prerequisite formulas हैं।
हर line में valid तथा dirty एक-एक bit हो तो metadata=t+2 bits। कुल storage=8C+L(t+2)+replacement bits, फिर दिए ECC/parity/अन्य bits। Dirty bit केवल stated design में गिनें। Direct mapping को victim-selection bits नहीं चाहिए। प्रत्येक line में पूरा address न गिनें: offset/index placement में implicit हैं।
उदाहरण: 32-bit byte address, data4 KiB, block32 bytes, two-way, write-back, प्रति line valid+dirty। L=128,S=64,b=5,s=6,t=21। Metadata=128×23=2944 bits। True two-way LRU में एक bit/set→64 bits। Data=32768 bits। कुल=35776 bits=4472 bytes। Advertised data capacity 4096 bytes ही है; metadata user data बढ़ाता नहीं।
5. Replacement-state representation बताएं
Two-way true LRU में दोनों lines valid हों तो एक bit/set कम recent way चुनता है। E ways की पूरी recency ordering E! possibilities रखती है; information minimum ceil(log2(E!)) bits है, practical representation अलग हो सकती है। चार ways में 24 orders→कम से कम पाँच bits। Power-of-two E में tree pseudo-LRU सामान्यतः E−1 bits लेता है, पर exact LRU नहीं। चार-way pseudo-LRU के तीन bits से true LRU तीन bits में होने का निष्कर्ष गलत। Storage प्रश्न में दी हुई representation लें; unspecified हो तो ambiguity बताएं।
सामान्य गलतियाँ
Seen-before और दोनों caches अलग track करें। पहली access compulsory है चाहे useful data हटाए। केवल actual misses को class दें। Data/metadata units न मिलाएँ। एक bit/set, एक bit/line नहीं। Replacement bits से पहले exact या approximate policy स्पष्ट करें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. खाली दो-line direct-mapped actual तथा दो-line fully associative LRU reference पर reads 0,2,0। तीसरा actual miss क्या है?
A. Compulsory B. बताए reference में capacity C. बताए reference में conflict D. Miss नहीं
उत्तर: C
A: 0 पहले देखा गया है।
B: Reference में 0 अभी है।
C: Actual ने line conflict से 0 हटाया; reference hit है।
D: Actual line में अभी 2 है।
P02. उन्हीं caches में 0,2,0,1,2 reads पर actual compulsory/conflict/capacity counts क्रमशः?
A. 3,1,1 B. 3,2,0 C. 2,1,2 D. 5,0,0
उत्तर: A
A: पहले 0,2,1 compulsory; तीसरा conflict; पाँचवाँ capacity।
B: अंतिम 2 reference में भी miss, इसलिए conflict नहीं।
C: तीन अलग blocks पहली बार आए हैं।
D: Repeated references compulsory नहीं।
P03. Actual total misses में से fully associative LRU total घटाने पर conflict count गलत क्यों हो सकता है?
A. Actual hit पर reference miss हो सकता है B. LRU की state नहीं होती C. Compulsory miss केवल direct mapping में है D. Tags compare नहीं किए जा सकते
उत्तर: A
A: अलग replacement histories से actual hit/reference miss संभव; paired जाँच चाहिए।
B: LRU recency state रखता है।
C: दोनों खाली caches में first-ever block miss है।
D: दोनों में tags/block identity track होती है।
P04. 32-bit byte address, 2 KiB data, 16-byte blocks, two-way cache। Tag width?
A. 20 bits B. 21 bits C. 22 bits D. 25 bits
उत्तर: C
A: Index/offset अधिक गिने हैं।
B: सात index bits 128 sets लेते, लेकिन 64 हैं।
C: 128/2=64 sets; index6,offset4,tag22।
D: Index+offset के लिए bits कम छोड़े।
P05. 128 lines में प्रति line tag21, valid1, dirty1 bits हैं। Replacement बिना metadata?
A. 2688 bits B. 2816 bits C. 2944 bits D. 3072 bits
उत्तर: C
A: केवल tags गिने हैं।
B: Valid/dirty में से एक छूटा।
C: 128×23=2944 bits।
D: एक अतिरिक्त unstated bit/line जोड़ा।
P06. चार अलग valid ways की सभी full recency orders के लिए information-theoretic minimum bits?
A. 3 B. 4 C. 5 D. 6
उत्तर: C
A: तीन bits आठ states; tree pseudo-LRU approximate है।
B: चार bits16 states, 24 से कम।
C: 4!=24; ceil(log2 24)=5।
D: छह पर्याप्त लेकिन minimum नहीं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे COA syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन