作业调度算法C++实现

第二章练习题及参考答案一、单项选择题1.用户作业可以通过（）方式由用户自己按照作业来进行操作。

A.脱机B.自动控制C.在线处理D.联机处理2.（）是操作系统提供的一种专门语言，它由操作系统的专门机制解释处理。

A.C语言B.JCL语言C.Ada语言D.Pascal语言3.作业调度算法中（）调度算法最有利于提高资源利用率。

A.先来先服务B.优先数C.响应比最高优先D.均衡4.终端用户在终端上控制作业的执行要经历四个阶段，最初阶段是（）。

A.用户注册B.终端连接C.作业控制D.用户退出5.在下面作业调度算法中（）调度算法最有利于小作业，从而提高系统吞吐能力。

A.先来先服务B.计算时间短的作业优先C.优先数D.响应比最高者优先6.当中央处理器处于目态时，它可以执行的指令是（）。

A.计算机系统中的全部指令B.仅限于非特权指令C.仅限于防管指令D.仅限于特权指令7.作业调度算法常考虑因素之一是使系统有最高的吞吐率，为此应（）。

A.不让处理机空闲B.能够处理尽可能多的作业C.使各类用户满意D.不使系统过于复杂8. 分时操作系统环境下运行的作业通常称为（）。

A.后台作业B.长作业C.批量型作业D.终端型作业9.在作业调度算法中，若所有作业同时到达，则平均等待时间最短的算法是（）。

A.先来先服务B.优先数C.响应比最高优先D.计算时间段的作业优先10.作业调度程序从处于（）状态的作业队列中选取适当的作业投入运行。

A.执行B.提交C.完成D.后备11.既考虑作业等待时间，又考虑作业执行时间的调度算法是（）。

A. 先来先服务B.优先数C.响应比最高优先D.均衡12.（）是指从作业提交给系统到作业完成的时间间隔。

A.周转时间B.响应时间C.等待时间D.执行时间13.作业从进入后备队列到被调度程序选中的时间间隔称为（）。

A.周转时间B.响应时间C.等待时间D.触发时间二、多项选择题1.响应比最高者优先调度算法是（）调度算法的折衷。

先来先服务和优先数调度算法c语言先来先服务和优先数调度算法c语言一、前言操作系统中的进程调度是指在多道程序环境下，按照一定的规则从就绪队列中选择一个进程，将CPU分配给它运行。

常用的进程调度算法有先来先服务（FCFS）、最短作业优先（SJF）、时间片轮转（RR）等。

本文将介绍两种常见的进程调度算法：先来先服务和优先数调度算法，并给出相应的C语言实现。

二、先来先服务算法1. 算法原理FCFS即First Come First Served，也称为FIFO（First In First Out），是一种非抢占式的进程调度算法。

按照任务到达时间的顺序进行处理，即谁先到达谁就被处理。

2. 算法流程（1）按照任务到达时间排序；（2）依次执行每个任务，直至所有任务都完成。

3. C语言实现下面是一个简单的FCFS程序：```c#include <stdio.h>struct process {int pid; // 进程IDint arrival_time; // 到达时间int burst_time; // 执行时间int waiting_time; // 等待时间};int main() {struct process p[10];int n, i, j;float avg_waiting_time = 0;printf("请输入进程数：");scanf("%d", &n);for (i = 0; i < n; i++) {printf("请输入第%d个进程的信息：\n", i + 1); printf("进程ID：");scanf("%d", &p[i].pid);printf("到达时间：");scanf("%d", &p[i].arrival_time);printf("执行时间：");scanf("%d", &p[i].burst_time);}for (i = 0; i < n; i++) {for (j = 0; j < i; j++) {if (p[j].arrival_time > p[j + 1].arrival_time) { struct process temp = p[j];p[j] = p[j + 1];p[j + 1] = temp;}}}int current_time = p[0].arrival_time;for (i = 0; i < n; i++) {if (current_time < p[i].arrival_time) {current_time = p[i].arrival_time;}p[i].waiting_time = current_time - p[i].arrival_time;current_time += p[i].burst_time;}printf("进程ID\t到达时间\t执行时间\t等待时间\n");for (i = 0; i < n; i++) {printf("%d\t%d\t%d\t%d\n", p[i].pid, p[i].arrival_time, p[i].burst_time, p[i].waiting_time);avg_waiting_time += (float)p[i].waiting_time / n;}printf("平均等待时间：%f\n", avg_waiting_time);return 0;}```三、优先数调度算法1. 算法原理优先数调度算法是一种非抢占式的进程调度算法。

