操作系统实验报告——进程调度(共21页).docx
精选优质文档-倾情为你奉上北京邮电大学软件学院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 stacknr",i,j);/内核栈最大为j，空字节数是i，比例i/j void show_stat(void)/打印所有进程的状态信息 int i; for (i=0;i<NR_TASKS;i+) if (taski) show_task(i,taski);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 signal */ for (p = &LAST_TASK; p > &FIRST_TASK; -p) /把p初始化为指向最后一个进程的地址的指针,逆向扫描所有进程 if (*p) /当前进程 if (*p)->timeout && (*p)->timeout < jiffies) / jiffies是持续变的，timeout 是阈值 (*p)->timeout = 0; /如果当前进程等待很久了，并且这个进程处于TASK_INTERRUPTIBLE if (*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 = &taskNR_TASKS; while (-i) /把所有进程都扫一遍，counter是递减的，找出counter最大的进程，保存在next里面 if (!*-p) /当前*p指向进程为空，下一个 continue; if (*p)->state = TASK_RUNNING && (*p)->counter > c) /counter是任务运行时间计数，如果当前进程是执行状态且运行时间数大于c c = (*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使用CPUSleep_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("task0 trying to sleep"); tmp = *p; / tmp 指向原等待队列的头指针 *p = current; /*p 指向等待队列的头指针，把current放入等待队列current->state = TASK_INTERRUPTIBLE; /当前状态为不可中断 schedule();/调度一下， if (tmp) tmp->state = 0;/task_runningWake_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算法：先给进程队列排序，按时间的先后顺序来排，先来的排前面。排好序后可以计算出每个进程的开始执行时间和结束时间void FCFS(p_pcb head) insertionSortList(head, fcfs); /按到达时间排序 p_pcb p = head; head->cmplt_time = head->demand_time; head->round_time = head->demand_time; head->wait_time = 0; /初始化头节点 while (p->next) if (p->next->arrive_time < p->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时到达，则先给所有程序按所需执行时间排序，然后依次执行，计算出开始时间和结束时间。void SJF(p_pcb head) /假设所有进程在同一时刻到达 insertionSortList(head, sjf); p_pcb p = 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->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就将其移除循环链表，然后指向下一个节点。最后依次轮回，直到循环链表中只剩下一个节点。void RR(p_pcb head) float quantum = 5.0; p_pcb p = head; while (p->next) /预处理，初始化remain-time p->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,star at %d,remain %dn", p->pid, p->start_time, p->remain_time); p->next = head; /初始化为循环链表，方便后续操作 /从头开始 p = head; int i = 0; /记录经过了多少时间片 while (p->next != p) if (p->next->remain_time > quantum) /还需要的时间大于时间片时间 p->next->start_time = i * quantum; /开始时间为时间片开始时间 p->next->suspend_time = p->next->start_time + quantum; /暂停时间为开始时间+时间片时间 p->next->remain_time -= quantum; /还需要的时间自减 printf("process %d start at time %d with time quantum %.2f,and %d leftn", 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 %d start at %dn", p->next->pid, p->next->start_time); printf("process %d complete at %dn", p->next->pid, p->next->cmplt_time); delete (p); /删除p->next i+; p = p->next; 还用到的算法：插入排序void insertionSortList(p_pcb head, Type type) /插入排序 if (head = NULL | head->next = NULL) return; p_pcb p = head->next, pstart = (p_pcb)malloc(sizeof(PCB), pend = head; pstart->next = head; /为了操作方便，添加一个头结点 while (p) p_pcb tmp = pstart->next, pre = pstart; if (type = fcfs) while (tmp != p && p->arrive_time >= tmp->arrive_time) /找到插入位置 tmp = tmp->next; pre = pre->next; else if (type = sjf) while (tmp != p && p->demand_time >= tmp->demand_time) /找到插入位置 tmp = tmp->next; pre = pre->next; if (tmp = p) pend = p; else pend->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 附件1：源代码Pcb.h#include "unistd.h"typedef enum Type fcfs=1,sjf=2Type;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;void visit(p_pcb);void FCFS(p_pcb);void SJF(p_pcb);void RR(p_pcb);void initial(p_pcb);void destroy(p_pcb);void insertionSortList(p_pcb head,Type type);scheduling.c#include "pcb.h"#include "stdlib.h"#include <stdio.h>#include<time.h>void initial(p_pcb queue) /初始化节点 queue->arrive_time = 0; queue->demand_time = 0; queue->next = NULL;void destroy(p_pcb head) /销毁链表 p_pcb p = head; while (p) p_pcb temp = p; p = p->next; free(temp); void add(p_pcb head, p_pcb new) /添加节点 p_pcb p = head; while (p->next) p = p->next; p->next = new; new->next = NULL;void delete (p_pcb p) /删除p之后的节点 p_pcb temp = p->next; p->next = p->next->next; free(temp);void insertionSortList(p_pcb head, Type type) /插入排序 if (head = NULL | head->next = NULL) return; p_pcb p = head->next, pstart = (p_pcb)malloc(sizeof(PCB), pend = head; pstart->next = head; /为了操作方便，添加一个头结点 while (p) p_pcb tmp = pstart->next, pre = pstart; if (type = fcfs) while (tmp != p && p->arrive_time >= tmp->arrive_time) /找到插入位置 tmp = tmp->next; pre = pre->next; else if (type = sjf) while (tmp != p && p->demand_time >= tmp->demand_time) /找到插入位置 tmp = tmp->next; pre = pre->next; if (tmp = p) pend = p; else pend->next = p->next; p->next = tmp; pre->next = p; p = pend->next; head = pstart->next; free(pstart);void FCFS(p_pcb head) insertionSortList(head, fcfs); /按到达时间排序 p_pcb p = head; head->cmplt_time = head->demand_time; head->round_time = head->demand_time; head->wait_time = 0; /初始化头节点 while (p->next) if (p->next->arrive_time < p->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); /打印结果void SJF(p_pcb head) /假设所有进程在同一时刻到达 insertionSortList(head, sjf); p_pcb p = 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->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);void RR(p_pcb head) float quantum = 5.0; p_pcb p = head; while (p->next) /预处理，初始化remain-time p->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,star at %d,remain %dn", p->pid, p->start_time, p->remain_time); p->next = head; /初始化为循环链表，方便后续操作 /从头开始 p = head; int i = 0; /记录经过了多少时间片 while (p->next != p) if (p->next->remain_time > quantum) /还需要的时间大于时间片时间 p->next->start_time = i * quantum; /开始时间为时间片开始时间 p->next->suspend_time = p->next->start_time + quantum; /暂停时间为开始时间+时间片时间 p->next->remain_time -= quantum; /还需要的时间自减 printf("process %d start at time %d with time quantum %.2f,and %d leftn", 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
