Mẫu Báo cáo thực hành lần 6 | Môn Hệ điều hành
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. Tài liệu giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao
Trường: Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh
Thông tin:
Tác giả:
Thông tin :
Môn:
Trường:
Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh
Tác giả:
Tài liệu liên quan:
Preview text:
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 nhiu 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 cu truy xuĀt
if (flag[t] == 1) count++;
if (count == frame) // SĀ trang c漃Ā nhu cu 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 cu 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 phn tử c漃Ā ln 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Ā phn tử chùi tham chiĀu: \n"); scanf("%d", &n);
printf(" \nNhập vào chù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|Chù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愃 điu 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ó.