一、单项选择题（每小题1分，共15分）1．MS-DOS的引导程序是在磁盘初始化时，由（ ）命令写在软盘或硬盘的0柱0面1扇区上的。

A．CHKDSKB．FDISKC．FORMATD．DISKCOPY2．MS-DOS 5．0开始把（ ）的内存区域作为基本内存区。

A．1MB与2MB之间B．1MB之后C．640KB与1MB之间D．0KB与640KB之间3．MS-DOS中的文件存储结构采用（ ）。

A．顺序结构B．链接结构C．索引结构D．成组链接结构4．与“计算时间”无关的作业调度算法是（ ）算法。

A．先来先服务B．响应比高者优先C．优先数D．可抢占的优先数5．实时系统中的进程调度通常采用（ ）算法。

A．响应比高者优先B．短作业优先C．时间片轮转D．抢占式的优先数高者优先6．在可变分区存储管理中，为了实现主存的空间分配，应设置（ ）来进行管理。

A．页表B．段表C．位示图D．空闲区表7．某系统有同类资源m个供n个进程共享，如果每个进程最多申请k个资源（1＜=k＜=m），则各进程的最大需求量之和（ ）时系统不会发生死锁。

A．＝mB．＝m+nC．＜m十nD．＞m+n8．动态重定位是在（ ）完成的。

A．作业执行前B．作业执行过程中由硬件C．作业执行过程中由OSD．作业执行过程中由用户9．Windows操作系统是由（ ）公司研制的。

A．MicrosoftB．IntelC．HPD．SUN SYSTEM10．进程从等待状态进人就绪状态可能是由于（ ）。

A．现运行进程运行结束B．现运行进程执行P操作C．现运行进程执行了V操作D．现运行进程时间片用完11．在以下的存储管理方案中，能扩充主存容量的是（ ）。

A．固定式分区管理B．可变式分区管理C．页式存储管理D．分页虚拟存储管理12．UNIX文件系统对盘空间的管理采用（ ）。

A．FAT表法B．位示图法C．空闲块链接法D．空闲块成组链接法13．通道在输人输出操作完成或出错时就形成（ ），等候CPU来处理。

调度算法C语言实现调度算法是操作系统中的重要内容之一，它决定了进程在系统中的运行方式和顺序。

本文将介绍两种常见的调度算法，先来先服务（FCFS）和最短作业优先（SJF），并用C语言实现它们。

一、先来先服务（FCFS）调度算法先来先服务（FCFS）调度算法是最简单的调度算法之一、它按照进程到达的先后顺序进行调度，即谁先到达就先执行。

实现这个算法的关键是记录进程到达的顺序和每个进程的执行时间。

下面是一个用C语言实现先来先服务调度算法的示例程序：```c#include <stdio.h>//进程控制块结构体typedef structint pid; // 进程IDint arrivalTime; // 到达时间int burstTime; // 执行时间} Process;int maiint n; // 进程数量printf("请输入进程数量：");scanf("%d", &n);//输入每个进程的到达时间和执行时间Process process[n];for (int i = 0; i < n; i++)printf("请输入进程 %d 的到达时间和执行时间：", i);scanf("%d%d", &process[i].arrivalTime,&process[i].burstTime);process[i].pid = i;}//根据到达时间排序进程for (int i = 0; i < n - 1; i++)for (int j = i + 1; j < n; j++)if (process[i].arrivalTime > process[j].arrivalTime) Process temp = process[i];process[i] = process[j];process[j] = temp;}}}//计算平均等待时间和平均周转时间float totalWaitingTime = 0; // 总等待时间float totalTurnaroundTime = 0; // 总周转时间int currentTime = 0; // 当前时间for (int i = 0; i < n; i++)if (currentTime < process[i].arrivalTime)currentTime = process[i].arrivalTime;}totalWaitingTime += currentTime - process[i].arrivalTime;totalTurnaroundTime += (currentTime + process[i].burstTime) - process[i].arrivalTime;currentTime += process[i].burstTime;}//输出结果float avgWaitingTime = totalWaitingTime / n;float avgTurnaroundTime = totalTurnaroundTime / n;printf("平均等待时间：%f\n", avgWaitingTime);printf("平均周转时间：%f\n", avgTurnaroundTime);return 0;```以上程序实现了先来先服务（FCFS）调度算法，首先根据进程的到达时间排序，然后依次执行每个进程，并计算总等待时间和总周转时间。

