非抢占式优先级调度
Non-Preemptive priority scheduling
算法解释：
Non-preemptive Priority scheduling
Each process has (arrival time, priority, and burst(execution) time) the process with first arrival time (less arrival time process) will be executed first, if two processes have same arrival time, then compare to priorities (highest process first). Also, if two processes have same priority then compare to process number (less process number first). This process is repeated while all process get executed.
我使用了下面的代码（代码已更新）但我没有得到正确的答案。我已经尝试解决了 2 周，但不幸的是我不知道错误在哪里（这是一个逻辑错误，但我无法识别）。调试了很多次，还是找不到原因。
#include <stdio.h>
void main()
{
int pn = 0; //Processes Number
int CPU = 0; //CPU Current time
int allTime = 0; // Time neded to finish all processes
printf("Enrer Processes Count: ");
scanf("%d",&pn);
int AT[pn];
int ATt[pn];
int NoP = pn;
int PT[pn]; //Processes Time
int PP[pn]; //Processes piriorty
int PPt[pn];
int waittingTime[pn];
int turnaroundTime[pn];
int i=0;
//Scanning Time and Piriorty
for(i=0 ;i<pn ;i++){
printf("\nProcessing time for P%d: ",i+1);
scanf("%d",&PT[i]);
printf("Piriorty for P%d: ",i+1);
scanf("%d",&PP[i]);
PPt[i] = PP[i];
printf("Arrival Time for P%d: ",i+1);
scanf("%d",&AT[i]);
ATt[i] = AT[i];
}
int LAT = 0; //LastArrivalTime
for(i = 0; i < pn; i++)
if(AT[i] > LAT)
LAT = AT[i];
int ATv = AT[0]; //Pointing to Arrival Time Value
int ATi = 0; //Pointing to Arrival Time indix
int P1 = PP[0]; //Pointing to 1st piriorty Value
int P2 = PP[0]; //Pointing to 2nd piriorty Value
//findding the First Arrival Time and Highst piriorty Process
while(NoP > 0 && CPU <= 1000){
for(i = 0; i < pn; i++){
if(ATt[i] < ATv){
ATi = i;
ATv = ATt[i];
P1 = PP[i];
P2 = PP[i];
}
else if(ATt[i] == ATv){
if(PP[i] != (pn+1))
P2 = PP[i];
if(P2 < P1){
ATi = i;
ATv = ATt[i];
P1 = PP[i];
P2 = PP[i];
}
}
}
if(CPU < ATv){
CPU = CPU+1;
ATi = 0; //Pointing to Arrival Time indix
ATv = ATt[ATi];
P1 = PP[0]; //Pointing to 1st piriorty Value
P2 = PP[0]; //Pointing to 2nd piriorty Value
continue;
}else{
waittingTime[ATi] = CPU - ATt[ATi];
CPU = CPU + PT[ATi];
turnaroundTime[ATi] = CPU - ATt[ATi];
ATt[ATi] = LAT +10;
ATv = LAT +10; //Pointing to Arrival Time Value
PPt[ATi] = pn + 1;
ATi = 0; //Pointing to Arrival Time indix
P1 = PP[0]; //Pointing to 1st piriorty Value
P2 = PP[0]; //Pointing to 2nd piriorty Value
NoP = NoP - 1;
}
}
printf("\nPN\tPT\tPP\tWT\tTT\n\n");
for(i = 0; i < pn; i++){
printf("P%d\t%d\t%d\t%d\t%d\n",i+1,PT[i],PP[i],waittingTime[i],turnaroundTime[i]);
}
int AvgWT = 0;
int AVGTaT = 0;
for(i = 0; i < pn; i++){
AvgWT = waittingTime[i] + AvgWT;
AVGTaT = turnaroundTime[i] + AVGTaT;
}
printf("AvgWaittingTime = %d\nAvgTurnaroundTime = %d\n",AvgWT/pn,AVGTaT/pn);
}
/*
Test Cases:
PT: Processing Time
PP: Process priority
WT Waitting Time
TaT: Turnaround Time
Arrival time for 1st 2 cases is 0
PN PT PP WT TaT
P1 10 3 6 16
P2 1 1 0 1
P3 2 4 16 18
P4 1 5 18 19
P5 5 2 1 6
PN PT PP WT TaT
P1 1 1 0 1
P2 2 2 1 3
P3 3 3 3 6
P4 4 4 6 10
P5 5 5 10 15
PN PP AT PT WT TaT
1 2 0 3 0 3
2 6 2 5 11 16
3 3 1 4 2 6
4 5 4 2 7 9
5 7 6 9 12 21
6 4 5 4 2 6
7 10 7 10 18 30
*/
正确的代码是：
#include <stdlib.h>
#include <stdio.h>
void main()
{
int pn = 0; //Processes Number
int CPU = 0; //CPU Current time
int allTime = 0; // Time neded to finish all processes
printf("Enrer Processes Count: ");
scanf("%d",&pn);
int AT[pn];
int ATt[pn];
int NoP = pn;
int PT[pn]; //Processes Time
int PP[pn]; //Processes piriorty
int PPt[pn];
int waittingTime[pn];
int turnaroundTime[pn];
int i=0;
//Scanning Time and Piriorty
for(i=0 ;i<pn ;i++){
printf("\nProcessing time for P%d: ",i+1);
scanf("%d",&PT[i]);
printf("Piriorty for P%d: ",i+1);
scanf("%d",&PP[i]);
PPt[i] = PP[i];
printf("Arrival Time for P%d: ",i+1);
scanf("%d",&AT[i]);
ATt[i] = AT[i];
}
int LAT = 0; //LastArrivalTime
for(i = 0; i < pn; i++)
if(AT[i] > LAT)
LAT = AT[i];
int MAX_P = 0; //Max Piriorty
for(i = 0; i < pn; i++)
if(PPt[i] > MAX_P)
MAX_P = PPt[i];
int ATi = 0; //Pointing to Arrival Time indix
int P1 = PPt[0]; //Pointing to 1st piriorty Value
int P2 = PPt[0]; //Pointing to 2nd piriorty Value
//findding the First Arrival Time and Highst piriorty Process
int j = -1;
while(NoP > 0 && CPU <= 1000){
for(i = 0; i < pn; i++){
if((ATt[i] <= CPU) && (ATt[i] != (LAT+10))){
if(PPt[i] != (MAX_P+1)){
P2 = PPt[i];
j= 1;
if(P2 < P1){
j= 1;
ATi = i;
P1 = PPt[i];
P2 = PPt[i];
}
}
}
}
if(j == -1){
CPU = CPU+1;
continue;
}else{
waittingTime[ATi] = CPU - ATt[ATi];
CPU = CPU + PT[ATi];
turnaroundTime[ATi] = CPU - ATt[ATi];
ATt[ATi] = LAT +10;
j = -1;
PPt[ATi] = MAX_P + 1;
ATi = 0; //Pointing to Arrival Time indix
P1 = MAX_P+1; //Pointing to 1st piriorty Value
P2 = MAX_P+1; //Pointing to 2nd piriorty Value
NoP = NoP - 1;
}
}
printf("\nPN\tPT\tPP\tAT\tWT\tTT\n\n");
for(i = 0; i < pn; i++){
printf("P%d\t%d\t%d\t%d\t%d\t%d\n",i+1,PT[i],PP[i],AT[i],waittingTime[i],turnaroundTime[i]);
}
int AvgWT = 0;
int AVGTaT = 0;
for(i = 0; i < pn; i++){
AvgWT = waittingTime[i] + AvgWT;
AVGTaT = turnaroundTime[i] + AVGTaT;
}
printf("AvgWaittingTime = %d\nAvgTurnaroundTime = %d\n",AvgWT/pn,AVGTaT/pn);
}
/*
Test Cases:
PT: Processing Time
PP: Process priority
WT Waitting Time
TaT: Turnaround Time
Arrival time for 1st 2 cases is 0
PN PT PP WT TaT
P1 10 3 6 16
P2 1 1 0 1
P3 2 4 16 18
P4 1 5 18 19
P5 5 2 1 6
PN PT PP WT TaT
P1 1 1 0 1
P2 2 2 1 3
P3 3 3 3 6
P4 4 4 6 10
P5 5 5 10 15
PN PT PP AT WT TT
P1 3 2 0 0 3
P2 5 6 2 11 16
P3 4 3 1 2 6
P4 2 5 4 7 9
P5 9 7 6 12 21
P6 4 4 5 2 6
P7 10 10 7 20 30
PN PT PP AT WT TT
P1 4 2 0 0 4
P2 3 3 1 3 6
P3 1 4 2 5 6
P4 5 5 3 5 10
P5 2 5 4 9 11
*/```
/*Non preemptive scheduling using C*/
#include<stdio.h>
#define MAX 20
typedef struct process{
int pid;
int arrival_time,burst_time,start_time,completion_time,ta_time,wait_time;
}Process;
Process p[MAX];
int main(){
int n,i;
int current_time = 0;
int completed = 0;
int is_completed[MAX]={0};
int totalta_time=0,totalwt_time=0;
float avgtt,avgwt;
printf(" enter number of processes ");
scanf("%d",&n);
for(i=0;i<n;i++){
printf("enter the id of the process ");
scanf("%d",&p[i].pid);
printf("enter arrival time ");
scanf("%d",&p[i].arrival_time);
printf("enter burst time ");
scanf("%d",&p[i].burst_time);
}
while(completed != n) {
int index = -1;
int min = 10000000;
for(i = 0; i < n; i++) {
if(p[i].arrival_time <= current_time && is_completed[i] == 0) {
if(p[i].burst_time < min) {
min = p[i].burst_time;
index = i;
}
if(p[i].burst_time == min) {
if(p[i].arrival_time < p[index].arrival_time) {
min = p[i].burst_time;
index = i;
}
}
}
}
if(index != -1) {
p[index].start_time = current_time;
p[index].completion_time = p[index].start_time + p[index].burst_time;
p[index].wait_time = p[index].start_time - p[index].arrival_time;
p[index].ta_time = p[index].wait_time + p[index].burst_time;
//total waiting and turnaround time
totalta_time += p[index].ta_time;
totalwt_time += p[index].wait_time;
is_completed[index] = 1;
completed++;
current_time = p[index].completion_time;
}
else {
current_time++;
}
}
avgtt = (float) totalta_time / (float)n;
avgwt = (float) totalwt_time /(float) n;
printf("PID \t Arrival time \t Burst time \t Priority\tStart time \t Completion time \tTurnaround time \t Waiting time \n");
for(i=0;i<n;i++)
{
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t\t%d\n",p[i].pid,p[i].arrival_time,p[i].burst_time,p[i].priority,p[i].start_time,p[i].completion_time,p[i].ta_time,p[i].wait_time);
}
printf("\n Average Turnaround Time %f",avgtt);
printf("\n Average Waiting Time %f\n\n",avgwt);
return 0;
}
算法解释：
Non-preemptive Priority scheduling
Each process has (arrival time, priority, and burst(execution) time) the process with first arrival time (less arrival time process) will be executed first, if two processes have same arrival time, then compare to priorities (highest process first). Also, if two processes have same priority then compare to process number (less process number first). This process is repeated while all process get executed.
我使用了下面的代码（代码已更新）但我没有得到正确的答案。我已经尝试解决了 2 周，但不幸的是我不知道错误在哪里（这是一个逻辑错误，但我无法识别）。调试了很多次，还是找不到原因。
#include <stdio.h>
void main()
{
int pn = 0; //Processes Number
int CPU = 0; //CPU Current time
int allTime = 0; // Time neded to finish all processes
printf("Enrer Processes Count: ");
scanf("%d",&pn);
int AT[pn];
int ATt[pn];
int NoP = pn;
int PT[pn]; //Processes Time
int PP[pn]; //Processes piriorty
int PPt[pn];
int waittingTime[pn];
int turnaroundTime[pn];
int i=0;
//Scanning Time and Piriorty
for(i=0 ;i<pn ;i++){
printf("\nProcessing time for P%d: ",i+1);
scanf("%d",&PT[i]);
printf("Piriorty for P%d: ",i+1);
scanf("%d",&PP[i]);
PPt[i] = PP[i];
printf("Arrival Time for P%d: ",i+1);
scanf("%d",&AT[i]);
ATt[i] = AT[i];
}
int LAT = 0; //LastArrivalTime
for(i = 0; i < pn; i++)
if(AT[i] > LAT)
LAT = AT[i];
int ATv = AT[0]; //Pointing to Arrival Time Value
int ATi = 0; //Pointing to Arrival Time indix
int P1 = PP[0]; //Pointing to 1st piriorty Value
int P2 = PP[0]; //Pointing to 2nd piriorty Value
//findding the First Arrival Time and Highst piriorty Process
while(NoP > 0 && CPU <= 1000){
for(i = 0; i < pn; i++){
if(ATt[i] < ATv){
ATi = i;
ATv = ATt[i];
P1 = PP[i];
P2 = PP[i];
}
else if(ATt[i] == ATv){
if(PP[i] != (pn+1))
P2 = PP[i];
if(P2 < P1){
ATi = i;
ATv = ATt[i];
P1 = PP[i];
P2 = PP[i];
}
}
}
if(CPU < ATv){
CPU = CPU+1;
ATi = 0; //Pointing to Arrival Time indix
ATv = ATt[ATi];
P1 = PP[0]; //Pointing to 1st piriorty Value
P2 = PP[0]; //Pointing to 2nd piriorty Value
continue;
}else{
waittingTime[ATi] = CPU - ATt[ATi];
CPU = CPU + PT[ATi];
turnaroundTime[ATi] = CPU - ATt[ATi];
ATt[ATi] = LAT +10;
ATv = LAT +10; //Pointing to Arrival Time Value
PPt[ATi] = pn + 1;
ATi = 0; //Pointing to Arrival Time indix
P1 = PP[0]; //Pointing to 1st piriorty Value
P2 = PP[0]; //Pointing to 2nd piriorty Value
NoP = NoP - 1;
}
}
printf("\nPN\tPT\tPP\tWT\tTT\n\n");
for(i = 0; i < pn; i++){
printf("P%d\t%d\t%d\t%d\t%d\n",i+1,PT[i],PP[i],waittingTime[i],turnaroundTime[i]);
}
int AvgWT = 0;
int AVGTaT = 0;
for(i = 0; i < pn; i++){
AvgWT = waittingTime[i] + AvgWT;
AVGTaT = turnaroundTime[i] + AVGTaT;
}
printf("AvgWaittingTime = %d\nAvgTurnaroundTime = %d\n",AvgWT/pn,AVGTaT/pn);
}
/*
Test Cases:
PT: Processing Time
PP: Process priority
WT Waitting Time
TaT: Turnaround Time
Arrival time for 1st 2 cases is 0
PN PT PP WT TaT
P1 10 3 6 16
P2 1 1 0 1
P3 2 4 16 18
P4 1 5 18 19
P5 5 2 1 6
PN PT PP WT TaT
P1 1 1 0 1
P2 2 2 1 3
P3 3 3 3 6
P4 4 4 6 10
P5 5 5 10 15
PN PP AT PT WT TaT
1 2 0 3 0 3
2 6 2 5 11 16
3 3 1 4 2 6
4 5 4 2 7 9
5 7 6 9 12 21
6 4 5 4 2 6
7 10 7 10 18 30
*/
正确的代码是：
#include <stdlib.h>
#include <stdio.h>
void main()
{
int pn = 0; //Processes Number
int CPU = 0; //CPU Current time
int allTime = 0; // Time neded to finish all processes
printf("Enrer Processes Count: ");
scanf("%d",&pn);
int AT[pn];
int ATt[pn];
int NoP = pn;
int PT[pn]; //Processes Time
int PP[pn]; //Processes piriorty
int PPt[pn];
int waittingTime[pn];
int turnaroundTime[pn];
int i=0;
//Scanning Time and Piriorty
for(i=0 ;i<pn ;i++){
printf("\nProcessing time for P%d: ",i+1);
scanf("%d",&PT[i]);
printf("Piriorty for P%d: ",i+1);
scanf("%d",&PP[i]);
PPt[i] = PP[i];
printf("Arrival Time for P%d: ",i+1);
scanf("%d",&AT[i]);
ATt[i] = AT[i];
}
int LAT = 0; //LastArrivalTime
for(i = 0; i < pn; i++)
if(AT[i] > LAT)
LAT = AT[i];
int MAX_P = 0; //Max Piriorty
for(i = 0; i < pn; i++)
if(PPt[i] > MAX_P)
MAX_P = PPt[i];
int ATi = 0; //Pointing to Arrival Time indix
int P1 = PPt[0]; //Pointing to 1st piriorty Value
int P2 = PPt[0]; //Pointing to 2nd piriorty Value
//findding the First Arrival Time and Highst piriorty Process
int j = -1;
while(NoP > 0 && CPU <= 1000){
for(i = 0; i < pn; i++){
if((ATt[i] <= CPU) && (ATt[i] != (LAT+10))){
if(PPt[i] != (MAX_P+1)){
P2 = PPt[i];
j= 1;
if(P2 < P1){
j= 1;
ATi = i;
P1 = PPt[i];
P2 = PPt[i];
}
}
}
}
if(j == -1){
CPU = CPU+1;
continue;
}else{
waittingTime[ATi] = CPU - ATt[ATi];
CPU = CPU + PT[ATi];
turnaroundTime[ATi] = CPU - ATt[ATi];
ATt[ATi] = LAT +10;
j = -1;
PPt[ATi] = MAX_P + 1;
ATi = 0; //Pointing to Arrival Time indix
P1 = MAX_P+1; //Pointing to 1st piriorty Value
P2 = MAX_P+1; //Pointing to 2nd piriorty Value
NoP = NoP - 1;
}
}
printf("\nPN\tPT\tPP\tAT\tWT\tTT\n\n");
for(i = 0; i < pn; i++){
printf("P%d\t%d\t%d\t%d\t%d\t%d\n",i+1,PT[i],PP[i],AT[i],waittingTime[i],turnaroundTime[i]);
}
int AvgWT = 0;
int AVGTaT = 0;
for(i = 0; i < pn; i++){
AvgWT = waittingTime[i] + AvgWT;
AVGTaT = turnaroundTime[i] + AVGTaT;
}
printf("AvgWaittingTime = %d\nAvgTurnaroundTime = %d\n",AvgWT/pn,AVGTaT/pn);
}
/*
Test Cases:
PT: Processing Time
PP: Process priority
WT Waitting Time
TaT: Turnaround Time
Arrival time for 1st 2 cases is 0
PN PT PP WT TaT
P1 10 3 6 16
P2 1 1 0 1
P3 2 4 16 18
P4 1 5 18 19
P5 5 2 1 6
PN PT PP WT TaT
P1 1 1 0 1
P2 2 2 1 3
P3 3 3 3 6
P4 4 4 6 10
P5 5 5 10 15
PN PT PP AT WT TT
P1 3 2 0 0 3
P2 5 6 2 11 16
P3 4 3 1 2 6
P4 2 5 4 7 9
P5 9 7 6 12 21
P6 4 4 5 2 6
P7 10 10 7 20 30
PN PT PP AT WT TT
P1 4 2 0 0 4
P2 3 3 1 3 6
P3 1 4 2 5 6
P4 5 5 3 5 10
P5 2 5 4 9 11
*/```
/*Non preemptive scheduling using C*/
#include<stdio.h>
#define MAX 20
typedef struct process{
int pid;
int arrival_time,burst_time,start_time,completion_time,ta_time,wait_time;
}Process;
Process p[MAX];
int main(){
int n,i;
int current_time = 0;
int completed = 0;
int is_completed[MAX]={0};
int totalta_time=0,totalwt_time=0;
float avgtt,avgwt;
printf(" enter number of processes ");
scanf("%d",&n);
for(i=0;i<n;i++){
printf("enter the id of the process ");
scanf("%d",&p[i].pid);
printf("enter arrival time ");
scanf("%d",&p[i].arrival_time);
printf("enter burst time ");
scanf("%d",&p[i].burst_time);
}
while(completed != n) {
int index = -1;
int min = 10000000;
for(i = 0; i < n; i++) {
if(p[i].arrival_time <= current_time && is_completed[i] == 0) {
if(p[i].burst_time < min) {
min = p[i].burst_time;
index = i;
}
if(p[i].burst_time == min) {
if(p[i].arrival_time < p[index].arrival_time) {
min = p[i].burst_time;
index = i;
}
}
}
}
if(index != -1) {
p[index].start_time = current_time;
p[index].completion_time = p[index].start_time + p[index].burst_time;
p[index].wait_time = p[index].start_time - p[index].arrival_time;
p[index].ta_time = p[index].wait_time + p[index].burst_time;
//total waiting and turnaround time
totalta_time += p[index].ta_time;
totalwt_time += p[index].wait_time;
is_completed[index] = 1;
completed++;
current_time = p[index].completion_time;
}
else {
current_time++;
}
}
avgtt = (float) totalta_time / (float)n;
avgwt = (float) totalwt_time /(float) n;
printf("PID \t Arrival time \t Burst time \t Priority\tStart time \t Completion time \tTurnaround time \t Waiting time \n");
for(i=0;i<n;i++)
{
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t\t%d\n",p[i].pid,p[i].arrival_time,p[i].burst_time,p[i].priority,p[i].start_time,p[i].completion_time,p[i].ta_time,p[i].wait_time);
}
printf("\n Average Turnaround Time %f",avgtt);
printf("\n Average Waiting Time %f\n\n",avgwt);
return 0;
}