操作系统之进程调度——优先权法和轮转法（附上样例讲解）
操作系统之银行家算法—详解流程及案例数据
操作系统之多线程编程—读者优先/写者优先详解
操作系统之存储管理——FIFO算法和LRU算法
操作系统之磁盘调度——SCAN实例讲解

要求

一、实验目的
多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。
二、实验内容
1．优先权法、轮转法
简化假设
1）进程为计算型的（无I/O）
2）进程状态：ready、running、finish
3）进程需要的CPU时间以时间片为单位确定
2．算法描述
1）优先权法——动态优先权
当前运行进程用完时间片后，其优先权减去一个常数。
2）轮转法
三、流程图
优先权：

轮转法：

分析

?想要完成操作系统算法第一步要弄清楚操作系统相关的专业术语。弄清各个算法的流程和目的要求。才能模拟出相关算法的过程。下面先附上实验的相关要求?

通过本次实验，深刻的理解了操作系统中线程资源的分配方式和进程的调度方式。操作系统实验重在理解每一个算法的意图和目的，那么就选择适当的数据结构模拟过程就可以完成相关算法了。

优先权算法：

1. 所有线程的序列核心是围绕优先权的权值大小。并且该优先权的大小会动态的变化，那么我们选区以权值为排序准则的优先队列是处理该结构的最好方法。能够有效的节省空间，算法复杂度。
2. 而优先权算法某个线程的结束标识是还需要的时间needtime。所以在随机选区线程的时候和输出状态的时候要判断该线程还需不需要资源。
3. 至于状态还有一点很重要的是要即使转换。当进行下一个操作要即使转换上一个线程的状态和下一个线程的状态防止状态混淆。

轮转法：

• 轮转法强调先进先出的拉链式顺序，而不以其他的权值作为开始/调度的先后顺序，所以普通先进先出的普通队列是解决该算法的最好方法。
• . 轮转法和优先权法不一样的是优先权法每次只进一个线程只执行一次。而轮转法是进一个可以执行最多是该线程可轮转的次数/轮转值（可能在中间就完成线程的释放），所以在写程序的时候每次都要判断是否已经轮转。并且到最后还要判断还是否需要调度。如果需要，再抛入队尾。

代码

实现的代码（java）:

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class priority {

	static pcb pcb[];
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		System.out.println("创建线程数量：");
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		pcb=new pcb[n];
		for(int i=0;i<n;i++)
		{
			pcb[i]=new pcb(i+1,"ready");
		}
		System.out.println("是否采用优先权？Y/N");
		String s=sc.next();
		if(s.equals("Y"))
		{
			priority();
		}
		else
		{
			lunzhuan();
		}
		//printstatus();
	}
	private static void lunzhuan() {
		Queue<pcb>q1=new ArrayDeque<>();
		for(int i=0;i<pcb.length;i++)
		{
			int lunhzun=(int) (Math.random()*4)+1+(int)(Math.random()*2);//不能为0
			int needtime=(int)(Math.random()*8)+1;
			pcb[i].lunhzuan=lunhzun;
			pcb[i].needalltime=needtime;	
			q1.add(pcb[i]);
		}
		while(!q1.isEmpty())
		{
			pcb team=q1.poll();
			int time=0;//占用cpu时间片树
			while(time<team.lunhzuan)
			{
				if(team.needalltime<=0)
				{break;}
				time++;
				team.needalltime-=1;
				team.status="running";
				printluzhuan();
				System.out.println();
			}
			if(team.needalltime<=0) {team.status="finish";}
			else
			{
				team.status="ready";
				q1.add(team);
			}
		}
		printluzhuan();
	}
	private static void printluzhuan() {
		for(int i=0;i<pcb.length;i++)
		{
			System.out.println("threadid:"+pcb[i].id+"  "+pcb[i].status+"  needtime:"+pcb[i].needalltime+"  lunzhuan:"+pcb[i].lunhzuan);
		}	
		
	}
	private static void priority() {//优先权
		Queue<pcb>q1=new PriorityQueue<pcb>(com);
		for(int i=0;i<pcb.length;i++)
		{
			int proty=(int) (Math.random()*15);
			int needtime=(int)(Math.random()*4)+1;
			pcb[i].proty=proty;
			pcb[i].needalltime=needtime;
			q1.add(pcb[i]);
		}	
//		for(int i=0;i<pcb.length;i++)
//		{
//			q1.add(pcb[i]);
//		}
		while(!q1.isEmpty())
		{
			pcb team=q1.poll();
			team.needalltime-=1;
			team.proty-=3;
			team.status="running";
			printstatus();
			System.out.println();
			if(team.needalltime>0)
			{
				team.status="ready";
				q1.add(team);	
			}
			else
				team.status="finish";
		}
		printstatus();
	}
	private static void printstatus() {
		// TODO 自动生成的方法存根
		for(int i=0;i<pcb.length;i++)
		{
			System.out.println("threadid:"+pcb[i].id+"  "+pcb[i].status+"  needtime:"+pcb[i].needalltime+"  priority:"+pcb[i].proty);
		}		
	}
	static Comparator<pcb> com=new Comparator<pcb>() {
		@Override
		public int compare(pcb o1, pcb o2) {
			// TODO 自动生成的方法存根
			return o2.proty-o1.proty;
		}
	}; 
	static class pcb
	{	
		int id;//进程id
		String status;//进程状态
		int proty;
		int needalltime;//需要总时间
		int lunhzuan;//轮转时间树
		public pcb(int id, String status) {
			// TODO 自动生成的构造函数存根
			this.id=id;
			this.status=status;
		}	
	}
}