一、选择1、操作系统的基本类型主要有____C______。

A、批处理系统、分时系统和多任务系统D、实时系统、分时系统和多用户系统2、操作系统的_____D_____管理部分负责对进程进行调度。

A、存储器B、文件C、设备3___B_____，则响应时间越长。

A、用户数越少C、内存越少D、内存越多4、实时系统追求的目标是______C____A、充分利用内存B、高吞吐率D、减少系统开销5______A____。

充分利用CPU，减少CPU等待时间B、提高实时响应速度C、有利于代码共享，减少主、辅存信息交换量D、充分利用存储器6、现代操作系统的基本特征是_____C______、资源共享和操作的异步性。

A、.多道程序设计B、中断处理D、实现分时与实时处理7、以下___C_____A、内存管理B、中断处理D、CPU调度8、如果分时系统中的时间片一定，用户数的多少与响应时间长短成__A__。

A、正比例B、反比例C、无正常比例关系D、呈线型关系9、三种基本类型的操作系统是____B____。

C、分时操作系统、实时操作系统和网络操作系统D、实时操作系统、网络操作系统和批处理操作系统10、不属于．．．单道．．批处理系统所具备的特征是____D____。

A、单道性B、顺序性C、自动性11。

A、时问片轮转调度算法C、先来先服务调度算法D、分级调度算法12_____A_____。

CPU，减少CPU等待时间B、提高实时响应速度C、有利于代码共享，减少主、辅存信息交换量D、充分利用存储器13、现代操作系统的基本特征是并发、_____D______和操作的异步性。

A、多道程序设计B、中断处理C、及时处理14、操作系统的类型按时间发展顺序，可分为______C____。

A、分时系统、批处理系统、实时系统D、实时系统、分时系统、批处理系统15. 下列哪一条不是批处理系统的优点？______D____A. 吞吐量大B. 资源利用率高C. 系统开销小16. UNIX 属于下列哪一类操作系统？___C____A. 单用户单任务B. 单用户多任务 D. 批处理17. 以下那个不是程序顺序执行的特性（C ）Ａ、封闭性Ｂ、顺序性Ｄ、不可再现性18. Windows NT属于哪一类操作系统？__DA、单用户单任务C、单道批处理1、如果信号量S的值是0，此时进程A执行P(S)操作，则进程A会__B ______。

操作系统实验报告（二）实验题目：进程调度算法实验环境：C++实验目的：编程模拟实现几种常见的进程调度算法，通过对几组进程分别使用不同的调度算法，计算进程的平均周转时间和平均带权周转时间，比较各种算法的性能优劣。

实验内容：编程实现如下算法：1.先来先服务算法；2.短进程优先算法；3.时间片轮转调度算法。

设计分析：程序流程图：1.先来先服务算法2.短进程优先算法3.时间片轮转调度算法实验代码：1.先来先服务算法#include <iostream.h>#define n 20typedef struct{int id; //进程名int atime; //进程到达时间int runtime; //进程运行时间}fcs;void main(){int amount,i,j,diao,huan;fcs f[n];cout<<"请输入进程个数:"<<endl;cin>>amount;for(i=0;i<amount;i++){cout<<"请输入进程名，进程到达时间，进程运行时间:"<<endl; cin>>f[i].id;cin>>f[i].atime;cin>>f[i].runtime;}for(i=0;i<amount;i++) //按进程到达时间的先后排序{ //如果两个进程同时到达，按在屏幕先输入的先运行for(j=0;j<amount-i-1;j++){ if(f[j].atime>f[j+1].atime){diao=f[j].atime;f[j].atime=f[j+1].atime;f[j+1].atime=diao;huan=f[j].id;f[j].id=f[j+1].id;f[j+1].id=huan;}}}for(i=0;i<amount;i++){cout<<"进程:"<<f[i].id<<"从"<<f[i].atime<<"开始"<<","<<"在"<<f[i].atime+f[i].runtime<<"之前结束。

c语言实现进程调度算法进程调度算法是操作系统中的一个重要组成部分，用于决定在多道程序环境下，选择哪个进程来占用CPU并执行。

C语言是一种通用的编程语言，可以用于实现各种进程调度算法。

这里我将分别介绍三种常见的进程调度算法：先来先服务调度算法（FCFS）、最短作业优先调度算法（SJF）和轮转法调度算法（RR），并给出用C语言实现的示例代码。

