Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. Họ và tên:
Trần Bảo Phú – 22521104
Nguyễn Hoàng Gia An – 22520021
Nguyễn Duy Khang – 22520619
Nguyễn Văn Duy Bảo – 22520114 Lớp: IT007.O11 HỆ ĐIỀU HÀNH BÁO CÁO LAB 4 CHECKLIST 3.5. BÀI TẬP THỰC HÀNH BT 1 BT 2
Vẽ lưu đồ giải thuật x x
Chạy tay lưu đồ giải thuật x x Hiện thực code x x
Chạy code và kiểm chứng x x 3.6. BÀI TẬP ÔN TẬP BT 1
Vẽ lưu đồ giải thuật 
Chạy tay lưu đồ giải thuật  Hiện thực code x
Chạy code và kiểm chứng x Tự chấm điểm: 9/10 1
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng.
*Lưu ý: Xuất báo cáo theo định dạng PDF, đặt tên theo cú pháp: _LAB3.pdf 2.5. BÀI TẬP THỰC HÀNH
1. Giải thuật Shortest-Job-First - Lưu đồ giải thuật: - Hàm sortByArrival: - Hàm sortByBurst: 2
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. - Giải thuật SJF: 3
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng.
 Chạy tay lưu đồ giải thuật: Process Arrival time Burst time P1 2 3 P2 4 7 P3 5 2 P4 3 2 P5 1 1
