模拟进程调度

程序员文章站 2024-02-27 18:17:45

...

关于进程的调度，首先了解俩个算法：时间片轮转算法与优先级调度算法。

时间片轮转：

模拟进程调度
具体的例子：

其中涉及到俩个概念：时间片与轮转。

本例设计思想

时间片：就是规定一个进程被调用一次最大可占用资源时间，这里我设定时间片大小为2s；设置小一点，更能接近模拟真实的进程调度。
轮转：这里采用while循环遍历，扣除时间。而队列则采用java的链表：LinkedList。初始化的队列(升序排列，队首出，队尾进)，优先级如下：
模拟进程调度

时间片轮转的java代码：

//package No1;

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

public class diaodu {
	private static LinkedList<RW> list = new LinkedList();// 就绪队列
	static {
		list.add(new RW(1, 3, Integer.MIN_VALUE, 10, 10, Integer.MAX_VALUE));// min代表进程从未进入cpu
																				// max代表进程还没有结束
		list.add(new RW(2, 1, Integer.MIN_VALUE, 6, 6, Integer.MAX_VALUE));
		list.add(new RW(3, 4, Integer.MIN_VALUE, 2, 2, Integer.MAX_VALUE));
		list.add(new RW(4, 5, Integer.MIN_VALUE, 4, 4, Integer.MAX_VALUE));
		list.add(new RW(5, 2, Integer.MIN_VALUE, 8, 8, Integer.MAX_VALUE));
	}

	public static void main(String[] args) {
		System.out.println("id" + "\t" + "pri" + "\t" + "c_time" + "\t"
				+ "all_time" + "\t" + "r_time" + "\t" + "f_time\n");
		Collections.sort(list, new Comparator<RW>() {// 按照进程优先级初始化就绪队列,这里按照优先级升序，队头出，队尾增加。
					public int compare(RW a, RW b) {
						return a.pri - b.pri;
					}
				});
		int currentTime = 0;// 记录当前总的时间参照,
		while (!list.isEmpty()) {// 当队列还有数据时，代表进程还未调用完毕，则继续轮转

			currentTime += 2;// 调用一个进程时，时间参考加2
			RW temp = list.removeFirst();// 取出队首，调用进程
			System.out.println(temp.id + "进程调用前的状态：");
			System.out.println(temp);
			if (temp.c_time == Integer.MIN_VALUE) {// 如果满足，代表该进程从来未进入cpu，此次调用需要记录第一次被调用的时间
				temp.c_time = (currentTime - 2);
			}
			temp.r_time -= 2;// 进程总的剩余的需要时间减少2s的时间片
			if (temp.r_time <= 0) {// 表示当前进程已经彻底调用完毕，需要设置进程结束时间，并且不进入队列
				temp.f_time = currentTime;
			} else {
				list.addLast(temp);// 从新进入优先级队列队尾
			}
			System.out.println(temp.id + "进程调用后的状态：");
			System.out.println(temp + "\n");

		}
		System.out.println("调用完毕");
	}

}

class RW {// 一个进程
	// 进程id
	int id;
	// 优先级
	int pri;
	// 进程已站cpu时间 线程第一次占cpu时的时间
	int c_time;
	// 进程总的需要运行时间
	int all_time;
	// 进程剩余运行时间
	int r_time;
	// 进程结束时间
	int f_time;

	public RW(int id, int pri, int c_time, int all_time, int r_time, int f_time) {
		this.id = id;
		this.pri = pri;
		this.c_time = c_time;
		this.all_time = all_time;
		this.r_time = r_time;
		this.f_time = f_time;
	}

	public String toString() {
		return this.id + "\t" + this.pri + "\t" + this.c_time + "\t" + all_time
				+ "\t" + this.r_time + "\t" + this.f_time;
	}

}

运行结果解析图：
模拟进程调度
全部整体截图：

模拟进程调度

优先级调度

模拟进程调度
由此可见，优先级调度又分为俩种：抢占式与非抢占式。

设计思想

1》用上面的程序扩展一个当前到达队列的时间的字段。
2》一个6大小的RW进程数组，而其下标代表进程到来的时间。举例，如果RW[5]==null，代表5时间处，并没有进程的到来.这里的6，表示允许排队的时间是5内，而本程序中的到达时间最迟的也是5。
3》为了方便在一个堆里面快速找到一个最大值，将利用一个java自带的快排维护优先级队列链表LinkedList。
4》第一个程序为非抢占式，不考虑优先级。第二个程序为抢占式，将考虑优先级，并且维护3》的一个链表。