数据打印

优先权：

2：轮转法：

声明：这只是本人的个人理解，如果又纰漏，还请大神指出！?

如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai

前言

我们在解决问题中经常使用到的数据结构一定少不了树，在数据结构这一大块中，我们对每一个结构都会讲各种形形色色的操作，比如栈的压栈出栈，树的各种遍历，但其实数据结构最重要的操作其实是搜索。如果我们不知道链表的搜索，如何插入删除？不知道图的搜索，如何寻找最小生成树？

虽然我们讲的是树的搜索，但是本篇文章探讨的问题并非是树，而是将问题转化为树结构来处理。

树的几种常见搜索方式

我们先给出几种常用的例子吧。

1. 布尔表达式，给一组布尔变量和一个用这些变量组成的布尔表达式，需要寻找一种赋值方式使表达式为真

2. 8-puzzle问题，给一个九宫格，需要进行排序

3. 有n个结点的连通图G=(V,E)，V为点集，E为边集，寻找哈密顿环。
   哈密顿环是沿着边遍历每一个结点有且仅有一次最后回到起点的环

上述的三个问题，很明显都是能将问题转换成一棵树结构的，第二个就是每次移动一格来形成树；第三个哈密顿环就不用说了，很明显的每一次选择一个顶点，标准树结构。
而且上述问题都是遍历树寻找正确答案的那种，所以我们先解决这几个问题。

接下来给出几个常用的树搜索策略：

• 暴力搜索
• 深度优先
• 广度优先

这几个其实都不常用，嗯就是这样，尤其第一个。
这里提到的原因主要是后面的其实还是会用到这些基本解决办法。

深度优先
说白了就是在搜索的时候，我们先从一条线走到叶子节点，然后回到上一个分支处，从另一条分支走，不断重复直到最后我们找到目标节点或者遍历完整棵树。

比如这样的一棵树，我们深度优先的方式就是ABD（回溯到A）CG（回溯到C）EF

因为需要回溯，所以我们采取的数据结构为栈

1. 首先将根节点压栈，
2. 判断栈顶元素是否为目标结点，不是继就续
3. 将栈顶弹出，将被弹出元素的所有孩子结点压栈（按照从右到左的顺序，因为我们要保证先走左子树）
4. 当S为空，说明没找到，否则继续操作2

广度优先
首先，广度优先和深度优先相似，但是我们这次采取的方法是先遍历行。
从顶点开始，先遍历所有的子节点，然后遍历第一个孩子结点的孩子结点，然后是第二个孩子的……

还是这棵树，这次我们广度优先的结果是：ABCD（找到第二个孩子C）GEF

因为也需要回溯，我们还是找一个结构存起来，这次我们采取的是队列

1. 首先将根节点入队列
2. 如果队列首元素是目标节点，结束程序
3. 否则将队首元素出队，将其所有孩子结点入队
4. 如果队列为空，说明没有找到，否则重复操作2

爬山法

在深度优先和广度优先中，我们每一个根节点都会遇到很多个可拓展对象，那么哪一个先进行就是一个问题，
但我们还学过贪心啊（点击查看博客），我们能否将两者合并？

爬山法就是这样的产物，是由贪心算法和深度优先算法相结合的产物。
同深度优先，爬山法也需要使用栈。

1. 将根节点压栈
2. 如果栈顶元素就是我们的目标节点，结束
3. 将栈顶元素出栈，同时将出栈的元素按照一定的顺序压栈
4. 如果栈空，说明没找到；否则继续操作2

就是将我们深度优先的压栈方式改了一下么，那么这一定的顺序是什么呢？
比如在8-puzzle问题中，我们需要将8个方块归位，那么我们就可以定义一个测度，这里的测度是放置错误的方块的个数，毕竟当前正确的方块越多，按理来说就应该更接近问题的正确答案。

然后，我们来看一下贪心部分，很明显，他不能保证每一次都是最好的……
接下来，就需要进一步优化了。
（虽然不能保证最好，但是在有些情况下用着也还行，kmp还牛皮了，但是我们暴力匹配一下也没啥，工程上也总是直接贪心，不怎么考虑正确性）

best-first

有没有一种方法，既能快速又能产生最短结果的方法？
之前是深度优先的同时，就直接选取了贪心出来的当前最优解，那么我们可以效仿广度优先，将当前所有的可能比较一下，而不是将目光限定在当前的一条分支的选择上。

比如上面的8-puzz问题截图，在爬山法选定最左边的3之后，我们的目光就停在2和4上了，
而我们的bf算法，则是将2、4和上一步留下的344都一起考虑了。

这次我们的存储结构再次更换，使用的是堆。
（如果对堆不够清楚，这是之前关于堆的博客）

1. 将根节点存入堆中
2. 如果堆的根节点是目标节点，结束程序
3. 否则将根节点删除，将根节点的孩子节点加入堆中
4. 如果堆为空，说明没找到，否则就继续操作2

在这种方法中，我们的贪心策略就是成立的，因为是全局选择。

总结

我们在这篇博客中讲解了深度优先、广度优先，虽然只是简单提了一下，
然后延申出了基于深度优先和贪心的爬山法，
还有深度优先、广度优先和贪心的best-first算法。
这些方法不但在上述问题中会遇到，而且在我们的下一篇博客也会提到关于最值问题的解决办法。
（提示一下，这篇博客主要是讲从树结构中选择正确的答案，但在最值问题中我们不知道最佳答案，这时就需要其他的算法了。）