操作系统实验报告——进程调度

北京邮电大学软件学院2019-2020学年第2学期实验报告课程名称：操作系统实验名称：进程调度实验完成人：日期：2019年11月26日一、实验目的1.理解Linux管理进程所用到的数据结构。2.理解Linux的进程调度算法的处理逻辑及其实现所用到的数据结构。二、实验内容1.通过查阅参考书或者上网找资料，熟悉/usr/src/linux（注意：这里最后一级目录名可能是个含有具体内核版本号和“linux”字符串的名字）下各子目录的内容，即所含Linux源代码的情况。2.分析Linux进程调度有关函数的源代码，主要是schedule()函数，并且要对它们引用的头文件等一并分析。3.实现Linux的进程调度算法及理解其实现所用的主要数据结构。三、实验环境Linux下使用gcc+vscode四、实验过程描述第一部分：源代码分析：所需头文件：#includelinux/sched.h#includelinux/kernel.h#includelinux/sys.h#includelinux/fdreg.h#includeasm/system.h#includeasm/io.h#includeasm/segment.h#includesignal.hlinux/kernel.h：内核头文件，含有一些内核常用函数的原形定义。linux/fdreg.h：软驱头文件，含有软盘控制器参数的一些定义。linux/sched.h：调度程序头文件，主要定义了任务结构task_struct、初始任务0的数据，以及一些有关描述符参数设置和获取的嵌入式汇编函数宏语句。linux/sys.h：系统调用头文件，主要是系统调用C函数处理程序。asm/io.h：I/O头文件，以宏的嵌入汇编程序形式定义对I/O端口操作的函数。asm/segment.h：段操作头文件，定义了有关段寄存器操作的嵌入式汇编函数。asm/system.h：系统头文件，定义了设置或修改描述符/中断门等的嵌入式汇编宏。signal.h：信号头文件，定义信号符号常量，信号结构以及信号操作函数原型。Schedule.c部分函数分析：（大多写在注释里）show_task()函数某个进程的状态信息以及空间大小voidshow_task(intnr,structtask_struct*p)//显示p指向的nr号进程的相关信息{inti,j=4096-sizeof(structtask_struct);//j记录了任务结构体之后的堆栈空间大小printk(%d:pid=%d,state=%d,,nr,p-pid,p-state);//打印进程的各种信息i=0;while(ij&&!((char*)(p+1))[i])//计算了任务之后空字节的大小i++;printk(%d/%dcharsfreeinkernelstack\n\r,i,j);//内核栈最大为j，空字节数是i，比例i/j}voidshow_stat(void)//打印所有进程的状态信息{inti;for(i=0;iNR_TASKS;i++)if(task[i])show_task(i,task[i]);}Schedule()分析：schedule函数首先对所有的任务检查，唤醒任何一个已经得到信号的任务，也就是针对任务数组中的每个任务，检查其警报定时值alarm。如果任务的alarm已经超期（alarmjiffies），则在它的信号位图中设置SIGALARM，然后清除alarm值。之后schedule()函数首先扫描任务队列，通过比较每个就绪状态任务的运行时间递减计数counter的值来确定当前哪个进程运行的时间最少，哪个counter值最大.counter越大就说明运行时间越短，于是就选中该进程，并使用任务切换宏函数到该进程运行利用switch_to函数完成任务转换。如果所有的就绪任务的该值都是0，则表示此刻所有任务的时间片都已运行完。于是就根据任务的优先权值priority，重置每个任务的运行时间counter。voidschedule(void){inti,next,c;structtask_struct**p;/*checkalarm,wakeupanyinterruptibletasksthathavegotasignal*/for(p=&LAST_TASK;p&FIRST_TASK;--p)//把p初始化为指向最后一个进程的地址的指针,逆向扫描所有进程if(*p){//当前进程if((*p)-timeout&&(*p)-timeoutjiffies){//jiffies是持续变的，timeout是阈值(*p)-timeout=0;//如果当前进程等待很久了，并且这个进程处于TASK_INTERRUPTIBLEif((*p)-state==TASK_INTERRUPTIBLE)(*p)-state=TASK_RUNNING;//我们就把这个进程置与TASK_RUNNING状态}if((*p)-alarm&&(*p)-alarmjiffies){//如果此时jiffies大于alarm信号周期，则让将SIGALRM写入进程的信号位(*p)-signal|=(1(SIGALRM-1));(*p)-alarm=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=&task[NR_TASKS];while(--i){//把所有进程都扫一遍，counter是递减的，找出counter最大的进程，保存在next里面if(!*--p)//当前*p指向进程为空，下一个continue;if((*p)-state==TASK_RUNNING&&(*p)-counterc)//counter是任务运行时间计数，如果当前进程是执行状态且运行时间数大于cc=(*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)+(*p)-priority;//重新计算counter=counter/2+priority}switch_to(next);//让进程next使用CPU}}Sleep_on()函数分析：Sleep_on()函数sleep_on()函数的主要功能是当一个进程（或任务）所请求的资源正等待资源响应或不在内存中时暂时切换出去，放在等待队列中等待一段时间，先让别的程序运行一段时间，当切换回来后再继续运行。巧妙的利用了tmp指针来作为与等待队列的联系voidsleep_on(structtask_struct**p){structtask_struct*tmp;if(!p)return;if(current==&(init_task.task))panic(task[0]tryingtosleep);tmp=*p;//tmp指向原等待队列的头指针*p=current;//*p指向等待队列的头指针，把current放入等待队列current-state=TASK_INTERRUPTIBLE;//当前状态为不可中断schedule();//调度一下，if(tmp)tmp-state=0;//task_running}Wake_up()函数分析：Wake_up用来唤醒进程（将状态置为task_running即可）voidwake_up(structtask_struct**p)//唤醒进程{if(p&&*p){if((**p).state==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;intpriority;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){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_timep-cmplt_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-round_time=p-next-wait_time+p-next-demand_time;//周转时间=等待时间+执行时间p=p-next;}visit(head);//打印结果}SJF算法：假设所有进程在时间0时到达，则先给所有程序按所需执行时间排序，然后依次执行，计算出开始时间和结束时间。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-s