先了解效率算法

模拟进程调度

非抢占优先调度

package No1;

import java.util.LinkedList;

public class diaodu {
	private static LinkedList<RW> list = new LinkedList();// 就绪队列
	private static RW[] rw = new RW[6];// 记录到达进程的时间点

	static {
		RW r1 = new RW(1, 4, Integer.MIN_VALUE, 7, 7, Integer.MAX_VALUE, 0);// min代表进程从未进入cpu
		// max代表进程还没有结束
		rw[0] = r1;// 表示0时刻，r1进程将进入就绪队列

		RW r2 = new RW(2, 3, Integer.MIN_VALUE, 4, 4, Integer.MAX_VALUE, 2);
		rw[2] = r2;

		RW r3 = new RW(3, 2, Integer.MIN_VALUE, 1, 1, Integer.MAX_VALUE, 4);
		rw[4] = r3;

		RW r4 = new RW(4, 1, Integer.MIN_VALUE, 4, 4, Integer.MAX_VALUE, 5);
		rw[5] = r4;
	}

	public static void main(String[] args) {
		System.out
				.println("id" + "\t" + "pri" + "\t" + "c_time" + "\t"
						+ "all_time" + "\t" + "r_time" + "\t" + "f_time\t"
						+ "d_time\n");
		for (int i = 0; i < 6; i++) {// 遍历六个时刻，因为本例只涉及到了6个时刻
			if (rw[i] != null) {// 代表i时刻有rw【i】进程到来
				list.addLast(rw[i]);// 因为是非抢占式的，所以这里直接“先来后到”插入，按照对头遍历调用即可
			}

		}
		int currentTime = 0;// 记录参照时间
		LinkedList<RW> list01 = new LinkedList();
		while (!list.isEmpty()) {// 直接按照先来后到遍历
			RW temp = list.removeFirst();
			System.out.println(temp.id + "进程本次调用前：" + temp);
			temp.c_time = currentTime;// 记录本进程调用的时间
			currentTime += temp.all_time;// 更新参照时间
			temp.r_time = 0;// 一次性执行完所有时间
			temp.f_time = currentTime;// 跟新结束时间
			System.out.println(temp.id + "进程本次调用后：" + temp + "\n");
			list01.add(temp);// 这里不考虑优先级，直接方便后面计算就可以了

		}
		int sum = 0;
		while (!list01.isEmpty()) {// 求评价指标
			RW temp = list01.removeFirst();
			System.out.print(temp.id + "的周转时间为： " + (temp.f_time - temp.c_time)
					+ "  ");
			System.out.println("带权的周转时间为： " + (temp.f_time - temp.c_time)
					/ temp.all_time + "  ");
			sum += temp.f_time - temp.c_time;
		}
		System.out.println("平均周转时间为：" + sum / 4);

	}

}

class RW {// 一个进程
	// 进程id
	int id;
	// 优先级
	int pri;
	// 进程已站cpu时间 线程第一次占cpu时的时间
	int c_time;
	// 进程总的需要运行时间
	int all_time;
	// 进程剩余运行时间
	int r_time;
	// 进程结束时间
	int f_time;
	// 新增的到达时间
	int d_time;

	public RW(int id, int pri, int c_time, int all_time, int r_time,
			int f_time, int d_time) {
		this.id = id;
		this.pri = pri;
		this.c_time = c_time;
		this.all_time = all_time;
		this.r_time = r_time;
		this.f_time = f_time;
		this.d_time = d_time;
	}

	public String toString() {
		return this.id + "\t" + this.pri + "\t" + this.c_time + "\t" + all_time
				+ "\t" + this.r_time + "\t" + this.f_time + "\t" + this.d_time;
	}

}

运行结果解析图：

模拟进程调度

抢占式优先调度

模拟进程调度
程序设计思想：
其中设置cpu的总工作等待时间为20s，然后按秒为单位维护一个就绪队列，最后每一秒，打印记录正在被调用的进程。结合前面提到的思想。

//package No1;

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

public class diaodu {
	private static LinkedList<RW> list = new LinkedList();// 就绪队列
	private static LinkedList<RW> list01 = new LinkedList();// 已经结束的进程队列
	private static RW[] rw = new RW[6];// 记录到达进程的时间点

