模拟在单处理器多进程操作系统的CPU调度。本实验为模拟实验，不要求实现真正的进程创建与进程调度。主要实现各种调度算法。

进程PCB结构：标识符、进程名称、到达时间、服务时间、剩余运行时间、已使用时间、进程状态。其中进程状态有三种：就绪R，运行E，结束F。

剩余运行时间和已使用时间两个属性用于时间片轮转算法和多级反馈队列算法。进程每使用完一个时间片，已使用时间就会增加一个时间片的长度，剩余运行时间=服务时间 – 已使用时间。

仅完成了先来先服务算法的调度和短作业优先算法：

在linux中因缺少conio包无法运行，可自行修改后 就能运行。我在VC++软件中运行如下代码：

#include "stdio.h"
#include<stdlib.h>
#include<conio.h>
#include<time.h>
#include<string.h>
#include <iostream.h>
#define getpch(type) (type*)malloc(sizeof(type))
typedef struct pcb PCB;

//定义进程控制块的PDB
struct pcb{

	int id; 	//标识符

	char name[10];	//名称

	int time_start;	//到达时间

	int time_need;	//服务时间
	
	int time_left;//剩余运行时间

	int time_used;	//已使用的CPU时间

	char state;	//进程状态
};

//系统函数

//停顿几秒
void _sleep(int n){
	clock_t goal;
	goal = (clock_t)n * CLOCKS_PER_SEC + clock();
	while(goal>clock());
}

//按任意键继续
char _keygo(){
	char c;
	printf("按任意键继续.......\n");
	c = getch();
	return c;
}

///用户函数///

//数据设置区域



int time_unit = 2;//时间片长度

const maxnum = 10;//最大进程数量

int num = 5;//实际进程数量
PCB pcbdata[maxnum] = {
	{1000,"A",0,4,4,0,'R'},
	{1001,"B",2,5,3,0,'R'},
	{1002,"C",5,3,5,0,'R'},
	{1003,"D",4,2,2,0,'R'},
	{1004,"E",1,1,4,0,'R'},

};

//就绪队列，存放进程的pcb
int ready[maxnum];
//记录排序使用哪个数值作为排序对象
int order[maxnum];

//手工输入数据
void input(){
	int i;
	printf("进程总数为：");
	scanf("%d",&num);
	for(i = 0; i< num; i++){
		//系统自动分配标识符
		pcbdata[i].id = 1000 + i;
		printf("输入第%d个进程名：",i+1);
		scanf("%s",&pcbdata[i].name);
		printf("输入第%d个进程达到时间：",i+1);
		scanf("%s",&pcbdata[i].time_start);
		printf("输入第%d个进程服务时间：",i+1);
		scanf("%s",&pcbdata[i].time_need);
	
		pcbdata[i].time_left = pcbdata[i].time_need;	//剩余运行时间，初始值和服务时间相同
		printf("\n");
		
		pcbdata[i].time_used = 0;//已使用CPU时间初始值为0
	
		pcbdata[i].state = 'R';	//进程初始状态为就绪R
	}
}


///调度函数/

//先来先服务算法
void FCFS(){
	int i,j,temp;
	double k;
	for(i = 0;i < num; i++){
		order[i] = pcbdata[i].time_start;
		ready[i] = i;
	}
	//冒泡排序
	for(i = 0; i< num; i++){//按照到达时间大小排序
		for(j = i+1; j<num; j++){
			if(order[i] > order[i+1]){
				temp = order[i];
				order[i] = order[j];
				order[j] = temp;
				temp = ready[i];
				ready[i] = ready[j];
				ready[j] = temp;
			} 
		}
	
	}
	printf("--先来先服务算法调度：非抢占，无时间片---\n");
	printf("\n");
	temp = pcbdata[ready[0]].time_start;
	for(i = 0; i < num; i++){
		printf("第%d个进程--%s,",i+1,pcbdata[ready[i]].name);
		printf("到达时间--%d,服务时间--%d\n",
			pcbdata[ready[i]].time_start,
			pcbdata[ready[i]].time_need);
		printf("本进程正在运行...........\n");
		_sleep(1);
		printf("运行完毕\n");
		temp += pcbdata[ready[i]].time_need;
		j = temp-pcbdata[ready[i]].time_start;
		k = (float)j/pcbdata[ready[i]].time_need;
		printf("完成时间--%d,周转时间--%d,带权周转时间--%.1f\n",
			temp,j,k);
		printf("\n");
	}
	printf("--------所有进程调度完毕------\n");
}