首先，我们来看先来先服务调度算法（FCFS）。

此算法根据到达时间的先后顺序，按照先来后到的顺序进行处理。

下面是基于C语言的先来先服务调度算法实现示例代码：```c#include<stdio.h>struct Process};void FCFS(struct Process proc[], int n)for (int i = 1; i < n; i++)}printf("进程号到达时间服务时间完成时间等待时间周转时间\n");for (int i = 0; i < n; i++)}for (int i = 0; i < n; i++)}int maiint n;printf("请输入进程数：");scanf("%d", &n);struct Process proc[n];for (int i = 0; i < n; i++)printf("请输入进程%d的到达时间和服务时间（用空格分隔）：", i + 1);}FCFS(proc, n);return 0;```其次，我们来看最短作业优先调度算法（SJF），该算法选择执行时间最短的进程先执行。

下面是基于C语言的最短作业优先调度算法实现示例代码：```c#include<stdio.h>struct Process};void SJF(struct Process proc[], int n)for (int i = 0; i < n; i++)for (int j = 0; j < i; j++)}shortest_job = i;for (int j = i + 1; j < n; j++)shortest_job = j;}}}for (int i = 1; i < n; i++)}printf("进程号到达时间服务时间完成时间等待时间周转时间\n");for (int i = 0; i < n; i++)}for (int i = 0; i < n; i++)}int maiint n;printf("请输入进程数：");scanf("%d", &n);struct Process proc[n];for (int i = 0; i < n; i++)printf("请输入进程%d的到达时间和服务时间（用空格分隔）：", i + 1);}SJF(proc, n);return 0;```最后，我们来看轮转法调度算法（RR），该算法分配一个时间片给每个进程，当时间片用完后，将CPU分配给下一个进程。

作业调度：从输入井中选中后备作业装入主存储器的过程，称为作业调度进程调度：从就绪队列中选中一个进程占用处理器运行作业调度的必要条件：系统现有尚未分配的资源可以满足被选中作业的资源要求。

作业调度算法的原则：公平性、平衡资源使用、极大的流量作业调度算法1、先来先服务算法按照作业进入输入井的先后次序来挑选作业，进入的作业优先被选中。

但是要注意，不是先进入的一定被选中，只有满足“必要条件”的作业才可能被选中。

一个先进入的作业，如果它所需要的资源或其中一部分资源已被在它先前的作业占用且尚未归还，那么这个作业将被推迟，而去选择在它之后进入的资源能满足的作业。

一旦有作业执行结束归还了资源后，作业调度再次选择作业时，仍要按照进入输入井的次序去挑选，刚刚被推迟的作业有可能被优先选中。

例子：假设用户使用的主存空间为100KB，作业调度和进程调度均采用先来先服务算法，进入输入井时间如下表：当作业调度是，A,B作业首先依次被选中装入主存，但作业C到达输入井后，由于不能满足它对主存量的要求，只能让它在输入井中等待，对随后到达输入井的作业D和E，作业D的主存需求可以得到满足，于是选中D装入主存。

于是A,B,C 总共占用85KB主存，还剩余15KB的空闲区，不够装入作业E，因此C,E均被推迟，在输入井中等待。

随后A被执行完，释放了15KB的主存，目前存储器有两个15KB的空闲区，仍不能装入C或E。

随后在11.3刻时间，B执行完，释放60K 的主存空间和A作业释放的15KB合并后成75KB的空闲区。

满足C和E的需求，因此C,E在11.3刻同时被装入主存。

优点：算法简单容易实现，具有一定的公平性缺点计算时间短的作业可能周转时间很长，从而增加了系统平均周转时间，降低了系统的吞吐率2、计算时间短的作业优先算法作业调度根据在输入井中的作业提出的计算时间为标准，优先选择计算时间短且资源能得到满足的作业。

由于作业是依次进入输入井的，所以该算法仍将像先来先服务算法一样，会依次把作业A,B,D先装入主存，调度进程按装入的次序让他们依次占用处理器。

【操作系统】先来先服务和短作业优先算法（C语⾔实现）【操作系统】先来先服务算法和短作业优先算法实现介绍:1.先来先服务 (FCFS: first come first service)如果早就绪的进程排在就绪队列的前⾯，迟就绪的进程排在就绪队列的后⾯，那么先来先服务(FCFS: first come first service)总是把当前处于就绪队列之⾸的那个进程调度到运⾏状态。

