下载文档原格式
MINIX 操作系统的启动过程与中断机制解析公维冰朱文俊(兰州大学数学与统计学院，甘肃兰州730000)摘要：MINIX 操作系统是一个面向教学的操作系统，它是第一个将所有源代码免费对外公布的系统，它的这个优点就为我们学习操作系统提供了很大的方便，我们可以通过学习源代码来更深刻的学习操作系统的基本原理。
系统的分层式结构，实现方式虽然简单，但是却给出了操作系统最基本的实现结构。
我们这里通过解析代码来说明MINIX2.0操作系统的中断机制是如何实现的，包括硬件中断，软件中断和异常中断。
关键词：MINIX2.0操作系统中断机制硬中断软中断异常中图分类号：TP31介绍MINIX 操作系统是一种与UNIX 操作系统兼容的小型操作系统，它最早是由计算机科学教育家的Tanenbaum 开发的。
与UNIX 相比，MINIX 的小巧和高度的模块化使其非常适合于操作系统教程，而其源代码的公开性又为操作系统研究者提供了极大的方便。
现在流行的LINUX 操作系统就是在开放的MINIX 操作系统基础上发展起来的。
在MINIX 操作系统家族中，MINIX1.0的设计基于UNIX V7标准，而MINIX2.0的设计则基于POSIX 标准，现己升级到了MINIX3。
我们将在第二节介绍MINIX2.0操作系统的整体结构，第三节是MINIX2.0操作系统的启动过程，第四节介绍MINIX2.0操作系统的中断机制，包括硬件中断机制，软件中断机制和异常机制，第五节我们给出结论。
2MINIX2.0操作系统的整体结构MINIX2.0操作系统整体实行分层结构，如下所示：第四层：用户进程层init 进程编译器编辑器其它用户进程第三层：服务器进程层内存管理器(mm)文件系统服务器(fs)网络服务器(nets)第二层：I/O 驱动任务层内存管理驱动硬盘驱动终端驱动时钟任务其它驱动任务第一层：操作系统最底层操作系统的启动，中断处理，进程调度等以上各层中层数越低就越底层，其中低层是高层的基础，高层依赖低层实现更高级和更复杂的功能。
进程调度算法代码进程调度算法是操作系统中的一种重要机制，它决定了在多道程序环境下，如何安排各个进程的执行顺序和时间片。
不同的进程调度算法有不同的实现方式和优缺点，本文将就常见的几种进程调度算法进行详细介绍。
1. 先来先服务（FCFS）先来先服务是最简单、最直观的进程调度算法。
它按照进程到达时间的先后顺序进行调度，即先到达的进程先执行。
当一个进程开始执行后，直到该进程执行完毕或者发生某些阻塞事件才会切换到另一个进程。
FCFS算法代码如下：```void FCFS(){int i;for(i=0;i<n;i++){run(p[i].need_time);if(i!=n-1){wait(p[i+1].arrive_time-p[i].arrive_time-p[i].need_time); }}}```其中，p数组表示所有需要执行的进程，n表示总共有多少个需要执行的进程。
run函数表示运行该进程所需时间片，wait函数表示等待下一个进程到达所需时间。
FCFS算法优点是简单易懂、公平性好，但其缺点也很明显：无法处理短作业优先问题、平均等待时间长等。
2. 短作业优先（SJF）短作业优先是一种非抢占式的进程调度算法，它根据每个进程的执行时间来进行排序，执行时间短的进程先执行。
如果有多个进程的执行时间相同，则按照到达时间的先后顺序进行调度。
SJF算法代码如下：```void SJF(){int i,j;for(i=0;i<n;i++){for(j=i+1;j<n;j++){if(p[i].need_time>p[j].need_time){swap(p[i],p[j]);}}}for(i=0;i<n;i++){run(p[i].need_time);if(i!=n-1){wait(p[i+1].arrive_time-p[i].arrive_time-p[i].need_time); }}}```其中，swap函数表示交换两个进程的位置。
操作系统进程调度C语言代码#include <stdio.h>#define MAX 20//进程控制块typedef struct PCBchar name[10]; // 进程名int AT; // 到达时间int BT; // 服务时间int Pri; // 优先数int FT; // 完成时间int WT; //等待时间int RT; // 响应时间int position; // 第几号进程int flag; // 用来判断进程是否执行过}PCB;//进程调度void schedule(PCB a[], int n, int alg)int i, j, k, flag, temp;int count = 0;int pri_max = 0;float ATAT = 0.0;float AWT = 0.0;float ART = 0.0;PCBt;//各种算法的调度if (alg == 1)printf("采用先来先服务调度：\n"); //根据到达时间执行for (i = 0; i < n; i++)for (j = i + 1; j < n; j++)if (a[i].AT > a[j].AT)t=a[i];a[i]=a[j];a[j]=t;}//按到达时间依次执行for (i = 0; count != n; i++)for (j = 0; j < n; j++)//查找第一个到达时间小于等于当前时间的进程if (a[j].AT <= i && a[j].flag == 0)//记录运行时间a[j].BT--;//如果运行完成，记录完成时间、等待时间、响应时间if (a[j].BT == 0)a[j].FT=i+1;a[j].WT = a[j].FT - a[j].AT - a[j].Pri;a[j].RT=a[j].WT;a[j].flag = 1;count++;}elsebreak;}}}else if (alg == 2)printf("采用最短服务时间优先（非抢占）调度：\n");for (i = 0; count != n; i++)//找出服务时间最短的进程，并将其放置到最前面for (j = 0; j < n; j++)。
第1篇一、实验目的通过本次实验，加深对操作系统进程调度原理的理解，掌握先来先服务（FCFS）、时间片轮转（RR）和动态优先级（DP）三种常见调度算法的实现，并能够分析这些算法的优缺点，提高程序设计能力。
二、实验环境- 编程语言：C语言- 操作系统：Linux- 编译器：GCC三、实验内容本实验主要实现以下内容：1. 定义进程控制块（PCB）结构体，包含进程名、到达时间、服务时间、优先级、状态等信息。
2. 实现三种调度算法：FCFS、RR和DP。
3. 创建一个进程队列，用于存储所有进程。
4. 实现调度函数，根据所选算法选择下一个执行的进程。
5. 模拟进程执行过程，打印进程执行状态和就绪队列。
四、实验步骤1. 定义PCB结构体：```ctypedef struct PCB {char processName[10];int arrivalTime;int serviceTime;int priority;int usedTime;int state; // 0: 等待，1: 运行，2: 完成} PCB;```2. 创建进程队列：```cPCB processes[MAX_PROCESSES]; // 假设最多有MAX_PROCESSES个进程int processCount = 0; // 实际进程数量```3. 实现三种调度算法：（1）FCFS调度算法：```cvoid fcfsScheduling() {int i, j;for (i = 0; i < processCount; i++) {processes[i].state = 1; // 设置为运行状态printf("正在运行进程：%s\n", processes[i].processName); processes[i].usedTime++;if (processes[i].usedTime == processes[i].serviceTime) { processes[i].state = 2; // 设置为完成状态printf("进程：%s 完成\n", processes[i].processName); }for (j = i + 1; j < processCount; j++) {processes[j].arrivalTime--;}}}```（2）RR调度算法：```cvoid rrScheduling() {int i, j, quantum = 1; // 时间片for (i = 0; i < processCount; i++) {processes[i].state = 1; // 设置为运行状态printf("正在运行进程：%s\n", processes[i].processName); processes[i].usedTime++;processes[i].serviceTime--;if (processes[i].serviceTime <= 0) {processes[i].state = 2; // 设置为完成状态printf("进程：%s 完成\n", processes[i].processName); } else {processes[i].arrivalTime++;}for (j = i + 1; j < processCount; j++) {processes[j].arrivalTime--;}}}```（3）DP调度算法：```cvoid dpScheduling() {int i, j, minPriority = MAX_PRIORITY;int minIndex = -1;for (i = 0; i < processCount; i++) {if (processes[i].arrivalTime <= 0 && processes[i].priority < minPriority) {minPriority = processes[i].priority;minIndex = i;}}if (minIndex != -1) {processes[minIndex].state = 1; // 设置为运行状态printf("正在运行进程：%s\n", processes[minIndex].processName);processes[minIndex].usedTime++;processes[minIndex].priority--;processes[minIndex].serviceTime--;if (processes[minIndex].serviceTime <= 0) {processes[minIndex].state = 2; // 设置为完成状态printf("进程：%s 完成\n", processes[minIndex].processName); }}}```4. 模拟进程执行过程：```cvoid simulateProcess() {printf("请选择调度算法（1：FCFS，2：RR，3：DP）：");int choice;scanf("%d", &choice);switch (choice) {case 1:fcfsScheduling();break;case 2:rrScheduling();break;case 3:dpScheduling();break;default:printf("无效的调度算法选择。
Minix进程实现2.5～2.6概述：本部分内容主要从两个部分介绍进程在Minix中的实现的：第一部分是介绍整个Minix的系统结构的，其中包括了Minix的内部结构以及各种头文件，其主要是对于各个头文件以及进程有关的数据结构的介绍的；第二部分讲的是Minix中进程的实现，其中包括Minix的系统初始化、中断处理、进程间的通信和进程调度。
Minix系统结构介绍：包括Minix内部结构以及各种头文件。
Minix内部四层结构最底层捕获所有的中断和陷入，完成进程调度，并向高层提供一个采用消息进行通信的独立顺序进程模型。
包含完成以下功能的函数：系统初始化、中断、消息传递以及进程调度。
第二层包括了I/O进程，每类设备都有一个I/O进程，我们称之为任务（task）。
只有一个任务，即系统任务与众不同，它不对应于任何I/O设备。
第三层包含向用户进程提供有用服务的进程。
这些服务器进程在低于内核和任务的特权级上运行，不能直接访问I/O端口，也不能访问属于自己段以外的内存。
第四层包含了所有的用户进程——shell、编译器、编辑器以及用户的a.out 程序。
Minix四层结构之间的联系：操作系统主要完成的两件事情：管理资源和通过系统调用方式提供扩展的计算机。
其中，资源管理主要是在内核（第一、二层）完成的，系统调用的解释在第三层。
第三层的各种服务进程被单独的设计成“服务器”，这样可以增加整个系统的可扩展性。
如果要是加入一个新的服务器进程，需要重新编译内核。
Minix源代码的组织源代码从逻辑上分成两个目录：/usr/include/和/usr/src/，记做：include/和/src/。
include/目录包含了许多符合POSIX标准的头文件，它又包含了三个子目录：1.sys/ 包含POSIX头文件2.minix/ 包含操作系统使用的头文件3.ibm/ 包含IBMPC特有定义的头文件。
src/目录包含了三个重要的子目录，其中包括了操作系统的源代码1.kernel/ 第一层和第二层的（进程、消息和驱动程序）2.mm/ 内存管理器代码3.fs/ 文件系统代码公共头文件其中，编译用户程序时可能用到的头文件放在include/目录下，而传统上include/sys/目录放那些编译系统程序和程序所用的头文件。
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分配给下一个进程。
操作系统五种进程调度算法的代码一、先来先服务（FCFS）调度算法先来先服务（FCFS）调度算法是操作系统处理进程调度时比较常用的算法，它的基本思想是按照进程的提交时间的先后顺序依次调度进程，新提交的进程会在当前运行进程之后排队，下面通过C语言代码来实现先来先服务（FCFS）调度算法：#include <stdio.h>#include <stdlib.h>//定义进程的数据结构struct Processint pid; // 进程标识符int at; // 到达时间int bt; // 执行时间};//进程调度函数void fcfs_schedule(struct Process *processes, int n)int i, j;//根据进程的到达时间排序for(i = 0; i < n; i++)for(j = i+1; j < n; j++)if(processes[i].at > processes[j].at) struct Process temp = processes[i]; processes[i] = processes[j];processes[j] = temp;//获取各个进程执行完毕的时间int ct[n];ct[0] = processes[0].at + processes[0].bt; for(i = 1; i < n; i++)if(ct[i-1] > processes[i].at)ct[i] = ct[i-1] + processes[i].bt;elsect[i] = processes[i].at + processes[i].bt; //计算各个进程的周转时间和带权周转时间int tat[n], wt[n], wt_r[n];for(i = 0; i < n; i++)tat[i] = ct[i] - processes[i].at;wt[i] = tat[i] - processes[i].bt;wt_r[i] = wt[i] / processes[i].bt;printf("P%d:\tAT=%d\tBT=%d\tCT=%d\tTAT=%d\tWT=%d\tWT_R=%f\n", processes[i].pid, processes[i].at, processes[i].bt, ct[i], tat[i], wt[i], wt_r[i]);//主函数int mainstruct Process processes[] ={1,0,3},{2,3,5},{3,4,6},{4,5,2},{5,6,4}};fcfs_schedule(processes, 5);return 0;输出：。
进程调度算法模拟程序设计引言进程调度算法是操作系统中的重要组成部分，它决定了进程在系统中的执行顺序和分配时间片的策略。
为了更好地理解和研究不同的进程调度算法，我们可以设计一个模拟程序来模拟进程的调度过程。
本文将介绍进程调度算法的基本概念和常见的调度算法，并详细讨论如何设计一个进程调度算法模拟程序。
什么是进程调度算法进程调度算法是操作系统中的一种策略，用于决定在多个进程同时请求执行时，系统按照什么样的顺序来选择并分配CPU资源。
进程调度算法的目标是尽可能地提高系统的吞吐量、响应时间和公平性。
常见的进程调度算法先来先服务（FCFS）先来先服务是最简单的进程调度算法，它按照进程到达的先后顺序进行调度。
当一个进程到达系统后，它会被放入就绪队列中，然后按照先后顺序执行。
这种算法的优点是简单易懂，但是存在”饥饿”问题，即长作业会占用CPU资源，导致其他短作业等待时间过长。
短作业优先（SJF）短作业优先算法是根据进程的执行时间来进行调度的。
当一个进程到达系统后，系统会根据其执行时间将其放入适当的位置，执行时间短的进程优先执行。
这种算法可以最大限度地减少平均等待时间，但是对于长作业来说可能会饥饿。
时间片轮转（RR）时间片轮转算法是一种分时调度算法，它将CPU的执行时间划分为多个时间片，每个进程在一个时间片内执行一定的时间，然后切换到下一个进程。
这种算法可以保证所有进程都有机会执行，并且对于响应时间要求较高的任务比较合适。
多级反馈队列（MFQ）多级反馈队列算法是一种综合了FCFS和RR的调度算法。
系统将进程根据优先级划分为多个队列，每个队列都有不同的时间片大小。
当一个进程到达系统后，它被放入第一个队列中，如果在时间片内没有执行完，则被移到下一个队列中。
这种算法可以根据进程的优先级和执行时间动态调整调度策略，提高系统的响应性能。
进程调度算法模拟程序设计程序结构为了设计一个进程调度算法模拟程序，我们需要考虑以下几个方面的内容：1.进程的数据结构：我们可以使用一个进程控制块（PCB）来表示一个进程，PCB包含了进程的状态、优先级、执行时间等信息。
进程调度算法的模拟实现⏹实验目的1．本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。
2．利用程序设计语言编写算法，模拟实现先到先服务算法FCFS、轮转调度算法RR、最短作业优先算法SJF、优先级调度算法PRIOR、最短剩余时间优先算法SRTF。
3．进行算法评价，计算平均等待时间和平均周转时间。
⏹实验内容及结果1．先来先服务算法2．轮转调度算法3. 优先级调度算法4. 最短时间优先算法5. 最短剩余时间优先算法⏹实验总结在此次模拟过程中，将SRTF单独拿了出来用指针表示，而其余均用数组表示。
⏹完整代码【Srtf.cpp代码如下：】//最短剩余时间优先算法的实现#include<stdio.h>#include<stdlib.h>#include<time.h>typedefstruct{int remain_time;//进程剩余执行时间int arrive_time;//进程到达时间int Tp;//进入就绪队列的时间int Tc;//进入执行队列的时间int To;//进程执行结束的时间int number;//进程编号}Process_Block;//定义进程模块typedefstruct _Queue{Process_Block PB;struct _Queue *next;}_Block,*Process;//定义一个进程模块队列中结点typedefstruct{Process head;//队列头指针Process end;//队列尾指针}Process_Queue;//进程队列Process_Queue PQ;//定义一个全局队列变量int t;//全局时间Process Run_Now;//当前正在运行的进程，作为全局变量void InitQueue(Process_Queue PQ){PQ.head ->next = NULL;PQ.end ->next = PQ.head;}/*初始化队列*/int IsEmpty(Process_Queue PQ){if(PQ.end->next == PQ.head)return 1;//队列空的条件为头指针指向尾指针并且尾指针指向头指针elsereturn 0;}/*判定队列是否为空队列*/void EnQueue(Process_Queue PQ,Process P){Process temp =(Process)malloc(sizeof(_Block));temp = PQ.end;temp->next->next = P;PQ.end->next = P;}/*插入队列操作*/Process DeQueue(Process_Queue PQ){if(IsEmpty(PQ))return NULL;Process temp = PQ.head->next;PQ.head->next= temp ->next;if(PQ.end->next == temp)PQ.end->next = PQ.head;return temp;}/*出列操作*/Process ShortestProcess(Process_Queue PQ){if(IsEmpty(PQ))//如果队列为空，返回{if(!Run_Now)return NULL;elsereturn Run_Now;}Process temp,shortest,prev;int min_time;if(Run_Now)//如果当前有进程正在执行，{shortest = Run_Now;//那么最短进程初始化为当前正在执行的进程，min_time = Run_Now->PB.remain_time;}else//如果当前没有进程执行，{shortest = PQ.head->next;//则最短进程初始化为队列中第一个进程min_time = PQ.head->next->PB.remain_time;}temp = PQ.head;prev = temp;while(temp->next){if(temp->next->PB.remain_time <min_time)//如果当前进程的剩余时间比min_time短，{shortest = temp->next;//则保存当前进程，min_time = shortest->PB.remain_time;prev=temp;//及其前驱}temp=temp->next;}if(shortest == PQ.end->next)//如果最短剩余时间进程是队列中最后一个进程，PQ.end->next = prev;//则需要修改尾指针指向其前驱prev->next = shortest->next;//修改指针将最短剩余时间进程插入到队头return shortest;}/*调度最短剩余时间的进程至队头*/void Run(){Run_Now->PB.remain_time--;//某一时间运行它的剩余时间减return;}/*运行函数*/void Wait(){return ;}int sum(intarray[],int n){int i,sum=0;for(i=0;i<n;i++)sum+=array[i];return sum;}int main(){PQ.head = (Process)malloc(sizeof(_Block));PQ.end = (Process)malloc(sizeof(_Block));Run_Now = (Process)malloc(sizeof(_Block));Run_Now =NULL;InitQueue(PQ);int i,N,Total_Time=0;//Total_Time为所有进程的执行时间之和printf("请输入计算机中的进程数目:\n");scanf("%d",&N);Process *P,temp;P = (Process*)malloc(N*sizeof(Process));int *wt,*circle_t;wt =(int*)malloc(N*sizeof(int));circle_t =(int*)malloc(N*sizeof(int));for(i=0;i<N;i++){P[i] = (Process)malloc(sizeof(_Block));P[i]->PB.number =i+1;P[i]->next =NULL;wt[i] =0;circle_t[i] =0;printf("输入第%d个进程的到达时间及剩余执行时间:\n",i+1);scanf("%d %d",&P[i]->PB.arrive_time,&P[i]->PB.remain_time);}for(i=0;i<N;i++)Total_Time+=P[i]->PB.remain_time;printf("\n进程按顺序运行依次为:\n");i=0;int k=0;for(t=0;;t++){if(Run_Now)//如果当前有进程正在执行{Run();if(t == P[i]->PB.arrive_time)//如果当前时间正好有进程进入{if(P[i]->PB.remain_time < Run_Now->PB.remain_time){temp = P[i];P[i] = Run_Now;Run_Now = temp;//则调度它至运行队列中，Run_Now->PB.Tp=t;Run_Now->PB.Tc=t;wt[Run_Now->PB.number-1]+=Run_Now->PB.Tc-Run_Now->PB.Tp;printf("%d ",Run_Now->PB.number);}EnQueue(PQ,P[i]);//并将当前运行进程重新插入队列中P[i]->PB.Tp=t;k++;i=(i+1)>(N-1)?(N-1):(i+1);}if(Run_Now->PB.remain_time == 0)//如果当前进程运行结束，{Run_Now->PB.To=t;//进程运行结束的时间circle_t[Run_Now->PB.number-1] +=t-Run_Now->PB.arrive_time;free(Run_Now);//则将它所占资源释放掉，Run_Now =NULL;//并修改Run_Now为NULLRun_Now = ShortestProcess(PQ);//从就绪队列中调出最短剩余时间进程至队头，if(!Run_Now)//如果队列为空，转为等待状态{if(IsEmpty(PQ) && k >= N) break;Wait();continue;}else{Run_Now->PB.Tc=t;wt[Run_Now->PB.number-1]+=Run_Now->PB.Tc-Run_Now->PB.Tp;printf("%d ",Run_Now->PB.number);}}}else//如果当前运行进程为空，那么{if(t == P[i]->PB.arrive_time)//如果正好这时有进程入队{k++;EnQueue(PQ,P[i]);Run_Now = DeQueue(PQ);//则直接被调入运行队列中Run_Now->PB.Tp=t;Run_Now->PB.Tc=t;printf("%d ",Run_Now->PB.number);i=(i+1)>(N-1)?(N-1):(i+1);}else{Wait();continue;}}}printf("\n");printf("平均等待时间是:\n%f\n",((float)sum(wt,N))/N);printf("平均周转时间是:\n%f\n",((float)sum(circle_t,N))/N);return 0;}//////////////////////////////////////////////////////【Process.cpp代码如下：】#include<iostream>#include<string>usingnamespace std;class Process{public:string ProcessName; // 进程名字int Time; // 进程需要时间int leval; // 进程优先级int LeftTime; // 进程运行一段时间后还需要的时间};void Copy ( Process proc1, Process proc2); // 把proc2赋值给proc1void Sort( Process pr[], int size) ; // 此排序后按优先级从大到小排列void sort1(Process pr[], int size) ; // 此排序后按需要的cpu时间从小到大排列void Fcfs( Process pr[], int num, int Timepice); // 先来先服务算法void TimeTurn( Process process[], int num, int Timepice); // 时间片轮转算法void Priority( Process process[], int num, int Timepice); // 优先级算法void main(){int a;cout<<endl;cout<<" 选择调度算法："<<endl;cout<<" 1: FCFS 2: 时间片轮换3: 优先级调度4: 最短作业优先5: 最短剩余时间优先"<<endl; cin>>a;constint Size =30;Process process[Size] ;int num;int TimePice;cout<<" 输入进程个数:"<<endl;cin>>num;cout<<" 输入此进程时间片大小: "<<endl;cin>>TimePice;for( int i=0; i< num; i++){string name;int CpuTime;int Leval;cout<<" 输入第"<< i+1<<" 个进程的名字、cpu时间和优先级:"<<endl;cin>>name;cin>> CpuTime>>Leval;process[i].ProcessName =name;process[i].Time =CpuTime;process[i].leval =Leval;cout<<endl;}for ( int k=0;k<num;k++)process[k].LeftTime=process[k].Time ;//对进程剩余时间初始化cout<<" ( 说明: 在本程序所列进程信息中，优先级一项是指进程运行后的优先级!! )";cout<<endl; cout<<endl;cout<<"进程名字"<<"共需占用CPU时间"<<" 还需要占用时间"<<" 优先级"<<" 状态"<<endl; if(a==1)Fcfs(process,num,TimePice);elseif(a==2)TimeTurn( process, num, TimePice);elseif(a==3){Sort( process, num);Priority( process , num, TimePice);}else// 最短作业算法，先按时间从小到大排序，再调用Fcfs算法即可{sort1(process,num);Fcfs(process,num,TimePice);}}void Copy ( Process proc1, Process proc2){proc1.leval =proc2.leval ;proc1.ProcessName =proc2.ProcessName ;proc1.Time =proc2.Time ;}void Sort( Process pr[], int size) //以进程优先级高低排序{// 直接插入排序for( int i=1;i<size;i++){Process temp;temp = pr[i];int j=i;while(j>0 && temp.leval<pr[j-1].leval){pr[j] = pr[j-1];j--;}pr[j] = temp;} // 直接插入排序后进程按优先级从小到大排列for( int d=size-1;d>size/2;d--){Process temp;temp=pr [d];pr [d] = pr [size-d-1];pr [size-d-1]=temp;} // 此排序后按优先级从大到小排列}/*最短作业优先算法的实现*/void sort1 ( Process pr[], int size) // 以进程时间从低到高排序{// 直接插入排序for( int i=1;i<size;i++){Process temp;temp = pr[i];int j=i;while(j>0 && temp.Time < pr[j-1].Time ){pr[j] = pr[j-1];j--;}pr[j] = temp;}}/*先来先服务算法的实现*/void Fcfs( Process process[], int num, int Timepice){ // process[] 是输入的进程，num是进程的数目，Timepice是时间片大小while(true){if(num==0){cout<<" 所有进程都已经执行完毕!"<<endl;exit(1);}if(process[0].LeftTime==0){cout<<" 进程"<<process[0].ProcessName<< " 已经执行完毕!"<<endl;for (int i=0;i<num;i++)process[i]=process[i+1];num--;}elseif(process[num-1].LeftTime==0){cout<<" 进程"<<process[num-1].ProcessName<< " 已经执行完毕!"<<endl;num--;}else{cout<<endl; //输出正在运行的进程process[0].LeftTime=process[0].LeftTime- Timepice;process[0].leval =process[0].leval-1;cout<<" "<<process[0].ProcessName <<" "<<process[0].Time <<"";cout<<process[0].LeftTime <<" "<<process[0].leval<<" 运行";cout<<endl;for(int s=1;s<num;s++){cout<<" "<<process[s].ProcessName <<" "<<process[s].Time <<"";cout<<process[s].LeftTime <<" "<<process[s].leval<<" 等待"<<endl; ;}} // elsecout<<endl;system(" pause");cout<<endl;} // while}/*时间片轮转调度算法实现*/void TimeTurn( Process process[], int num, int Timepice){while(true){if(num==0){cout<<" 所有进程都已经执行完毕!"<<endl;exit(1);}if(process[0].LeftTime==0){cout<<" 进程"<<process[0].ProcessName<< " 已经执行完毕!"<<endl;for (int i=0;i<num;i++)process[i]=process[i+1];num--;}if( process[num-1].LeftTime ==0 ){cout<<" 进程" << process[num-1].ProcessName <<" 已经执行完毕! "<<endl;num--;}elseif(process[0].LeftTime > 0){cout<<endl; //输出正在运行的进程process[0].LeftTime=process[0].LeftTime- Timepice;process[0].leval =process[0].leval-1;cout<<" "<<process[0].ProcessName <<" "<<process[0].Time <<"";cout<<process[0].LeftTime <<" "<<process[0].leval<<" 运行";cout<<endl;for(int s=1;s<num;s++){cout<<" "<<process[s].ProcessName <<" "<<process[s].Time <<"";cout<<process[s].LeftTime <<" "<<process[s].leval;if(s==1)cout<<" 就绪"<<endl;elsecout<<" 等待"<<endl;}Process temp;temp = process[0];for( int j=0;j<num;j++)process[j] = process[j+1];process[num-1] = temp;} // elsecout<<endl;system(" pause");cout<<endl;} // while}/*优先级调度算法的实现*/void Priority( Process process[], int num, int Timepice){while( true){if(num==0){cout<< "所有进程都已经执行完毕!"<<endl;exit(1);}if(process[0].LeftTime==0){cout<<" 进程" << process[0].ProcessName <<" 已经执行完毕! "<<endl;for( int m=0;m<num;m++)process[m] = process[m+1]; //一个进程执行完毕后从数组中删除num--; // 此时进程数目减少一个}if( num!=1 && process[num-1].LeftTime ==0 ){cout<<" 进程" << process[num-1].ProcessName <<" 已经执行完毕! "<<endl;num--;}if(process[0].LeftTime > 0){cout<<endl; //输出正在运行的进程process[0].LeftTime=process[0].LeftTime- Timepice;process[0].leval =process[0].leval-1;cout<<" "<<process[0].ProcessName <<" "<<process[0].Time <<"";cout<<process[0].LeftTime <<" "<<process[0].leval<<" 运行";cout<<endl; // 输出其他进程for(int s=1;s<num;s++){cout<<" "<<process[s].ProcessName <<" "<<process[s].Time <<" ";cout<<process[s].LeftTime <<" "<<process[s].leval ; if(s==1)cout<<" 就绪"<<endl;elsecout<<" 等待"<<endl;}} // elseSort(process, num);cout<<endl;system(" pause");cout<<endl;} // while}。
1.Minix3中为每个进程分配的时间片，当进程的时间片用完后，将进行进程调度。
进程的时间片以时钟滴答为单位进行分配。
每次时钟中断，中断处理程序将减少当前进程的时间片。
当时间片减小到0时，进行进程调度，选择一个合适的进程来拥有CPU。
Minix3以每秒钟60次的频率进行时钟中断，即时钟中断处理程序每秒执行60次。
每次执行，减少当前进程的时间片：/* Get number of ticks and update realtime. */ticks = lost_ticks + 1; /* lost_ticks为BIOS中断所花费的时间 */lost_ticks = 0; /* lost_ticks清0 */realtime += ticks; /* 更新时间 */proc_ptr->p_user_time += ticks; /* 更新当前进程的user_time */if (priv(proc_ptr)->s_flags & PREEMPTIBLE) {/* 如果进程可被抢占，则减少时间片 */proc_ptr->p_ticks_left -= ticks;}if (! (priv(proc_ptr)->s_flags & BILLABLE)) {/* 如果当前进程能付费，则修改sys_time及减少时间片 */bill_ptr->p_sys_time += ticks;bill_ptr->p_ticks_left -= ticks;}如果时间片用完，则向clock_task发送通知。
因为该进程的时间片用完，需要重新调度，所以该进程就成为了上一个执行的进程。
if((next_timeout <= realtime)||(proc_ptr->p_ticks_left<= 0)) { /* 如果定时器到期或者进程时间片用完，则进行调度 */prev_ptr = proc_ptr; /* 当前进程成为上一次执行的进程 */lock_notify(HARDWARE, CLOCK); /* send notification */ /* 时间到期时发送通知给clock_task，由该函数进行后续处理 */}2.clock_task为时钟任务的主程序，用一个无限循环等待并处理时钟中断处理程序发来的通知。
没有通知发来时，处于阻塞状态。
while (TRUE) {/* 获取消息 */receive(ANY, &m); /* 无消息时则阻塞 *//* 检查消息类型，只处理时钟中断处理程序发来的消息 */switch (m.m_type) {case HARD_INT:/* 这个消息由时钟中断处理程序(clock_handler)发出 */result = do_clocktick(&m); /* 处理该消息,检查时间片是否到期等 */break; /* result变量没有实际意义 */default: /* illegal request type */kprintf("CLOCK:illegal request %d from %d.\n", m.m_type,m.m_source);}}3.当通过消息检查后，调用do_clocktick函数处理该消息。
首先，检查是否是进程的时间片到期。
如果时间片到期，则重置该进程的时间片，并插入到就绪队列的适当位置。
将进程移出、移入就绪队列，就能完成为进程重新分配时间片和插入适当位置的任务。
if(prev_ptr->p_ticks_left<=0 && priv(prev_ptr)->s_flags & PREEMPTIBLE) { lock_dequeue(prev_ptr); /* 将进程移出队列 */lock_enqueue(prev_ptr); /* 在将进程移入队列 */}lock_dequeue函数将屏蔽中断，然后调用函数dequeue将进程移出就绪队列。
而函数lock_enqueue同样将屏蔽中断，然后调用函数enqueue。
下面详细讨论enqueue 函数。
4.enqueue首先调用函数sched，计算函数的优先级和应分配的时间片。
如果该进程为前一次运行过的进程，即进程连续运行过两次，则降低进程的优先级。
否则该进程可能无限期的占用CPU。
if ( ! time_left) { /* 时间片是否用完 */rp->p_ticks_left = rp->p_quantum_size; /* 分配完整的时间片？ */if (prev_ptr == rp) penalty ++; /* 是否要降低进程优先级？ */else penalty --; /* 进程都没执行过，则增加进程的优先级 */ prev_ptr = rp; /* 该进程刚运行过 */}接下来，确定进程的优先级。
Minix3中，共有16个优先级队列，最高为0，最低为15。
进程优先级最大为其规定的优先级，最小不能小于IDLE进程的优先级，即最小为14。
if (penalty != 0 && ! iskernelp(rp)) {/* 惩罚值不为0，且该进程不是内核进程 */ rp->p_priority += penalty; /* 根据惩罚值，确定新的优先级 */if (rp->p_priority < rp->p_max_priority) /* 最大为规定的最大优先级*/ rp->p_priority=rp->p_max_priority;else if (rp->p_priority > IDLE_Q-1) /* 不能小于IDLE的优先级 */ rp->p_priority = IDLE_Q-1;}最后，返回进程的优先级。
*queue = rp->p_priority;当进程的时间片未用完，则进程插入队列头部。
用完则插入队列尾部。
时间片未用完的原因有：1.其要求的定时器到期；2.进程请求了I/O操作而被阻塞。
5.进程优先级确定后，就将其插入对应的优先级队列。
这16个队列分别由rdy_head 数组指向每个队列的头和 rdy_tail数组指向每个队列的尾。
if (rdy_head[q] == NIL_PROC) { /* 如果队列为空 */rdy_head[q] = rdy_tail[q] = rp; /* create a new queue */rp->p_nextready = NIL_PROC; /* mark new end */}else if (front) { /* 队列非空，且插入头部。
即时间片未用完 */rp->p_nextready = rdy_head[q]; /* chain head of queue */rdy_head[q] = rp; /* set new queue head */}else { /* 插入队列尾部，即时间片用完 */rdy_tail[q]->p_nextready = rp; /* chain tail of queue */rdy_tail[q] = rp; /* set new queue tail */rp->p_nextready = NIL_PROC; /* mark new end */}6.最后，调用函数pick_proc选择一个优先级最高的进程来拥有CPU。
从16个队列中，从最高的优先级队列开始，选择队头的进程来占有CPU。
for (q=0; q < NR_SCHED_QUEUES; q++) {if ( (rp = rdy_head[q]) != NIL_PROC) {next_ptr = rp; /* run process 'rp' next */if (priv(rp)->s_flags & BILLABLE)bill_ptr = rp; /* bill for system time */return;}}最后，即将要运行的进程由next_ptr指针指示。
7.enqueue函数结束后，将返回到函数lock_enqueue。
接着lock_enqueue将开中断，在中断处理函数运行完之后，内核跳转到_restart处继续执行来完成进程的切换：save:cld ! set direction flag to a known valuepushad ! 保存通用寄存器o16 push ds ! save dso16 push es ! save eso16 push fs ! save fso16 push gs ! save gsmov dx, ss ! ss is kernel data segmentmov ds, dx ! load rest of kernel segmentsmov es, dx ! kernel does not use fs, gsmov eax, esp ! prepare to returnincb (_k_reenter) ! from -1 if not reenteringjnz set_restart1 ! 是否已经是内核堆栈，该情况发生在响应异常时mov esp, k_stktop ! 切换内核堆栈push _restart ! 中断处理完成后的返回地址入栈，即中断完成后转restart进行调度xor ebp, ebp ! for stacktracejmp RETADR-P_STACKBASE(eax) ! 返回到中断处理程序.align 4set_restart1: ! 检查到异常时，才会执行到此处push restart1jmp RETADR-P_STACKBASE(eax)上面的汇编代码是处理中断前保存现场信息的代码，其中在栈中压入了中断完成后的返回地址_restrart。
当中断处理完成后，将转入_restart代码启动一个进程。
_restart:! Restart the current process or the next process if it is set.cmp (_next_ptr), 0 ! 是否有其他进程被调度,pick_proc函数已经选择了一个进程! 所以next_ptr不为0jz 0f ! 如果没有调度其他进程，进继续执行前一个进程mov e ax, (_next_ptr)mov (_proc_ptr), eax ! 调度新进程，proc_ptr = next_ptrmov (_next_ptr), 0 ! next_ptr清00: mov esp, (_proc_ptr) ! will assume P_STACKBASE == 0lldt P_LDT_SEL(esp) ! 装入新进程的局部描述符表(LDT)lea eax, P_STACKTOP(esp) ! 下一次中断的临时堆栈将建立在这地址之后mov (_tss+TSS3_S_SP0), eax ! 将地址保存在TSS中restart1: ! 发生异常时从此处开始执行decb (_k_reenter)o16 pop gso16 pop fso16 pop eso16 pop dspopadadd esp, 4 ! skip return adriretd ! continue process下次中断的临时堆栈将建立在进程结构的stackframe_p结构的后面，硬件将保证临时堆栈不会溢出。