//短作业优先算法
void SJF(){
	int i,j,temp,min,index,temp1;
	double k;
	for(i = 0;i < num; i++){
		order[i] = pcbdata[i].time_start;
		ready[i] = i;
	}
	//冒泡排序
	for(i = 0; i< num; i++){//按照到达时间大小排序
		for(j = i+1; j<num; j++){
			if(order[i] > order[i+1]){
				temp = order[i];
				order[i] = order[j];
				order[j] = temp;
				temp = ready[i];
				ready[i] = ready[j];
				ready[j] = temp;
			} 
		}
	
	}
	temp = pcbdata[ready[0]].time_start;
	for(i=0;i<num-1;i++)
	{
	//	cout<<"ready[i]="<<ready[i]<<endl;
		temp =temp+ pcbdata[ready[i]].time_need;//完成时间
		min=999;
		for(j=i+1;j<num-1;j++)
		{
	//		cout<<"temp="<<temp<<endl;
			
			if(pcbdata[ready[j]].time_start < temp)//到达时间<完成时间
			{
	//			cout<<pcbdata[ready[j]].time_start<<" "<<temp<<endl;
				 if(pcbdata[ready[j]].time_need<min)//服务时间最小
				 {
					 index=j;//记录下标
					 min=pcbdata[ready[j]].time_need;
				 }
			}
		}
		//把服务时间最小的放到前面优先调度
		temp1 = ready[i+1];
		ready[i+1] = ready[index];
		ready[index] = temp1;

	}

	printf("--短作业优先算法调度：非抢占，无时间片---\n");
	printf("\n");
	temp = pcbdata[ready[0]].time_start;
	for(i = 0; i < num; i++){
		printf("第%d个进程--%s,",i+1,pcbdata[ready[i]].name);
		printf("到达时间--%d,服务时间--%d\n",
			pcbdata[ready[i]].time_start,
			pcbdata[ready[i]].time_need);
		printf("本进程正在运行...........\n");
		_sleep(1);
		printf("运行完毕\n");
		temp += pcbdata[ready[i]].time_need;
		j = temp-pcbdata[ready[i]].time_start;
		k = (float)j/pcbdata[ready[i]].time_need;
		printf("完成时间--%d,周转时间--%d,带权周转时间--%.1f\n",
			temp,j,k);
		printf("\n");
	}
	printf("--------所有进程调度完毕------\n");

}

//高相应比算法
void HRF(){
}

//按照先来先服务并使用时间片轮转
void Timeslice(){
}

//多级反馈调度队列，抢占式调度
void MRLA(){
}

/主函数
void main(){
	int i = 0, sch = 99;
	while(sch != 0){
		printf("\n请选择其中一种调度算法:\n");
		printf("(1)先来先服务FCFS\n");
		printf("(2)短作业优先SJF\n");
		printf("(3)高相应比HRF\n");
		printf("(4)时间片轮转Timeslice\n");
		printf("(5)多级反馈队列MRLA\n");
		printf("(0)退出\n");
		printf("请输入一个数字：");
		scanf("%d",&sch);
		switch (sch){
		case 1:FCFS();break;
		case 2: SJF();break;
		case 3:HRF();break;
		case 4:Timeslice();break;
		case 5:MRLA();break;
		case 0:	printf("退出程序\n");;break;
		}
	}
	_keygo();
}


//一下函数主要用于程序调试跟踪

