操作系统实验报告——进程调度(共21页).docx

《操作系统实验报告——进程调度(共21页).docx》由会员分享，可在线阅读，更多相关《操作系统实验报告——进程调度(共21页).docx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上北京邮电大学软件学院2019-2020学年第2学期实验报告 课程名称： 操作系统 实验名称： 进程调度 实验完成人： 日 期： 2019 年 11 月 26 日一、 实验目的1. 理解 Linux 管理进程所用到的数据结构。 2. 理解 Linux 的进程调度算法的处理逻辑及其实现所用到的数据结构。二、 实验内容1. 通过查阅参考书或者上网找资料，熟悉/usr/src/linux（注意：这里最后一级目录名 可能是个含有具体内核版本号和“linux”字符串的名字）下各子目录的内容，即所含 Linux 源代码的情况。 2. 分析 Linux 进程调度有关函数的源代码，主要

2、是 schedule()函数，并且要对它们 引用的头文件等一并分析。 3. 实现 Linux 的进程调度算法及理解其实现所用的主要数据结构。三、 实验环境Linux下使用gcc+vscode四、 实验过程描述第一部分：源代码分析：所需头文件：#include#include#include#include#include#include#include#include：内核头文件，含有一些内核常用函数的原形定义。：软驱头文件，含有软盘控制器参数的一些定义。：调度程序头文件，主要定义了任务结构task_struct、初始任务0的数据，以及一些有关描述符参数设置和获取的嵌入式汇编函数宏语句。：系统

3、调用头文件，主要是系统调用C函数处理程序。 ：I/O头文件，以宏的嵌入汇编程序形式定义对I/O端口操作的函数。：段操作头文件，定义了有关段寄存器操作的嵌入式汇编函数。：系统头文件，定义了设置或修改描述符/中断门等的嵌入式汇编宏。：信号头文件，定义信号符号常量，信号结构以及信号操作函数原型。Schedule.c部分函数分析：（大多写在注释里）show_task()函数某个进程的状态信息以及空间大小voidshow_task(intnr,structtask_struct*p)/显示p指向的nr号进程的相关信息inti,j=4096-sizeof(structtask_struct);/j记录了任

4、务结构体之后的堆栈空间大小printk(%d:pid=%d,state=%d,nr,p-pid,p-state);/打印进程的各种信息i=0;while(ij&!(char*)(p+1)i)/计算了任务之后空字节的大小i+;printk(%d/%dcharsfreeinkernel stacknr,i,j);/内核栈最大为j，空字节数是i，比例i/jvoidshow_stat(void)/打印所有进程的状态信息inti;for(i=0;iNR_TASKS;i+)if(taski)show_task(i,taski);Schedule()分析：schedule函数首先对所有的任务检查，唤醒任何一

5、个已经得到信号的任务，也就是针对任务数组中的每个任务，检查其警报定时值alarm。如果任务的alarm已经超期（alarm &FIRST_TASK;-p)/把p初始化为指向最后一个进程的地址的指针,逆向扫描所有进程if(*p)/当前进程if(*p)-timeout&(*p)-timeouttimeout=0;/如果当前进程等待很久了，并且这个进程处于TASK_INTERRUPTIBLEif(*p)-state=TASK_INTERRUPTIBLE) (*p)-state=TASK_RUNNING; /我们就把这个进程置与TASK_RUNNING状态if(*p)-alarm&(*p)-alarm

6、signal|=(1alarm=0;if(*p)-signal&(_BLOCKABLE&(*p)-blocked)&(*p)-state=TASK_INTERRUPTIBLE)/除SIGKILLSIGSTOP信号外，其他信号都是非阻塞状态的话，并且进程处于TASK_INTERRUPTIBLE(*p)-state=TASK_RUNNING;/把这个进程置与TASK_RUNNING状态/*thisistheschedulerproper:*/while(1)c=-1;next=0;i=NR_TASKS;p=&taskNR_TASKS;while(-i)/把所有进程都扫一遍，counter是递减的，