-Nhập n=5 với dữ liệu như bảng trên. Sau khi chạy hàm sortByArrivalTime ta được bảng mới: 4
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. Process Arrival time Burst time P3 5 2 P2 4 7 P4 3 2 P1 2 3 P5 1 1
*Xét n=5 ta có: p[n-1] = p[5-1] = p[4] ( Tiến trình P5) + i=0
+ time_current = p[n-1].arrival_time = p[5-1].arrival_time = p[4].arrival.time
=> time_current là arrival time của tiến trình P5 =>time_current = 1;
-Do i+time_current += p[n-1].burst_time ⇔ time_current += p[4].burst_time ⇔time_current = 1+1 = 2;
+Start = time_current - p[n-1].burst_time ⇔ 2- 1 = 1; TAT = time_current - p[n-
1].arrival_time ⇔ 2 - 1 = 1; End = time_current = 2; Gantt chart: 0 1 2
+avg_waiting_time += start - p[n-1].arrival_time
⇔ avg_waiting_time += start - p[n-1].arrival_time = 1 - 1 = 0; avg_turn_around_time +=
TAT ⇔ avg_turn_around_time = 0 + 1 = 1; 5
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. +n = n - 1 = 4
+Sử dụng hàm sortByBurstTime ta được Process Arrival time Burst time P3 5 2 P2 4 7 P4 3 2 P1 2 3
*Xét n=4 ta có: ( Thực thi tiến trình P1) Tương tự, ta có:
+time_current += p[n-1].burst_time ⇔ time_current = 2 + 3 = 5;
+Start = time_current - p[n-1].burst_time ⇔ 5 - 3 = 2; TAT = time_current - p[n-
1].arrival_time ⇔ 5 - 2 = 3; End = time_current = 5; Gantt chart: P5 P1 0 1 2 5
+avg_waiting_time += start - p[n-1].arrival_time
⇔ avg_waiting_time += start - p[n-1].arrival_time = 0+( 2 - 2) = 0; avg_turn_around_time += TAT
⇔ avg_turn_around_time = 1 + 5 = 6; +n = n - 1 = 3
+Sử dụng hàm sortByBurstTime ta có: 6
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. Process Arrival time Burst time P2 4 7 P3 5 2 P4 3 2
*Xét n=3 ta có: ( Thực thi tiến trình P4) Tương tự, ta có:
+time_current += p[n-1].burst_time ⇔ time_current = 5+ 2 = 7;
+Start = time_current - p[n-1].burst_time ⇔ 7- 2 = 5; TAT = time_current - p[n-
1].arrival_time ⇔ 7 - 3 = 4; End = time_current = 7; Gantt chart: P5 P1 P4 0 1 2 5 7
+avg_waiting_time += start - p[n-1].arrival_time
⇔ avg_waiting_time += start - p[n-1].arrival_time = 0+(5 - 3) = 2; avg_turn_around_time += TAT
⇔ avg_turn_around_time =6 + 4 = 10; +n = n - 1 = 2
+Sử dụng hàm sortByBurstTime ta có bảng: Process Arrival time Burst time P2 4 7 P3 5 2 7
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng.
*Xét n=2 ta có: ( Thực thi tiến trình P3) Tương tự, ta có:
+time_current += p[n-1].burst_time ⇔ time_current = 7+ 2 = 9;
+Start = time_current - p[n-1].burst_time ⇔ 9- 2 = 7; TAT = time_current - p[n-
1].arrival_time ⇔ 9 - 5 = 4; End = time_current = 9; Gantt chart: P5 P1 P4 P3 0 1 2 5 7 9
+avg_waiting_time += start - p[n-1].arrival_time
⇔ avg_waiting_time += start - p[n-1].arrival_time =2 + ( 7 - 5 ) = 4; avg_turn_around_time += TAT
⇔ avg_turn_around_time =10 + 4 = 14; +n = n - 1 = 1
+Sử dụng hàm sortByBurstTime ta có bảng: Process Arrival time Burst time P2 4 7
*Xét n=1 ta có: ( Thực thi tiến trình P2) Tương tự, ta có:
+time_current += p[n-1].burst_time ⇔ time_current = 9+ 7 = 16;
+Start = time_current - p[n-1].burst_time ⇔ 16 - 2 = 14; TAT = time_current - p[n-
1].arrival_time ⇔ 16 - 4 = 12; End = time_current = 16; Gantt chart: 8
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. P5 P1 P4 P3 P2 0 1 2 5 7 9 16
+avg_waiting_time += start - p[n-1].arrival_time
⇔ avg_waiting_time += start - p[n-1].arrival_time = 4 + (9 - 4) = 9; avg_turn_around_time += TAT
⇔ avg_turn_around_time = 14 + 12 = 26; +n = n - 1 = 0
*Xét n=0: Vòng lặp sẽ dừng
+Chương trình xuất ra kết quả avg_waiting_time = 9/5 = 1.8
+Chương trình xuất ra kết quả avg_waiting_time = 26/5 = 5.2  Hiện thực code: #include #include #include typedef struct { int iPID; int iArrival, iBurst;
int iStart, iFinish, iWaiting, iResponse, iTaT, iQuantumTime; } PCB; typedef struct 9
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. { int iPID; int iStart, iFinish; } Gantt;
float iAverageWT = 0, iAverageTaT = 0;
void inputProcess(int n, PCB P[]) { srand(time(0));
for (int i = 0; i < n; i++) { P[i].iPID = i + 1; P[i].iArrival = rand() % 21;
P[i].iBurst = 2 + rand() % 11; } }
void printProcess(int n, PCB P[]) {
for (int i = 0; i < n; i++) {
printf("PID: %d, Arrival time: %d, Bursting time: %d\n", P[i].iPID, P[i].iArrival, P[i].iBurst); } } Gantt GanttChart[20]; 10
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. int ganttSize = 0;
void addToGanttChart(int iPID, int iStart, int iFinish) {
if ((ganttSize > 0) && (GanttChart[ganttSize - 1].iPID == iPID)) {
GanttChart[ganttSize - 1].iFinish = iFinish; } else {
GanttChart[ganttSize].iPID = iPID;
GanttChart[ganttSize].iStart = iStart;
GanttChart[ganttSize].iFinish = iFinish; ganttSize++; } } void exportGanttChart() { printf("\nGantt Chart:\n");
for (int i = 0; i < ganttSize; i++) {
if(GanttChart[i].iPID > 0)
printf("| P%d ", GanttChart[i].iPID); else printf("| __ "); } 11
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. printf("|\n");
for (int i = 0; i < ganttSize; i++) {
printf("%d ", GanttChart[i].iStart); if (i == ganttSize - 1)
printf("%d\n", GanttChart[i].iFinish); } printf("\n\n"); }
void sortByArrival(int n, PCB P[]) { PCB Ptemp;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (P[i].iArrival < P[j].iArrival) { Ptemp = P[i]; P[i] = P[j]; P[j] = Ptemp; } } } } 12
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng.
void sortByBurst(int n, PCB P[], int iTime) { PCB Ptemp;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (P[i].iBurst < P[j].iBurst && P[i].iArrival <= iTime) { Ptemp = P[i]; P[i] = P[j]; P[j] = Ptemp; } } } }
void ShortestJobFirst(int n, PCB P[]) {
int i, j, iTime = 0, iMin, iTemp, iCount = 0; sortByArrival(n, P); iTime = P[n - 1].iArrival; for (i = 0; i < n; n--) {
if(P[n - 1].iArrival > iTime) { 13
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. P[n - 1].iStart = iTime; iTime = P[n - 1].iArrival; P[n - 1].iFinish = iTime;
addToGanttChart(-1, P[n - 1].iStart, P[n - 1].iFinish); n++; continue; } else{ P[n - 1].iStart = iTime; } iTime += P[n - 1].iBurst; P[n - 1].iFinish = iTime;
addToGanttChart(P[n - 1].iPID, P[n - 1].iStart, P[n - 1].iFinish);
sortByBurst(n - 1, P, iTime);
iAverageWT += (iTime - P[n - 1].iArrival - P[n - 1].iBurst);
iAverageTaT += (iTime - P[n - 1].iArrival); P[n - 1].iStart = 0; P[n - 1].iFinish = 0; } } int main() { PCB Input[20]; Gantt GanttChart[100];
int iNumberOfProcess, ganttSize = 0; 14
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng.
printf("Enter number of process: ");
scanf("%d", &iNumberOfProcess);
inputProcess(iNumberOfProcess, Input);
printProcess(iNumberOfProcess, Input);
printf("\n================================\n");
printf("====== Shortest Job First ======\n");
printf("================================\n\n");
ShortestJobFirst(iNumberOfProcess, Input);
// printf("| PID | Arrival Time | Bursting Time | Turn-around Time | Waiting Time |\n");
// for (int i = 0; i < iNumberOfProcess; i++) // {
// printf("| %d | %d | %d | %d | %d |\n",
Input[i].iPID, Input[i].iArrival, Input[i].iBurst, Input[i].iTaT, Input[i].iWaiting); // }
exportGanttChart(ganttSize, GanttChart);
printf("Average Waiting Time: %2f\n", iAverageWT / iNumberOfProcess);
printf("Average Turn-around Time: %2f\n", iAverageTaT / iNumberOfProcess); }
 Chạy code và kiểm chứng: 1. Test case 1 a. Kết quả chạy code 15
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. - Gantt Chart: P2 - P4 - P3 P5 P1 0 5 6 12 15 24 31 41 P1 P2 P3 P4 P5 Average TG đáp ứng 13 0 0 0 5 3.6 TG đợi 13 0 0 0 5 3.6 TG hoàn 23 5 9 6 12 11 thành 2. Test case 2 a. Kết quả chạy code 16
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. b. Chạy tay kiểm chứng - Gantt chart: P3 P2 P4 P5 P1 1 11 17 23 33 44 P1 P2 P3 P4 P5 Average TG đáp ứng 30 10 0 9 19 13.6 TG đợi 30 10 0 9 19 13.6 TG hoàn 41 16 10 15 29 22.2 thành 3. Test case 3 a. Kết quả chạy code 17
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. b. Chạy tay kiểm chứng P3 P5 P1 P4 P2 3 5 8 10 21 33 P1 P2 P3 P4 P5 Average TG đáp ứng 2 17 0 4 0 4.6 TG đợi 2 17 0 4 0 4.6 TG hoàn 4 29 2 15 3 10.6 thành
2. Giải thuật Shortest-Remaining-Time-First
 Lưu đồ giải thuật:
- Lưu đồ hàm sort giảm dần các tiến trình đưa vào arrival time 18
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng. 19
Báo cáo thực hành môn Hệ điều hành - Giảng viên: Thân Thế Tùng.
- Lưu đồ hàm ShortestRemainingTimeFirst để lọc qua các cặp tiến trình và sort các
giá trị có burst_time nhỏ hơn burst_time của tiến trình đang được thực thi. 20