//显示一个PCB的具体参数内容
void dis_pcb(PCB *pr){
	printf("%s的PCB:\n",pr->name);
	printf("标识符--%d,状态--%c,到达时间--%d\n",
		pr->id,pr->state,pr->time_start);
	printf("服务时间--%d,剩余运行时间--%d,已用时间--%的\n",
		pr->time_need,pr->time_left,pr->time_used);
	printf("-------------------------\n");
}

//像是所有进程PCB
void dis_pcb_all(){
	int i;
	printf("******当前所有进程状态*****\n");
	for(i = 0; i< num; i++)
		dis_pcb(&pcbdata[i]);
}

//显示就绪队列
void dis_ready(){
	int i;
	printf("当前就绪队列为：\n");
	for(i = 0; i< num-1; i++)
		printf("%s--",pcbdata[order[i]].name);
	printf("%s\n",pcbdata[order[i]].name);
}

先来先服务算法运行结果如图：

从运行结果可以看出，先到先服务算法是按照到达时间来调度的，到达时间从早到晚分别为：A（0）->B（1）->C（2）->D（3）->E（4）。

短作业优先算法运行结果如下：

短作业优先思想就是先按照到达时间排序，按照到达时间早晚获得第一个调度的进程，以及服务时间，完成时间=开始时间+服务时间。然后在后面几个进程中寻找开始时间在完成时间之前的进程，在这些进程中再找服务时间最短的进程作为第二个调度的进程，依次类推。

根据算法可以推出以下步骤：

首先第一个调度 的进程为A进程，因为到达时间最快。

                  然后计算A进程的完成时间为0+4=4

                  然后在BCDE进程中找到到达时间小于4的进程，分别为：B C D

                  然后在B C D进程中找到服务时间最小的：D进程，所以D进程为第二个调度进程。此时完成时间为4+2=6

                  继续在B C E进程中找到达时间小于6的进程，分别为：B C E

                  然后在B C E进程中找到服务时间最小的：B进程，所以B进程为第三个调度进程。此时完成时间为6+3=9

                  继续在C E进程中找到达时间小于9的进程，分别为C E

                  然后在C E进程中找到服务时间最小的 ：E进程，所以E进程为第四个调度进程，C进程为最后一个调度进程。

从代码执行结果可看出算法正确。

多进程和多线程的主要区别是：线程是进程的子集（部分），一个进程可能由多个线程组成。多进程的数据是分开的、共享复杂，需要用IPC；但同步简单。多线程共享进程数据，共享简单；但同步复杂。

　　多进程，Windows 应用程序中消息有两种送出途径；直接和排队。Windows或某些运行的应用程序可直接发布消息给窗口过程，或者，消息可送到消息列象连续不断轮询消息队列的OS中当前执行的每个进程都 事件驱动程序不是由事件的顺序来控制，而是由事件的发生来控，而事件的发生是随机的、不确定的，这就允许程序的用户用各种合理的顺序来安排程序的流程。

　　多线程（英语：multithreading），是指从软件或者硬件上实现多个线程并发执行的技术。具有多线程能力的计算机因有硬件支持而能够在同一时间执行多于一个线程，进而提升整体处理性能。具有这种能力的系统包括对称多处理机、多核心处理器以及芯片级多处理（Chip-level multithreading）或同时多线程（Simultaneous multithreading）处理器。［1］ 在一个程序中，这些独立运行的程序片段叫作“线程”（Thread），利用它编程的概念就叫作“多线程处理（Multithreading）”。具有多线程能力的计算机因有硬件支持而能够在同一时间执行多于一个线程（台湾译作“执行绪”），进而提升整体处理性能。

一、多进程和多线程的区别是什么？

　　在Linux下编程多用多进程编程少用多线程编程。

　　IBM有个家伙做了个测试，发现切换线程context的时候，windows比linux快一倍多。进出最快的锁（windows2k的 critical section和linux的pthread_mutex），windows比linux的要快五倍左右。当然这并不是说linux不好，而且在经过实际编程之后，综合来看我觉得linux更适合做high performance server，不过在多线程这个具体的领域内，linux还是稍逊windows一点。这应该是情有可原的，毕竟unix家族都是从多进程过来的，而 windows从头就是多线程的。