7、找出counter最大的进程，保存在next里面if(!*-p)/当前*p指向进程为空，下一个continue;if(*p)-state=TASK_RUNNING&(*p)-counterc)/counter是任务运行时间计数，如果当前进程是执行状态且运行时间数大于c c=(*p)-counter,next=i;if(c)break;/c0就说明找到了已经运行一段时间，并且运行时间最短的进程，跳出while(1)for(p=&LAST_TASK;p&FIRST_TASK;-p)/如果c=0，说明所有schedule的进程都没有运行if(*p)(*p)-counter=(*p)-counter1

8、)+(*p)-priority;/重新计算counter=counter/2+priorityswitch_to(next);/让进程next使用CPUSleep_on()函数分析：Sleep_on()函数 sleep_on()函数的主要功能是当一个进程（或任务）所请求的资源正等待资源响应或不在内存中时暂时切换出去，放在等待队列中等待一段时间，先让别的程序运行一段时间，当切换回来后再继续运行。巧妙的利用了tmp指针来作为与等待队列的联系voidsleep_on(structtask_struct*p)structtask_struct*tmp;if(!p)return;if(current=&

9、(init_task.task) panic(task0tryingtosleep);tmp=*p;/tmp指向原等待队列的头指针*p=current;/*p指向等待队列的头指针，把current放入等待队列current-state=TASK_INTERRUPTIBLE; /当前状态为不可中断schedule();/调度一下，if(tmp)tmp-state=0;/task_runningWake_up()函数分析：Wake_up用来唤醒进程（将状态置为task_running即可）voidwake_up(structtask_struct*p)/唤醒进程if(p&*p)if(*p).sta

10、te=TASK_STOPPED)printk(wake_up:TASK_STOPPED);if(*p).state=TASK_ZOMBIE)printk(wake_up:TASK_ZOMBIE);(*p).state=0;/TASK_RUNNING第二部分：实现进程调度算法进程调度算法：操作系统通过PCB来控制进程。PCB是进程实体的一部分，是操作系统中最重要的记录性数据结构，用来管理和控制进程，每一个进程均有一个PCB，在创建进程时，建立PCB，伴随进程运行的全过程，直到进程撤消而撤消。为了模拟进程调度算法，自定义了PCB：typedefstructPCB_pid_tpid;intprior

11、ity;intround_time;intwait_time;intdemand_time;/所需要的总时间intcmplt_time;/完成时间intremain_time;/还需要的时间（RR）intsuspend_time;/暂时被挂起的时刻(RR)intarrive_time;/到达时间intstart_time;/开始执行时间structPCB*next;*p_pcb,PCB;然后实现FCFS,SJF,RR算法：FCFS算法：先给进程队列排序，按时间的先后顺序来排，先来的排前面。排好序后可以计算出每个进程的开始执行时间和结束时间voidFCFS(p_pcbhead)insertion

12、SortList(head,fcfs);/按到达时间排序p_pcbp=head;head-cmplt_time=head-demand_time;head-round_time=head-demand_time;head-wait_time=0;/初始化头节点while(p-next)if(p-next-arrive_timecmplt_time)/当前到达时间在上一个作业结束时间之前p-next-start_time=p-cmplt_time;/上一个任务完成时下一个任务开始else/当前到达时间在上一个作业结束时间之后p-next-start_time=p-next-arrive_time

13、;/开始时间及到达时间p-next-wait_time=p-next-start_time-p-next-arrive_time;/等待时间=开始时间-到达时间p-next-cmplt_time=p-next-start_time+p-next-demand_time;/完成时间=开始时间+服务时间p-next-round_time=p-next-wait_time+p-next-demand_time;/周转时间=等待时间+执行时间p=p-next;visit(head);/打印结果SJF算法：假设所有进程在时间0时到达，则先给所有程序按所需执行时间排序，然后依次执行，计算出开始时间和结束时

14、间。voidSJF(p_pcbhead)/假设所有进程在同一时刻到达insertionSortList(head,sjf);p_pcbp=head;head-arrive_time=0;head-cmplt_time=head-demand_time;head-round_time=head-demand_time;head-wait_time=0;/初始化头节点while(p-next)p-next-arrive_time=0;p-next-start_time=p-cmplt_time;/上一个任务完成时下一个任务开始p-next-wait_time=p-next-start_time-p

15、-next-arrive_time;/等待时间=开始时间-到达时间p-next-cmplt_time=p-next-start_time+p-next-demand_time;/完成时间=上一个完成时间+服务时间p-next-round_time=p-next-wait_time+p-next-demand_time;/周转时间=完成时间-到达时间p=p-next;visit(head);RR：时间片轮转。假设所有程序在时间0时到达，然后每个程序轮流用时间片来执行。利用循环链表来操作，轮到该程序（该pcb的节点）执行时给该节点的剩余时间remain-time减时间片时间，如果剩余时间为0就将其

16、移除循环链表，然后指向下一个节点。最后依次轮回，直到循环链表中只剩下一个节点。voidRR(p_pcbhead)floatquantum=5.0;p_pcbp=head;while(p-next)/预处理，初始化remain-timep-start_time=0;p-remain_time=p-demand_time;p=p-next;p-start_time=0;/处理最后一个节点p-remain_time=p-demand_time;printf(pid%d,starat%d,remain%dn,p-pid,p-start_time,p-remain_time);p-next=head;/

17、初始化为循环链表，方便后续操作/从头开始p=head;inti=0;/记录经过了多少时间片while(p-next!=p)if(p-next-remain_timequantum)/还需要的时间大于时间片时间p-next-start_time=i*quantum;/开始时间为时间片开始时间p-next-suspend_time=p-next-start_time+quantum;/暂停时间为开始时间+时间片时间p-next-remain_time-=quantum;/还需要的时间自减printf(process%dstartattime%dwithtimequantum%.2f,and%dle

18、ftn,p-next-pid,p-next-start_time,quantum,p-next-remain_time);else/在改时间片内可以完成此任务p-next-cmplt_time=p-next-start_time+p-next-remain_time;/开始时间+所需时间printf(process%dstartat%dn,p-next-pid,p-next-start_time);printf(process%dcompleteat%dn,p-next-pid,p-next-cmplt_time);delete(p);/删除p-nexti+;p=p-next;还用到的算法：插

19、入排序voidinsertionSortList(p_pcbhead,Typetype)/插入排序if(head=NULL|head-next=NULL)return;p_pcbp=head-next,pstart=(p_pcb)malloc(sizeof(PCB),pend=head;pstart-next=head;/为了操作方便，添加一个头结点while(p)p_pcbtmp=pstart-next,pre=pstart;if(type=fcfs)while(tmp!=p&p-arrive_time=tmp-arrive_time)/找到插入位置tmp=tmp-next;pre=pre-

20、next;elseif(type=sjf)while(tmp!=p&p-demand_time=tmp-demand_time)/找到插入位置tmp=tmp-next;pre=pre-next;if(tmp=p)pend=p;elsepend-next=p-next;p-next=tmp;pre-next=p;p=pend-next;head=pstart-next;free(pstart);五、 实验结果模拟了FCFS算法，SJF算法以及RR算法（代码见后面）。FCFS算法：先来先执行，根据到达时间对执行顺序行排序:SJF:短任务执行：时间片为2时的RR：时间片为5时的RR:六、 附件6.1

21、 附件1：源代码Pcb.h#includeunistd.htypedefenumTypefcfs=1,sjf=2Type;typedefstructPCB_pid_tpid;intpriority;intround_time;intwait_time;intdemand_time;/所需要的总时间intcmplt_time;/完成时间intremain_time;/还需要的时间（RR）intsuspend_time;/暂时被挂起的时刻(RR)intarrive_time;/到达时间intstart_time;/开始执行时间structPCB*next;*p_pcb,PCB;voidvisit(

22、p_pcb);voidFCFS(p_pcb);voidSJF(p_pcb);voidRR(p_pcb);voidinitial(p_pcb);voiddestroy(p_pcb);voidinsertionSortList(p_pcbhead,Typetype);scheduling.c#includepcb.h#includestdlib.h#include#includevoidinitial(p_pcbqueue)/初始化节点queue-arrive_time=0;queue-demand_time=0;queue-next=NULL;voiddestroy(p_pcbhead)/销毁链

23、表p_pcbp=head;while(p)p_pcbtemp=p;p=p-next;free(temp);voidadd(p_pcbhead,p_pcbnew)/添加节点p_pcbp=head;while(p-next)p=p-next;p-next=new;new-next=NULL;voiddelete(p_pcbp)/删除p之后的节点p_pcbtemp=p-next;p-next=p-next-next;free(temp);voidinsertionSortList(p_pcbhead,Typetype)/插入排序if(head=NULL|head-next=NULL)return;p

24、_pcbp=head-next,pstart=(p_pcb)malloc(sizeof(PCB),pend=head;pstart-next=head;/为了操作方便，添加一个头结点while(p)p_pcbtmp=pstart-next,pre=pstart;if(type=fcfs)while(tmp!=p&p-arrive_time=tmp-arrive_time)/找到插入位置tmp=tmp-next;pre=pre-next;elseif(type=sjf)while(tmp!=p&p-demand_time=tmp-demand_time)/找到插入位置tmp=tmp-next;p

25、re=pre-next;if(tmp=p)pend=p;elsepend-next=p-next;p-next=tmp;pre-next=p;p=pend-next;head=pstart-next;free(pstart);voidFCFS(p_pcbhead)insertionSortList(head,fcfs);/按到达时间排序p_pcbp=head;head-cmplt_time=head-demand_time;head-round_time=head-demand_time;head-wait_time=0;/初始化头节点while(p-next)if(p-next-arrive

26、_timecmplt_time)/当前到达时间在上一个作业结束时间之前p-next-start_time=p-cmplt_time;/上一个任务完成时下一个任务开始else/当前到达时间在上一个作业结束时间之后p-next-start_time=p-next-arrive_time;/开始时间及到达时间p-next-wait_time=p-next-start_time-p-next-arrive_time;/等待时间=开始时间-到达时间p-next-cmplt_time=p-next-start_time+p-next-demand_time;/完成时间=开始时间+服务时间p-next-ro

27、und_time=p-next-wait_time+p-next-demand_time;/周转时间=等待时间+执行时间p=p-next;visit(head);/打印结果voidSJF(p_pcbhead)/假设所有进程在同一时刻到达insertionSortList(head,sjf);p_pcbp=head;head-arrive_time=0;head-cmplt_time=head-demand_time;head-round_time=head-demand_time;head-wait_time=0;/初始化头节点while(p-next)p-next-arrive_time=0

28、;p-next-start_time=p-cmplt_time;/上一个任务完成时下一个任务开始p-next-wait_time=p-next-start_time-p-next-arrive_time;/等待时间=开始时间-到达时间p-next-cmplt_time=p-next-start_time+p-next-demand_time;/完成时间=上一个完成时间+服务时间p-next-round_time=p-next-wait_time+p-next-demand_time;/周转时间=完成时间-到达时间p=p-next;visit(head);voidRR(p_pcbhead)flo

29、atquantum=5.0;p_pcbp=head;while(p-next)/预处理，初始化remain-timep-start_time=0;p-remain_time=p-demand_time;p=p-next;p-start_time=0;/处理最后一个节点p-remain_time=p-demand_time;printf(pid%d,starat%d,remain%dn,p-pid,p-start_time,p-remain_time);p-next=head;/初始化为循环链表，方便后续操作/从头开始p=head;inti=0;/记录经过了多少时间片while(p-next!=

30、p)if(p-next-remain_timequantum)/还需要的时间大于时间片时间p-next-start_time=i*quantum;/开始时间为时间片开始时间p-next-suspend_time=p-next-start_time+quantum;/暂停时间为开始时间+时间片时间p-next-remain_time-=quantum;/还需要的时间自减printf(process%dstartattime%dwithtimequantum%.2f,and%dleftn,p-next-pid,p-next-start_time,quantum,p-next-remain_time);else/在改时间片内可以完成此任务p-next-cmplt_time=p-next-start_time+p-next-remain_time;/开始时间+所需时间printf(pro