This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: the last Gwen Challenge in 2021

I. Purpose and requirements of the experiment

Objective: To improve the process scheduling algorithm used in operating system.

Requirements: In-depth analysis of several process scheduling algorithms described in the textbook, and then select an algorithm to improve, and programming to achieve this algorithm.

2. Experimental environment

10 Windows system

3. Experiment preview

The experimental principle

First-come-first-served scheduling algorithm: Processes that can occupy the processor are selected in the order in which they enter the ready queue.

Priority scheduling algorithm: A priority number is assigned to each process, and the algorithm always gives the highest priority to the process that uses the processor first. Processes with the same number of priorities are assigned processors in a first-come, first-served order. Systems often prioritize processes based on factors such as task urgency and system efficiency. The number of priorities of a process can be fixed or can change dynamically as the process executes. When a high-priority process occupies the processor, the system can handle the process in two ways: “non-preemptive” and “preemptive”. The former means that the process occupies the processor and runs until the end unless it voluntarily cedes the processor, while the latter strictly guarantees that the process with the highest priority is always running on the processor at any time (” preemption “is adopted in this experiment).

The experiment to prepare

The experiment content,

(1) Design process control block PCB table structure, respectively applicable to the number of priority scheduling algorithm and first-come-first-served scheduling algorithm.

(2) Establish a process ready queue. Two different algorithms are programmed into a chain program.

(3) Two scheduling algorithms are developed: 1) priority number scheduling; 2) First come, first served

The experiment design

(1) Use two algorithms to schedule multiple processes, each process can have three states, and assume that the initial state is ready state.

(2) In order to facilitate processing, the running time of a process in the program is calculated in time slices. The priority number of each process and the initial value of the number of time slices that the process needs to run are set by the user.

(3) In the priority number algorithm, the priority number can be set to N first, and each time the process executes, the priority number decreases by 3, and the number of CPU time slices required by the process decreases by 1. In the first-come-first-served algorithm, fixed time slices are used (i.e., the number of execution time slices of the process is 2 units that have been executed every time the process is executed). In this case, the number of time slices required by the process is reduced by 2 and arranged at the end of the ready queue.

(4) FIFO strategy is adopted to solve the problem of consistent priority number.

(5) Flow chart

Code implementation