　　如果是UNIX/linux环境，采用多线程没必要。

　　多线程比多进程性能高？误导！

　　应该说，多线程比多进程成本低，但性能更低。

　　在UNIX环境，多进程调度开销比多线程调度开销，没有显著区别，就是说，UNIX进程调度效率是很高的。内存消耗方面，二者只差全局数据区，现在内存都很便宜，服务器内存动辄若干G，根本不是问题。

　　多进程是立体交通系统，虽然造价高，上坡下坡多耗点油，但是不堵车。

　　多线程是平面交通系统，造价低，但红绿灯太多，老堵车。

　　我们现在都开跑车，油（主频）有的是，不怕上坡下坡，就怕堵车。

　　高性能交易服务器中间件，如TUXEDO，都是主张多进程的。实际测试表明，TUXEDO性能和并发效率是非常高的。TUXEDO是贝尔实验室的，与UNIX同宗，应该是对UNIX理解最为深刻的，他们的意见应该具有很大的参考意义。

　　二、多进程和多线程的优缺点分析：

　　多进程：

　　多进程优点：

　　1、每个进程互相独立，不影响主程序的稳定性，子进程崩溃没关系；

　　2、通过增加CPU，就可以容易扩充性能；

　　3、可以尽量减少线程加锁/解锁的影响，极大提高性能，就算是线程运行的模块算法效率低也没关系；

　　4、每个子进程都有2GB地址空间和相关资源，总体能够达到的性能上限非常大。

　　多进程缺点：

　　1、逻辑控制复杂，需要和主程序交互；

　　2、需要跨进程边界，如果有大数据量传送，就不太好，适合小数据量传送、密集运算 多进程调度开销比较大；

　　3、最好是多进程和多线程结合，即根据实际的需要，每个CPU开启一个子进程，这个子进程开启多线程可以为若干同类型的数据进行处理。当然你也可以利用多线程+多CPU+轮询方式来解决问题……

　　4、方法和手段是多样的，关键是自己看起来实现方便有能够满足要求，代价也合适。

　　多线程：

　　多线程的优点：

　　1、无需跨进程边界；

　　2、程序逻辑和控制方式简单；

　　3、所有线程可以直接共享内存和变量等；

　　4、线程方式消耗的总资源比进程方式好。

　　多线程缺点：

　　1、每个线程与主程序共用地址空间，受限于2GB地址空间；

　　2、线程之间的同步和加锁控制比较麻烦；

　　3、一个线程的崩溃可能影响到整个程序的稳定性；

　　4、到达一定的线程数程度后，即使再增加CPU也无法提高性能，例如Windows Server 2003，大约是1500个左右的线程数就快到极限了（线程堆栈设定为1M），如果设定线程堆栈为2M，还达不到1500个线程总数；

　　5、线程能够提高的总性能有限，而且线程多了之后，线程本身的调度也是一个麻烦事儿，需要消耗较多的CPU。

参考：

多进程和多线程的区别是什么​？ 

用图文描述组成进程的要素，并说明其作用。

一、进程概念

引子 ：程序运行在并发环境中的问题
    （1）运行过程不确定
    （2）结果不可再现
1.进程定义
    进程是程序在某个数据集合上的一次运行活动。数据集合是指软硬件环境，多个进程共存或共享的环境。
2.进程的特征
    （1）动态性
        进程是程序的一次执行过程，动态产生且动态消亡；
    （2）并发性
        进程同其他进程一起向前推进；
    （3）异步性
        进程按照各自的速度向前推进（每一个进程按照自定逻辑，不考虑其他进程的运行，各自占用CPU）；
    （4）独立性
        进程是系统分配资源和调度CPU的单位（但是有了线程后，操作系统调度CPU的单位就变成了线程）。
3.进程与程序的区别
    （1）进程是动态的：程序的一次执行过程；
    （2）程序是静态的：一组指令的有序集合；
    （3）进程是暂存的：在内存中短期驻留；
    （4）程序是长存的：可以在存储介质上长期保存；
    （5）一个程序可能有多个进程。
