Shulou(Shulou.com)06/01 Report--

1. Brief introduction of SPF algorithm

SJF algorithm

SJF (shortest job first) takes the length of the running time of the process as the priority, the shorter the running time of the process, the higher the priority.

Shortcomings of SJF algorithm

You must know when the process will run. It is difficult for even programmers to accurately estimate the running time of a process. If the estimate is too low, the system may terminate the process at the estimated time, but at this time the process is not completed, so it is generally overestimated.

It is bad for the long process. The turnaround time of a long process will increase significantly. The terrible thing is that the SJF algorithm completely ignores the waiting time of the process, which may make the waiting time of the process too long and lead to hunger.

Man-machine interaction can not be achieved.

The urgency of the process has not been taken into account. There is no guarantee that the urgent process will be dealt with in a timely manner.

2. Algorithm flow chart

The flow chart I made: http://www.processon.com/diagraming/5835692de4b086d1e79f81af

III. Source code

1. Variable declaration and structure definition

1 # include 2 # include 3 # include 4 5 / * run this program using the console pauser or add your own getch, system ("pause") or input loop * / 6 7 8 struct pcb {9 char name [10]; / / process name 10 int arrival_time; / / process arrival time () 11 int start_time; / / process start time 12 int need_time; / / process running time 13 int finish_time / / run end time 14 struct pcb * link; / / pointer to the next pcb 15}; 16 17 18 int num = 0; / / number of processes entered 19 typedef struct pcb PCB / / define structure variable 20 / * 21 structure pointer p to each newly created process 22 ready pointer to the first pcb 23 finish pointer of the linked list to the first pcb structure of the completion queue 24 * / 25 struct pcb * p = NULL, * ready = NULL, * finish = NULL

two。 Input function

1 / / to test list creation, enter linked list structure data 2 void print_test () {3 int I; 4 struct pcb * test = ready; 5 for (NULL! = test- > link); 8 if (NULL! = test- > link) {9 test = test- > link;10} 11 else {12 printf ("\ ntest_link end\ n") 13} 14 15} 16} 17 18 19 20 / / input function, create the linked table 21 void input () {22 int I * 23 struct pcb * Q; / / define the structure variable 24 printf ("Please enter the number of processes:"); 25 scanf ("% d", & num); 26 for (iTun0; iname); 31 printf ("\ nPlease enter the process arrival time:") 32 scanf ("% d", & p-> arrival_time); 33 printf ("\ nPlease enter the process run time:"); 34 scanf ("% d", & p-> need_time); 35 36 p-> link = NULL 37 / / create the linked list 38 if (NULL = = ready) {/ / create the first structure, so that the pointer pMagee Q points to it 39 ready = pten 40 Q = ready;41} 42 else {/ / linked list creation 43 Q-> link = pten 44 Q = p 45} 46 printf ("input success"); 47} 48 print_test (); / / Test whether the linked list is established 49}

3. When all processes are finished, output all process information

1 / / output data related to the current running process or print 2 void output (struct pcb * p, int now_time) {3 if (NULL = = p) {4 printf ("current moment:% d, no process running!\ n", now_time) 5} 6 else {7 printf ("process name:% s, arrival time:% d, run time:% d\ n", p-> name,p- > arrival_time,p- > need_time); 8} 9}

4. Find the process with the shortest running time

1 / / sjf shortest job first shortest job priority 2 struct pcb * SJF (int now_time, int * after) {3 int min_time = 0; / / shortest time, that is, 4 struct pcb * now_progress = NULL, * p = ready 5 / / iterate through the linked list to find the process with the shortest running time 6 if (NULL! = ready) {7 while (NULL! = p) {8 if (now_time > = p-> arrival_time) {/ / if the process has arrived, note: the time unit is 1 9 / * 10 min_time = p-> need_time / / wrong 11 now_progress = pash 12 if (p-> need_time)

< min_time){13 min_time = p->

Need_time;14 now_progress = p min_time 15} * / 16 if (0 = = min_time) {/ / give the minimum time an initial value of 17 now_progress = p politics 18 min_time = p-> need_time 19} 20 else {21 if (p-> need_time

< min_time){22 now_progress = p;23 min_time = p->

Need_time;24} 25} 26} 27 p = p-> link;28} 29} 30 * after = min_time + now_time;31 printf ("\ nSJF:a shortest progress running!\ n"); 32 return now_progress; / / returns the pointer to the running process 33}

