|
代码在最后
目录
实验一? 进程调度（时间片）
实验二? 动态分区分配方式的模拟
实验三? 请求调页存储管理方式的模拟
实验四? 扩展，银行家算法，磁盘调度算法，多级反馈队列调度算法，位示图
源代码
时间片调度算法
页面置换算法LRU
磁盘调度算法
进程调度短作业优先算法
多级反馈队列（python实现）
????????高响应比算法
动态分区分配(首次适应算法)
位示图
动态分区分配（循环首次适应）
银行家算法
最佳适应算法
最佳置换算法
实验一? 进程调度（时间片）
一、实验目的
编写并调试一个模拟的进程调度程序，以加深对进程的概念及进程调度算法的理解。
时间片轮转算法，短作业优先算法，高响应比算法
根据给出的题目以及指定算法， 求解过程
- 时间片轮转算法
时间片轮转算法在运行前设置好时间片长度，让就绪队列中的每个进程每次仅运行一个时间片，则在队列中的进程都可均匀的得到运行。
-
- 调试运行“时间片轮转”调度算法，给出运行结果。采用“时间片轮转”调度算法对进程进行调度。每个进程有一个进程控制块（ PCB）表示。
- 进程控制块可以包含如下信息：进程名、到达时间、需要运行时间、已用CPU时间、进程状态等等。 每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。
- 显示进程运行过程，以及进程的带权周转时间和系统的平均带权周转时间。
- 短作业优先算法
短作业优先算法（SJF）以作业的长短计算优先级，作业越短，其优先级越高。从外存的作业调度队列中选择若干个估计运行时间最短的作业，优先将他们调入内存。
-
- 调试运行“短进程优先调度”调度算法，给出运行结果。
- 采用“时间片轮转”调度算法对进程进行调度。每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、到达时间、需要运行时间、已用CPU时间、进程状态等等。 每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。
- 显示进程运行过程，以及进程的带权周转时间和系统的平均带权周转时间。
- 高响应比算法
高响应比算法通过对每个作业采用动态优先级，即每个作业的优先级随着等待时间的延长而增加
-
- 调试运行“高响应比”调度算法，给出运行结果。
- 采用“高响应比”调度算法对进程进行调度。每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、到达时间、需要运行时间、已用CPU时间、进程状态等等。 每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。
- 显示进程运行过程，以及进程的带权周转时间和系统的平均带权周转时间。
- 时间片轮转算法
输入结构体相关数据后，更根据输入的结构体中，进程的到达时间进行排序，使得得到链表为按照到达时间顺序。通过头指针ready指向链表表头，开始遍历链表。通过p指向reday，并让ready指向下一个元素，根据设定的时间片长度，每次运行指定时间片时间。每次运行完时间片后，重新检查链表，检查是否有进程到达， 将其状态改为已经到达。如此反复，直到ready指向为空，则程序结束。
- 短作业优先算法
根据输入建立到达队列。对到达队列按照到达运行时间排序，并检查是否到达。若进程到达，则置到达标志位1，在运行过程中，每个时间都对队列检查一遍是否达到，并对标志位更改。且每次运行过程中，从对头遍历，若进程到达并且且未完成，则运行改进程。如此反复，直到进程全部运行完成。
- 高响应比算法
??? 根据输入建立到达队列，对到达队列按照达到时间排序，并检查是否到达，更新标志位。用给定公式计算优先级。每运行一个时间，则对全队更新优先级并检查是否到达。每次检查全队，选取优先级最高并且达到的进程执行。如此反复，直到全部进程运行完成。
- 时间片轮转算法
struct pcb { /* 定义进程控制块PCB */
??? char name[10];
??? char state;? //状态
??? int atime;?? //到达时间
??? int ntime;?? //需要时间
??? int rtime;?? //已运行时间
??? struct pcb* link;
}*ready = NULL, * p;
typedef struct pcb PCB;
- 短作业优先算法
struct pcb { /* 定义进程控制块PCB */
??? char name[10];
??? char state;? //状态
??? int atime;?? //到达时间
??? int ntime;?? //需要时间
??? int rtime;?? //已运行时间
??? int over;? //0未完成，1已完成
??? int a_t;??? //是否到达，1到达，0未到达
??? struct pcb* link;
}*ready = NULL, * p;
typedef struct pcb PCB;
int h = 0;?? //h表示当前运行时间
int have_run = 0;//已经运行的进程数量
float ans = 0;//记录周转时间和
- 高响应比算法
struct pcb { /* 定义进程控制块PCB */
??? char name[10];
??? char state;? //状态
??? int atime;?? //到达时间
??? int ntime;?? //需要时间
??? int rtime;?? //已运行时间
??? int over;? //0未完成，1已完成
??? int a_t;??? //是否到达，1到达，0未到达
??? float pri;
??? struct pcb* link;
}*ready = NULL, * p;
typedef struct pcb PCB;
int h = 0;?? //h表示当前运行时间
int have_run = 0;//已经运行的进程数量
float ans = 0;//记录周转时间和
实验二? 动态分区分配方式的模拟
一、实验目的
了解动态分区分配方式中的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。
首次适应算法，最佳适应算法.
二、实验内容
? ?空
???
三、实现思路
??? 1. 首次适应算法
??? 首次适算法要求从链首开始寻找，直到找到一个大小能满足要求的空闲分区为止，再按照作业的大小从该分区中划出一块内存。
??? 根据给定内存建立初始空间链表，初始空间只有一个区。设立表头指针，表尾指针。每次遍历从表头开始遍历，每当找到一个空闲的分区，则在当前区前建立新区，并分配空间，对当前区减少对应分配的空间。若恰好完全分配，则销毁当前区。当释放时，若相邻两个区都空闲，则进行合并变为一个区。释放过程则根据输入找到对应作业，并释放该分区（标志位置0），并进行合并检查
??? 2.最佳适应算法
??? 最佳适应算法每次从表头开始比遍历， 找出最小且能放入当前进程的区。
??? 根据给定内存建立初始空间链表，初始空间只有一个区。设立表头指针，表尾指针。每次开始从表头开始搜索，找出当前最适和分区，并分配，分配过程以及释放过程与首次适应算法相同。
四、主要的数据结构
??? 1.首次适应算法
??? #define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1??? //完成
#define ERROR 0 //出错
typedef int Status;
int flag;
typedef struct freearea//定义一个空闲区说明表结构
{
??? int name;
??? int size;?? //分区大小
??? int address; //分区地址
??? int state;?? //状态? 1占用，0空闲
}ElemType;
// 线性表的双向链表存储结构
typedef struct DuLNode
{
??? ElemType data;
??? struct DuLNode* prior; //前趋指针
??? struct DuLNode* next;? //后继指针
}DuLNode, * DuLinkList;
DuLinkList head = NULL; //头结点
DuLinkList end = NULL;? //尾结点
DuLinkList node_run;//初始链表空间节点
//初始化链表
??? 2.最佳适应算法
#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1??? //完成
#define ERROR 0 //出错
typedef int Status;
int flag;
typedef struct freearea//定义一个空闲区说明表结构
{
??? int name;
??? int size;?? //分区大小
??? int address; //分区地址
??? int state;?? //状态? 1占用，0空闲
}ElemType;
// 线性表的双向链表存储结构
typedef struct DuLNode
{
??? ElemType data;
??? struct DuLNode* prior; //前趋指针
??? struct DuLNode* next;? //后继指针
}DuLNode, * DuLinkList;
DuLinkList head = NULL; //头结点
DuLinkList end = NULL;? //尾结点
DuLinkList node_run;//初始链表空间节点
实验三? 请求调页存储管理方式的模拟
一、实验目的
通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。
二、实验内容
空
三、实现思路
??? 本题中生成随机序列时采用的为c语言中的rand（）函数，该函数为伪随机代码。故在多次运行中显示同一序列，但在单次运行中的表现时随机的。这导致了每次运行结果都相同。
1.OPT（最佳置换算法）
??? 最佳置换算法将未来最长时间内不再被访问的页面淘汰。在本题中，提前给出运行的页面号引串。故若块未满，则直接插入。若块满，则建立一个n（n为块的容纳量）项的一维数组，记录当前块在未来出现第一次的位置。选取位置最远（即最久出现）的页面淘汰并完成插入操作。
- lru(最近最久未使用)
lru算法通过淘汰最近最久未使用的页面。在运行过程中，若块未满，则直接插入。若块满，通过查找每个页面的属性t，选择t最大的页面淘汰并完成插入。每次完成页面操作后，更新块中的t属性。（t为块中该页面上次被访问到现在的时间）
四、主要的数据结构
??? 1.OPT
??? float count = 0;??? //缺页次数
int instruction_addr[320];??? //指令地址数组
int page_addr[320];???? //页地址数组
typedef struct Data //数据域
{
??? int page_num;???? //装进的用户虚存页号
??? int block_num;??? //块号
} Data;
typedef struct BlockNode
{
??? Data data;
??? struct BlockNode* next;
}Block, * BlockList;
BlockList block1;?? //内存块
BlockList block2;
BlockList block3;
??? 2.LRU
??? float count = 0;??? //缺页次数
int instruction_addr[320];??? //指令地址数组
int page_addr[320];???? //页地址数组
typedef struct Data //数据域
{
??? int page_num;???? //装进的用户虚存页号
??? int block_num;??? //块号
??? int t;??????? //自上次被访问以来所经历的时间
} Data;
typedef struct BlockNode
{
??? Data data;
??? struct BlockNode* next;
}Block, * BlockList;
BlockList block1;??? //内存块
BlockList block2;
BlockList block3;
实验四? 扩展，银行家算法，磁盘调度算法，多级反馈队列调度算法，位示图
1.银行家算法
??? 银行家算法即一种防止死锁的算法， 主要同通过不断进行安全性检查找出合适的序列。
??? 首先初始化数据，输入进程数量以及每个进程allocation分配状况，还需要分配的资源need，以及各个资源的总数。通过程序计算出各个进程需要的资源总数MAX以及目前各个资源的剩余量（Avaliable）。
??? 当发出请求时，先检查当前请求是否超出进程的需求量或可用资源是否不能满足需求，是则直接报错结束。否则进入下一步。下一步进行安全性检查，当前进程已经可以满足要求，对后续进程进行检查。设所有进程Finish都为false，顺序检查进程，是否存在可以分配的进程，若存在则分配，并将该进程Finish设置为true，并反复执行直到所有都为true。若成功让所有都为ture，则安全性检查通过，否则失败。
??????
??? 2.磁盘调度算法（SSTF,SCAN）
SSTF访问要求要访问的磁道与当前磁道距离最近。故从开始时，每次都先检查与当前磁道距离最短的磁道，并将其定为下一个移动的目标。
SCAN要访问的下一个磁道为离当前磁道最近的磁道。且满足先自里向外直到最外没有其他磁道，再从外到里。设置初始磁道。先对所有磁道按照从小到达排序。每次运行的时候，先从里到外，每次顺序查找第一个比当前磁道大的磁道。再从初始磁道的位置从大到小遍历。
3. 多级反馈队列调度算法
设置多个就绪队列，每个队列设置不同的优先级，第一个队列优先级最高，往后逐队降低。且第一个队列时间片最短，往后不断增加（每队增加一倍）。
每个队列按照FCFS算法调度，在当前队列运行一个时间片，若未完成则进入下一个时间片。并且，只当上级队全空时，下级队才开始运行。若下级队运行的时候上级队有进程到达，则下级队将当前进程放入队尾。
4. 位示图
??? 采用图标的方式（二进制位）表示磁盘情况。从磁盘头部开始，找出大小合适的部分分配。程序中，通过对当前位置向好查找size（请求大小）位，判断是否存在空间分配。释放时，直接将对应部分位置1。
四、主要的数据结构
??? 1.银行家算法
typedef struct Res
{
??? int a;
??? int b;
??? int c;
??? int d;
}Res;
typedef struct Pro
{
??? Res max;????? //所需资源总数
??? Res allocation;??? //已分配
??? Res need;???? //剩余需求数
??? Res work;
??? Res work_allocation;
??? Res request;????? //资源请求
??? int finish;?? //是否完成
}Pro;
typedef struct All_P
{
??? Res resourse_MAX;??? //各资源总数
??? Res total_resourse;??? //已分配资源总数
??? Pro rocess[PROCESS_MAX];
??? Res available;??? //剩余资源总数
??? int size;???? //进程数总数
??? int array[PROCESS_MAX];??? //安全序列号（从0开始）
}All_P;
??? 2.磁盘调度算法（SSTF,SCAN）
typedef struct Disk
{
? int num[MAX_count];??? //作业磁道号
? int flag[MAX_count];?? //是否被访问，0表示无，1表示有
}disk;
3.多级反馈队列调度算法(python)
class Pcb:
??? def __init__(self, name, atime, ntime):
??????? self.name = name
??????? self.atime = atime
??????? self.ntime = ntime
??????? self.rtime = 0? # 已经运行的时间
??????? self.state = wait
4.位示图
bool map[m][n];
typedef struct fileLNode
{
??? char name[10];
??? int i; int j;
??? int size;
??? int begin;
??? int end;
??? struct fileLNode* prior;
??? struct fileLNode* next;
}fileLNode, * fileLinkList;
fileLinkList file_first, file_last;
fileLinkList temp;
源代码
时间片调度算法
#include "stdio.h"?
#include <stdlib.h>?
#include <conio.h>?
#define getpch(type) (type*)malloc(sizeof(type))?
#define NULL 0?
struct pcb { /* 定义进程控制块PCB */
?? ?char name[10];
?? ?char state;?? ?//状态
?? ?int atime;?? ?//到达时间
?? ?int ntime;?? ?//需要时间
?? ?int rtime;?? ?//已运行时间
?? ?struct pcb* link;
}*ready = NULL, * p;
typedef struct pcb PCB;
float ans = 0; //记录周转时间之和
int h = 0;?? ?//h表示当前运行时间
int cpu_t = 3; ?//表示时间片?
void sort()
{
?? ?PCB* first, * second;
?? ?int insert = 0;
?? ?if ((ready == NULL) || (h < ready->atime))?? ?//若为就绪队列为空，则p仍然是就绪队列队头
?? ?{
?? ??? ?p->link = ready;
?? ??? ?ready = p;
?? ?}
?? ?else
?? ?{
?? ??? ?first = ready;
?? ??? ?second = first->link;
?? ??? ?while (second != NULL)
?? ??? ?{
?? ??? ??? ?if ((h < second->atime))
?? ??? ??? ?{
?? ??? ??? ??? ?p->link = second;
?? ??? ??? ??? ?first->link = p;
?? ??? ??? ??? ?second = NULL;
?? ??? ??? ??? ?insert = 1;
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?first = first->link;
?? ??? ??? ??? ?second = second->link;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?if (insert == 0) first->link = p;
?? ?}
}
void input_sort()?? ?//根据到达时间建立就绪队列
{
?? ?PCB* first, * second;
?? ?int insert = 0;
?? ?if ((ready == NULL) || ((p->atime) < (ready->atime)))
?? ?{
?? ??? ?p->link = ready;
?? ??? ?ready = p;
?? ?}
?? ?else
?? ?{
?? ??? ?first = ready;
?? ??? ?second = first->link;
?? ??? ?while (second != NULL)
?? ??? ?{
?? ??? ??? ?if ((p->atime) < (second->atime))
?? ??? ??? ?{?
?? ??? ??? ??? ?p->link = second;
?? ??? ??? ??? ?first->link = p;
?? ??? ??? ??? ?second = NULL;
?? ??? ??? ??? ?insert = 1;
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?first = first->link;
?? ??? ??? ??? ?second = second->link;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?if (insert == 0) first->link = p;
?? ?}
}
void input() /* 建立进程控制块函数*/
{
?? ?int i, num;
?? ?system("cls");
?? ?printf("\n 请输入进程数量:");
?? ?scanf_s("%d", &num);
?? ?for (i = 0; i < num; i++)
?? ?{
?? ??? ?printf("\n 进程号No.%d:\n", i);
?? ??? ?p = getpch(PCB);
?? ??? ?printf("\n 输入进程名:");
?? ??? ?scanf_s("%s", p->name, 20);
?? ??? ?printf("\n 输入进程到达时间:");
?? ??? ?scanf_s("%d", &p->atime);
?? ??? ?printf("\n 输入进程运行时间:");
?? ??? ?scanf_s("%d", &p->ntime);
?? ??? ?printf("\n");
?? ??? ?p->rtime = 0; p->state = 'w';
?? ??? ?p->link = NULL;
?? ??? ?input_sort();
?? ?}
}
int space()
{
?? ?int i = 0;
?? ?PCB* pr = ready;
?? ?while (pr != NULL)
?? ?{
?? ??? ?i++;
?? ??? ?pr = pr->link;
?? ?}
?? ?return(i);
}
void disp(PCB* pr) /*建立进程显示函数,用于显示当前进程*/
{
?? ?printf("\n 进程 \t 状态 \t 到达时间 \t 服务时间 \t 已运行时间 \n");
?? ?printf("|%s\t", pr->name);
?? ?printf("|%c\t", pr->state);
?? ?printf("|%d\t", pr->atime);
?? ?printf("\t|%d\t", pr->ntime);
?? ?printf("\t|%d\t", pr->rtime);
?? ?printf("\n");
}
void check() /* 建立进程查看函数 */
{
?? ?PCB* pr;
?? ?printf("\n **** 当前正在运行的进程是:%s", p->name); /*显示当前运行进程*/
?? ?disp(p);
?? ?pr = ready;
?? ?printf("\n ****当前就绪队列状态为:\n"); /*显示就绪队列状态*/
?? ?while (pr != NULL && pr->atime <= h)
?? ?{
?? ??? ?disp(pr);
?? ??? ?pr = pr->link;
?? ?}
}
void destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/
{
?? ?printf("\n 进程 [%s] 已完成,其周转时间为:%d,其带权周转时间为:%.2f\n", p->name, h - p->atime, (h - p->atime * 1.0) / p->rtime);
?? ?ans += (h - p->atime * 1.0) / p->ntime;
?? ?free(p);
}
void running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/
{
?? ?for (int i = 1; i <= cpu_t; i++)?
?? ?{
?? ??? ?printf("\n The execute number:%d \n", h);
?? ??? ?check();
?? ??? ?(p->rtime)++;
?? ??? ?h += 1;
?? ??? ?if (p->rtime == p->ntime)
?? ??? ?{
?? ??? ??? ?destroy(); /* 调用destroy函数*/
?? ??? ??? ?system("pause");
?? ??? ??? ?system("cls");
?? ??? ??? ?return;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?p->state = 'w';
?? ??? ?}
?? ??? ?printf("\n 按任一键继续......");
?? ??? ?system("pause");
?? ??? ?system("cls");
?? ?}
?? ?sort();
}
void main() /*主函数*/
{
?? ?int len;
?? ?input();
?? ?len = space();
?? ?while ((len != 0) && (ready != NULL))
?? ?{
?? ??? ?getchar();
?? ??? ?p = ready;
?? ??? ?ready = p->link;
?? ??? ?p->link = NULL;
?? ??? ?p->state = 'R';
?? ??? ?running();
?? ?}
?? ?printf("\n\n 进程已经完成.平均带权周转时间为:%.3f\n", ans / len);
?? ?getchar();
?? ?getchar();
}
?
页面置换算法LRU
#include <stdio.h>
#include <stdlib.h>
float count = 0; ? ?//缺页次数
int instruction_addr[320]; ? ?//指令地址数组
int page_addr[320]; ? ? //页地址数组
typedef struct Data //数据域
{
? ? int page_num; ? ? //装进的用户虚存页号
? ? int block_num; ? ?//块号
? ? int t; ? ? ? ?//自上次被访问以来所经历的时间
} Data;
typedef struct BlockNode
{
? ? Data data;
? ? struct BlockNode* next;
}Block, * BlockList;
BlockList block1; ? ?//内存块
BlockList block2;
BlockList block3;
BlockList block4;
void initialize() ? ? ?//初始化
{
? ? block1 = (BlockList)malloc(sizeof(Block));
? ? block2 = (BlockList)malloc(sizeof(Block));
? ? block3 = (BlockList)malloc(sizeof(Block));
? ? //block4 = (BlockList)malloc(sizeof(Block));
? ? block1->data.page_num = -1;
? ? block2->data.page_num = -1;
? ? block3->data.page_num = -1;
? ? //block4->data.page_num = -1;
? ? block1->data.block_num = 0;
? ? block2->data.block_num = 1;
? ? block3->data.block_num = 2;
? // ?block4->data.block_num = 3;
? ? block1->data.t = 0;
? ? block2->data.t = 0;
? ? block3->data.t = 0;
? ?// block4->data.t = 0;
? ? block1->next = block2; ? ?//循环链表
? ? block2->next = block3;
? ? block3->next = block1;
? ?// block4->next = block1;
? ? //地址生成原则，50%的指令是顺序执行的，25%的指令是均匀分布在前地址部分，25%的指令是均匀分布在后地址部分
? ? for (int i = 0; i < 320;) ? ?//初始化地址
? ? {
? ? ? ? int m0 = rand() % 320; ? ? //步骤一，[0,319]随机选取一个起点m0
? ? ? ? instruction_addr[i] = m0 + 1; ? ? ? //步骤二，顺序执行一条指令，m0+1
? ? ? ? page_addr[i] = instruction_addr[i] / 10; ? //计算块地址
? ? ? ? i++;
? ? ? ? int m1 = rand() % (m0 - 1); ? ? ?//步骤三，在前地址[0,m0-1]中随机选取一条指令并执行，记为m1
? ? ? ? instruction_addr[i] = m1; ? ? //计算块地址
? ? ? ? page_addr[i] = m1 / 10;
? ? ? ? i++;
? ? ? ? instruction_addr[i] = m1 + 1; ? ? ?//步骤四，顺序执行一条指令，m1+1
? ? ? ? page_addr[i] = instruction_addr[i] / 10; ? ? ?//计算块地址
? ? ? ? i++;
? ? ? ? int m2 = rand() % (319 - m1 - 1) + m1 + 2; ? ? ?//步骤五，在后地址[m1+2,319]中随机选取一条指令并执行，记为m2
? ? ? ? instruction_addr[i] = m2; ? ? ?//计算块地址
? ? ? ? page_addr[i] = m2 / 10;
? ? ? ? i++;
? ? ? ? instruction_addr[i] = m2 + 1; ? ? ? ? ? ? ? //步骤六，顺序执行一条指令，m2+1
? ? ? ? page_addr[i] = instruction_addr[i] / 10; ? ? ?//计算块地址
? ? ? ? i++;
? ? }
}
int LRU(int page_num_0, int cur_addr)
{
? ? Block* p = block1;
? ? for (int i = 0; i < 3; i++)
? ? {
? ? ? ? if (p->data.page_num == -1) ? ?//块为空闲
? ? ? ? {
? ? ? ? ? ? p->data.page_num = page_num_0;
? ? ? ? ? ? count++; ? ? ? ?//计算缺页次数
? ? ? ? ? ? printf("指令逻辑地址:%d \n", cur_addr);
? ? ? ? ? ? printf("内存中不存在该指令\n");
? ? ? ? ? ? printf("进行页面置换操作：\n");
? ? ? ? ? ? printf("页面置换完成。\n%d页%d条物理地址为:%d块%d条 \n\n",
? ? ? ? ? ? ? ? page_num_0, (cur_addr % 10), p->data.block_num, (cur_addr % 10));
? ? ? ? ? ? printf("------------------------------------------------------------------------------\n");
? ? ? ? ? ? //将所有块经历的时间+1，再将当前访问块的时间置0
? ? ? ? ? ? for (int i = 0; i < 3; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? p->data.t++;
? ? ? ? ? ? ? ? p = p->next;
? ? ? ? ? ? }
? ? ? ? ? ? p->data.t = 0;
? ? ? ? ? ? return 1;
? ? ? ? }
? ? ? ? if (p->data.page_num == page_num_0)
? ? ? ? {
? ? ? ? ? ? printf("指令逻辑地址:%d \n", cur_addr);
? ? ? ? ? ? printf("指令已在内存中\n");
? ? ? ? ? ? printf("无需置换\n ?%d页%d条物理地址为:%d块%d条 \n\n",
? ? ? ? ? ? ? ? page_num_0, (cur_addr % 10), p->data.block_num, (cur_addr % 10));
? ? ? ? ? ? printf("------------------------------------------------------------------------------\n");
? ? ? ? ? ? for (int i = 0; i < 3; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? p->data.t++;
? ? ? ? ? ? ? ? p = p->next;
? ? ? ? ? ? }
? ? ? ? ? ? p->data.t = 0;
? ? ? ? ? ? return 1;
? ? ? ? }
? ? ? ? p = p->next;
? ? }
? ? int largestT = -1; ? ? //最近最久未使用时间
? ? for (int i = 0; i < 3; i++) ? ?//找到最近最久未使用时间
? ? {
? ? ? ? if (p->data.t > largestT)
? ? ? ? {
? ? ? ? ? ? largestT = p->data.t;
? ? ? ? }
? ? ? ? p = p->next;
? ? }
? ? for (int i = 0; i < 3; i++)
? ? {
? ? ? ? if (p->data.t == largestT)
? ? ? ? {
? ? ? ? ? ? for (int j = 0; j < 3; j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? p->data.t++;
? ? ? ? ? ? ? ? p = p->next;
? ? ? ? ? ? }
? ? ? ? ? ? p->data.page_num = page_num_0;
? ? ? ? ? ? count++;
? ? ? ? ? ? p->data.t = 0;
? ? ? ? ? ? printf("指令的逻辑地址:%d \n", cur_addr);
? ? ? ? ? ? printf("指令未装入内存且内存块已满\n");
? ? ? ? ? ? printf("进行页面置换操作：\n");
? ? ? ? ? ? printf("页面置换完成。\n ? %d页%d条物理地址为:%d块%d条 \n\n",
? ? ? ? ? ? ? ? page_num_0, (cur_addr % 10), p->data.block_num, (cur_addr % 10));
? ? ? ? ? ? printf("------------------------------------------------------------------------------\n");
? ? ? ? ? ? return 1;
? ? ? ? }
? ? ? ? p = p->next;
? ? }
? ? return 1;
}
void calculate() //计算缺页率
{
? ? for (int i = 0; i < 320; i++)
? ? ? ? LRU(page_addr[i], instruction_addr[i]);
? ? printf("\n");
? ? printf("缺页次数：%.0f\n", count);
? ? printf("缺页率：%.3f \n", count / 320);
}
int main()
{
? ? printf("---------LRU----------\n\n");
? ? initialize();
? ? calculate();
? ? return 0;
}
?
磁盘调度算法
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define MAX_count 12
typedef struct Disk {
int num[MAX_count]; //作业磁道号
int flag[MAX_count]; //标志是否被访问，0表示没有被访问，1表示被访问过
}disk;
int max_position(int position, int disk[]) //求磁盘作业的最大磁道号
{
int max_position = -1;
for (int i = 0; i < MAX_count; i++)
{
if (disk[i] > max_position)
max_position = disk[i];
if (position > max_position && i == MAX_count - 1)
max_position = position;
}
max_position = 399;
return max_position;
}
void SSTF(int position, int SSTF[], int flag[])
{
int min = 0, temp = 0, tag = 0; //tag记录完成个数
float count = 0;
printf("最短寻道时间优先调度\n");
printf("SSTF：初始磁道%d\n", position);
printf("下一个磁道号\t移动的磁道数\n");
while (1)
{
min = max_position(position, SSTF);
for (int i = 0; i < MAX_count; i++) //选出移动距离最少的磁盘作业
{
if ((min > abs(position - SSTF[i])) && flag[i] == 0)
{
min = abs(position - SSTF[i]);
temp = i;
}
}
flag[temp] = 1;
printf("%d\t\t\t%d\n", SSTF[temp], abs(position - SSTF[temp]));
count += min;
position = SSTF[temp]; //下一个位置
tag++;
if (tag == MAX_count)
break;
}
printf("平均寻道长度:%.3f\n", count / MAX_count);
printf("--------------------------------------------------------\n");
}
int sort(int* b) //冒泡排序，从小到大
{
int i, j;
int t;
for (i = 0; i < MAX_count - 1; i++)
for (j = i + 1; j < MAX_count; j++)
{
if (b[i] > b[j])
{
t = b[i];
b[i] = b[j];
b[j] = t;
}
}
return *b;
}
void SCANmax(int position, int* SCAN)
{
int temp;
float count = 0;
sort(SCAN);
printf("电梯调度算法\n");
printf("SCAN:初始磁道%d\n(磁道递增)\n", position);
printf("下一个磁道号\t移动的磁道数\n");
for (int i = 0; i < MAX_count; i++)
{
if (position < SCAN[i]) //由于是自里向外移动，因此需要找到第一个比初始位置大的磁道号
{
temp = i;
break;
}
}
for (int i = temp; i < MAX_count; i++) //输出比初始位置大的磁道号
{
printf("%d\t\t\t%d\n", SCAN[i], abs(position - SCAN[i]));
count += abs(position - SCAN[i]);
position = SCAN[i];
}
for (int i = temp - 1; i >= 0; i--) //输出比初始位置小的磁道号，从比初始位置小，但最接近的磁道开始
{
printf("%d\t\t\t%d\n", SCAN[i], abs(position - SCAN[i]));
count += abs(position - SCAN[i]);
position = SCAN[i];
}
printf("平均寻道长度:%.3f\n", count / MAX_count);
printf("--------------------------------------------------------\n");
}
int main()
{
int position; //初始位置
struct Disk d;
while (1)
{
for (int i = 0; i < MAX_count; i++)
d.flag[i] = 0; //初始均为未被访问
printf("请输入磁道初始的位置：");
scanf("%d", &position);
printf("接下来请输入%d个磁盘请求。\n\n", MAX_count);
for (int i = 0; i < MAX_count; i++)
{
printf("请输入第%d个磁盘请求:", i + 1);
scanf("%d", &d.num[i]);
}
printf("\n");
SSTF(position, d.num, d.flag);
SCANmax(position, d.num);
}
return 0;
}
进程调度短作业优先算法
#include "stdio.h"
#include <stdlib.h>
#include <conio.h>
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0
struct pcb { /* 定义进程控制块PCB */
char name[10];
char state; //状态
int atime; //到达时间
int ntime; //需要时间
int rtime; //已运行时间
int over; //0未完成，1已完成
int a_t; //是否到达，1到达，0未到达
struct pcb* link;
}*ready = NULL, * p;
typedef struct pcb PCB;
int h = 0; //h表示当前运行时间
int have_run = 0;//已经运行的进程数量
float ans = 0;//记录周转时间和
//根据到达时间建立就绪队列
void input_sort()
{
PCB* first, * second;
int insert = 0;
if ((ready == NULL) || ((p->atime) < (ready->atime)))
{
p->link = ready;
ready = p;
}
else
{
first = ready;
second = first->link;
while (second != NULL)
{
if ((p->atime) < (second->atime))
{ /*插入到当前进程前面*/
p->link = second;
first->link = p;
second = NULL;
insert = 1;
}
else
{
first = first->link;
second = second->link;
}
}
if (insert == 0) first->link = p;
}
}
/* 建立进程控制块函数*/
void input()
{
int i, num;
system("cls");
printf("\n 请输入进程数量:");
scanf_s("%d", &num);
for (i = 0; i < num; i++)
{
printf("\n 进程号No.%d:\n", i);
p = getpch(PCB);
printf("\n 输入进程名:");
scanf_s("%s", p->name, 20);
printf("\n 输入进程到达时间:");
scanf_s("%d", &p->atime);
printf("\n 输入进程运行时间:");
scanf_s("%d", &p->ntime);
printf("\n");
p->rtime = 0; p->state = 'w';
p->link = NULL;
p->a_t = 0;
p->over = 0;
input_sort();
}
}
//计算长度
int space()
{
int i = 0;
PCB* pr = ready;
while (pr != NULL)
{
i++;
pr = pr->link;
}
return(i);
}
//进程显示函数,用于显示当前进程
void disp(PCB* pr)
{
printf("\n 进程 \t 状态 \t 到达时间 \t 服务时间 \t 已运行时间 \n");
printf("|%s\t", pr->name);
printf("|%c\t", pr->state);
printf("|%d\t", pr->atime);
printf("\t|%d\t", pr->ntime);
printf("\t|%d\t", pr->rtime);
printf("\n");
}
//进程查看函数
void check()
{
PCB* pr;
printf("\n **** 当前正在运行的进程是:%s", p->name); /*显示当前运行进程*/
disp(p);
pr = ready;
printf("\n ****当前就绪队列状态为:\n"); /*显示就绪队列状态*/
while (pr != NULL && pr->atime <= h)
{
disp(pr);
pr = pr->link;
}
}
//检查节点到达,返回到达的节点数
int check_arrive()
{
PCB* first;
int num=0;
first = ready;//指向头节点
while (first != NULL)
{
if ((first->atime <= h) && (first->a_t == 0))
{
first->a_t = 1;
}
if (first->atime <= h)
num++;
first = first->link;
}
return num;
}
void running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/
{
int num;
num = check_arrive();//检查到达数量
PCB* first,*min;
min = ready;
first = ready;
int temp_n=0,min_n=-1;//temp_n表示已经到达数量中寻找，min_n表示当前最小
while (temp_n < num)
{
if (first->over == 0 && min_n == -1)
{
min_n = first->ntime;
min = first;
}
if (first->over == 0 && min_n != -1 && first->ntime < min_n)
{
min_n = first->ntime;
min = first;
}
first = first->link;
temp_n++;
}
if (min != -1)
{
h = h + min->ntime;
min->over = 1;
min->rtime = min->ntime;
have_run++;
disp(min);
ans += (h - min->atime * 1.0) / min->ntime;
printf("\n 进程 [%s] 已完成,其周转时间为:%d,其带权周转时间为:%.2f，完成时间为：%d\n", min->name, h - min->atime, (h - min->atime * 1.0) / min->rtime,h);
printf("------------------------------------------------");
}
else
{
h = h + 1;
}
}
//显示还未完成的队伍
void rest()
{
PCB* temp;
temp = ready;
while (temp != NULL)
{
if (temp->over == 0 && temp->a_t == 1)
{
disp(temp);
}
temp = temp->link;
}
}
void main() /*主函数*/
{
int len;
input(); //根据到达时间建立队列 ready为头节点
len = space();
while (have_run != len)
{
getchar();;
running();
rest();
system("pause");
system("cls");
}
printf("总运行时间：%d", h);
printf("\n\n 进程已经完成.平均带权周转时间为:%.3f\n", (ans / len));
getchar();
getchar();
}
?
多级反馈队列（python实现）
import queue as Q
run = 'r'
wait = 'w'
finish = 'f'
class Pcb:
def __init__(self, name, atime, ntime):
self.name = name
self.atime = atime
self.ntime = ntime
self.rtime = 0 # 已经运行的时间
self.state = wait
def into_queue():
global tmp, tmp_index
t = tmp_index
for i in range(t, len(tmp)):
if tmp[i].atime <= h:
queue_list[0].put(tmp[i])
tmp_index = i + 1
else:
return
if __name__ == '__main__':
print('进程数量:')
n = int(input())
print('设置队列数量:')
q_num = int(input())
queue_list = [Q.Queue() for _ in range(q_num)]
tmp = []
for _ in range(n):
name = input()
atime = int(input())
ntime = int(input())
pcb = Pcb(name, atime, ntime)
tmp.append(pcb)
tmp.sort(key=lambda x: x.atime) #按照到达时间排序
tmp_index = 0
h = 0 # 此时运行时间
i
ans = 0
flag = 1
while flag:
flag = 0
for i in range(q_num):
queue = queue_list[i]
if not queue.empty():
time = pow(2, i)
if i != q_num - 1:
next_queue = queue_list[i + 1]
pcb = queue.get()
print('\n当前时间', h)
print('当前进程', pcb.name, '进程已运行时间', pcb.rtime)
if pcb.ntime - pcb.rtime > time: # 如果该时间片无法运行完该进程
pcb.rtime += time
print('此次运行时间:', time)
h += time
if i != q_num - 1:
next_queue.put(pcb)
else:
queue.put(pcb)
else:
h += pcb.ntime - pcb.rtime
print('此次运行时间:', pcb.ntime - pcb.rtime)
pcb.rtime = pcb.ntime
print('\n进程', pcb.name, '已完成')
print('其周转时间为', h - pcb.atime, '\t', '带权周转时间:', (h - pcb.atime) / pcb.ntime)
ans += (h - pcb.atime) / pcb.ntime
if tmp_index != n:
into_queue()
break
for queue in queue_list:
if not queue.empty():
flag = 1
break
print('结束\n平均带权周转时间为:{:.3f}'.format(ans / n))
高响应比算法
#include "stdio.h"
#include <stdlib.h>
#include <conio.h>
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0
struct pcb { /* 定义进程控制块PCB */
char name[10];
char state; //状态
int atime; //到达时间
int ntime; //需要时间
int rtime; //已运行时间
int over; //0未完成，1已完成
int a_t; //是否到达，1到达，0未到达
float pri;
struct pcb* link;
}*ready = NULL, * p;
typedef struct pcb PCB;
int h = 0; //h表示当前运行时间
int have_run = 0;//已经运行的进程数量
float ans = 0;//记录周转时间和
//根据到达时间建立就绪队列
void input_sort()
{
PCB* first, * second;
int insert = 0;
if ((ready == NULL) || ((p->atime) < (ready->atime)))
{
p->link = ready;
ready = p;
}
else
{
first = ready;
second = first->link;
while (second != NULL)
{
if ((p->atime) < (second->atime))
{ /*插入到当前进程前面*/
p->link = second;
first->link = p;
second = NULL;
insert = 1;
}
else
{
first = first->link;
second = second->link;
}
}
if (insert == 0) first->link = p;
}
}
/* 建立进程控制块函数*/
void input()
{
int i, num;
system("cls");
printf("\n 请输入进程数量:");
scanf_s("%d", &num);
for (i = 0; i < num; i++)
{
printf("\n 进程号No.%d:\n", i);
p = getpch(PCB);
printf("\n 输入进程名:");
scanf_s("%s", p->name, 20);
printf("\n 输入进程到达时间:");
scanf_s("%d", &p->atime);
printf("\n 输入进程运行时间:");
scanf_s("%d", &p->ntime);
printf("\n");
p->rtime = 0; p->state = 'w';
p->link = NULL;
p->a_t = 0;
p->over = 0;
p->pri =(float)p->ntime/p->ntime;
input_sort();
}
}
//计算长度
int space()
{
int i = 0;
PCB* pr = ready;
while (pr != NULL)
{
i++;
pr = pr->link;
}
return(i);
}
//进程显示函数,用于显示当前进程
void disp(PCB* pr)
{
printf("\n 进程 \t 状态 \t 到达时间 \t 服务时间 \t 已运行时间 \t 优先级\n");
printf("|%s\t", pr->name);
printf("|%c\t", pr->state);
printf("|%d\t", pr->atime);
printf("\t|%d\t", pr->ntime);
printf("\t|%d\t", pr->rtime);
printf("\t|%f", pr->pri);
printf("\n");
}
//进程查看函数
void check()
{
PCB* pr;
printf("\n **** 当前正在运行的进程是:%s", p->name); /*显示当前运行进程*/
disp(p);
pr = ready;
printf("\n ****当前就绪队列状态为:\n"); /*显示就绪队列状态*/
while (pr != NULL && pr->atime <= h)
{
disp(pr);
pr = pr->link;
}
}
//检查节点到达,返回到达的节点数
int check_arrive()
{
PCB* first;
int num = 0;
first = ready;//指向头节点
while (first != NULL)
{
if ((first->atime <= h) && (first->a_t == 0))
{
first->a_t = 1;
}
if (first->atime <= h)
num++;
first = first->link;
}
return num;
}
//显示当前就绪队列队伍
void rest()
{
PCB* temp;
temp = ready;
while (temp != NULL)
{
if (temp->over == 0 && temp->a_t == 1)
{
disp(temp);
}
temp = temp->link;
}
printf("-----------------------------------------------");
}
void running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/
{
int num;
num = check_arrive();//检查到达数量
PCB* first, * max,*add_pri;
max = ready;
add_pri = ready;
first = ready;
int temp_n = 0;
float pri = -1;//temp_n表示已经到达数量中寻找，max表示优先级最高
rest();
while (temp_n < num)
{
if (first->over == 0 && pri == -1)
{
pri = first->pri;
max = first;
}
if (first->over == 0 && pri != -1 && first->pri > pri)
{
pri = first->pri;
max = first;
}
first = first->link;
temp_n++;
}
if (pri != -1)
{
h = h + max->ntime;
max->over = 1;
max->rtime = max->ntime;
have_run++;
disp(max);
ans += (h - max->atime * 1.0) / max->ntime;
printf("\n 进程 [%s] 已完成,其周转时间为:%d,其带权周转时间为:%.2f，完成时间为：%d\n", max->name, h - max->atime, (h - max->atime * 1.0) / max->rtime, h);
int ttttt = check_arrive();
while (add_pri != NULL)
{
if (add_pri->over == 0 && add_pri->a_t == 1)
{
add_pri->pri = ((float)h - (float)add_pri->atime + (float)add_pri->ntime) / add_pri->ntime;
}
add_pri = add_pri->link;
}
}
else
{
h = h + 1;
while (add_pri != NULL)
{
if (add_pri->over == 0 && add_pri->a_t == 1)
{
add_pri->pri = (float)h / add_pri->ntime;
}
add_pri = add_pri->link;
}
}
}
void main() /*主函数*/
{
int len;
input(); //根据到达时间建立队列 ready为头节点
len = space();
PCB* TTT;
TTT = ready;
while (have_run != len)
{
getchar();;
running();
//rest();
system("pause");
system("cls");
}
printf("总运行时间：%d", h);
printf("\n\n 进程已经完成.平均带权周转时间为:%.3f\n", (ans / len));
getchar();
getchar();
}
动态分区分配(首次适应算法)
#include "stdio.h"
#include <stdlib.h>
#include <conio.h>
#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1 //完成
#define ERROR 0 //出错
typedef int Status;
int flag;
typedef struct freearea//定义一个空闲区说明表结构
{
int name;
int size; //分区大小
int address; //分区地址
int state; //状态 1占用，0空闲
}ElemType;
// 线性表的双向链表存储结构
typedef struct DuLNode
{
ElemType data;
struct DuLNode* prior; //前趋指针
struct DuLNode* next; //后继指针
}DuLNode, * DuLinkList;
DuLinkList head = NULL; //头结点
DuLinkList end = NULL; //尾结点
DuLinkList node_run;//初始链表空间节点
//初始化链表
Status Init()
{
node_run = (DuLinkList)malloc(sizeof(DuLNode));
node_run->prior = NULL;
node_run->next = NULL;
node_run->data.size = 640;
node_run->data.address = 0;
node_run->data.state = Free;
node_run->data.name = 0;
head = node_run;
end = node_run;
return OK;
}
Status Create_node(long num,int name)
{
DuLinkList node_new;
node_new = (DuLinkList)malloc(sizeof(DuLNode));
node_new->data.size = num;
node_new->data.name = name;
node_new->data.state = Free;
node_new->data.address = 0;
node_new->next = NULL;
node_new->prior = NULL;
return node_new;
}
Status First_sq()
{
int find=0; //1找到，0没找到
int size_sc;
int work_n;
DuLinkList new; //指向新创建的节点
DuLinkList first,second;//用于遍历当前空间
new = NULL;
first = NULL; second = NULL;
//申请
printf("请输入需要申请空间的作业名：");
scanf("%d",&work_n);
printf("请输入需要申请的内存空间:");
scanf("%d", &size_sc);
new = Create_node(size_sc,work_n);
first = head;
second = first->next;
//只有一个节点
if (first != NULL && second == NULL)
{
if (first->data.state == Free)
{
first->prior = new;
new->prior = NULL;
new->next = first;
head = new;
first->data.address = new->data.size;
first->data.size = first->data.size - new->data.size;
new->data.state = Busy;
find = 1;
}
else
{
printf("内存不足，请先释放");
return;
}
}
if (first == NULL)
{
printf("错误");
return;
}
//节点不唯一
if (first != NULL && second != NULL)
{
if (first->data.state == Free && first->data.size >= new->data.size)
{
if (first->data.size == new->data.size)
{
first->data.state = Busy;
first->data.name = new->data.name;
find = 1;
}
else
{
first->prior = new;
new->prior = NULL;
new->next = first;
head = new;
first->data.address = new->data.size;
first->data.size = first->data.size - new->data.size;
new->data.state = Busy;
find = 1;
}
}
else
{
do
{
//找到可以存放
if (second->data.state == Free && second->data.size >= new->data.size)
{
if (second->data.size == new->data.size)
{
second->data.state = Busy;
second->data.name = new->data.name;
find = 1;
break;
}
else
{
first->next = new;
second->prior = new;
new->prior = first;
new->next = second;
new->data.state = Busy;
new->data.address = second->data.address;
second->data.address = second->data.address + new->data.size;
second->data.size = second->data.size - new->data.size;
find = 1;
break;
}
}
//当前节点不能存放
else
{
first = first->next;
second = second->next;
if (second == NULL)break;
}
}while(1);
}
}
if (find == 1)
{
printf("分配完毕\n");
return 1;
}
else
{
printf("分配失败，请先释放\n");
return 0;
}
}
Status merge()
{
DuLinkList first, second,temp;//用于遍历当前空间
first = head;
second = first->next;
if (second == NULL)return;
while (first != NULL)
{
if (second != NULL)
{
if ((first->data.state == 0) && (second->data.state == 0))
{
if (second->next == NULL)
{
first->next = NULL;
first->data.size = first->data.size + second->data.size;
free(second);
break;
}
temp = second;
second = second->next;
first->next = second;
second->prior = first;
first->data.size = first->data.size + temp->data.size;
free(temp);
}
else
{
first = first->next;
second = second->next;
}
}
else
break;
}
}
Status relax()
{
int num;
printf("请输入要释放的进程:");
scanf("%d", &num);
int r_flag=0;
DuLinkList first, second;//用于遍历当前空间
first = head;
while (first != NULL)
{
if (first->data.name == num)
{
first->data.state = Free;
r_flag = 1;
break;
}
else
first = first->next;
}
if (r_flag == 1)printf("释放成功\n");
else printf("释放失败或该作业不存在\n");
return;
}
void disp()
{
DuLinkList first=NULL;//用于遍历当前空间
first = head;
if (first == NULL)printf("错误\n");
printf("区域号\t 区域始址\t 区域大小\t 区域状态\n");
printf("--------------------------------------------------------\n");
while (first != NULL)
{
printf("%d\t\t%d\t\t%d\t\t%d\n",first->data.name,first->data.address,first->data.size,first->data.state);
first = first->next;
}
printf("\n\n");
return;
}
void main()
{
Init();
disp();
int i;
int chos;
int run_flag=1;
while (run_flag == 1)
{
printf("进程状态0为空闲区，1为已被分配区\n");
printf("释放空间(1)/请求空间(2)");
scanf("%d", &chos);
printf("\n");
if (chos == 1)
{
relax();
merge();
}
if (chos == 2)
{
run_flag = First_sq();
}
disp();
printf("***********************************************************\n\n");
// printf("%d\n", head->data.size);
//printf("%d\n", end->data.size);
}
return;
}
? ?
位示图
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define m 2000
#define n 32
bool map[m][n];
typedef struct fileLNode
{
char name[10];
int i; int j;
int size;
int begin;
int end;
struct fileLNode* prior;
struct fileLNode* next;
}fileLNode, * fileLinkList;
fileLinkList file_first, file_last;
fileLinkList temp;
void show() {
int i, j;
printf("位示图:\n\n");
for (i = 0; i < m; i++) {
printf("%d| ", i);
for (j = 0; j < n; j++) {
printf("%d ", map[i][j]);
}
printf("\n");
}
printf("\n");
printf("已存文件:\n");
fileLNode* p = file_first->next;
while (p) {
printf("文件名:%s,文件大小:%d,分配的盘块号：%d到%d\n\n", p->name, p->size,p->begin,p->end);
p = p->next;
}
if (file_first->next == NULL)printf("无\n");
}
void alloc(fileLinkList f)
{
int i, j, i0 = -1, j0 = -1;
int spa = 0;
for (i = 0; i < m; i++) {//顺序检索位示图，找到第一个值为1的二进制位，向后查找size次，查询是否有连续的空间可以存储
for (j = 0; j < n; j++)
{
if (map[i][j] == 1)
{
spa++;
if (i0 == -1 & j0 == -1) {
i0 = i; j0 = j;
}
}
else {
spa = 0;
i0 = -1;
j0 = -1;
}
if (spa == f->size)break;
}
if (spa == f->size)break;
}
f->i = i0; f->j = j0;
if (spa == f->size && i0 != -1 && j0 != -1) {//拥有足够空间
for (j = j0; j < n; j++) {//
map[i0][j] = 0;
spa--;
if (spa == 0)break;
}
if (spa != 0) {
for (i = i0 + 1; i < m; i++) {
for (j = 0; j < n; j++) {
map[i][j] = 0;
spa--;
if (spa == 0)break;
}
if (spa == 0)break;
}
}
//printf("分配的盘块号为%d到%d", i0 * n + j0 + 1, i * n + j + 1);
f->begin = i0 * n + j0 + 1;
f->end = i * n + j + 1;
}
else {
printf("空间不足\n");
}
}
void free() {
printf("请输入要删除的文件名字:");
char name[10];
scanf("%s", name);
fileLinkList p = file_first->next;
int i, j;
printf("释放的盘块号位置：%d字，%d位\n", (p->begin - 1)/n , (p->begin-1)%n);
while (p) {
if (strcmp(p->name, name) == 0) {
//处理map
for (j = p->j; j < n; j++) {
map[p->i][j] = 1;
p->size--;
if (p->size == 0)break;
}
if (p->size != 0) {
for (i = p->i + 1; i < m; i++) {
for (j = 0; j < n; j++) {
map[i][j] = 1;
p->size--;
if (p->size == 0)break;
}
if (p->size == 0)break;
}
}
//处理指针
if (p->next == NULL) {
p->prior->next = NULL;
file_last = p->prior;
p = NULL;
free(p);
}
else {
p->prior->next = p->next;
p->next->prior = p->prior;
p = NULL;
free(p);
}
break;
}
p = p->next;
}
}
int main() {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
map[i][j] = 1;
}
}
file_first = (fileLinkList)malloc(sizeof(fileLNode));
file_first->prior = NULL;
file_last = file_first;
while (1) {
int ch;
printf("请输入选项:\n");
printf("(1)分配\n");
printf("(2)释放\n");
printf("(0)退出\n");
scanf("%d", &ch);
if (ch == 1) {
temp = (fileLinkList)malloc(sizeof(fileLNode));
printf("请输入文件名:");
scanf("%s", temp->name);
printf("请输入文件分配的大小:");
scanf("%d", &temp->size);
file_last->next = temp;
temp->prior = file_last;
file_last = file_last->next;
file_last->next = NULL;
alloc(temp);
show();
}
else if (ch == 2) {
free();
show();
}
else {
break;
}
}
return 0;
}
动态分区分配（循环首次适应）
#include "stdio.h"
#include <stdlib.h>
#include <conio.h>
#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1 //完成
#define ERROR 0 //出错
typedef int Status;
int flag;
typedef struct freearea//定义一个空闲区说明表结构
{
int name;
int size; //分区大小
int address; //分区地址
int state; //状态 1占用，0空闲
}ElemType;
// 线性表的双向链表存储结构
typedef struct DuLNode
{
ElemType data;
struct DuLNode* prior; //前趋指针
struct DuLNode* next; //后继指针
}DuLNode, * DuLinkList;
DuLinkList head = NULL; //头结点
DuLinkList end = NULL; //尾结点
DuLinkList last_f = NULL; //上次查找到的位置
DuLinkList node_run;//初始链表空间节点
//初始化链表
Status Init()
{
node_run = (DuLinkList)malloc(sizeof(DuLNode));
node_run->prior = NULL;
node_run->next = NULL;
node_run->data.size = 600;
node_run->data.address = 0;
node_run->data.state = Free;
node_run->data.name = 0;
head = node_run;
end = node_run;
last_f = node_run;
return OK;
}
Status Create_node(long num, int name)
{
DuLinkList node_new;
node_new = (DuLinkList)malloc(sizeof(DuLNode));
node_new->data.size = num;
node_new->data.name = name;
node_new->data.state = Free;
node_new->data.address = 0;
node_new->next = NULL;
node_new->prior = NULL;
return node_new;
}
Status First_sq1()
{
int find = 0; //1找到，0没找到
int size_sc;
int work_n;
DuLinkList new; //指向新创建的节点
DuLinkList first, second;//用于遍历当前空间
new = NULL;
first = NULL; second = NULL;
//申请
printf("请输入需要申请空间的作业名：");
scanf("%d", &work_n);
printf("请输入需要申请的内存空间:");
scanf("%d", &size_sc);
new = Create_node(size_sc, work_n);
first = head;
second = first->next;
//只有一个节点
if (first != NULL && second == NULL)
{
if (first->data.state == Free)
{
first->prior = new;
new->prior = NULL;
new->next = first;
head = new;
first->data.address = new->data.size;
first->data.size = first->data.size - new->data.size;
new->data.state = Busy;
find = 1;
}
else
{
printf("内存不足，请先释放");
return;
}
}
if (first == NULL)
{
printf("错误");
return;
}
//节点不唯一
if (first != NULL && second != NULL)
{
if (first->data.state == Free && first->data.size >= new->data.size)
{
if (first->data.size == new->data.size)
{
first->data.state = Busy;
first->data.name = new->data.name;
find = 1;
}
else
{
first->prior = new;
new->prior = NULL;
new->next = first;
head = new;
first->data.address = new->data.size;
first->data.size = first->data.size - new->data.size;
new->data.state = Busy;
find = 1;
}
}
else
{
do
{
//找到可以存放
if (second->data.state == Free && second->data.size >= new->data.size)
{
if (second->data.size == new->data.size)
{
second->data.state = Busy;
second->data.name = new->data.name;
find = 1;
break;
}
else
{
first->next = new;
second->prior = new;
new->prior = first;
new->next = second;
new->data.state = Busy;
new->data.address = second->data.address;
second->data.address = second->data.address + new->data.size;
second->data.size = second->data.size - new->data.size;
find = 1;
break;
}
}
//当前节点不能存放
else
{
first = first->next;
second = second->next;
if (second == NULL)break;
}
} while (1);
}
}
if (find == 1)
{
printf("分配完毕\n");
return 1;
}
else
{
printf("分配失败，请先释放\n");
return 0;
}
}
Status First_sq()
{
int find = 0; //1找到，0没找到
int size_sc;
int work_n;
DuLinkList new; //指向新创建的节点
DuLinkList first, second;//用于遍历当前空间
new = NULL;
first = NULL; second = NULL;
//申请
printf("请输入需要申请空间的作业名：");
scanf("%d", &work_n);
printf("请输入需要申请的内存空间:");
scanf("%d", &size_sc);
new = Create_node(size_sc, work_n);
if (last_f->next != NULL)
{
first = last_f->next;
second = first->next;
}
else
{
first = head;
second = first->next;
}
//只有一个节点
if (first != NULL && second == NULL)
{
if (first->data.state == Free)
{
last_f = first;
first->prior = new;
new->prior = NULL;
new->next = first;
head = new;
first->data.address = new->data.size;
first->data.size = first->data.size - new->data.size;
new->data.state = Busy;
find = 1;
}
else
{
printf("内存不足，请先释放");
return;
}
}
if (first == NULL)
{
printf("错误");
return;
}
//节点不唯一
if (first != NULL && second != NULL)
{
if (first->data.state == Free && first->data.size >= new->data.size)
{
if (first->data.size == new->data.size)
{
first->data.state = Busy;
first->data.name = new->data.name;
find = 1;
last_f = first;
}
else
{
first->prior = new;
new->prior = NULL;
new->next = first;
head = new;
first->data.address = new->data.size;
first->data.size = first->data.size - new->data.size;
new->data.state = Busy;
find = 1;
last_f = first;
}
}
else
{
do
{
//找到可以存放
if (second->data.state == Free && second->data.size >= new->data.size)
{
if (second->data.size == new->data.size)
{
second->data.state = Busy;
second->data.name = new->data.name;
find = 1;
last_f = first;
break;
}
else
{
first->next = new;
second->prior = new;
new->prior = first;
new->next = second;
new->data.state = Busy;
new->data.address = second->data.address;
second->data.address = second->data.address + new->data.size;
second->data.size = second->data.size - new->data.size;
find = 1;
last_f = first;
break;
}
}
//当前节点不能存放
else
{
first = first->next;
second = second->next;
if (second == NULL)break;
}
} while (1);
}
}
if (flag == 0 && last_f != end && first == end)
{
first = head;
while (first != last_f)
{
if (first->data.state == Free && first->data.size >= new->data.size)
{
if (first->data.size == new->data.size)
{
first->data.state = Busy;
first->data.name = new->data.name;
find = 1;
last_f = first;
}
else
{
first->prior = new;
new->prior = NULL;
new->next = first;
head = new;
first->data.address = new->data.size;
first->data.size = first->data.size - new->data.size;
new->data.state = Busy;
find = 1;
last_f = first;
}
}
first = first->next;
}
}
if (find == 1)
{
printf("分配完毕\n");
return 1;
}
else
{
printf("分配失败，请先释放\n");
return 0;
}
}
Status merge()
{
DuLinkList first, second, temp;//用于遍历当前空间
first = head;
second = first->next;
if (second == NULL)return;
while (first != NULL)
{
if (second != NULL)
{
if ((first->data.state == 0) && (second->data.state == 0))
{
if (second->next == NULL)
{
first->next = NULL;
first->data.size = first->data.size + second->data.size;
free(second);
break;
}
temp = second;
second = second->next;
first->next = second;
second->prior = first;
first->data.size = first->data.size + temp->data.size;
free(temp);
}
else
{
printf("#\n");
first = first->next;
second = second->next;
}
}
else
break;
}
}
Status relax()
{
int num;
printf("请输入要释放的进程:");
scanf("%d", &num);
int r_flag = 0;
DuLinkList first, second;//用于遍历当前空间
first = head;
while (first != NULL)
{
if (first->data.name == num)
{
first->data.state = Free;
r_flag = 1;
break;
}
else
first = first->next;
}
if (r_flag == 1)printf("释放成功\n");
else printf("释放失败或该作业不存在\n");
return;
}
void disp()
{
DuLinkList first = NULL;//用于遍历当前空间
first = head;
if (first == NULL)printf("错误\n");
printf("区域号\t 区域大小\t 区域地址\t 区域状态\n");
printf("------------------------------------------\n");
while (first != NULL)
{
printf("%d\t\t%d\t\t%d\t\t%d\n", first->data.name, first->data.size, first->data.address, first->data.state);
first = first->next;
}
printf("\n\n");
return;
}
void main()
{
Init();
disp();
int i;
int chos;
int sq_time = 0;
int run_flag = 1;
while (run_flag == 1)
{
printf("释放空间(1)/请求空间(2)");
scanf("%d", &chos);
printf("\n");
if (chos == 1)
{
relax();
merge();
}
if (chos == 2)
{
if (sq_time == 0)
{
run_flag = First_sq1();
sq_time++;
}
else
{
run_flag = First_sq();
}
}
disp();
// printf("%d\n", head->data.size);
//printf("%d\n", end->data.size);
}
return;
}
银行家算法
#include<stdio.h>
#include<stdlib.h>
#define PROCESS_MAX 10
#define RESOURCE_KIND 4 //资源种类
typedef struct res //资源
{
int a;
int b;
int c;
int d;
}res;
typedef struct Pro
{
res max; //所需资源总数
res allocation; //已分配
res need; //所需资源数
res work;
res work_allocation;
res request; //资源请求
int finish; //标志是否完成
}Pro;
typedef struct All_P
{
res resourse_MAX; //各资源总数
res total_resourse; //已分配资源总和
Pro process[PROCESS_MAX];
res available; //剩余资源
int size; //进程数
int array[PROCESS_MAX]; //安全序列号（从0开始）
}All_P;
//输出函数
void print(All_P* allProcess)
{
Pro* p = allProcess->process;
printf("**************************************************************************************************************\n");
printf(" \t\t Max\t\t Allocation\t\t\tNeed\n");
printf("资源名称| A\tB\tC\tD |A\tB\tC\tD |A\tB\tC\tD\n");
for (int i = 0; i < allProcess->size; i++)
{
printf("进程%d\t| %-2d\t%-2d\t%-2d\t%-2d|", i + 1,
p[i].max.a, p[i].max.b, p[i].max.c, p[i].max.d);
printf("%d\t%d\t%d\t%d |",
p[i].allocation.a, p[i].allocation.b,
p[i].allocation.c, p[i].allocation.d);
printf("%d\t%d\t%d\t%d\n",
p[i].need.a, p[i].need.b, p[i].need.c, p[i].need.d);
}
printf("\n");
printf("**************************************************************************************************************\n");
printf("\t\t\t\t安全性检查过程\n");
printf(" \t\t Work\t\t\tAllocation\t\tNeed\t\t\tWork+Allocation\n");
printf("资源名称| A\tB\tC\tD | A\t B \t C \t D | A\t B\t C\t D | A\t B\t C\t D\t\n");
for (int i = 0; i < allProcess->size; i++)
{
printf("进程%d\t| %-2d\t%-2d\t%-2d\t%-2d |", i + 1,
p[i].work.a, p[i].work.b, p[i].work.c, p[i].work.d);
printf("%2d\t%2d\t%2d\t%2d |",
p[i].allocation.a, p[i].allocation.b,
p[i].allocation.c, p[i].allocation.d);
printf("%2d\t%2d\t%2d\t%2d |",
p[i].need.a, p[i].need.b, p[i].need.c, p[i].need.d);
printf("%2d\t%2d\t%2d\t%2d\n",
p[i].work_allocation.a, p[i].work_allocation.b, p[i].work_allocation.c, p[i].work_allocation.d);
}
printf("**************************************************************************************************************\n");
//整个系统剩余资源数
printf("\n\n");
printf("\tAvailable\n");
printf("A\tB\tC\tD\n");
printf("%d\t%d\t%d\t%d\n",
allProcess->available.a, allProcess->available.b,
allProcess->available.c, allProcess->available.d);
}
//求最大需求量
void Max(All_P* allProcess)
{
Pro* p = allProcess->process;
for (int i = 0; i < allProcess->size; i++)
{
p[i].max.a = p[i].allocation.a + p[i].need.a;
p[i].max.b = p[i].allocation.b + p[i].need.b;
p[i].max.c = p[i].allocation.c + p[i].need.c;
p[i].max.d = p[i].allocation.d + p[i].need.d;
}
}
//求剩余量
void remainResource(All_P* allProcess)
{
res* ava = &allProcess->available;
res* MAX = &allProcess->resourse_MAX;
res* total = &allProcess->total_resourse;
ava->a = MAX->a - total->a;
ava->b = MAX->b - total->b;
ava->c = MAX->c - total->c;
ava->d = MAX->d - total->d;
}
//求所有进程占用资源(即已分配资源)的总和
void totalResource(All_P* allProcess)
{
Pro* p = allProcess->process;
res* total = &allProcess->total_resourse;
total->a = 0;
total->b = 0;
total->c = 0;
total->d = 0;
for (int i = 0; i < allProcess->size; i++)
{
total->a += p[i].allocation.a;
total->b += p[i].allocation.b;
total->c += p[i].allocation.c;
total->d += p[i].allocation.d;
}
}
//初始化
void initAllProcess(All_P* allProcess) //初始化输入
{
printf("请输入该系统的进程数:");
scanf("%d", &allProcess->size);
Pro* p = allProcess->process;
for (int i = 0; i < allProcess->size; i++)
{
printf("请输入第%d个进程的allocation资源分配情况\n", i+1);
printf("A:");
scanf("%d", &p[i].allocation.a);
printf("B:");
scanf("%d", &p[i].allocation.b);
printf("C:");
scanf("%d", &p[i].allocation.c);
printf("D:");
scanf("%d", &p[i].allocation.d);
printf("请输入第%d个进程的need资源情况\n", i+1);
printf("A:");
scanf("%d", &p[i].need.a);
printf("B:");
scanf("%d", &p[i].need.b);
printf("C:");
scanf("%d", &p[i].need.c);
printf("D:");
scanf("%d", &p[i].need.d);
printf("\n-------------------------------------------------\n");
printf("\n");
p[i].finish = 0; //0表示未执行
}
totalResource(allProcess);
res* MAX = &allProcess->resourse_MAX;
res* total = &allProcess->total_resourse;
while (1)
{
printf("输入系统各项资源总数:\n");
printf("A:");
scanf("%d", &MAX->a);
printf("B:");
scanf("%d", &MAX->b);
printf("C:");
scanf("%d", &MAX->c);
printf("D:");
scanf("%d", &MAX->d);
if (MAX->a >= total->a && MAX->b >= total->b && MAX->c >= total->c && MAX->d >= total->d)
break;
else
{
printf("输入的资源总数错误,请重新输入资源总数:");
continue;
}
}
remainResource(allProcess);
Max(allProcess);
}
//安全性检查
int Secure(All_P* allProcess)
{
Pro* p = allProcess->process;
int count = 0;
for (int i = 0; i < allProcess->size; i++)
{
if (allProcess->available.a >= p[i].need.a
&& allProcess->available.b >= p[i].need.b
&& allProcess->available.c >= p[i].need.c
&& allProcess->available.d >= p[i].need.d)
{
(p + i)->work.a = allProcess->available.a;
p[i].work.b = allProcess->available.b;
p[i].work.c = allProcess->available.c;
p[i].work.d = allProcess->available.d;
p[i].finish = 1;
allProcess->array[count++] = i;
p[i].work_allocation.a = p[i].work.a + p[i].allocation.a;
p[i].work_allocation.b = p[i].work.b + p[i].allocation.b;
p[i].work_allocation.c = p[i].work.c + p[i].allocation.c;
p[i].work_allocation.d = p[i].work.d + p[i].allocation.d;
break;
}
}
int count1 = 0;
while (count < allProcess->size && count1 != count)
{
count1 = count;
for (int i = 0; i < allProcess->size; i++)
{
if (p[i].finish != 1
&& p[allProcess->array[count - 1]].work_allocation.a >= p[i].need.a
&& p[allProcess->array[count - 1]].work_allocation.b >= p[i].need.b
&& p[allProcess->array[count - 1]].work_allocation.c >= p[i].need.c
&& p[allProcess->array[count - 1]].work_allocation.d >= p[i].need.d
)
{
p[i].work.a = p[allProcess->array[count - 1]].work_allocation.a;
p[i].work.b = p[allProcess->array[count - 1]].work_allocation.b;
p[i].work.c = p[allProcess->array[count - 1]].work_allocation.c;
p[i].work.d = p[allProcess->array[count - 1]].work_allocation.d;
allProcess->process[i].finish = 1;
allProcess->array[count++] = i;
p[i].work_allocation.a = p[i].work.a + p[i].allocation.a;
p[i].work_allocation.b = p[i].work.b + p[i].allocation.b;
p[i].work_allocation.c = p[i].work.c + p[i].allocation.c;
p[i].work_allocation.d = p[i].work.d + p[i].allocation.d;
}
}
}
print(allProcess);
if (count >= allProcess->size)
return 1;
return 0;
}
int main()
{
All_P allProcess;
All_P* alp = &allProcess;
initAllProcess(alp);
remainResource(alp);
int num = 0;
printf("输入请求分配资源的进程号:\n");
while (1)
{
scanf("%d", &num);
if (num <= alp->size && num >= 0)
break;
else
{
printf("进程号不存在，请重新输入:");
continue;
}
}
printf("请输入进程%d的资源请求(A,B,C,D):\n", num);
res* r = &alp->process[num - 1].request;
printf("A:");
scanf("%d", &r->a);
printf("B:");
scanf("%d", &r->b);
printf("C:");
scanf("%d", &r->c);
printf("D:");
scanf("%d", &r->d);
printf("\n");
res* n = &alp->process[num - 1].need;
res* all = &alp->process[num - 1].allocation;
//检查是否超出需求,以及是否满足
if (r->a <= n->a && r->b <= n->b && r->c <= n->c && r->d <= n->d
&& r->a <= alp->available.a && r->b <= alp->available.b
&& r->c <= alp->available.c && r->d <= alp->available.d
)
{
all->a += r->a;
all->b += r->b;
all->c += r->c;
all->d += r->d;
n->a -= r->a;
n->b -= r->b;
n->c -= r->c;
n->d -= r->d;
alp->available.a -= r->a;
alp->available.b -= r->b;
alp->available.c -= r->c;
alp->available.d -= r->d;
if (Secure(alp) == 1)
{
printf("\n安全序列为:");
printf("{");
for (int i = 0; i < alp->size; i++)
{
if (i == alp->size - 1)
printf("%d}\n\n", alp->array[i] + 1);
else
printf("%d => ", alp->array[i] + 1);
}
}
else
printf("不存在安全序列\n");
}
else
{
printf("请求失败,不存在安全序列\n");
}
system("pause");
return 0;
}
最佳适应算法
#include "stdio.h"
#include <stdlib.h>
#include <conio.h>
#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1 //完成
#define ERROR 0 //出错
typedef int Status;
int flag;
typedef struct freearea//定义一个空闲区说明表结构
{
int name;
int size; //分区大小
int address; //分区地址
int state; //状态 1占用，0空闲
}ElemType;
// 线性表的双向链表存储结构
typedef struct DuLNode
{
ElemType data;
struct DuLNode* prior; //前趋指针
struct DuLNode* next; //后继指针
}DuLNode, * DuLinkList;
DuLinkList head = NULL; //头结点
DuLinkList end = NULL; //尾结点
DuLinkList node_run;//初始链表空间节点
//初始化链表
Status Init()
{
node_run = (DuLinkList)malloc(sizeof(DuLNode));
node_run->prior = NULL;
node_run->next = NULL;
node_run->data.size = 640;
node_run->data.address = 0;
node_run->data.state = Free;
node_run->data.name = 0;
head = node_run;
end = node_run;
return OK;
}
Status Create_node(long num, int name)
{
DuLinkList node_new;
node_new = (DuLinkList)malloc(sizeof(DuLNode));
node_new->data.size = num;
node_new->data.name = name;
node_new->data.state = Free;
node_new->data.address = 0;
node_new->next = NULL;
node_new->prior = NULL;
return node_new;
}
DuLinkList find_min(int need)
{
DuLinkList first, min_find, cons;//用于遍历当前空间
int find = 0,min=-1;
first = head;
min_find = NULL;
while (first != NULL)
{
if (min == -1)
{
if (first->data.state == Free && first->data.size >= need)
{
min = first->data.size;
min_find = first;
}
}
else
{
if (first->data.state == Free && first->data.size >= need && first->data.size < min)
{
min = first->data.size;
min_find = first;
}
}
first = first->next;
}
if (min != -1)
{
return min_find;
}
else
{
min_find = NULL;
return min_find;
}
}
Status First_sq()
{
int find = 0; //1找到，0没找到
int size_sc;
int work_n;
DuLinkList new; //指向新创建的节点
DuLinkList first, second;//用于遍历当前空间
new = NULL;
first = NULL; second = NULL;
//申请
printf("请输入需要申请空间的作业名：");
scanf("%d", &work_n);
printf("请输入需要申请的内存空间:");
scanf("%d", &size_sc);
new = Create_node(size_sc, work_n);
first = head;
first = find_min(new->data.size); //指向用于分配的目标指针
if (first == NULL)
{
find = 0;
return;
}
else
{
second = first->prior;
if (second == NULL)//此时first为头节点
{
if (first->data.size == new->data.size)
{
first->data.state = Busy;
first->data.name = new->data.name;
find = 1;
}
else
{
new->next = first;
new->prior = NULL;
first->prior = new;
head = new;
first->data.address = new->data.size;
first->data.size = first->data.size - new->data.size;
new->data.state = Busy;
find = 1;
}
}
else
{
if (first->data.size == new->data.size)
{
first->data.state = Busy;
first->data.name = new->data.name;
find = 1;
}
else
{
first->prior = new;
new->prior = second;
new->next = first;
second->next = new;
new->data.state = Busy;
new->data.address = first->data.address;
first->data.address = first->data.address + new->data.size;
first->data.size = first->data.size - new->data.size;
find = 1;
}
}
}
if (find == 1)
{
printf("分配完毕\n");
return 1;
}
else
{
printf("分配失败，请先释放\n");
return 0;
}
}
Status merge()
{
DuLinkList first, second, temp;//用于遍历当前空间
first = head;
second = first->next;
if (second == NULL)return;
while (first != NULL)
{
if (second != NULL)
{
if ((first->data.state == 0) && (second->data.state == 0))
{
if (second->next == NULL)
{
first->next = NULL;
first->data.size = first->data.size + second->data.size;
free(second);
break;
}
temp = second;
second = second->next;
first->next = second;
second->prior = first;
first->data.size = first->data.size + temp->data.size;
free(temp);
}
else
{
first = first->next;
second = second->next;
}
}
else
break;
}
}
Status relax()
{
int num;
printf("请输入要释放的进程:");
scanf("%d", &num);
int r_flag = 0;
DuLinkList first, second;//用于遍历当前空间
first = head;
while (first != NULL)
{
if (first->data.name == num)
{
first->data.state = Free;
r_flag = 1;
break;
}
else
first = first->next;
}
if (r_flag == 1)printf("释放成功\n");
else printf("释放失败或该作业不存在\n");
return;
}
void disp()
{
DuLinkList first = NULL;//用于遍历当前空间
first = head;
if (first == NULL)printf("错误\n");
printf("区域号\t 区域始址\t 区域大小\t 区域状态\n");
printf("--------------------------------------------------------\n");
while (first != NULL)
{
printf("%d\t\t%d\t\t%d\t\t%d\n", first->data.name, first->data.address, first->data.size, first->data.state);
first = first->next;
}
printf("\n\n");
return;
}
void main()
{
Init();
disp();
int i;
int chos;
int run_flag = 1;
while (run_flag == 1)
{
printf("0表示空闲区，1表示已被分配区\n");
printf("释放空间(1)/请求空间(2)");
scanf("%d", &chos);
printf("\n");
if (chos == 1)
{
relax();
merge();
}
if (chos == 2)
{
run_flag = First_sq();
}
disp();
// printf("%d\n", head->data.size);
//printf("%d\n", end->data.size);
}
return;
}
最佳置换算法
#include <stdio.h>
#include <stdlib.h>
float count = 0; //缺页次数
int instruction_addr[320]; //指令地址数组
int page_addr[320]; //页地址数组
typedef struct Data //数据域
{
int page_num; //装进的用户虚存页号
int block_num; //块号
} Data;
typedef struct BlockNode
{
Data data;
struct BlockNode* next;
}Block, * BlockList;
BlockList block1; //内存块
BlockList block2;
BlockList block3;
void initialize() //初始化
{
block1 = (BlockList)malloc(sizeof(Block));
block2 = (BlockList)malloc(sizeof(Block));
block3 = (BlockList)malloc(sizeof(Block));
//block4 = (BlockList)malloc(sizeof(Block));
block1->data.page_num = -1;
block2->data.page_num = -1;
block3->data.page_num = -1;
//block4->data.page_num = -1;
block1->data.block_num = 0;
block2->data.block_num = 1;
block3->data.block_num = 2;
//block4->data.block_num = 3;
block1->next = block2; //循环链表
block2->next = block3;
block3->next = block1;
//block4->next = block1;
//地址生成原则，50%的指令是顺序执行的，25%的指令是均匀分布在前地址部分，25%的指令是均匀分布在后地址部分
for (int i = 0; i < 320;) //初始化地址
{
int m0 = rand() % 320; //步骤一，[0,319]随机选取一个起点m0
instruction_addr[i] = m0 + 1; //步骤二，顺序执行一条指令，m0+1
page_addr[i] = instruction_addr[i] / 10; //计算块地址
i++;
int m1 = rand() % (m0 - 1); //步骤三，在前地址[0,m0-1]中随机选取一条指令并执行，记为m1
instruction_addr[i] = m1; //计算块地址
page_addr[i] = m1 / 10;
i++;
instruction_addr[i] = m1 + 1; //步骤四，顺序执行一条指令，m1+1
page_addr[i] = instruction_addr[i] / 10; //计算块地址
i++;
int m2 = rand() % (319 - m1 - 1) + m1 + 2; //步骤五，在后地址[m1+2,319]中随机选取一条指令并执行，记为m2
instruction_addr[i] = m2; //计算块地址
page_addr[i] = m2 / 10;
i++;
instruction_addr[i] = m2 + 1; //步骤六，顺序执行一条指令，m2+1
page_addr[i] = instruction_addr[i] / 10; //计算块地址
i++;
}
}
int Optimal(int page_num_0, int cur_addr, int pos) //最佳置换算法
{
Block* p = block1;
for (int i = 0; i < 3; i++)
{
if (p->data.page_num == -1) //块为空闲
{
p->data.page_num = page_num_0;
count++; //计算缺页次数
printf("================================================================================\n");
printf("第%d条指令：\n", pos);
printf("指令地址: %d \n", cur_addr);
//printf("指令未装入内存。页面置换完成。\n指令第%d页第%d条的物理地址为:第%d块第%d条 \n\n", page_num_0, (cur_addr % 10), p->data.block_num, (cur_addr % 10));
printf("指令未装入内存。页面置换完成。\n 外存地址为:%d\n 内存地址:第 %d 块,第 %d 条 \n\n", pos, p->data.block_num, (cur_addr % 10));
return 1;
}
if (p->data.page_num == page_num_0)
{
printf("================================================================================\n");
printf("第%d条指令：\n", pos);
printf("指令地址: %d \n", cur_addr);
//printf("指令已在内存中。\n指令第%d页第%d条的物理地址为:第%d块第%d条 \n\n", page_num_0, (cur_addr % 10), p->data.block_num, (cur_addr % 10));
printf("指令已在内存中。\n 外存地址为:%d\n 内存地址:第 %d 块,第 %d 条 \n\n", pos, p->data.block_num, (cur_addr % 10));
return 1;
}
p = p->next;
}
//页面置换
int alloc[3]; //记录已装入内存的页地址
for (int i = 0; i < 3; i++)
{
alloc[i] = p->data.page_num;
p = p->next;
}
int nextAddr[3]; //记录已装入内存的页地址下次在指令数组中出现的位置
for (int i = 0; i < 3; i++)
{
for (int j = pos; j < 320; j++)
{
if (alloc[i] == page_addr[j]) //找到第一个位置即停止
{
nextAddr[i] = j;
break;
}
nextAddr[i] = 320 + 1;
}
}
int temp = 0; //页地址
int blockPos; //内存块的地址
for (int i = 0; i < 3; i++) //找到最长时间内不再被访问的页面
{
if (nextAddr[i] > temp)
{
temp = nextAddr[i];
blockPos = i;
}
}
for (int i = 0; i < 3; i++)
{
if (p->data.block_num == blockPos)
{
p->data.page_num = page_num_0;
count++;
printf("================================================================================\n");
printf("第%d条指令：\n", pos);
printf("指令地址: %d \n", cur_addr);
//printf("指令未装入内存且内存块已满，页面置换完成。\n指令第%d页第%d条的物理地址为:第%d块第%d条 \n\n", page_num_0, (cur_addr % 10), p->data.block_num, (cur_addr % 10));
printf("指令未装入内存，内存块已满，页面置换完成。\n 外存地址:%d\n 内存地址:第 %d 块,第 %d 条 \n\n", pos, p->data.block_num, (cur_addr % 10));
}
p = p->next;
}
return 1;
}
void calculate() //计算缺页率
{
for (int i = 0; i < 320; i++)
{
Optimal(page_addr[i], instruction_addr[i], i);
}
printf("\n");
printf("缺页次数:%.0f\n", count);
printf("缺页率:%.3f \n", count / 320);
}
int main()
{
printf("----------最佳置换算法----------\n\n");
initialize();
calculate();
return 0;
}
|