import java.util.LinkedList;
import java.util.Random;
public class Main {
public static void main(String[] args) throws InterruptedException {
new ProcessMemoryScheduling().run();
}
}
public class PCB {
String name; // 进程名
int needMemory; // 所需内存
int address; // 主存起始位置
double arriveTime; // 到达时间
double needTime; // 需要运行时间
double hasUsedTime; // 已用时间
String status; // 进程状态：运行中、就绪、阻塞(Running、 Waiting、 Blocking)
}
public class MemoryBlock {
int address; // 内存块地址
int length; // 内存块长度
String status = "Free"; // 内存块的状态：Busy或 Free
MemoryBlock(int address, int length) {
this.address = address;
this.length = length;
}
}
public class ProcessMemoryScheduling {
private static int PROCESS_NUM = 10; // 进程数
private int blocked = 0; // 阻塞进程的标识，表示是否有进程属于阻塞状态
private int blockIndex = -1; // 阻塞进程的下标，没有阻塞进程则为-1
private PCB[] pcb = new PCB[PROCESS_NUM]; // 进程数组，存放所有进程
private LinkedList<MemoryBlock> memoryBlockList = new LinkedList<>();
private double timeSlice; // 时间片的大小
private int runningIndex; // 当前运行的进程的下标（索引），没有则为-1
private long lastTime; // 每次调度程序都记录当前时间
private long beginTime; // 程序开始运行的时间
/* 用于判断所有进程是否运行完*/
private boolean isFinishALLProcess() {
for (int i = 0; i < PROCESS_NUM; i++) {
if (!pcb[i].status.equals("Finish")) {
return false;
}
}
return true;
}
/* 初始化测试数据*/
private void initData() {
runningIndex = -1;
Random r = new Random();
for (int n = 0; n < PROCESS_NUM; n++) {
pcb[n] = new PCB();
pcb[n].name = "P" + Integer.toString(n + 1); // 设置进程名
pcb[n].needTime = r.nextDouble() * 4 + 12; // 随机产生服务时间，4到12秒
pcb[n].needMemory = r.nextInt(122) + 38; // 随机产生需要的内存，38到150KB
if (n == 0) {
pcb[n].arriveTime = 0; // 第一个作业默认0时刻到达
pcb[0].needMemory = 50;
} else {
pcb[n].arriveTime = r.nextDouble() * 5 + 1; // 随机设置到达时间
pcb[n].needMemory = r.nextInt(122) + 38; // 随机产生需要的内存，38到150KB
}
}
for (int n = 0; n < PROCESS_NUM; n++) {
pcb[n].hasUsedTime = 0;
pcb[n].address = 0;
pcb[n].status = "U";
}
MemoryBlock firstBlock = new MemoryBlock(0, 1024); //设置用户内存在0到1024之间
memoryBlockList.add(firstBlock);
print();
}
/*精确度位数的截图*/
private String d2s(double d) {
String tmp = d + "";
int index = tmp.indexOf(".");
int EXACT_DIGIT = 1; // double型变量小数点后精确的尾数
return tmp.substring(0, index + EXACT_DIGIT + 1);
}
/*一次划分算法，为快排做准备*/
private int getStandard(int i, int j) {
PCB key = pcb[i]; // 基准数据
while (i < j) {
// 因为默认基准是从左边开始，所以从右边开始比较
// 当队尾的元素大于等于基准数据 时,就一直向前挪动 j 指针
while (i < j && pcb[j].arriveTime >= key.arriveTime) {
j--;
}
// 当找到比 array[i] 小的时，就把后面的值 array[j] 赋给它
if (i < j) {
pcb[i] = pcb[j];
}
// 当队首元素小于等于基准数据 时,就一直向后挪动 i 指针
while (i < j && pcb[i].arriveTime <= key.arriveTime) {
i++;
}
// 当找到比 array[j] 大的时，就把前面的值 array[i] 赋给它
if (i < j) {
pcb[j] = pcb[i];
}
}
// 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置
// 把基准数据赋给正确位置
pcb[i] = key;
return i;
}
/*根据到达时间使用快排算法进行排序*/
private void quickSortByArriTime(int low, int high) {
// 开始默认基准为 low
if (low < high) {
int standard = getStandard( low, high); // 分段位置下标
quickSortByArriTime( low, standard - 1); // 左边排序
quickSortByArriTime(standard + 1, high); // 右边排序
}
}
/*结果显示函数*/
private void print() {
System.out.println("\n-----------------------------------------------------------------------------");
System.out.println("内存分区表(Busy:占用 Free:空闲)：");
System.out.println("起址(K) 长度（KB） 状态");
for (MemoryBlock memoryBlock : memoryBlockList) {
System.out.printf("%-8d %-10d %-6s\n", memoryBlock.address, memoryBlock.length, memoryBlock.status);
}
/* 打印后备队列中的作业 */
System.out.println("\n后备队列中的作业:");
for (int i = 0; i < PROCESS_NUM; i++) {
if (pcb[i].status.equals("U")) {
System.out.print(pcb[i].name + "\t");
}
}
/* 打印就绪队列、运行中、阻塞状态、完成调度这几个状态的进程 */
System.out.println("\n当前各进程PCB信息：");
System.out.print("进程名 到达时间/s 需要时间/s 已用时间/s 所需内存/KB 内存起址 进程状态\n");
for (int i = 0; i < PROCESS_NUM; i++) {
if (!pcb[i].status.equals("U")) {
System.out.printf("%-6s %-10s %-10s %-10s %-11d %-8d %-8s\n", pcb[i].name, d2s(pcb[i].arriveTime)
, d2s(pcb[i].needTime), d2s(pcb[i].hasUsedTime), pcb[i].needMemory, pcb[i].address, pcb[i].status);
}
}
System.out.println("-----------------------------------------------------------------------------");
lastTime = System.currentTimeMillis(); // 更新上次调度时间
}
/* 获取后续等待进程信息*/
private int getNextWaiting(int curr) {
int p = curr;
while ((p = ++p % PROCESS_NUM) != curr) {
if (pcb[p].status.equals( "Waiting") ) {
return p;
}
}
return -1;
}
/*从后备队列中选择作业并申请内存*/
private void getNextOnDisk(double allTime) {
int memoryProcessNum = 0; // 在内存中的进程个数
for (PCB aPcb : pcb) {
if (aPcb.status.equals("Waiting") || aPcb.status.equals("Running") || aPcb.status.equals("Blocking")) {
memoryProcessNum++;
}
}
int MAX_OCCURS = 5; //允许并发的进程数量，小于这个数时从后备队列调入进程
if (memoryProcessNum < MAX_OCCURS) { // 如果内存中程序数少于最大并发数，从后备队列找到最先到达的进程调入内存
for (int p = 0; p < pcb.length && memoryProcessNum < MAX_OCCURS; p++) {
if (pcb[p].status.equals("U") && allTime >= pcb[p].arriveTime) {
int address = applyMemory(p);
if (address != -2) { // 分配内存成功才修改状态
pcb[p].address = address;
pcb[p].status = "Waiting";
memoryProcessNum++;
}
}
}
}
}
/*申请内存*/
private int applyMemory(int curr) {
if (!pcb[curr].status.equals("U")) {
return -2;
}
MemoryBlock target = null;
int needMemory = pcb[curr].needMemory;
for (MemoryBlock memoryBlock : memoryBlockList) {
if (memoryBlock.status.equals("Free") && memoryBlock.length >= needMemory) {
target = memoryBlock;
break;
}
}
if (target == null) { // 找不到合适的内存块用于分配
return -2;
} else if (target.length == needMemory) { // 申请的内存和内存分区刚好相等，直接将整块分区分给该进程
target.status = "Busy";
return target.address;
} else {
target.status = "Busy";
MemoryBlock block = new MemoryBlock(target.address + needMemory, target.length - needMemory);
target.length -= block.length;
memoryBlockList.add(memoryBlockList.indexOf(target) + 1, block); // 将新建的空闲分区插入到分区连中
return target.address;
}
}
/*进程运行完之后释放内存*/
private void releaseMemory(int address) {
MemoryBlock target = null;
for (MemoryBlock memoryBlock : memoryBlockList) {
if (memoryBlock.address == address) {
target = memoryBlock;
break;
}
}
if (target == null){
return;
}
if(memoryBlockList.size()==1){
target.status = "Free";
return;
}
int index = memoryBlockList.indexOf(target);
if (index == 0) {
MemoryBlock memoryBlock = memoryBlockList.get(1);
if (memoryBlock.status.equals( "Free")) {
target.length += memoryBlock.length;
memoryBlockList.remove(memoryBlock);
}
target.status = "Free";
} else if (index == memoryBlockList.size() - 1) {
MemoryBlock m = memoryBlockList.get(index - 1);
if (m.status.equals("Free") ) {
m.length += target.length;
memoryBlockList.remove(target);
}
target.status = "Free";
} else {
MemoryBlock preMemoryBlock= memoryBlockList.get(index - 1);
MemoryBlock nextMemoryBlock = memoryBlockList.get(index + 1);
if (preMemoryBlock.status.equals("Free") && nextMemoryBlock.status.equals( "Free")) {
preMemoryBlock.length += target.length;
preMemoryBlock.length += nextMemoryBlock.length;
memoryBlockList.remove(target);
memoryBlockList.remove(nextMemoryBlock);
} else if (preMemoryBlock.status.equals("Free") && nextMemoryBlock.status.equals("Busy") ) {
preMemoryBlock.length += target.length;
memoryBlockList.remove(target);
} else if (preMemoryBlock.status.equals("Busy") && nextMemoryBlock.status.equals("Free") ) {
target.length += nextMemoryBlock.length;
target.status = "Free";
memoryBlockList.remove(nextMemoryBlock);
} else {
target.status = "Free";
}
}
}
/*调度方法 */
private void dispatch() throws InterruptedException {
if (isFinishALLProcess()) {
return;
}
long now = System.currentTimeMillis();
double passedTime = (now - lastTime) / 1000.0; //距离上次调度经过的时间
double allTime = (now - beginTime) / 1000.0;
/* 从后备队列调入进程 */
getNextOnDisk(allTime);
if (runningIndex != -1) {
double oldhasUsedTime = pcb[runningIndex].hasUsedTime;
if (passedTime >= timeSlice) {
if (oldhasUsedTime + passedTime >= pcb[runningIndex].needTime) {
pcb[runningIndex].hasUsedTime = pcb[runningIndex].needTime;
pcb[runningIndex].status = "Finish";
releaseMemory(pcb[runningIndex].address);
} else {
pcb[runningIndex].hasUsedTime = oldhasUsedTime + timeSlice;
pcb[runningIndex].status = "Waiting";
}
/* 从就绪队列中选择下一个进程 */
int next = getNextWaiting(runningIndex);
if (next != -1) {
pcb[next].status = "Running";
runningIndex = next;
print();
}
}
} else {
pcb[0].status = "Running";
runningIndex = 0;
print();
}
/* 随机阻塞进程 */
Random random = new Random();
int randomNum = random.nextInt(3);
if (randomNum == 2 && (blocked == 0 ) ) { // 符合此条件的进程将被阻塞
blockIndex = runningIndex;
pcb[runningIndex].status = "Blocking";
blocked = 1;
runningIndex = getNextWaiting(runningIndex);
}
/* 唤醒进程 */
if (blocked == 1) {
long time = System.currentTimeMillis();
double intervalTime = (time - lastTime) / 1000.0;
if (runningIndex == -1) {
// 只剩下最后一个阻塞进程未执行完，则该进程休眠1秒后唤醒
Thread.sleep(1000);
runningIndex = blockIndex;
pcb[runningIndex].status = "Waiting";
blocked = 0;
} else if (intervalTime > 2.0) {
// 有进程属于阻塞状态时，满足阻塞时间大于2s则唤醒进程
if (blockIndex != -1) {
pcb[blockIndex].status = "Waiting";
blocked = 0;
}
}
}
}
/*启动进程调度*/
public void run() throws InterruptedException {
System.out.println();
System.out.println("------------------------------------------------------");
System.out.println(" 课程设计：进程管理系统 ");
System.out.println("------------------------------------------------------");
initData();
timeSlice=2;
/* 使用快速排序算法，按照先来先服务的原则排序 */
quickSortByArriTime(0, PROCESS_NUM - 1);
beginTime = System.currentTimeMillis();
lastTime = System.currentTimeMillis();
while (true) {
dispatch();
if (isFinishALLProcess()) { // 如果所有进程都已经完成调度，则退出循环
break;
}
}
print();
System.out.print("------------------所有进程运行结束------------------\n\n");
}
}