SHARE
TWEET

Untitled

a guest May 22nd, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. struct Process {
  5.     int name;
  6.     int burst_time;
  7.     int arrival_time;
  8.  
  9. };
  10. static double ave_turnaround_time = 0;
  11. static double ave_waiting_time = 0;
  12. void swap(Process &p1, Process &p2) {
  13.     Process tmp;
  14.     tmp = p1;
  15.     p1 = p2;
  16.     p2 = tmp;
  17. }
  18.  
  19. int minBurstTime(Process *p, int n) {
  20.     int min = p[0].burst_time;
  21.     int imin = 0;
  22.     for (int i = 0; i < n; i++)
  23.     {
  24.         if (p[i].burst_time < min) {
  25.             min = p[i].burst_time;
  26.             imin = i;
  27.  
  28.  
  29.         }
  30.     }
  31.     return imin;
  32. }
  33.  
  34. void sortByArrivalTime(Process *p, int n) {
  35.     for (int i = 0; i < n; i++)
  36.     {
  37.         for (int j = i + 1; j < n; j++)
  38.         {
  39.             if (p[i].arrival_time < p[j].arrival_time) {
  40.                 swap(p[i], p[j]);
  41.             }
  42.             else {
  43.                 if (p[i].arrival_time == p[j].arrival_time) {
  44.                     if (p[i].burst_time < p[j].burst_time)
  45.                     {
  46.                         swap(p[i], p[j]);
  47.                     }
  48.  
  49.                 }
  50.             }
  51.  
  52.         }
  53.     }
  54. }
  55.  
  56. void ShortestRemainingTimeFirst(Process *p, int n, int time_current, int burst_time) {
  57.     for (int i = 0; i < n - 1; i++)
  58.     {
  59.         for (int j = i + 1; j < n; j++)
  60.         {
  61.             if (p[i].burst_time < p[j].burst_time && p[i].arrival_time <= time_current && p[i].burst_time < burst_time) {
  62.                 swap(p[i], p[j]);
  63.             }
  64.         }
  65.     }
  66.  
  67. }
  68.  
  69. void Input(Process *p, int n) {
  70.     for (int i = 0; i < n; i++) {
  71.         cout << "-----------------" << endl;
  72.         cout << "Nhap ID process: "; cin >> p[i].name;
  73.         cout << "Nhap burst time: "; cin >> p[i].burst_time;
  74.         cout << "Nhap arrival time: "; cin >> p[i].arrival_time;
  75.  
  76.     }
  77. }
  78.  
  79. int check(int flag[], int n) {
  80.     for (int i = 0; i < n; i++) {
  81.         if (flag[i] == 1) return 1;
  82.     }
  83.     return 0;
  84. }
  85.  
  86. void SelectionFunction(Process *p, int n) {
  87.     Process *p_temp = new Process[100];
  88.     int time_current = 0; // timeline chương trình
  89.     ///
  90.     int flag_c = 1; // phòng trừ trường hợp không có process nào tới tại thời điểm 0
  91.     int flag_first_come[100]; // đánh dấu thời điểm được thực thi lần đầu
  92.     int flag_previous; // vị trí process vừa chạy trước đó
  93.     int flag_current; // vị trí process hiện đang chạy
  94.     int waiting_time[100]; // tính thời gian chờ mỗi khi bị preemtive đến lúc được thực thi lại
  95.     /// khởi tạo các mảng tạm
  96.     for (int i = 0; i < 100; i++) {
  97.         waiting_time[i] = 0;
  98.         flag_first_come[i] = -1; // -1 vì nếu sử dụng 0 để đánh dấu (flag chỉ cập nhật duy nhất 1 lần
  99.                                     // ) thì sẽ có process đầu tiên có arrival time = 0 cập nhật 2 lần
  100.     }
  101.     sortByArrivalTime(p, n); // chọn ra process có burst time min xếp ra phía cuối
  102.     flag_first_come[p[n - 1].name] = p[n-1].arrival_time;
  103.     // Duyệt từ cuối lên
  104.     while (n > 0) {
  105.         p[n - 1].burst_time--; // Xét từ từ chậm rãi
  106.         // tăng waiting time khi process đã đến hàng đợi mà chưa được thực thi
  107.         for (int i = 0; i < n; i++) {
  108.             if (p[i].arrival_time <= time_current) {
  109.                 waiting_time[p[i].name]++;
  110.             }
  111.         }
  112.         // Chừa thằng đang thực thi ra
  113.         waiting_time[p[n - 1].name]--;
  114.         // Trừ trường hợp ko có process nào đến lúc time_current = 0
  115.         if (flag_c == 1) {
  116.             time_current = p[n - 1].arrival_time;
  117.             flag_c = 0;
  118.         }
  119.         time_current++;
  120.         flag_previous = p[n - 1].name; // Lưu tên process sắp rời/ có khả năng rời hàng đợi
  121.         // Nếu đã thực thi hết (không còn burst thì cout trạng thái
  122.         if (p[n - 1].burst_time == 0) {
  123.             cout << p[n - 1].name << "            " << flag_first_come[p[n - 1].name] - p[n-1].arrival_time << "               " << waiting_time[p[n - 1].name] << "            " << (time_current - p[n-1].arrival_time) << endl;
  124.             ave_waiting_time += waiting_time[p[n - 1].name]; // cộng dồn waiting time đã cộng nãy giờ
  125.             ave_turnaround_time += time_current - p[n - 1].arrival_time;   
  126.             n--; // thu hẹp kích thước để xét những thằng còn lại
  127.             if (n == 0) return;
  128.         }      
  129.         ShortestRemainingTimeFirst(p, n, time_current, p[n-1].burst_time); // chọn ra thằng có burst < burst còn lại của p[flag_current]
  130.         flag_current = p[n - 1].name; // cập nhập lại nếu có thằng nào đó thỏa cái trên
  131.         // nếu chuyển ngữ cảnh xảy ra
  132.         if (flag_current != flag_previous) {
  133.             if (flag_first_come[p[n - 1].name] == -1) {
  134.                 flag_first_come[p[n - 1].name] = time_current;
  135.             }
  136.  
  137.  
  138.         }
  139.     }
  140. }
  141.  
  142.  
  143. int main()
  144. {
  145.     Process *p = new Process[100];
  146.     queue<Process> pQueue;
  147.     int n;
  148.     cout << "Nhap so luong process: "; cin >> n;
  149.     Input(p, n);
  150.     cout << "Process   Response-time   Waiting-time   Turn around-time" << endl;
  151.  
  152.     SelectionFunction(p, n);
  153.  
  154.     cout << "Thoi gian dap ung trung binh: " << ave_waiting_time / n << endl;
  155.     cout << "Thoi gian hoan thanh trung binh: " << ave_turnaround_time / n << endl;
  156.  
  157.     system("pause");
  158.     return 0;
  159. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top