也就说，它只考虑进程进⼊就绪队列的先后，⽽不考虑它的下⼀个CPU周期的长短及其他因素。

FCFS算法简单易⾏，是⼀种⾮抢占式策略，但性能却不⼤好。

简单来说，先来先服务就是那个进程到达时间最早，那么CPU就先处理哪个进程。

2.短作业优先（SJF, Shortest Job First）对预计执⾏时间短的作业（进程）优先分派处理机。

通常后来的短作业不抢先正在执⾏的作业。

也就是说，不但要考虑进程的到达时间，还要考虑进程需要运⾏的时间。

当⼀个进程正在运⾏时，假如有其他的进程到达，那么这些到达的进程就需要按照其需要运⾏的时间长短排序，运⾏时间短的在前，运⾏时间长的在后。

3.例⼦：4.运⾏截图1.先来先服务2.短作业优先5.话不多说，直接上代码。

第⼀次写，有很多不⾜的地⽅。

希望⼤家看到可以帮忙纠正⼀下，谢谢⼤家。

#include <stdio.h>#include <stdlib.h>#define MAX 10typedef struct PCB {int id,arrive_time,service_time,start_time,finish_time; //进程id、到达时间、服务时间、开始时间、完成时间float zhouzhuan_time,daiquanzhouzhuan_time; //周转时间、带权周转时间。

只能说我的拼英。

emm，。

尴尬。

int status;}PCB;typedef enum {OK,ERROR}Status;typedef enum {FALSE,TRUE}Bool;typedef PCB datatype;typedef struct LinkQueue {int front;int rear;int length;datatype* base;}quene;int arrive[MAX]; // 记录每个作业的到达时间int service[MAX]; //记录每个作业的服务时间int num; //输⼊的进程个数quene init(){quene q_pcb;q_pcb.base = (datatype *)malloc(sizeof(datatype)*MAX);q_pcb.front = q_pcb.rear = 0;q_pcb.length = 0;return q_pcb;}Bool isFull(quene *q) {if ((q->rear + 1) % MAX == q->front) {return TRUE;}return FALSE;}Bool isEmpty(quene *q) {if (q->rear == q->front) {return TRUE;}return FALSE;}Status rudui(quene *q,datatype p){ //⼊队。

第一章绪论一、单项选择题1、在下列选择中，（D）不是操作系统关心的主要问题。

A、管理计算机裸机B、设计、提供用户程序计算机硬件系统的界面C、管理计算机系统资源D、高级程序设计语言的编译器2、批处理系统的主要缺点是（C）。

A、CPU利用率低B、不能并发执行C、缺少交互性D、以上都不是3、多道程序设计是指（D）。

A、在实时系统中并发运行多个程序B、在分布系统中同一时刻运行多个程序C、在一台处理器上同一时刻运行多个程序D、在一台处理器上并发运行多个程序4、以下最早的OS是（D）。

A、分布式系统B、实时系统C、分时系统D、批处理系统5、批处理OS提高了计算机系统的工作效率，但（D）。

A、不能自动选择作业执行B、无法协调资源分配C、不能缩短作业执行时间D、在作业执行时用户不能直接干预6、分时OS追求的目标是（C）。

A、高吞吐量B、充分利用内存C、快速响应D、减少系统开销7、多道批处理系统提高了计算机系统的资源利用率，同时（B）A、减少了各作业的执行时间B、增加了作业吞吐量C、减少了作业的吞吐量D、减少了部分作业的执行时间8、设计实时OS时，（B）不是主要追求目标。

A、安全可靠B、资源利用率C、及时响应D、快速处理9、现代OS的两个基本特征是（C）和资源共享。

A、多道程序设计B、中断处理C、程序的并发执行D、实现分时与时实处理10、OS中采用多道程序设计技术提高了CPU和外部设备的（A）。

A、利用率B、可靠性C、稳定性D、兼容性11、OS的基本类型有（B）A、批处理系统、分时系统及多任务系统B、实时OS、批处理OS及分时OSC、单用户系统、多用户系统及批处理系统D、实时系统、分时系统和多用户系统12、为了使系统中所有的用户都能得到及时响应，该OS应该是（B）A、多道批处理系统B、分时系统C、实时系统D、网络系统13、从下列叙述中选出正确的叙述（A）。

A、OS的不确定性是指在OS控制下的多个作业执行顺序和每个作业的执行时间是不确定的。