Question:
Consider the following page reference string:
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
For FIFO page replacement algorithm with 4 frames (the first 4 unique pages will be page faults), the number of page faults is
निम्न पेज रिफरेन्स स्ट्रिंंग पर विचार करें:
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
4 फ्रेेम के साथ फीफो पेज कॉपीस्थापन एल्गोरिदम के लिए (पहले 4 अनन्य पृष्ठ – पृष्ठ फाल्ट होगी), पेज फाल्ट की संख्या है
Options:
- 14
- 15
- 11
- 12
- 14
- 15
- 11
- 12
Correct Answer: a)
Explanation:
Detailed Explanation:
The correct answer is a) 14.
Trace of FIFO Page Replacement Algorithm (4 Frames):
Reference String: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
- Ref 1: Fault $\rightarrow$ [1, -, -, -] (Fault 1)
- Ref 2: Fault $\rightarrow$ [1, 2, -, -] (Fault 2)
- Ref 3: Fault $\rightarrow$ [1, 2, 3, -] (Fault 3)
- Ref 4: Fault $\rightarrow$ [1, 2, 3, 4] (Fault 4)
- Ref 2: Hit $\rightarrow$ [1, 2, 3, 4]
- Ref 1: Hit $\rightarrow$ [1, 2, 3, 4]
- Ref 5: Fault $\rightarrow$ replaces oldest (1) $\rightarrow$ [5, 2, 3, 4] (Fault 5)
- Ref 6: Fault $\rightarrow$ replaces oldest (2) $\rightarrow$ [5, 6, 3, 4] (Fault 6)
- Ref 2: Fault $\rightarrow$ replaces oldest (3) $\rightarrow$ [5, 6, 2, 4] (Fault 7)
- Ref 1: Fault $\rightarrow$ replaces oldest (4) $\rightarrow$ [5, 6, 2, 1] (Fault 8)
- Ref 2: Hit $\rightarrow$ [5, 6, 2, 1]
- Ref 3: Fault $\rightarrow$ replaces oldest (5) $\rightarrow$ [3, 6, 2, 1] (Fault 9)
- Ref 7: Fault $\rightarrow$ replaces oldest (6) $\rightarrow$ [3, 7, 2, 1] (Fault 10)
- Ref 6: Fault $\rightarrow$ replaces oldest (2) $\rightarrow$ [3, 7, 6, 1] (Fault 11)
- Ref 3: Hit $\rightarrow$ [3, 7, 6, 1]
- Ref 2: Fault $\rightarrow$ replaces oldest (1) $\rightarrow$ [3, 7, 6, 2] (Fault 12)
- Ref 1: Fault $\rightarrow$ replaces oldest (3) $\rightarrow$ [1, 7, 6, 2] (Fault 13)
- Ref 2: Hit $\rightarrow$ [1, 7, 6, 2]
- Ref 3: Fault $\rightarrow$ replaces oldest (7) $\rightarrow$ [1, 3, 6, 2] (Fault 14)
- Ref 6: Hit $\rightarrow$ [1, 3, 6, 2]
Summary: Total Page Faults = 14, Total Hits = 6.
विस्तृत व्याख्या:
सही उत्तर a) 14 है।
4 फ्रेम के साथ FIFO पेज रिप्लेसमेंट एल्गोरिदम की गणना:
पेज संदर्भ स्ट्रिंग: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
- संदर्भ 1: पेज फॉल्ट $\rightarrow$ [1, -, -, -] (फॉल्ट 1)
- संदर्भ 2: पेज फॉल्ट $\rightarrow$ [1, 2, -, -] (फॉल्ट 2)
- संदर्भ 3: पेज फॉल्ट $\rightarrow$ [1, 2, 3, -] (फॉल्ट 3)
- संदर्भ 4: पेज फॉल्ट $\rightarrow$ [1, 2, 3, 4] (फॉल्ट 4)
- संदर्भ 2: हिट (Hit) $\rightarrow$ [1, 2, 3, 4]
- संदर्भ 1: हिट (Hit) $\rightarrow$ [1, 2, 3, 4]
- संदर्भ 5: फॉल्ट $\rightarrow$ सबसे पुराने (1) को बदला $\rightarrow$ [5, 2, 3, 4] (फॉल्ट 5)
- संदर्भ 6: फॉल्ट $\rightarrow$ सबसे पुराने (2) को बदला $\rightarrow$ [5, 6, 3, 4] (फॉल्ट 6)
- संदर्भ 2: फॉल्ट $\rightarrow$ सबसे पुराने (3) को बदला $\rightarrow$ [5, 6, 2, 4] (फॉल्ट 7)
- संदर्भ 1: फॉल्ट $\rightarrow$ सबसे पुराने (4) को बदला $\rightarrow$ [5, 6, 2, 1] (फॉल्ट 8)
- संदर्भ 2: हिट (Hit) $\rightarrow$ [5, 6, 2, 1]
- संदर्भ 3: फॉल्ट $\rightarrow$ सबसे पुराने (5) को बदला $\rightarrow$ [3, 6, 2, 1] (फॉल्ट 9)
- संदर्भ 7: फॉल्ट $\rightarrow$ सबसे पुराने (6) को बदला $\rightarrow$ [3, 7, 2, 1] (फॉल्ट 10)
- संदर्भ 6: फॉल्ट $\rightarrow$ सबसे पुराने (2) को बदला $\rightarrow$ [3, 7, 6, 1] (फॉल्ट 11)
- संदर्भ 3: हिट (Hit) $\rightarrow$ [3, 7, 6, 1]
- संदर्भ 2: फॉल्ट $\rightarrow$ सबसे पुराने (1) को बदला $\rightarrow$ [3, 7, 6, 2] (फॉल्ट 12)
- संदर्भ 1: फॉल्ट $\rightarrow$ सबसे पुराने (3) को बदला $\rightarrow$ [1, 7, 6, 2] (फॉल्ट 13)
- संदर्भ 2: हिट (Hit) $\rightarrow$ [1, 7, 6, 2]
- संदर्भ 3: फॉल्ट $\rightarrow$ सबसे पुराने (7) को बदला $\rightarrow$ [1, 3, 6, 2] (फॉल्ट 14)
- संदर्भ 6: हिट (Hit) $\rightarrow$ [1, 3, 6, 2]
अतः कुल पेज फॉल्ट की संख्या = 14 है।