LAB 6- HỆ ĐIỀU HÀNH – IT007.018.1
NGUYỄN HOÀNG GIA BẢO – 22520111
6.3.3: Câu hỏi chuẩn bị:
1. Vẽ lưu đồ thuật toán mô tả cách thức xử lý của 3 giải thuật thay thế
trang: FIFO, OPT, LRU? Vẽ sơ đồ trình bày thay thế trang bằng 3 giải
thuật trên với chuỗi tham chiếu:
0, 2, 1, 6, 4, 0, 1, 0, 3, 1, 2, 1
Giả sử có 3 khung trang và các khung trang ban đầu là rỗng. Xác định
số Page Fault từ đó đưa ra đánh giá các giải thuật. Giải thuật FIFO: 0 2 1 6 4 0 1 0 3 1 2 1 0 0 0 6 6 6 1 1 1 1 1 1 2 2 2 4 4 4 4 3 3 3 3 1 1 1 0 0 0 0 0 2 2 * * * * * * * * *  Có 9 lỗi trang. Giải thuật LRU: 0 2 1 6 4 0 1 0 3 1 2 1 0 0 0 6 6 6 1 1 1 1 1 1 2 2 2 4 4 4 4 3 3 3 3 1 1 1 0 0 0 0 0 2 2 * * * * * * * * *  Có 9 lỗi trang Giải thuật OPT: 0 2 1 6 4 0 1 0 3 1 2 1 0 0 0 0 0 0 0 0 3 3 2 2 2 2 6 4 4 4 4 4 4 4 4 1 1 1 1 1 1 1 1 1 1 * * * * * * *  Có 7 lỗi trang.
Đánh giá: Thuâ ̣t to愃Ān LRU v愃 thuâ ̣t to愃Ān FIFO gây ra lỗi trang nhiu nhĀt (9
lỗi) v愃 giải thuâ ̣t OTP l愃 thuâ ̣t to愃Ān tĀi ưu nhĀt v椃 gây ra lỗi 椃Āt nhĀt (7 lỗi).
6.4 Hướng dẫn thực hành Code: #include
int OTP(int a[50], int frames[5], int pos, int frame, int n) {
int flag[5] = { 0,0,0,0,0 }; int i = pos + 1;
if(i == n) return 0; // NĀu l̀i trang xuĀt hiê
̣n ở ngay v椃⌀ tr椃Ā c甃ऀa trnag cuĀi for (i; i < n; i++) { int t = 0;
for (t = 0; t < frame; t++) if (frames[t] == a[i]) flag[t] = 1; int count = 0;
for (t = 0; t < frame; t++) // ĐĀm sĀ c愃Āc trang c漃Ā nhu cu truy xuĀt
if (flag[t] == 1) count++;
if (count == frame) // SĀ trang c漃Ā nhu cu truy xuĀt bằng với sĀ frames { int f = 0;
for (f; f < frame; f++) if (frames[f] == a[i]) return f; }
if (i == n - 1) // Trường hợp sĀ trang c漃n l愃⌀i c漃Ā nhu cu truy
xuĀt 椃Āt hơn sĀ frames { int i = 0;
for (i; i < frame; i++)
if (flag[i] == 0) return i; } } }
int IsExist(int a, int temp[50], int index) { int i = 0;
for (i; i < index; i++) if (a == temp[i]) return 1; return 0; }
int LRU(int a[50], int frames[5], int pos, int frame, int n) {
int temp[50]; // Lưu c愃Āc gi愃Ā tr椃⌀ được truy xuĀt từ v椃⌀ tr椃Ā pos trở v trước int j = 0; int i = pos - 1;
for (i; i >= 0; i--) { if (j == 0) { temp[j] = a[i]; j++; } else {
if (IsExist(a[i], temp, j) == 0) { temp[j] = a[i]; j++; }
if (j == frame) // T椃m thĀy phn tử c漃Ā ln truy xuĀt xa nhĀt { int t = 0;
for (t; t < frame; t++) if (frames[t] == a[i]) return t; } } } }
int DefaultInput(int a[50]) { int n; n = 11;
int b[11] = { 2,1,5,2,0,1,5,1,0,0,7 }; int i = 0; for (i; i < n; i++) a[i] = b[i]; a[i] = 0; return n; }
int ManualInput(int a[50]) { int n;
printf(" \nNhập sĀ phn tử chu̀i tham chiĀu: \n"); scanf("%d", &n);
printf(" \nNhập vào chu̀i tham chiĀu: \n"); int i = 0; for (i; i < n; i++) scanf("%d", &a[i]); return n; } int main() {
int i, j, n, a[50], frames[5], frame, k, available, count = 0; int input;
printf("---- - Page Replacement algorithm---- -\n");
printf("1. Default referenced sequence.\n");
printf("2. Manual input sequence.\n"); scanf("%d", &input); if (input == 1) n = DefaultInput(a); if (input == 2) n = ManualInput(a);
printf("\nInput page frames: \n"); scanf("%d", &frame); int y = 0;
for (y; y < frame; y++)
frames[y] = -1; // Ban đu c愃Āc frames đu trĀng
printf("------Page Replacement algorithm-----\n"); printf("1. FIFO Algorithm\n"); printf("2.
OPT(optimal) Algorithm\n"); printf("3. LRU Algorithm\n"); int choose; scanf("%d", &choose); if (choose == 1)
printf("---FIFO Page Replacement algorithm---\n"); if (choose == 2)
printf("------OTP Page Replacement algorithm-----\n"); if (choose == 3)
printf("------LRU Page Replacement algorithm-----\n"); j = 0;
printf("\t|Chu̀i|\t|Khung trang");
for (k = 0; k < frame - 1; k++) printf("\t"); printf("|\n");
for (i = 0; i < n; i++) {
printf("\t| %d |\t", a[i]);
available = 0; // Kiऀm tra trang c漃Ā sẵn trong c愃Āc frames hay không
for (k = 0; k < frame; k++)
if (frames[k] == a[i]) // NĀu trang c漃Ā sẵn available = 1;
if (available == 0) // Thay thĀ trang nĀu không c漃Ā sẵn trong c愃Āc frames { if (choose == 1) { frames[j] = a[i]; j = (j + 1) % frame; }
else if (choose == 2) { if (i < frame) { frames[j] = a[i]; j++; } else
frames[OTP(a, frames, i, frame, n)] = a[i]; }
else if (choose == 3) { if (i < frame) { frames[j] = a[i]; j++; } else
frames[LRU(a, frames, i, frame, n)] = a[i]; } count++; printf("|");
for (k = 0; k < frame; k++)
printf("%d\t", frames[k]); printf("| F"); // DĀu hiê ̣u nhâ
̣n biĀt khi x愃ऀy ra l̀i trang } else { printf("|");
for (k = 0; k < frame; k++)
printf("%d\t", frames[k]); printf("|"); } printf("\n"); }
printf("SĀ trang l̀i là: %d\n", count); return 0; }
Kết quả chương tr椃nh khi ch愃⌀y với chuỗi mă ̣c đ椃⌀nh [2 1 5 2 0 1 5 1 0 0 7] v愃 3 frame: FIFO OTP: LRU
Kết quả chương tr椃nh khi ch愃⌀y với chuỗi tự nhâ ̣p [1 2 3 4 1 2 5 1 2 3 4 5]: FIFO: OTP: LRU:
6.5 Bài tập ôn tập
1. Nghịch lý Belady là gì? Sử dụng chương trình đã viết trên để chứng minh nghịch lý này.
Ngh椃⌀ch l礃Ā Belady chứng minh rằng có khả năng s攃̀ có thêm lỗi khi ta tăng sĀ khung trang lên.
Ta s攃̀ 愃Āp dụng thuật to愃Ān FIFO: Với 2 khung trang: Với 3 khung trang: Với 4 khung trang:
Có thऀ thĀy kết quả khi d甃ng 2 khung trang th椃 chương tr椃nh mắc 12
lỗi v愃 khi tăng sĀ khung trang lên 3 th椃 ch椃ऀ c漃n l愃⌀i 9 lỗi. Nhưng khi tăng
khung trang lên th愃nh 4 th椃 sĀ lỗi l愃⌀i tăng lên => Ngh椃⌀ch l礃Ā Belady
2. Nhận xét về mức độ hiệu quả và tính khả thi của các giải thuật FIFO, OPT, LRU.
 Giải thuật n愃o l愃 bĀt khả thi nhĀt? V椃 sao?
 Giải thuật n愃o l愃 phức t愃⌀p nhĀt? V椃 sao? Nhận xét:
 Giải thuật FIFO: dễ c愃i đặt, dễ hiện thực, hiệu quả kém
 Giải thuật LRU: khó c愃i đặt, phức t愃⌀p, hiệu quả
 Giải thuật OPT: không khả thi, nhưng hiệu quả nhĀt
Giải thuật bĀt khả thi nhĀt l愃 OPT v椃 việc biết trước những trang n愃o có
thऀ được truy xuĀt tiếp theo gần như l愃 điu không thऀ.
Giải thuật phức t愃⌀p nhĀt l愃 OPT v愃 LRU v椃 mỗi lần lỗi trang, khi t椃m
khung trang th椃Āch hợp đऀ thay thế th椃 phải xét đến to愃n bộ chuỗi tham chiếu trước/sau nó.