1, Experimental purpose
1.1 understand the concepts of process control block and process queue.
1.2 master the processing logic of process priority scheduling algorithm and time slice rotation scheduling algorithm.
2, Experimental content
2.1 design the structure of process control block PCB, which is applicable to priority scheduling algorithm and time slice rotation scheduling algorithm respectively.
2.2 establish process ready queue.
2.3 prepare two process scheduling algorithms: priority scheduling and time slice rotation scheduling.
3, Experiment preparation
3.1 priority algorithm
in order to take care of urgent processes to obtain priority processing, priority scheduling algorithm is introduced. It selects a process with the highest priority from the ready queue to get the processor and execute it. At this time, the algorithm is further divided into two ways.
3.1.1 non preemptive priority scheduling algorithm.
in this way, once the system assigns the processor to the process with the highest priority in the ready queue, the process will occupy the processor and run until the process is completed or blocked by an event. The system can then assign the processor to another process with high priority. This method actually assigns the processor to the process with the highest priority in the current ready queue every time. It is often used in batch processing systems, and can also be used in some real-time systems that do not have strict time requirements.
3.1.2 preemptive priority scheduling algorithm.
in this way, the system also assigns the processor to the process with the highest priority in the current ready queue for execution. However, during its execution, new ready processes will continue to enter the ready queue. If a process appears and its priority is higher than that of the currently executing process, the process scheduler will immediately suspend the execution of the current process and withdraw the processor, and assign the processor to the newly emerging process with higher priority for execution, In fact, this method is the process with the highest priority in the system, occupying the processor for execution. Therefore, it can better meet the requirements of urgent processes, so it is often used in real-time systems with strict requirements, as well as batch processing and time-sharing systems with high performance requirements.
for the priority scheduling algorithm, the key lies in whether to adopt static priority or dynamic priority, and how to determine the priority of the process.
Static priority:
is determined when the process is created, and it is specified that it will remain unchanged throughout the operation of the process. Generally speaking, priority is expressed by an integer in a certain range, such as an integer in 0 ~ 7 or 0 ~ 255, so it is also called priority number. In use, some systems use "0" to indicate the highest priority. The larger the value, the smaller the priority, while some systems are just the opposite.
Dynamic priority
it should be used in conjunction with preemptive scheduling. It refers to the priority given when creating a process, which can be changed with the progress of the process, so as to obtain better scheduling performance. The priority of a process waiting for scheduling in the ready queue can increase at a certain rate as its waiting time increases. Therefore, for processes with low initial priority, after waiting long enough, their priority may also rise to the highest, so as to obtain scheduling, occupy the processor and execute. Similarly, it is stipulated that the priority of the process being executed will gradually decrease with the increase of execution time, so that its priority may no longer be the highest, so as to suspend its execution and recycle and assign the processor to other processes with higher priority. This method can prevent individual processes from occupying the processor for a long time.
3.2 time slice rotation scheduling algorithm
in the time-sharing system, in order to ensure the timeliness of human-computer interaction, the system makes each process execute in turn according to the time slice, that is, the time slice rotation scheduling algorithm. In this algorithm, the system arranges all ready processes in the order of entering the ready queue. Each time, the CPU is allocated to the process at the head of the queue to execute a time slice. When the time slice runs out, the timer sends a clock interrupt, and the scheduler pauses the execution of the process to exit the processor, and sends it to the end of the ready queue to wait for the next round of scheduling execution. Then, the CPU is allocated to the new queue leader process in the ready queue, and it is also allowed to execute a time slice. This ensures that all processes in the ready queue can obtain the execution time of a time slice within a certain time (acceptable waiting time).
in the time slice rotation scheduling algorithm, the size of the time slice has a great impact on the performance of the system. If the time slice is so large that each process can execute the knot in one time slice, the time slice rotation scheduling algorithm will degenerate into a first come first serve scheduling algorithm, and users will not be able to obtain satisfactory response time. If the time slice is too small, even the simple and common commands typed by the user will take multiple time slices, then the system will switch processes frequently, which is also difficult to ensure the user's requirements for response time.
4, Experiment
1. Students must complete the debugging and operation of the program independently, record the operation results and analyze the results;
2. The data structure defined by the analyzer;
3. Analyze the structure of the program and draw the program flow chart;
4. Write analysis report
4.2 data type definition:
1.1 data structure
#include<conio. h> / / getch function output
#define PSUM 3 / / the number of processes is 3
#define PTIME 30 / / the process time is 30
enum process_state
{
ready,//Ready status
execute,//Execution status
finish//Completion status
};//Define process status
struct lskpcb
{
char name[4];//Process name
int priority;//Priority
int cputime;//CPU running time
int needtime;//Time required for the process to run
int count;//Number of process executions
int round;//Time slice rotation
int process;//Process status
struct lskpcb *next;//Create a pointer
};// Define PCB created by process
4.3 the procedure flow chart is as follows:
The priority flow chart is as follows:
The program flow chart of time slice rotation scheduling method is as follows:
The complete code is as follows:
#include<stdio.h>
#include<conio. h> / / getch function output
#include<stdlib.h>
#include<iostream>
#include<windows.h>
#define PSUM 3 / / the number of processes is 3
#define PTIME 30 / / the process time is 30
enum process_state
{
ready,//Ready status
execute,//Execution status
finish//Completion status
};//Define process status
struct lskpcb
{
char name[4];//Process name
int priority;//Priority
int cputime;//CPU running time
int needtime;//Time required for the process to run
int count;//Number of process executions
int round;//Time slice rotation
int process;//Process status
struct lskpcb *next;//Create a pointer
};// Define PCB created by process
lskpcb *get_process()
{
lskpcb *q;
lskpcb *t;
lskpcb *p;
int i = 0;
printf("Please enter the process name and cpu Running time:\n");
while(i < PSUM)
{
q=(struct lskpcb *)malloc(sizeof(struct lskpcb));
scanf("%s", &(q -> name));
scanf("%d", &(q -> needtime));
q -> cputime = 0;
q -> priority = PTIME - q -> needtime;
q -> process = ready;
q -> next = NULL;//The default value of the pointer is null
if(i == 0)
{
p = q;
t = q;
}
else
{
t -> next = q;//Create ready process queue
t = q;
}
i++;
}//Enter the process name and execution time of the simulation test. The initial setting can simulate the scheduling of 5 processes
return p;
}
void display(struct lskpcb *p)
{
printf("Process name"" ""cpu Running time"" ""It will take more time"" " "Priority"" ""state\n");
while(p)
{
printf("%s",p -> name);
printf(" ");
printf("%d",p -> cputime);
printf(" ");
printf("%d",p -> needtime);
printf(" ");
printf("%d",p -> priority);
printf(" ");
switch(p -> process)//Process state loop
{
case ready:
printf("be ready\n",ready);
break;
case execute:
printf("implement\n",execute);
break;
case finish:
printf("complete\n",finish);
break;
}
p = p->next;
}//Display the simulation results, including process name, CPU time, running time and priority
}
int process_finish(lskpcb *q)
{
int ks = 1;
while(ks && q)
{
ks = ks && q -> needtime == 0;
q = q -> next;
}
return ks;
}//End the process, that is, set the time required for each process in the queue to 0
void cpuexe(lskpcb *q)
{
lskpcb *t = q;
int tp = 0;
while(q)
{
if(q -> process != finish)
{
q -> process = ready;
}
if(q -> needtime == 0)
{
q -> process = finish;
}
if(tp < q -> priority && q -> process != finish)
{
tp = q -> priority;
t = q;
}
q = q -> next;
}
if(t -> needtime != 0)
{
t -> priority -= 2;
t -> needtime --;
t -> process = execute;
t -> cputime ++;
}
}//Select a process and assign it CPU
//Calculate process priority
void priority_cal()
{
lskpcb *p;
system("cls");//Screen clearing function
p = get_process();
int cpu = 0;
system("cls");
while(!process_finish(p))
{
cpu++;
printf("CPU Running time:%d\n",cpu);
cpuexe(p);
display(p);
getch();
system("cls");
}
printf("All priority processes have been completed. Please enter your student number to exit the demonstration or press any key to enter the main menu selection interface:\n");
getch();
system("cls");
}
void displaymenu()
{
printf("******The program is only used for simulation testing******\n");
printf("Please select the following function menu:\n");
printf("1.Time slice wheel method\n");
printf("2.Priority scheduling\n");
printf("3.To exit, enter the correct command:\n");
}//The scheduling algorithm menu is displayed for users to select priority scheduling algorithm and time slice rotation scheduling algorithm
lskpcb *getprocess_round()
{
lskpcb *q;
lskpcb *t;
lskpcb *p;
int i = 0;
printf("Please enter the process name and time\n");
while(i<PSUM)
{
q = (struct lskpcb * )malloc(sizeof(struct lskpcb));
scanf("%s", &(q->name));
scanf("%d", &(q->needtime));
q -> cputime = 0;
q -> round = 0;
q -> count = 0;
q -> process = ready;
q -> next = NULL;
if(i == 0)
{
p = q;
t = q;
}
else
{
t -> next = q;
t = q;
}
i++;
}
return p;
}//Time slice rotation scheduling algorithm creates ready process queue
void cpu_round(lskpcb *q)
{
q -> cputime += 1;//CPU time plus 2
q -> needtime -= 1;//The time needed is reduced by 2
if(q -> needtime < 0)
{
q-> needtime = 0;
}
q -> count ++;
q -> round ++;
q -> process = execute;
}//Time slice rotation scheduling algorithm is used to execute a process
lskpcb *get_next(lskpcb *L,lskpcb *H)
{
lskpcb *t;
t = L;
do
{
t = t->next;
}
while(t && t -> process == finish);
if(t == NULL)
{
t = H;
while(t -> next != L && t -> process == finish)
{
t = t-> next;
}
}
return t;
}//Get next process
void setstate(lskpcb *p)
{
while(p)
{
if(p -> needtime == 0)
{
p -> process = finish;//If the required execution time is 0, set the operation status to Jiedong
}
if(p -> process == execute)
{
p -> process = ready;//If it is in execution status, it is set to ready
}
p = p -> next;
}
}//Set the execution status of processes in the queue
void display_round(lskpcb *p)
{
printf("Process name" " " "CPU Running time" " " "It will take more time" " " "Number of time slices" " " "Time slice process rounds" " " "state\n");
while(p)
{
printf("%s", p -> name);
printf(" ");
printf("%d", p -> cputime);
printf(" ");
printf("%d", p -> needtime);
printf(" ");
printf("%d",p -> count);
printf(" ");
printf("%d",p -> round);
printf(" ");
switch(p -> process)
{
case ready:
printf("be ready\n",ready);
break;
case execute:
printf("implement\n",execute);
break;
case finish:
printf("complete\n",finish);
break;
}
p = p -> next;
}
}//Time slice rotation scheduling algorithm outputs scheduling information
void round_cal()
{
lskpcb *p;
lskpcb *r;
system("cls");
p = getprocess_round();
int cpu = 0;
system("cls");
r = p;
while(!process_finish(p))
{
cpu += 1;
cpu_round(r);
r = get_next(r,p);
printf("CPU Running time:%d\n",cpu) ;
display_round(p);
setstate(p);
getch();
system("cls");
}
printf("All time slice processes have been completed. Please enter any key to enter the main menu selection interface:\n");
getch();//Waiting to read keyboard characters
system("cls");
}//Time slice rotation scheduling algorithm calculates rounds and outputs scheduling information
int main()
{
displaymenu();
while(true)
{
int lsp = 0;
int flag = 0;
scanf("%d",&lsp);
switch(lsp)
{
case 1:
round_cal();
break;
case 2:
priority_cal();
break;
case 3:
{
printf("warning!!!!Exit system error. You need to enter the correct command to exit the system. Please re-enter:\n") ;
break;
}
case 49:
{
flag = 1;
break;
}//Code to exit the system. When you enter 49 password, you can exit the system correctly
default:
break;
}
if(flag == 1)
{
break;
}//When flag=1, jump out of the loop and enter the menu selection mode
displaymenu();
}
}
select time slice rotation:
