不同到达时间的优先级CPU调度

先决条件—— 优先级调度程序-设置1 优先级调度是一种非抢占式算法，是批处理系统中最常见的调度算法之一。如果两个流程的到达时间相同，则为每个流程分配第一个到达时间（少于第一个流程的到达时间），然后比较优先级（最高流程优先）。此外，如果两个进程具有相同的优先级，则将其与进程号进行比较（先减少进程号）。在执行所有过程时，重复此过程。

null

实施——

首先输入进程的到达时间、突发时间和优先级。
第一个进程的到达时间最短，如果两个或多个进程的到达时间最短，则优先级较高的人将首先进行调度。
现在将根据流程的到达时间和优先级安排进一步的流程。（这里我们假设优先级越低，优先级越高）。我如果两个进程优先级相同，则根据进程编号进行排序。注：在问题中，他们会清楚地提到，哪个数字的优先级更高，哪个数字的优先级更低。
一旦所有流程完成，我们就可以根据它们的优先级来安排它们。

图片[1]-不同到达时间的优先级CPU调度–设置2-yiteyi-C++库

甘特图-

图片[2]-不同到达时间的优先级CPU调度–设置2-yiteyi-C++库

示例——

Input :process no-> 1 2 3 4 5 arrival time-> 0 1 3 2 4burst time-> 3 6 1 2 4priority-> 3 4 9 7 8Output :Process_no   arrival_time   Burst_time   Complete_time    Turn_Around_Time       Waiting_Time1             0               3                3                   3               02             1               6                9                   8               2 3             3               1                16                  13              124             2               2                11                  9               75             4               4                15                  11              7Average Waiting Time is : 5.6Average Turn Around time is : 8.8

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

