操作系统课程设计大作业C++进程调度算法的模拟实现源码.zip

# OS-master #### 实验目的 多道系统中，进程与进程之间存在同步与互斥关系。当就绪进程数大于处理机数时，需要按照某种策略决定哪些进程先占用处理机。在可变分区管理方式下，采用首次适应算法实现主存空间的分配和回收。 模拟实现处理机调度及内存分配及回收机制，以对处理机调度的工作原理以及内存管理的工作过程进行更深入的了解。 #### 实验具体内容 - 设计一个抢占式优先权调度算法实现多处理机调度的程序，并且实现在可变分区管理方式下，采用首次适应算法实现主存空间的分配和回收。 - PCB 内容包括：进程名/PID；要求运行时间（单位时间）；优先权；状态；进程属性：独立进程、同步进程（前趋、后继）。 - 可以随机输入若干进程，可随时添加进程，并按优先权排序； - 从就绪队首选进程运行：优先权-1；要求运行时间-1；要求运行时间为 0 时，撤销该进程；一个时间片结束后重新排序，进行下轮调度； - 自行假设主存空间大小，预设操作系统所占大小并构造未分分区表。表目内容：起址、长度、状态（未分/空表目）。对内存空间分配采用首次适应算法。 - 进程完成后，回收主存，并与相邻空闲分区合并。 - 设置后备队列和挂起状态。若内存空间足够，可自动从后备队列调度一作业进入。被挂起进程入挂起队列，设置解挂功能用于将制定挂起进程解挂入就绪队列。 - 最好采用图形界面。 ## 需求分析 ### 进程的设计 为了实现进程调度，首先要设计进程的类型。本次实验采用基于对象的高级语言C++，因此进程在该问题中可设计为Procress类，该类仅包括一些基本的数据结构，可以使外界访问私有变量的接口和信息展示这些最基本的功能。 将Procress的属性和方法封装起来之后在后续可以方便地使用。 进程的私有变量包括进程名（即进程Pid），要求运行时间，进程到达时间，进程优先级，进程状态（后备、活动就绪、阻塞、挂起、结束），进程属性（独立进程与同步进程），进程的前驱节点（仅针对同步进程）和进程所需的空间大小。 类包含的方法为仅有展示该类的信息和外界访问类私有变量的接口。 ### 调度算法的实现 操作系统中最重要的就是CPU资源的管理，要想管理好CPU资源就要合理地调度进程。本次实验采用抢占式优先权调度完成。 由于模拟的是多处理机系统，因此每一时刻处在运行态的进程有多个，需要设置运行队列来展示处于运行状态的进程。要想实现优先权调度就要在进程的属性中增加优先权，同时在就绪队列中对进程按优先权排序，如果就绪队列中的进程数量足够，每次调度可以从就绪队列中挑选前n个进程，将其状态设置为“run”，并从原队列中删除，加到运行队列中。 为了实现抢占式调度，需要等到每次时间片结束之后重新对进程进行调度，而非等到进程全部运行完成。每次运行完一个时间片，进程的优先级将减一并重新回到就绪队列，对就绪队列中的进程重新按照优先权排序并重新调度，此时如果有优先级更高的进程进入则可实现抢占式调度。 若每次运行之后进程要求运行的时间减为0，则说明进程结束，将其状态设置为“end”，移入到结束队列中。 ### 内存的分配与回收 内存的分配与回收采用的是可变分区管理方式，采用首次适应算法来实现主存空间的分配与回收。 要实现可变分区管理，首先要设置分区状态表。分区状态表为向量，向量中每个元素为分区记录数组，包括起始地址，长度，分区状态。如果分区未分配，则设置分区状态为“unmalloced”，否则设置为对应进程的pid。 首先在构造函数中为分区状态表添加第一块分区，即初始化内存空间。起始地址为0，长度为主存空间大小，状态为“unmalloced”。之后只需要对进程操作时调用分配和回收函数即可。 主存空间的分配采用首次适应算法。遍历分区状态表，如果当前分区（i）长度大于进程(p)所需长度，则修改i的状态为p的pid，i的长度为p所需空间。若剩余空间为0，则直接退出，否则增加一条记录到分区状态表中，起始地址为i的起始地址+p的空间，长度为i的长度减p的空间，同时设置状态为“unmalloced”。若遍历结束仍未找到长度大于p所需空间的分区，则返回False。 主存空间回收首先遍历分区状态表，找到分区状态等于进程pid的分区，然后设置其状态为空闲。之后需要根据不同情况对分区状态表进行不同的合并操作。如果当前分区为第一块分区，需要判断下一块分区状态是否空闲，若空闲则合并；如果当前分区为最后一块分区，需要判断上一块分区是否空闲，若空闲则合并；若既不是第一块分区又不是最后一块分区，则需要判断上下两块分区的状态是否空闲，从而执行相应的合并操作。 ### 进程挂起 进程挂起时需要回收进程的内存空间，然后设置进程状态为“suspend”，之后将其从就绪队列中移除，然后加入到挂起队列中。 进程解挂时首先为其分配主存空间，如果分配成功，则将其状态设置为“ready”并且从原队列移除，移入就绪队列。若主存空间分配失败，则将其状态设置为“back”并且从原队列移除，移入后备队列。 ### 阻塞队列 进程分为独立进程和同步进程，独立进程没有前驱，同步进程设置前驱进程。同步进程需要等到其全部前驱全部运行完成它才可以运行。为此，需要设置阻塞态，当某一进程被调度时首先检查其前驱节点是否完成，如果前驱节点全在结束队列中，则直接进入运行态，否则进入阻塞态，直到该进程所有前驱进程全部完成，它才可以再次被调度。 与挂起状态不同的是，阻塞队列中的进程仍然在内存空间中，它的状态转移不需要进行内存空间的分配与回收。 ### 后备队列 当某一时刻进程数过多，主存空间无法容纳所有的进程，此时需要将多余的进程暂时放到后备队列中，后备队列中的进程不占用主存空间。一旦主存空间足够，将会自动从后备队列中调度进程，为其分配主存空间并将其加入就绪队列。 为此，需要在每次调度之前遍历就绪队列，检查为其分配主存空间是否成功，如果成功则将其加入就绪队列，否则继续向后遍历。 ### 程序流程图  ### 主界面展示