4.进程的分类
    （1）按照使用资源的权限进行分类
        ①系统进程：系统内核相关的进程；
        ②用户进程：运行于用户态的进程。
    （2）按照对CPU的依赖性进行分类
        ①CPU型进程：主要用于计算；
        ②I/O型进程：主要用于I/O操作。

二、进程状态

1.进程的状态
    （1）运行状态（Running）
        进程已经占用CPU，在CPU上运行。
    （2）就绪状态（Ready）
        具备运行条件但是由于没有CPU可用，所以暂时不能运行。
    （3）阻塞状态（Block）也叫等待状态（Wait）
        由于等待某项服务完成或者等待某个信号而不能运行的状态，比如等待系统调用，I/O操作等等。
2.进程的三态模型
    （1）就绪->运行：进程调度。
    （2）运行->就绪：时间片到或者被强占。
    （3）运行->阻塞：请求服务后等待响应，或者等待某个信号的到来。
    （4）阻塞->就绪：请求的服务已经完成，或者等待的信号已经到来。

3.进程的五态模型

    （1）新建状态
        用户向系统提交程序后，在进程建立之前的过程。
    （2）终止状态
        进程撤出系统的过程.

用图文描述什么是进程切换，为什么进行进程切换，进程切换的步骤？

进程的切换

为了控制进程的执行，内核必须有能力挂起正在CPU执行的进程，恢复以前挂起的进程执行。 
所有进程共享CPU寄存器，进程恢复时必须装入寄存器的一组数据（硬件上下文TSS）。在进程切换时，首先要保存挂起进程的硬件

上下文，同时要装载唤醒进程的硬件上下文。这块linux实现的是使用软件执行进程切换。这样可以通过move指令检查装入寄存器值的合法性。 

进程的上下文

        Context，指进程运行环境，CPU环境（比如各个寄存器的取值）等等。进程的上下文由三部分组成：用户级上下文（程序、数据、共享

        存储区、用户栈，它们占用进程的虚拟地址空间）、寄存器上下文（由各个寄存器组成）、系统级上下文（PCB、核心栈等）。
    

进程切换的工作过程
1、（中断／异常等触发）正向模式切换并压入PSW／PC 。 （Program Status Word 程序状态字。program counter 程序计数器。指向下一条要执行的指令）

2、保存被中断进程的现场信息。

3、处理具体中断、异常。

4、把被中断进程的系统堆栈指针SP值保存到PCB。（Stack Pointer 栈指针。Process Control Block 进程控制块。）

5、调整被中断进程的PCB信息，如进程状态）。

6、把被中断进程的PCB加入相关队列。

7、选择下一个占用CPU运行的进程。

8、修改被选中进程的PCB信息，如进程状态。

9、设置被选中进程的地址空间，恢复存储管理信息。

10、恢复被选中进程的SP值到处理器寄存器SP。

11、恢复被选中进程的现场信息进入处理器。

12、（中断返回指令触发）逆向模式转换并弹出PSW／PC。

用图文描述模式转换、进程切换、进程状态转换三者之间的关系？

◆运行状态（TASK_RUNNING）

指正在被CPU运行或者就绪的状态。这样的进程被成为runnning进程。运行态的进程可以分为3种情况：内核运行态、用户运行态、就绪态。

◆可中断睡眠状态（TASK_INTERRUPTIBLE）

处于等待状态中的进程，一旦被该进程等待的资源被释放，那么该进程就会进入运行状态。

◆不可中断睡眠状态（TASK_UNINTERRUPTIBLE）

该状态的进程只能用wake_up()函数唤醒。

◆暂停状态（TASK_STOPPED）

当进程收到信号SIGSTOP、SIGTSTP、SIGTTIN或SIGTTOU时就会进入暂停状态。可向其发送SIGCONT信号让进程转换到可运行状态。

◆僵死状态（TASK_ZOMBIE）

当进程已经终止运行，但是父进程还没有询问其状态的情况。