北京邮电大学软件学院2019-2020学年第2学期实验报告课程名称：操作系统实验名称：进程调度实验完成人：日期： 2019 年 11 月 26 日一、实验目的1. 理解 Linux 管理进程所用到的数据结构。
2. 理解 Linux 的进程调度算法的处理逻辑及其实现所用到的数据结构。
二、实验内容1. 通过查阅参考书或者上网找资料，熟悉/usr/src/linux（注意：这里最后一级目录名可能是个含有具体内核版本号和“linux”字符串的名字）下各子目录的内容，即所含 Linux 源代码的情况。
2. 分析 Linux 进程调度有关函数的源代码，主要是 schedule()函数，并且要对它们引用的头文件等一并分析。
3. 实现 Linux 的进程调度算法及理解其实现所用的主要数据结构。
三、实验环境Linux下使用gcc+vscode四、实验过程描述第一部分：源代码分析：所需头文件：#include<linux/sched.h>#include<linux/kernel.h>#include<linux/sys.h>#include<linux/fdreg.h>#include<asm/system.h>#include<asm/io.h>#include<asm/segment.h>#include<signal.h><linux/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()函数某个进程的状态信息以及空间大小void show_task(int nr,struct task_struct*p)//显示p指向的nr号进程的相关信息{int i,j = 4096-sizeof(struct task_struct);//j记录了任务结构体之后的堆栈空间大小printk("%d: pid=%d, state=%d, ",nr,p->pid,p->state);//打印进程的各种信息i=0;while (i<j && !((char *)(p+1))[i])//计算了任务之后空字节的大小i++;printk("%d/%d chars free in kernel stack\n\r",i,j);//内核栈最大为j，空字节数是i，比例i/j}void show_stat(void) //打印所有进程的状态信息{int i;for (i=0;i<NR_TASKS;i++)if (task[i])show_task(i,task[i]);}Schedule()分析：schedule函数首先对所有的任务检查，唤醒任何一个已经得到信号的任务，也就是针对任务数组中的每个任务，检查其警报定时值alarm。
如果任务的alarm 已经超期（alarm < jiffies），则在它的信号位图中设置SIGALARM，然后清除alarm值。
之后schedule()函数首先扫描任务队列，通过比较每个就绪状态任务的运行时间递减计数counter的值来确定当前哪个进程运行的时间最少，哪个counter值最大.counter越大就说明运行时间越短，于是就选中该进程，并使用任务切换宏函数到该进程运行利用switch_to函数完成任务转换。
如果所有的就绪任务的该值都是0，则表示此刻所有任务的时间片都已运行完。
于是就根据任务的优先权值priority，重置每个任务的运行时间counter。
void schedule(void){int i, next, c;struct task_struct**p;/* check alarm, wake up any interruptible tasks that have got a sig nal */for (p = &LAST_TASK; p > &FIRST_TASK; --p) //把p初始化为指向最后一个进程的地址的指针,逆向扫描所有进程if (*p){ //当前进程if ((*p)->timeout && (*p)->timeout < jiffies){ // jiffies是持续变的，timeout 是阈值(*p)->timeout = 0;//如果当前进程等待很久了，并且这个进程处于TASK_INTERRUPTIBLEif ((*p)->state == TASK_INTERRUPTIBLE)(*p)->state = TASK_RUNNING; //我们就把这个进程置与TASK_RUNNING状态}if ((*p)->alarm && (*p)->alarm < jiffies){ //如果此时jiffies大于alarm信号周期，则让将SIGALRM写入进程的信号位(*p)->signal |= (1 << (SIGALRM - 1));(*p)->alarm = 0;}if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&(*p)->state == TASK_INTERRUPTIBLE) // 除SIGKILL SIGSTOP 信号外，其他信号都是非阻塞状态的话，并且进程处于TASK_INTERRUPTIBLE(*p)->state = TASK_RUNNING; //把这个进程置与TASK_RUNNING 状态}/* this is the scheduler proper: */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)->counter > c)//counter是任务运行时间计数，如果当前进程是执行状态且运行时间数大于cc = (*p)->counter, next = i;}if (c)break; //c>0 就说明找到了已经运行一段时间，并且运行时间最短的进程，跳出while(1)for (p = &LAST_TASK; p > &FIRST_TASK; --p) //如果c==0，说明所有schedule的进程都没有运行if (*p)(*p)->counter = ((*p)->counter >> 1) +(*p)->priority; //重新计算counter = counter/2 + priority}switch_to(next); //让进程next使用CPU}}Sleep_on()函数分析：Sleep_on()函数sleep_on()函数的主要功能是当一个进程（或任务）所请求的资源正等待资源响应或不在内存中时暂时切换出去，放在等待队列中等待一段时间，先让别的程序运行一段时间，当切换回来后再继续运行。
巧妙的利用了tmp指针来作为与等待队列的联系void sleep_on(struct task_struct **p){struct task_struct *tmp;if (!p)return;if (current == &(init_task.task))panic("task[0] trying to sleep");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即可）void wake_up(struct task_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：typedef struct PCB{__pid_t pid;int priority;int round_time;int wait_time;int demand_time; //所需要的总时间int cmplt_time; //完成时间int remain_time; //还需要的时间（RR）int suspend_time; //暂时被挂起的时刻(RR)int arrive_time; //到达时间int start_time; //开始执行时间struct PCB*next;}*p_pcb,PCB;然后实现FCFS,SJF,RR算法：FCFS算法：先给进程队列排序，按时间的先后顺序来排，先来的排前面。