4. Process execution completed

1 / / add the processes that have already run to the finish queue, and the number of processes minus one 2 void destory (struct pcb * p, int now_time) {3 printf ("destory start!\ n"); 4 struct pcb * Q = ready; 5 struct pcb * f = NULL / / add 6 7 8 if for finish linked list (strcmp (p-> name, ready- > name) = = 0) {/ / if the first process completes 9 ready = ready- > link;10} 11 / / if the middle or last process completes 12 else {13 Q = ready 14 while ((strcmp (Q-> link- > name,p- > name)! = 0) & & NULL! = Q-> link) {15 Q = Q-> link;16} 17 Q-> link = p-> link;18} 19 20 p-> finish_time = now_time; / / end time 21 p-> start_time = now_time-p-> need_time / / start time 22 23 / / add running processes to finish queue 24 if (NULL = = finish) {25 finish = p; / / finish points to header 26 p-> link = NULL;27} 28 else {29 f = finish;30 while (NULL! = f-> link) {31 f = f-> link 32} 33 f-> link = ppolitics 34 p-> link = NULL;35} 36 37 num--; / / the number of processes minus 38 printf ("\ ndestory success!\ n"); 39}

5. Principal function

1 int main (int argc, char * argv []) {2 34 input (); / call input function 56 int now_time = 0; / / initial time is 0 7 int after = 0; / / time after execution of a process: run time of priority running process + current time 8 struct pcb * now_progress = NULL / / now_progress points to the running process (structure) 9 struct pcb * m = NULL;10 11 while (num > 0) {/ / the number of processes is greater than 0, and each cycle num decreases by 12 printf ("start SJF"); 13 now_progress = SJF (now_time, & after) / / call the SJF function, traverse the linked list 14 15 16 if (NULL! = now_progress) {17 / * process execution, each cycle, plus one 18 at the current time and determine whether any process is arriving at the current time and is waiting for * / 19 for (; now_time)

< after; now_time++){20 printf("\n当前时刻:%d", now_time);21 printf("\n-----------当前执行进程------------\n");22 output(now_progress, now_time); //调用output函数 23 printf("\n-----------等待执行进程------------\n");24 25 m = ready;26 while(NULL != m){ //循环，若当前时间有进程到达，打印相关信息 27 if(m != now_progress){28 if(m->

Arrival_time link;34} 35} 36 / / call the destory function 37 destory (now_progress, now_time) after the process has finished execution; 38 39} 40 else {/ / No process is running 41 output (now_progress, now_time); 42 now_time++ 43} 44 45} 46 output_all (); 47 return 0 Ten 48 49}

I write so clearly, coupled with the flow chart I draw, I believe you can understand.

IV. Testing

5. Pit

I originally wrote this function like this, but I found that the result was not correct.

Press the running result of the above code:

According to theory, the execution of a process should not be the execution of e process, but the execution of d process with the shortest running time. By the same token, there are b, e, c

I went back to look at the previous code and corrected it as follows:

Running result:

VI. Summarize the knowledge points

P = (struct pcb*) malloc (sizeof (struct pcb)) is the same as p = (struct pcb*) malloc (sizeof (PCB)). PCB is a structural variable of the structural body struct pcb.

When using the string handling function (puts,gets,strcat,strcpy,strcmp,strlen,strlwr), you should include the "string.h" file in this file with # include at the beginning of the program file.

Malloc function. For example, malloc (100) opens up a 100-byte temporary allocation domain with a function value of its first byte address. Only one address is provided. If the function cannot be executed successfully (for example, out of memory), a null pointer is returned. (int*) malloc (sizeof (int)) converts the requested space address into an int type space address and then can assign a value to the p pointer to the int type space.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.