C++

                         // C++ implementation for Priority Scheduling with                       
                         //Different Arrival Time priority scheduling                       
                         /*1. sort the processes according to arrival time                       
                         2. if arrival time is same the acc to priority                       
                         3. apply fcfs                       
                         */                       
           
                         #include <bits/stdc++.h>                       
           
                         using                                     namespace                                     std;                       
           
                         #define totalprocess 5                       
           
                         // Making a struct to hold the given input                       
           
                         struct                                     process                       
                         {                       
                         int                                     at,bt,pr,pno;                       
                         };                       
           
                         process proc[50];                       
           
                         /*                       
                         Writing comparator function to sort according to priority if                       
                         arrival time is same                       
                         */                       
           
                         bool                                     comp(process a,process b)                       
                         {                       
                         if                                     (a.at == b.at)                       
                         {                       
                         return                                     a.pr<b.pr;                       
                         }                       
                         else                       
                         {                       
                                                 return                                     a.at<b.at;                       
                         }                       
                         }                       
           
                         // Using FCFS Algorithm to find Waiting time                       
                         void                                     get_wt_time(                                     int                                     wt[])                       
                         {                       
                         // declaring service array that stores cumulative burst time                       
                         int                                     service[50];                       
           
                         // Initialising initial elements of the arrays                       
                         service[0] = proc[0].at;                       
                         wt[0]=0;                       
           
           
                         for                                     (                                     int                                     i=1;i<totalprocess;i++)                       
                         {                       
                         service[i]=proc[i-1].bt+service[i-1];                       
           
                         wt[i]=service[i]-proc[i].at;                       
           
                         // If waiting time is negative, change it into zero                       
                                   
                                                 if                                     (wt[i]<0)                       
                                                 {                       
                                                 wt[i]=0;                       
                                                 }                       
                         }                       
           
                         }                       
           
                         void                                     get_tat_time(                                     int                                     tat[],                                     int                                     wt[])                       
                         {                       
                         // Filling turnaroundtime array                       
           
                         for                                     (                                     int                                     i=0;i<totalprocess;i++)                       
                         {                       
                                                 tat[i]=proc[i].bt+wt[i];                       
                         }                       
                                   
                         }                       
           
                         void                                     findgc()                       
                         {                       
                         //Declare waiting time and turnaround time array                       
                         int                                     wt[50],tat[50];                       
           
                         double                                     wavg=0,tavg=0;                       
           
                         // Function call to find waiting time array                       
                         get_wt_time(wt);                       
                         //Function call to find turnaround time                       
                         get_tat_time(tat,wt);                       
                                   
                         int                                     stime[50],                                     ctime                                     [50];                       
           
                         stime[0] = proc[0].at;                       
                         ctime                                     [0]=stime[0]+tat[0];                       
           
                         // calculating starting and ending time                       
                         for                                     (                                     int                                     i=1;i<totalprocess;i++)                       
                                                 {                       
                                                 stime[i]=                                     ctime                                     [i-1];                       
                                                 ctime                                     [i]=stime[i]+tat[i]-wt[i];                       
                                                 }                       
                                   
                         cout<<                                     "Process_no	Start_time	Complete_time	Turn_Around_Time	Waiting_Time"                                     <<endl;                       
                                   
                                                 // display the process details                       
                                   
                         for                                     (                                     int                                     i=0;i<totalprocess;i++)                       
                                                 {                       
                                                 wavg += wt[i];                       
                                                 tavg += tat[i];                       
                                   
                                                 cout<<proc[i].pno<<                                     "		"                                     <<                       
                                                 stime[i]<<                                     "		"                                     <<                                     ctime                                     [i]<<                                     "		"                                     <<                       
                                                 tat[i]<<                                     "			"                                     <<wt[i]<<endl;                       
                                                 }                       
                                   
                                                 // display the average waiting time                       
                                                 //and average turn around time                       
                                   
                                                 cout<<                                     "Average waiting time is : "                                     ;                       
                                                 cout<<wavg/(                                     float                                     )totalprocess<<endl;                       
                                                 cout<<                                     "average turnaround time : "                                     ;                       
                                                 cout<<tavg/(                                     float                                     )totalprocess<<endl;                       
           
                         }                       
           
                         int                                     main()                       
                         {                       
                         int                                     arrivaltime[] = { 1, 2, 3, 4, 5 };                       
                         int                                     bursttime[] = { 3, 5, 1, 7, 4 };                       
                         int                                     priority[] = { 3, 4, 1, 7, 8 };                       
                                   
                         for                                     (                                     int                                     i=0;i<totalprocess;i++)                       
                         {                       
                                                 proc[i].at=arrivaltime[i];                       
                                                 proc[i].bt=bursttime[i];                       
                                                 proc[i].pr=priority[i];                       
                                                 proc[i].pno=i+1;                       
                                                 }                       
                                   
                                                 //Using inbuilt sort function                       
                                   
                                                 sort(proc,proc+totalprocess,comp);                       
                                   
                                                 //Calling function findgc for finding Gantt Chart                       
                                   
                                                 findgc();                       
           
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by Anukul Chand.                       

JAVA

                         // Java implementation for Priority Scheduling with                       
                         //Different Arrival Time priority scheduling                       
                         import                                     java.util.*;                       
           
                         /// Data Structure                       
                         class                                     Process {                       
                                                 int                                     at, bt, pri, pno;                       
                                                 Process(                                     int                                     pno,                                     int                                     at,                                     int                                     bt,                                     int                                     pri)                       
                                                 {                       
                                                 this                                     .pno = pno;                       
                                                 this                                     .pri = pri;                       
                                                 this                                     .at = at;                       
                                                 this                                     .bt = bt;                       
                                                 }                       
                         }                       
           
                         /// Gantt chart structure                       
                         class                                     GChart {                       
                                                 // process number, start time, complete time,                       
                                                 // turn around time, waiting time                       
                                                 int                                     pno, stime, ctime, wtime, ttime;                       
                         }                       
           
                         // user define comparative method (first arrival first serve,                       
                         // if arrival time same then heigh priority first)                       
                         class                                     MyComparator                                     implements                                     Comparator {                       
           
                                                 public                                     int                                     compare(Object o1, Object o2)                       
                                                 {                       
           
                                                 Process p1 = (Process)o1;                       
                                                 Process p2 = (Process)o2;                       
                                                 if                                     (p1.at < p2.at)                       
                                                 return                                     (-                                     1                                     );                       
           
                                                 else                                     if                                     (p1.at == p2.at && p1.pri > p2.pri)                       
                                                 return                                     (-                                     1                                     );                       
           
                                                 else                       
                                                 return                                     (                                     1                                     );                       
                                                 }                       
                         }                       
           
           
                         // class to find Gantt chart                       
                         class                                     FindGantChart {                       
                                                 void                                     findGc(LinkedList queue)                       
                                                 {                       
           
                                                 // initial time = 0                       
                                                 int                                     time =                                     0                                     ;                       
           
                                                 // priority Queue sort data according                       
                                                 // to arrival time or priority (ready queue)                       
                                                 TreeSet prique =                                     new                                     TreeSet(                                     new                                     MyComparator());                       
           
                                                 // link list for store processes data                       
                                                 LinkedList result =                                     new                                     LinkedList();                       
           
                                                 // process in ready queue from new state queue                       
                                                 while                                     (queue.size() >                                     0                                     )                       
                                                 prique.add((Process)queue.removeFirst());                       
           
                                                 Iterator it = prique.iterator();                       
           
                                                 // time set to according to first process                       
                                                 time = ((Process)prique.first()).at;                       
           
                                                 // scheduling process                       
                                                 while                                     (it.hasNext()) {                       
           
                                                 // dispatcher dispatch the                       
                                                 // process ready to running state                       
                                                 Process obj = (Process)it.next();                       
           
                                                 GChart gc1 =                                     new                                     GChart();                       
                                                 gc1.pno = obj.pno;                       
                                                 gc1.stime = time;                       
                                                 time += obj.bt;                       
                                                 gc1.ctime = time;                       
                                                 gc1.ttime = gc1.ctime - obj.at;                       
                                                 gc1.wtime = gc1.ttime - obj.bt;                       
           
                                                 /// store the exxtreted process                       
                                                 result.add(gc1);                       
                                                 }                       
           
                                                 // create object of output class and call method                       
                                                 new                                     ResultOutput(result);                       
                                                 }                       
                         }                       

Python3

                         # Python3 implementation for Priority Scheduling with                       
                         # Different Arrival Time priority scheduling                       
                         """1. sort the processes according to arrival time                       
                                                 2. if arrival time is same the acc to priority                       
                                                 3. apply fcfs """                       
                                   
                         totalprocess                                     =                                     5                       
                         proc                                     =                                     []                       
                         for                                     i                                     in                                     range                                     (                                     5                                     ):                       
                                                 l                                     =                                     []                       
                                                 for                                     j                                     in                                     range                                     (                                     4                                     ):                       
                                                 l.append(                                     0                                     )                       
                                                 proc.append(l)                       
           
                         # Using FCFS Algorithm to find Waiting time                       
                         def                                     get_wt_time( wt):                       
           
                                                 # declaring service array that stores                       
                                                 # cumulative burst time                       
                                                 service                                     =                                     [                                     0                                     ]                                     *                                     5                       
           
                                                 # Initialising initial elements                       
                                                 # of the arrays                       
                                                 service[                                     0                                     ]                                     =                                     0                       
                                                 wt[                                     0                                     ]                                     =                                     0                       
           
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , totalprocess):                       
                                                 service[i]                                     =                                     proc[i                                     -                                     1                                     ][                                     1                                     ]                                     +                                     service[i                                     -                                     1                                     ]                       
                                                 wt[i]                                     =                                     service[i]                                     -                                     proc[i][                                     0                                     ]                                     +                                     1                       
           
                                                 # If waiting time is negative,                       
                                                 # change it o zero                       
                                                 if                                     (wt[i] <                                     0                                     ) :                       
                                                 wt[i]                                     =                                     0                       
                                   
                         def                                     get_tat_time(tat, wt):                       
           
                                                 # Filling turnaroundtime array                       
                                                 for                                     i                                     in                                     range                                     (totalprocess):                       
                                                 tat[i]                                     =                                     proc[i][                                     1                                     ]                                     +                                     wt[i]                       
           
                         def                                     findgc():                       
                                   
                                                 # Declare waiting time and                       
                                                 # turnaround time array                       
                                                 wt                                     =                                     [                                     0                                     ]                                     *                                     5                       
                                                 tat                                     =                                     [                                     0                                     ]                                     *                                     5                       
           
                                                 wavg                                     =                                     0                       
                                                 tavg                                     =                                     0                       
           
                                                 # Function call to find waiting time array                       
                                                 get_wt_time(wt)                       
                                   
                                                 # Function call to find turnaround time                       
                                                 get_tat_time(tat, wt)                       
           
                                                 stime                                     =                                     [                                     0                                     ]                                     *                                     5                       
                                                 ctime                                     =                                     [                                     0                                     ]                                     *                                     5                       
                                                 stime[                                     0                                     ]                                     =                                     1                       
                                                 ctime[                                     0                                     ]                                     =                                     stime[                                     0                                     ]                                     +                                     tat[                                     0                                     ]                       
                                   
                                                 # calculating starting and ending time                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , totalprocess):                       
                                                 stime[i]                                     =                                     ctime[i                                     -                                     1                                     ]                       
                                                 ctime[i]                                     =                                     stime[i]                                     +                                     tat[i]                                     -                                     wt[i]                       
           
                                                 print                                     (                                     "Process_no	Start_time	Complete_time"                                     ,                       
                                                 "	Turn_Around_Time	Waiting_Time"                                     )                       
           
                                                 # display the process details                       
                                                 for                                     i                                     in                                     range                                     (totalprocess):                       
                                                 wavg                                     +                                     =                                     wt[i]                       
                                                 tavg                                     +                                     =                                     tat[i]                       
                                   
                                                 print                                     (proc[i][                                     3                                     ],                                     "		"                                     , stime[i],                       
                                                 "		"                                     , end                                     =                                     " "                                     )                       
                                                 print                                     (ctime[i],                                     "		"                                     , tat[i],                                     "			"                                     , wt[i])                       
           
           
                                                 # display the average waiting time                       
                                                 # and average turn around time                       
                                                 print                                     (                                     "Average waiting time is : "                                     , end                                     =                                     " "                                     )                       
                                                 print                                     (wavg                                     /                                     totalprocess)                       
                                                 print                                     (                                     "average turnaround time : "                                     , end                                     =                                     " "                                     )                       
                                                 print                                     (tavg                                     /                                     totalprocess)                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                                 arrivaltime                                     =                                     [                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ]                       
                                                 bursttime                                     =                                     [                                     3                                     ,                                     5                                     ,                                     1                                     ,                                     7                                     ,                                     4                                     ]                       
                                                 priority                                     =                                     [                                     3                                     ,                                     4                                     ,                                     1                                     ,                                     7                                     ,                                     8                                     ]                       
                                   
                                                 for                                     i                                     in                                     range                                     (totalprocess):                       
           
                                                 proc[i][                                     0                                     ]                                     =                                     arrivaltime[i]                       
                                                 proc[i][                                     1                                     ]                                     =                                     bursttime[i]                       
                                                 proc[i][                                     2                                     ]                                     =                                     priority[i]                       
                                                 proc[i][                                     3                                     ]                                     =                                     i                                     +                                     1                       
                                   
                                                 # Using inbuilt sort function                       
                                                 proc                                     =                                     sorted                                     (proc, key                                     =                                     lambda                                     x:x[                                     2                                     ])                       
                                                 proc                                     =                                     sorted                                     (proc)                       
                                   
                                                 # Calling function findgc for                       
                                                 # finding Gantt Chart                       
                                                 findgc()                       
           
                         # This code is contributed by                       
                         # Shubham Singh(SHUBHAMSINGH10)                       

输出：

Process_no Start_time Complete_time Turn_Around_Time Waiting_Time1           1           4              3              0 2           5           10             8              33           4           5              2              14          10           17             13             65          17           21             16             12Average Waiting Time is : 4.4 Average Turn Around time is : 8.4

时间复杂性： O（N*logN），其中N是进程总数。 辅助空间： O（N）

本文由 阿米特·维尔玛 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

Java