	static {
		RW r1 = new RW(1, 4, Integer.MIN_VALUE, 7, 7, Integer.MAX_VALUE, 0);// min代表进程从未进入cpu
		// max代表进程还没有结束
		rw[0] = r1;// 表示0时刻，r1进程将进入就绪队列

		RW r2 = new RW(2, 3, Integer.MIN_VALUE, 4, 4, Integer.MAX_VALUE, 2);
		rw[2] = r2;

		RW r3 = new RW(3, 2, Integer.MIN_VALUE, 1, 1, Integer.MAX_VALUE, 4);
		rw[4] = r3;

		RW r4 = new RW(4, 1, Integer.MIN_VALUE, 4, 4, Integer.MAX_VALUE, 5);
		rw[5] = r4;
	}

	public static void main(String[] args) {
		System.out
				.println("id" + "\t" + "pri" + "\t" + "c_time" + "\t"
						+ "all_time" + "\t" + "r_time" + "\t" + "f_time\t"
						+ "d_time\n");
		for (int i = 0; i < 20; i++) {// 这里设置cpu一共工作的时间为20s
			if (i < 6 && rw[i] != null) {// 代表i时刻有rw【i】进程到来,本例只涉及到了6
				list.addLast(rw[i]);
				Collections.sort(list, new Comparator<RW>() {// 进入就绪队列，并且按照优先级重新排序初始化，即实现抢占
							public int compare(RW a, RW b) {
								return a.pri - b.pri;
							}
						});
			}
			if (!list.isEmpty()) {
				RW temp = list.removeFirst();// 拿出优先级最高的
				System.out.println(temp.id + "进程本次调用前：" + temp);
				if (temp.c_time == Integer.MIN_VALUE) {// 代表该进程是第一次调用，需要记录第一次的时间
					temp.c_time = i;
				}
				temp.r_time -= 1;// 剩余需要的时间-1；
				if (temp.r_time <= 0) {// 表示该进程已经彻底运行完毕，需要记录结束时间
					temp.f_time = i + 1;
					list01.add(temp);// 追加到已经完成的队列，方便后面评价指标计算
				} else {// 反之则追加到原来的优先级队列
					list.addFirst(temp);// 注意是直接追加到头
				}
				System.out.println(temp.id + "进程本次调用后：" + temp + "\n");
			} else {
				System.out.println("当前时刻无就绪进程");
			}

		}
		System.out.println("调用结束");
		int sum = 0;
		while (!list01.isEmpty()) {// 求评价指标
			RW temp = list01.removeFirst();
			System.out.print(temp.id + "的周转时间为： " + (temp.f_time - temp.c_time)
					+ "  ");
			System.out.println("带权的周转时间为： " + (temp.f_time - temp.c_time)
					/ temp.all_time + "  ");
			sum += temp.f_time - temp.c_time;
		}
		System.out.println("平均周转时间为：" + sum / 4);

	}

}

class RW {// 一个进程
	// 进程id
	int id;
	// 优先级
	int pri;
	// 进程已站cpu时间 线程第一次占cpu时的时间
	int c_time;
	// 进程总的需要运行时间
	int all_time;
	// 进程剩余运行时间
	int r_time;
	// 进程结束时间
	int f_time;
	// 新增的到达时间
	int d_time;

	public RW(int id, int pri, int c_time, int all_time, int r_time,
			int f_time, int d_time) {
		this.id = id;
		this.pri = pri;
		this.c_time = c_time;
		this.all_time = all_time;
		this.r_time = r_time;
		this.f_time = f_time;
		this.d_time = d_time;
	}

	public String toString() {
		return this.id + "\t" + this.pri + "\t" + this.c_time + "\t" + all_time
				+ "\t" + this.r_time + "\t" + this.f_time + "\t" + this.d_time;
	}

}

结果解析图：
模拟进程调度
完整运行图：

模拟进程调度

模拟进程调度

时间片轮转：

本例设计思想

时间片轮转的java代码：

优先级调度

设计思想

先了解效率算法

非抢占优先调度

抢占式优先调度

进程调度算法模拟

模拟进程调度

洛谷——简单模拟

详解Python实现多进程异步事件驱动引擎

java模拟ajax访问另一个项目的controller代码实例

实例讲解Android中的AIDL内部进程通信接口使用

Android开发中多进程共享数据简析

详解Python进程间通信之命名管道

Android使用listview实现分页刷新（线程休眠模拟）

简单学习Python多进程Multiprocessing