LRU算法
demo
int N1 =20;
scanf("%d",&N1); //为N1赋新值
int list[20] = {0}; //用0填充20个单位
for(int i=0;i<Nl;i++)
scanf("%d", &list[i]);
int tem[10] = {0};
printf("%d\n",tem[0]); //C打印不支持执行使用变量,需要引用
/*
============================================================================
Name : lruSub.c
Author :
Version :
Copyright : Your copyright notice
Description : Hello World in C, Ansi-style
============================================================================
*/
//#include
//#include
//int main(void) {
// puts("!!!Hello World!!!"); /* prints !!!Hello World!!! */
// return EXIT_SUCCESS;
//}
#include
#define N 3 //物理块的个数
int Nl = 20;//页面访问序列的长度
void LRU(int block[],int blockN,int list[],int listN)
//LRU替换算法
//列表、物理块数,将要到来的序列列表,要进入算法的数目
{
int i, j;//定义替换次数
int rep1 = 0;//缺页次数
int rep2 = 0;//置换页面次数
int DisplacedPages[20] = {0};
int time[N];//各个物理块最近一次访问至现在的时间
for(i = 0;i < blockN;i++)//初始化
time[i] = 0;//用作各个块的驻留计数
for(i = 0;i < listN; i++)
{
for(j = 0; j < blockN; j++) //更新时间记录
if(block[j] != -1)
time[j]++;
for(j = 0; j < blockN; j++)
if(block[j] == list[i]) //命中
{
time[j] = 0;
break;
}
else if(block[j] == -1) //未命中但块中为空
break;
if(j < blockN && block[j] == -1)//未命中且物理块未满,直接存入
{
block[j] = list[i];
time[j] = 0;
rep1++;
}
else if(j == blockN)//需要替换
{
int max = 0;
for(int k = 0;k < blockN;k++)//寻找最久未访问的地址所在的物理块的位置
{
if(time[max] < time[k])
max = k;
}
DisplacedPages[rep2] = block[max];
rep2++;
rep1++;
block[max] = list[i];
time[max] = 0;
}
printf("current access page is:%d\n",list[i]);
printf("after access of The page physics block are:");//访问后物理块内的页面为
for(int m = 0;m < blockN;m++)//显示当前物理块的状态
{
if(block[m] == -1)
break;
printf("|%d| ",block[m]);
}
if (j == blockN)
printf("Replaced %d\n", DisplacedPages[rep2-1]);
printf("\n");
}
printf("Lake Page num are:%d Lake rate of page:%d/%d=%.2f\n", rep1, rep1, listN, (float)(rep1)/(float)listN);
printf("Replaced page are:");//置换的页面是
for (i=0; i<rep2; i++)
printf("%d,", DisplacedPages[i]);
}
int main()
{
int block[N], list[20] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};//默认序列
int df = 1;
for(int i = 0;i < N;i++)//初始化
{
block[i] = -1;
}
// printf("是否使用默认序列?(1:否 其他数字:是)");
printf("Are you prepare use default sequence?(1 no . 2 either)");
printf("\n");
scanf("%d", &df);
if (df == 1)
{
printf("please Input of page Num:\n");
scanf("%d", &Nl);
printf("please Input page access sequence:\n");
for(int i=0;i<Nl;i++)
scanf("%d", &list[i]);
}
printf("Start Sequence");
LRU(block, N, list, Nl);//调用LRU页面置换算法
//列表、物理块,将要到来的序列列表,要进入算法的数目
printf("\n");
return 0;
}
银行家算法
#include
#include
#define MAX_PROCESS 10 // 最大进程数
#define MAX_RESOURCES 5 // 最大资源数
int available[MAX_RESOURCES]; // 可用资源数组
int max[MAX_PROCESS][MAX_RESOURCES]; // 最大需求矩阵
int allocation[MAX_PROCESS][MAX_RESOURCES]; // 已分配矩阵
int need[MAX_PROCESS][MAX_RESOURCES]; // 需求矩阵
int work[MAX_RESOURCES]; // 工作数组
int finish[MAX_PROCESS]; // 完成标志数组
int n_processes; // 进程数
int n_resources; // 资源数
int tmp[MAX_PROCESS] = {0};
// 初始化函数
void init() {
printf("Enter the number of processes: ");
scanf("%d", &n_processes); //进程数
printf("Enter the number of resources: ");
scanf("%d", &n_resources); //资源类型
// 输入可用资源数组
printf("Enter available resources:\n");
for (int j = 0; j < n_resources; j++) {
scanf("%d", &available[j]); //活跃的资源数
}
// 输入最大需求矩阵
printf("Enter maximum demand:\n");
for (int i = 0; i < n_processes; i++) {
printf("For process %d: ", i);
for (int j = 0; j < n_resources; j++) {
scanf("%d", &max[i][j]); //最大的资源数
}
}
// 输入已分配矩阵
printf("Enter allocated resources:\n");
for (int i = 0; i < n_processes; i++) {
printf("For process %d: ", i);
for (int j = 0; j < n_resources; j++) {
scanf("%d", &allocation[i][j]); //分配的资源数
}
}
// 计算需求矩阵
for (int i = 0; i < n_processes; i++) {
for (int j = 0; j < n_resources; j++) {
need[i][j] = max[i][j] - allocation[i][j];
}
}
// 初始化完成标志数组
for (int i = 0; i < n_processes; i++) {
finish[i] = 0;
}
}
// 检查进程i是否满足条件
int check(int i) {
for (int j = 0; j < n_resources; j++) {
if (need[i][j] > work[j]) {
return 0;
}
}
return 1;
}
// 银行家算法函数
void banker() {
int count = 0; // 完成的进程数
// 将available赋值给work
for (int i = 0; i < n_resources; i++) {
work[i] = available[i];
}
// 检查所有进程是否满足条件
while (count < n_processes) {
int found = 0;
for (int i = 0; i < n_processes; i++) {
if (!finish[i] && check(i)) {
found = 1;
finish[i] = 1;
tmp[i] = i;
count++;
for (int j = 0; j < n_resources; j++) {
work[j] += allocation[i][j];
}
}
}
if (!found) {
printf("\nSystem is not in safe state. \n");
for (int i = 0;i < n_processes; i++){
if(tmp[i]){
printf("%d not safe.", tmp[i]);
}
}
return;
}
}
for (int i = 0; i < n_processes; i++) {
if ( i != 0){
printf("\nSystem is in safe state. \n");
}
}
}
// 主函数
int main() {
init();
banker();
return 0;
}
/*
============================================================================
Name : EmptyStack.c
Author : Mr.xinghaizhuiqing
Version :
Copyright : Your copyright notice
Description : Hello World in C, Ansi-style
============================================================================
*/
#pragma once
#include
#include
#include
#include
#define N 10
typedef int STDataType;
typedef struct Stack
{
STDataType* data;
int top; //已有的数据个数
int capacity; //容量
}ST;
//初始化
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//找到栈顶数据
STDataType StackTop(ST* ps);
//栈的里数据的多少
int StackSize(ST* ps);
//栈是否为空,1位空,0为非空
bool StackEmpty(ST* ps);
#define _CRT_SECURE_NO_WARNINGS 1
#include "EmptyStack.h"
void StackInit(ST* ps)
{
assert(ps);
ps->data = NULL;
ps->capacity = ps->top = 0;
}
void StackDestory(ST* ps)
{
assert(ps);
free(ps->data);
ps->data = NULL;
ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* temp = (STDataType*)realloc(ps->data,newcapacity*sizeof(STDataType));
if (temp == NULL)
{
printf("realloc fail!\n");
exit(-1);
}
ps->data = temp;
ps->capacity = newcapacity;
}
ps->data[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->data[ps->top-1];
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps)
{
assert(ps);
if (ps->top == 0)
{
return 1;
}
else
return 0;
}
main.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "EmptyStack.h"
#include "StackFunc.c"
//高版的VS默认不让使用scanf,fopen等函数,说是scanf,fopen等函数不安全,而代替其函数的是scanf_s,fopen_s等函数,后边有个"_s"的形式
void Test1()
{
ST a;
StackInit(&a);
StackPush(&a, 1);
StackPush(&a, 2);
StackPush(&a, 3);
StackPush(&a, 4);
printf("%d ", StackTop(&a));
StackPop(&a);
printf("%d ", StackTop(&a));
StackPop(&a);
StackPush(&a, 5);
StackPush(&a, 6);
while (!StackEmpty(&a))
{
printf("%d ", StackTop(&a));
StackPop(&a);
}
}
int main()
{
Test1();
return 0;
}
/*
============================================================================
Name : HP.c
Author : Mr.xinghaizhuiqing
Version :
Copyright : Your copyright notice
Description : Hello World in C, Ansi-style
============================================================================
*/
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
void Swap(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
void AdjustUp(int* a, size_t child)
{
/*父子间下标关系计算公式
leftchild = parent*2 + 1
rightchild = parent*2 + 2
parent = (child - 1)/2
物理结构是数组,逻辑结构是完全二叉树*/
//向上调整算法,
printf("%d\n", child);
size_t parent = (child - 1) / 2;
while (child > 0)//因为child变为0,parent也会变成0,所以只能用child>0判断
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
//交换的是a数组的两个数,改变的是int,那就要传int*,改变地址
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
//向上调整--建堆
int i = 0;
for (i = 1; i < n; i++)
{
AdjustUp(a, i);
for (int j = 0; j < 10 ; j++)
{
printf("%d ", a[j]);
}
}
//向下调整--建堆
/*for (i = (n - 1 - 1) / 2; i >= 0; i--)//最后一个节点的父亲开始调整
{
AdjustDown(a, n, i);
}*/
}
int main()
{
int a[10] = { 5,7,8,9,20,50,10,30,6,11 };
HeapSort(a, 10);
int j = 0;
for (j = 0; j < 10; j++)
{
printf("%d ", a[j]);
}
return 0;
}
Base.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 01
#include
#include
#include
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//打印
void SLTPrint(SLTNode* phead);
//生成新的节点
SLTNode* BuySListNode(SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
// 找节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SLTDestroy(SLTNode** pphead);
LinkList.c
/*
============================================================================
Name : LinkList.c
Author : Mr.xinghaizhuiqing
Version :
Copyright : Your copyright notice
Description : Hello World in C, Ansi-style
============================================================================
*/
#include"Base.h"
SLTNode* BuySListNode(SLTDataType x)//申请新的节点
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
}
void SLTPrint(SLTNode* phead)//打印全部节点
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
SLTNode* newnode = BuySListNode(x);
//pphead空指针,对地址进行操作
if(!*pphead)
*pphead = newnode;
else//不为空,以下为对结构体进行操作
{
SLTNode* dit = *pphead;
while (dit->next)
{
dit = dit->next;
}
dit->next = newnode;
}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
SLTNode* newnode = BuySListNode(x);
if (!*pphead)//加这个干啥?
*pphead = newnode;
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}
void SLTPopBack(SLTNode** pphead)//尾删
{
//判空
assert(pphead);
assert(*pphead);//空链表不能删
//一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else//多个节点
{
SLTNode* tail = *pphead,*ftail=*pphead;
while (tail->next != NULL)
{
ftail = tail;
tail = tail->next;
}
free(ftail->next);
ftail->next = NULL;
}
}
void SLTPopFront(SLTNode** pphead)//头删
{
assert(*pphead);//判空
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{
//判空
assert(phead);
//遍历找值
SLTNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)// 在pos之前插入x
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
/*SLTNode* newnode=BuySListNode(x);
newnode->next = pos;
*pphead=newnode;*/
SLTPushFront(pphead, x);
}
else
{
SLTNode* pre = *pphead;
/*while (pre != NULL)
{
if (pre->next == pos)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = pos;
pre->next = newnode;
}
}*/
while (pre->next != pos)
{
pre = pre->next;
}
SLTNode* newnode = BuySListNode(x);
newnode->next = pos;
pre->next = newnode;
}
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)// 在pos以后插入x
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)// 删除pos位置
{
assert(pphead);
assert(pos);
if (*pphead == pos)//在头
{
SLTPopFront(pphead);
}
else
{
SLTNode* dit = *pphead;
while (dit->next != pos)
{
dit = dit->next;
}
dit->next = pos->next;
free(pos);
//pos=NULL//此为形参无用
}
}
void SLTEraseAfter(SLTNode* pos)// 删除pos的后一个位置
{
assert(pos);
assert(pos->next);//检查pos是否为尾结点
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
next = NULL;
}
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
main.c
#include"Base.h"
#include "LinkList.c"
void text()
{
SLTNode* plist = NULL;
SLTPushFront(&plist, 10);
SLTPushFront(&plist, 20);
SLTPushFront(&plist, 30);
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTNode* p = SLTFind(plist, 10);//把找到的地址给p
SLTInsert(&plist, p, 100);
SLTPrint(plist);
SLTInsertAfter(p, 200);
SLTPrint(plist);
SLTErase(&plist, p);
SLTPrint(plist);
SLTNode* pp = SLTFind(plist, 100);
SLTEraseAfter(pp);
SLTPrint(plist);
SLTDestroy(&plist);
}
int main()
{
text();
return 0;
}
#include
#include
int tmp[10] = {0};
int i,j;
int a = 0;
int b = 0;
int limit[50];
int jisuan();
void deleteElement();
int main(int argc, const char * argv[]) {
int n = 5;
//
int List[5] = {90,22,70,10,55};
int head = 20; //磁盘头
int N = 5;//磁盘点位数量
for(int c=0;c=N;c++){
printf("jisuan %d\n", c);
jisuan(head,List,N);
printf("Now disk seed in: %d \n",List[a]);
head = List[a];
deleteElement(List,a,N); //最后一个值变为了0
N = N - 1;
}
return 0;
}
void deleteElement(int list[],int index,int p){
for(int i=index;i<p;i++){
list[i] = list[i+1];
}
}
int jisuan(int head,int disk_Link[],int n){
//int *jisuan(){
//计算出最小的绝对值。第一个参数为锚点。
//第二个参数为传入的列表。
//第三个参数为列表的长度。
int temp = 9999;
for(int i=0;i<n;i++){
limit[i] = head - disk_Link[i];
if(limit[i] < 0){
limit[i] = limit[i] * -1;
}
if (limit[i] < temp){
temp = limit[i];
}
}
/*
for(int i=0;i
for(int i=0;i<n;i++){
if( temp == limit[i] ){
a = i;//得到下标
}
}
}