H > #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <string.h> #define TIME 1 // Define a TIME slice // process control block PCB structure typedef struct pcb { char name[10]; // Process name int status; // Ready (0) int priority; // Priority int times; // Run time} PCB; typedef pcb ElemType; Typedef struct node {ElemType data; // struct node* next; }PCB; Typedef struct linkquene {PCB *front; PCB *rear; }LinkQuene; // Initialize the PCB queue void initPcbQuene(LinkQuene *pcbquene){pcbquene->front = pcbquene->rear = (PCB*)malloc(sizeof(PCB)); if(! Pcbquene ->front){printf(" application failed "); } pcbquene->front->next = NULL; } void InputProInfo(int n,LinkQuene *pcbquene){// Number of processes to input PCB *pt = NULL; int i=0; for(i =0; i<n; i++){ pt = (PCB*)malloc(sizeof(PCB)); Printf (" Please enter information about process %d \n", I +1); Printf (" name: "); scanf("%s",pt->data.name); pt->data.status = 0; Printf (" priority :"); scanf("%d",&pt->data.priority); Printf (" runtime :"); scanf("%d",&pt->data.times); Pt ->next = NULL; pcbquene->rear->next = pt; pcbquene->rear = pt; Void sortProcess(LinkQuene *pcbquene){PCB *head = pcbquene->front; PCB *temp=NULL; PCB *p = NULL; ElemType t; For (temp = head->next; temp->next ! = NULL; temp =temp->next){ for(p = head->next; p->next ! = NULL; p=p->next){ if(p->data.priority < p->next->data.priority){ t= p->data; p->data = p->next->data; p->next->data = t; }}}} // printProcess information void printProcess(LinkQuene *pcbquene){PCB *pt = pcbquene->front; //if(pcbquene->front->next == pcbquene->rear){ //pcbquene->front == pcbquene->rear; } if(pcbquene-> rear == pcbquene->rear){printf(" Ready queue is empty "); }else{printf(" Ready queue :\n"); printf("-------------------------------------\n"); Printf (" Name running state priority remaining running time \n"); while(pt->next ! = NULL){if(pt->next->data.status == 1){// Running process printf("%3s running %7d %7d\n",pt->next->data.name,pt->next->data.priority,pt->next->data.times); }else if(pt->next->data.status == 0){// Waiting process printf("%3s ready %7d %7d\n",pt->next->data.name,pt->next->data.priority,pt->next->data.times); } pt = pt->next; } printf("-------------------------------------\n"); Int Traversal(LinkQuene *pcbquene){int I =0; PCB *pt = pcbquene->front; while(pt->next! =NULL){ // printf("%s",pt->next->data.name); i++; pt = pt->next; } return i; } void run(LinkQuene *pcbquene){PCB *pt = pcbquene->front->next; ElemType TMP; if(pcbquene->front == pcbquene->rear){ return; } tmp = pt->data; pcbquene->front->next = pt->next; If (pcbquene->front->next == NULL) {pcbquene->front = pcbquene->rear; } // Change the status to running tmp.status = 1; tmp.priority-=3; If (tmp.times-1 <= 0){printf(" Process name :%s Status: Running priority :%d remaining running time :%d\n\n",tmp.name,tmp.priority,0); Process name:} else {printf (" % s status: running state priority: % d remaining run time: % d \ n \ n ", TMP. The name, TMP, priority, TMP. The Times - 1); } if(tmp.times <= 1){// If the remaining running time of the current process is 0 printf("%s end! \n\n",tmp.name); if(Traversal(pcbquene) ! = 0){ printProcess(pcbquene); }}else{// greater than TIME slice tmp.times-=TIME; tmp.status = 0; // The outgoing process is queued to the end of the queue. if(curpt){ curpt->data = tmp; curpt->next = NULL; pcbquene->rear->next = curpt; pcbquene->rear = curpt; }else{ exit(0); } printProcess(pcbquene); sortProcess(pcbquene); } } int main() { LinkQuene pcbquene; initPcbQuene(&pcbquene); int n; Printf (" Input process number :"); scanf("%d",&n); InputProInfo(n,&pcbquene); sortProcess(&pcbquene); // Traversal(&pcbquene); printProcess(&pcbquene); while(pcbquene.rear ! = pcbquene.front){ run(&pcbquene); } return 0; }Copy the code

Example of run results

Four, conclusion

In this experiment, we design an improved preemptive priority scheduling algorithm based on priority scheduling algorithm to schedule multiple processes.

The process control block PCB structure is designed, including the process name, state, priority and running time. In addition, queue structure is used to store the ready process in the queue and sort the process according to the priority from large to small. The process with the same priority is sorted according to the time order of joining the queue. If the process is running but the time slice is up, add the process to the end of the queue, sort the queue again, and then take the first process to run. This loop continues until all processes in the queue have finished running.

The algorithm uses the dynamic priority, each time the process executes, the priority number is reduced by 3, the number of CPU time slices required by the process is reduced by 1 (a time slice designed in this experiment is a unit of running time), and arranged at the end of the ready queue. The priority of a process can be changed as the process progresses. The system always processes the high-priority and urgent processes first, and the high-priority processes do not occupy resources all the time. Better scheduling performance can be achieved.

5. Problems encountered in the process

1. There are many small technical problems encountered during the process, to name one:

A process terminated due to a time slice is restarted if it has a higher priority than all other processes in the ready queue. Therefore, each time a process terminates due to a time slice, it is put back on the queue for sorting. However, when there is only one process left in the ready queue, the process runs out of the queue. If the process has not finished running but the number of time slices has reached, the process enters the queue again and is ready, then the output ready queue is empty. The process failed to join the team.

Solution: The queue only allows insert operations on one end and delete operations on the other.

Initialization front=rear

Insert new node: rear-> Next = new node, rear= new node

Delete a node: temp=front->next,front->next=temp->next.

Front ->next=rear->next=NULL when the last element in the queue is left: front->next=rear->next=NULL Add the element again, front-> Next is still empty, and you cannot iterate over the printed element through the queue’s head pointer.

When the problem is found, the node deletion mode is changed to:

Temp =front->next,front=front->next; Or if, when the element that leaves the team is the last element, and then front=rear, the problem is solved.