湖北师范大学——操作系统实训题目
仅供参考,有更好的方法请评论,有错误请指出,谢谢!
题目1:进程调度1—静态非剥夺式优先级调度计算平均作业周转时间
问题描述:要求输入3个进程的信息,假设这些进程均是在0时刻同时到达,若进程调度采用非剥夺式静态优先级(优先数数值大的表示优先级比较高;如果遇到优先级一样,按照输入顺序执行。),计算并输出平均作业周转时间。
输入格式:程序要求输入3行,以回车符号作为分隔,每行有3个数据,以空格作为分隔。首先输入一个字符串(长度小于等于10),为进程名,第2个数据类型为整型,表示进程的优先数,第3个数据类型为整型,表示进程的运行时间。
输出格式:输出结果为一个浮点数,保留到小数点后一位,为系统的平均作业周转时间。
样例输入1:
P1 1 1
P2 2 2
P3 3 3
样例输出1:
4.7
样例输入2:
P1 10 10
P2 100 100
P3 100 100
样例输出2:
170.0
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct PROCESS
{
char PROCESS_NAME[10]; //进程名
int SPN; //优先数
int PTIME; //运行时间
};
int main()
{
struct PROCESS process[3];
int i,j,avag_time=0;
for(i=0;i<3;i++)
scanf("%s %d %d",&process[i].PROCESS_NAME,&process[i].SPN,&process[i].PTIME);
//优先级排序
for(i = 0;i<3;i++)
{
for(j = 0;j<2-i;j++)
{
struct PROCESS temp;
if(process[j+1].SPN>process[j].SPN)
{
temp = process[j];
process[j] = process[j + 1];
process[j + 1] = temp;
}
}
}
for(i=0;i<3;i++)
{
int time;
if(i==0)
time=process[i].PTIME;
else if(i==1)
time=process[i].PTIME+process[i-1].PTIME;
else
time = process[i].PTIME+process[i-1].PTIME+process[i-2].PTIME;
avag_time+=time;
}
printf("%.1f",avag_time/3.0);
system("pause");
return 0;
}
def time(Process, n):
ttime = 0
for i in range(n):
ttime += int(Process[i][2])
return ttime
if __name__ == '__main__':
Process = []
Time = []
for i in range(3):
Process.append(input().split())
Process.sort(key=lambda Process: Process[1], reverse=True)
for i in range(3):
Time.append(time(Process, i+1))
print('%.1f' % float(sum(Time)/3))
题目2:进程调度2–最高响应比优先计算每个作业的周转时间
问题描述:要求输入3个进程的信息,按照最高响应比优先的调度算法计算并输出每个进程的周转时间。(若两个进程的响应比相同,则优先选择先进入的进程。若两个进程的响应比相同,而且进入时刻也相同,则按照输入的顺序执行,如:P4和P6的响应比相同且进入时刻也相同,如P4先输入则选择P4先执行)
输入格式:程序要求输入3行,以回车符号作为分隔,每行有3个数据,以空格作为分隔。首先输入一个字符串(长度小于等于10),为进程名,第2个数据类型为整型,表示进程的进入时刻,第3个数据类型为整型,表示进程的运行时间。
输出格式:输出三个整数之间,整数之间用空格作为分隔,为每个进程的周转时间。
样例输入1:
P1 1 1
P2 2 2
P3 3 3
样例输出1:
1 2 4
样例输入2:
P1 1 4
P2 2 8
P3 3 1
样例输出2:
4 12 3
#include<stdio.h>
#include<stdlib.h>
struct PROCESS
{
char PROCESS_NAME[10];
int atime;
int rtime;
int ttime;
int X;
float Response_ratio;
};
int main()
{
struct PROCESS p[3];
for (int i=0;i<3;i++)
{
scanf("%s %d %d",&p[i].PROCESS_NAME,&p[i].atime,&p[i].rtime);
p[i].X=i+1;
}
struct PROCESS temp;
int nowtime=p[0].atime;
int sign=0;
int flag=0;
int m=0;
int n=0;
for(int i=1;i<3;i++)
{
if(p[i].atime==nowtime)
{
if(p[i].rtime<p[sign].rtime)
{
sign=i;
nowtime=p[i].atime;
temp=p[i];
p[i]=p[0];
p[0]=temp;
}
}
else if(p[i].atime<nowtime)
{
sign=i;
nowtime=p[i].atime;
temp=p[i];
p[i]=p[0];
p[0]=temp;
}
}
while (1)
{
if(p[m].atime>=n)
{
p[m].ttime=p[m].rtime;
n=p[m].atime+p[m].rtime;
}
else
{
p[m].ttime=p[m].rtime+n-p[m].atime;
n+=p[m].rtime;
}
for(int i=1;i<3;i++)
{
p[i].Response_ratio=(float)(n-p[i].atime)/p[i].rtime;
}
m++;
if(m==3)
{
break;
}
if(flag==0)
{
if(p[1].Response_ratio>=p[2].Response_ratio)
{
if(p[1].Response_ratio==p[2].Response_ratio)
{
if(p[1].X>p[2].X)
{
temp=p[1];
p[1]=p[2];
p[2]=temp;
}
}
}
else
{
temp=p[1];
p[1]=p[2];
p[2]=temp;
}
flag=1;
}
}
for(int i=0;i<2;i++)
{
for(int j=1;j<3;j++)
{
if(p[i].X>p[j].X)
{
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
}
for(int i=0;i<3;i++)
{
printf("%d ",p[i].ttime);
}
}
下面的有些许问题:(请在评论区提出错误,不甚感激!)
#include<stdio.h>
#include<stdlib.h>
struct PROCESS
{
char PROCESS_NAME[10]; //进程名
int atime; //到达时间
int rtime; //运行时间
int ttime; //周转时间
int X; //进程编号
float Response_ratio; //响应比
int state; //执行状态 1表示已经执行
};
void HRRF(struct PROCESS *p)
{
int count = 0; //记录已经完成的进程数
int position = 0; //记录未完成进程的位置
int nowtime = 0; //现在的时刻
while (count < 3)
{
float max_rp = 0;
int next = 0; //记录下一个要运行的进程的位置下标
//找出最大响应比的进程下标
for (int i = position; i < 3 && p[i].atime <= nowtime && i!=0; i++)
{
if (p[i].state == 1)
{
continue;
}
if (p[i].Response_ratio > max_rp)
{
max_rp = p[i].Response_ratio;
next = i; //记录下一个要执行进程下标
}
}
//到达的进程都运行完毕, 后续进程还没到达(或者没有进程到达)
if (nowtime < p[position].atime * 1.0)
{
nowtime = p[position].atime * 1.0;
next = position;
}
int flag = p[next].X;
nowtime = nowtime + p[next].rtime; //更新现在时间
p[next].state = 1; //更新运行状态
p[flag].ttime = nowtime - p[next].atime; //周转时间 =现在时间-到达时间
count++; //运行完成的个数
for (int i = position; i < 3; i++)
{ //指向下一个未运行的进程
if (p[i].state == 0)
{
position = i;
break;
}
}
//响应比 = 1+(现在时间-到达时间)/运行时间
for (int j = 0; j < 3 && p[j].atime <= nowtime; j++)
{
//进程已完成,无需计算响应比
if (p[j].state == 1)
continue;
else
p[j].Response_ratio = 1 + (nowtime - p[j].atime) / (p[j].rtime*1.0);
}
}
}
int main()
{
struct PROCESS p[3];
int i,j;
for(i=0;i<3;i++)
{
scanf("%s %d %d",&p[i].PROCESS_NAME,&p[i].atime,&p[i].rtime);
}
for(i=0;i<3;i++)
{
p[i].X=i;
p[i].state = 0; //执行状态全置0
}
//到达时间按升序排序
for (i = 0; i < 3; i++)
{
struct PROCESS temp;
for (j = 0; j < 2-i; j++)
{
if (p[j].atime >= p[j + 1].atime)
{
temp = p[j];
p[j] = p[j + 1];
p[j + 1] = temp;
}
}
}
HRRF(p);
for (int i = 0; i < 3; i++)
printf("%d ", p[i].ttime);
return 0;
}
题目3:进程调度3
问题描述:要求输入N个进程(N为正整型数,0<N<=25535),输出按照优先级从高到低执行的进程名字符串序列,直至结束。(如果遇到优先级一样,按照输入顺序先后执行。),本题中,优先数数值较高的进程,优先级也较高。
输入格式:程序首先要求输入一个整型变量N,接下来输入为N行,以回车符号作为分隔,每行有3个数据,以空格作为分隔。首先输入一个字符串(长度小于等于10),该字符串为进程名。第2个数据类型为整型,表示进程的优先数。第3个数据类型为整型,表示进程的运行时间。
输出格式:输出1行,M个字符串,字符串之间用空格作为分隔。
样例输入1:
3
P1 1 1
P2 2 2
P3 3 3
样例输出1:
P3 P2 P3 P1 P2 P3
样例输入2:
2
P1 3 3
P2 1 1
样例输出2:
P1 P1 P1 P2
#include <stdio.h>
#include <string.h> //strcpy()
#include<stdlib.h>//malloc()
struct PROCESS
{
char Process_Name[10];
int Priority;
int Time;
};
int main()
{
int i,j,k,n;
scanf("%d",&n);
struct PROCESS process[n];
for (i = 0; i < n; i++)
{
scanf("%s %d %d",&process[i].Process_Name,&process[i].Priority,&process[i].Time);
}
//算法实现
int sum=0;
char Return_Process_Name[10];
for (i = 0; i < n; i++)
{
sum+=process[i].Time;
}
int max=process[0].Priority;
strcpy(Return_Process_Name,process[0].Process_Name);
for(i=0;i<sum;i++)
{
for(j=0;j<n;j++)
{
if((process[j].Time > 0) && (process[j].Priority > max))
{
max = process[j].Priority;
strcpy(Return_Process_Name,process[j].Process_Name);
}
}
for(k=0;k<n;k++)
{
if(strcmp(process[k].Process_Name,Return_Process_Name) == 0)
{
printf("%s ",process[k].Process_Name);
process[k].Priority--;
process[k].Time--;
}
}
max=process[0].Priority;
strcpy(Return_Process_Name,process[0].Process_Name);
}
return 0;
}
if __name__ == '__main__':
Process = []
n = int(input())
for i in range(n):
Process.append(input().split())
sum = 0
for i in range(n):
sum += int(Process[i][2])
for i in range(sum):
Process.sort(key=lambda Process: Process[0], reverse=False)
Process.sort(key=lambda Process: int(Process[1]), reverse=True)
Process[0][1] = int(Process[0][1])-1
Process[0][2] = int(Process[0][2])-1
print(Process[0][0], end=' ')
题目4:进程调度4—-时间片轮转
问题描述:要求输入N个进程(0<N<=100),输入时间片M(0<M〈=5),按照进程输入的顺序以时间片轮转的方法输出指定的第K轮(K>0)执行的那个进程的进程名。
输入格式:程序首先输入一个正整数M(0<M〈=5)作为时间片,下一行输入一个正整数N(0<N<=100),接下来输入为N行,以回车符号作为分隔,每行有2个数据,以空格作为分隔。第一个数据是字符串(长度小于等于10),该字符串为进程名,第2个数据类型为整型,表示该进程需要的运行时间。最后输入一个正整数K,作为时间片轮转的次数(次数从1开始计数)。
输出格式:输出一个字符串,为最后执行进程的进程名;若无进程运行,则输出“over”(不含双引号,所有字母皆为小写)。
样例输入1:
1
3
P1 1
P2 2
P3 3
3
样例输出1:P3
样例输入2:
1
3
P1 1
P2 2
P3 3
10
样例输出2:over
#include<stdio.h>
#include<stdlib.h>
struct PROCESS{
char PROCESS_NAME[10]; //进程名
int PTIME; //运行时间
};
int main(){
int M,N,K,Count,Num_Count=0,Final_Num_Count;
scanf("%d %d",&M,&N); //输入一个正整数M(0<M<=5)作为时间片 一个正整数N(0<N<=100),接下来输入为N行
struct PROCESS process[N];
int i,j=0,avag_time=0;
for(i=0;i<N;i++)
scanf("%s %d",&process[i].PROCESS_NAME,&process[i].PTIME);
scanf("%d",&K);
for (i = 0; i < 100; i++)
{
while(j<N){
if(process[j].PTIME>0)
{
process[j].PTIME -= M;
Num_Count++;
Final_Num_Count=Num_Count;
if (Num_Count==K)
printf("%s",process[j].PROCESS_NAME);
}
j++;
}
j=0;
}
if(Final_Num_Count < K)
printf("over");
}
题目5:死锁—利用银行家算法判断系统的安全性
问题描述:假设系统中有A、B、C三类资源,且有四个并发进程,要求输入资源总量Resource,以及每个进程运行所需的资源总量Claim和已经分配得到的资源量Allocation,利用银行家算法判断当前状态是否为安全状态,若为安全状态则给出一个安全序列。
输入格式:程序要求输入五行,以回车符号作为分隔。第一行是三个整数,整数之间以空格作为分隔,表示A、B、C三类资源的总量。下面的四行分别表示每个进程运行所需的资源总量Claim和已经分配得到的资源量Allocation;每行有7个数据,以空格作为分隔。首先输入一个字符串(长度小于等于10),为进程名;第2、3、4个数据类型为整型,表示相应进程运行所需A、B、C三种资源总量Claim;第5、6、7个数据类型为整型,表示相应进程已经分配得到的A、B、C三种资源量Allocation。
输出格式:输出一个字符串。若当前为不安全状态则输出为”false”(不含双引号,所有字母皆为小写);若当前为安全状态则输出一个安全序列,进程名之间用空格作为分隔)。
样例输入1:
9 5 7
P1 5 3 4 2 1 3
P2 9 5 2 2 1 1
P3 3 2 2 2 2 1
P4 6 4 1 1 1 1
样例输出1:
P3 P1 P4 P2
样例输入2:
9 5 7
P1 5 3 4 2 1 4
P2 9 5 2 2 1 1
P3 3 2 2 2 2 1
P4 6 4 1 1 1 1
样例输出2:
false
#include<stdio.h>
#include<stdlib.h>
struct Process{
char Process_Name[10]; //进程名
int Claim[3]; //每个进程运行所需的资源总量
int Allocation[3]; //已经分配得到的1资源量
int Need[3]; //进程当前所需要的资源
};
int main()
{
int Resource[3]; //A、B、C三类资源的总数向量
int Available[3]; //系统中每类资源当前可用量
struct Process process[4];
int i,j,k=0,m,n;
for(i=0;i<3;i++)
scanf("%d",&Resource[i]);
for(i=0; i<4; i++)
{
for(j=0; j<7; j++)
{
if(j == 0)
scanf("%s",&process[i].Process_Name);
else if(j<4)
scanf("%d",&process[i].Claim[j-1]);
else
scanf("%d",&process[i].Allocation[j-4]);
}
}
//初始化进程需要的资源向量
for(i=0;i<4;i++)
{
for(j=0;j<3;j++)
{
process[i].Need[j] = process[i].Claim[j]-process[i].Allocation[j];
}
}
for(i=0;i<3;i++)
{
int sum = 0;
for(j=0;j<4;j++)
{
sum+=process[j].Allocation[i];
}
Available[i]=Resource[i]-sum;
}
int Work[3]; //工作向量
int Temp[4]; //存放安全序列编号
int Finish[4]; //1:当前进程安全 0:不安全
for(i=0;i<4;i++)
Finish[i]=0;
for(i=0;i<3;i++)
Work[i]=Available[i]; //初始化工作向量
for(i=0; i<4; i++)
{
int flag=0;
for(j=0; j<4; j++)
{
if(flag==1)
break;
int count=0;
for(n=0;n<3;n++)
{
if(Finish[j]==0 && process[j].Need[n]<=Work[n])
{
count++;
}
if(count==3) //请求的资源都小于剩余的资源数
{
flag=1;
for(m=0; m<3; m++)
{
Work[m] += process[j].Allocation[m];
}
Finish[j] = 1; //满足的进程置1
Temp[k] = j+1; //记录进程编号
k++; //序列安全+
}
}
}
}
if(k!=4) //有一个进程不满足条件,则断言系统不是安全状态,输出"false"
{
printf("false");
}
else //所有进程都满足,断言系统为安全状态,输出安全序列
{
for(i=0;i<4;i++)
{
printf("P%d ",Temp[i]);
}
}
system("pause");
return 0;
}
题目6:存储管理—可变分区存储管理方式的最佳适应分配算法
问题描述:当内存管理采用可变分区分配方案时,要求输入多个空闲分区和进程内存请求序列,输出显示采用下次适应分配算法分配给各个进程的分区编号。
输入格式:程序要求输入3行,以回车符号作为分隔,第一行是一个整数n(n>=3),表示空闲分区的数量;第二行是n个整数,依次按地址递增对应第一行n个空闲分区的存储容量,每个整型数的数值代表所对应空间的剩余存储容量。n个分区(分区按地址递增依次从1开始编号,若分区X被切割分配了,剩余部分即使为0也保留原来的分区编号X)。第三行是3个整数,两个数之间以空格作为分隔,分别表示三个进程先后依次申请的内存空间的大小。
输出格式:输出一行三个整数,整数之间用空格作为分隔,分别表示三个进程所分配的分区编号;若分配失败,则用”false”表示(不含双引号,所有字母皆为小写)。
样例输入1:
6
20 5 6 18 60 4
12 7 20
样例输出1:
4 1 5
样例输入2:
5
10 20 60 30 40
50 48 25
样例输出2:
3 false 4
#include<stdio.h>
#include<stdlib.h>
#define M 100
struct MEMORY
{
int storage_capacity; //存储容量
int X; //分区编号
};
int main()
{
int i,j,k,n,m,sign;
scanf("%d",&n); //空闲分区的数量
if(n<3)
{
exit(0);
}
MEMORY memory[M]; //空闲分区表
int process[3]; //三个进程先后依次申请的内存空间的大小
for(i=0;i<n;i++)
scanf("%d",&memory[i].storage_capacity);
for(i=0;i<3;i++)
scanf("%d",&process[i]);
for(i=0;i<n;i++)
memory[i].X = i+1;
for(i=0;i<3;i++)
{
sign = -1;
//按升序排序
for(k=0; k<n; k++)
{
for(m = 0;m<n-k-1;m++)
{
struct MEMORY temp;
if(memory[m].storage_capacity>memory[m+1].storage_capacity)
{
temp = memory[m];
memory[m] = memory[m + 1];
memory[m + 1] = temp;
}
}
}
/*
printf("剩余内存\t分区编号\n");
for(int y =0;y<n;y++)
{
printf("%d\t\t%d\n",memory[y].storage_capacity,memory[y].X);
}
*/
for(j=0;j<n;j++)
{
if(memory[j].storage_capacity >= process[i])
{
sign=memory[j].X;
memory[j].storage_capacity-=process[i];
break;
}
}
if(sign==-1)
printf("false ");
else
printf("%d ",sign);
printf("\n");
}
return 0;
}
题目7:存储管理—FIFO页面替换算法计算中断次数
问题描述:在请求分页式存储管理方式中,要求输入一个对5个页面的访问序列,输出当系统分配给进程物理页框数为m个时,按照FIFO页面替换算法的缺页中断次数(假设初始时页框均为空)。
输入格式:程序要求输入3行,以回车符号作为分隔,第一行是一个整数n,表示页面访问序列中访问页面的次数;第二行是n个整数,数之间以空格作为分隔,表示页面访问序列。第三行是一个整数m,表示系统分配给进程物理页框数。
输出格式:输出一个整数,表示缺页中断次数。
样例输入1:
12
4 3 2 1 4 3 5 4 3 2 1 5
3
样例输出1:
9
样例输入2:
12
4 3 2 1 4 3 5 4 3 2 1 5
4
样例输出2:
10
#include<stdio.h>
int FIFO(int a[],int b[],int n,int m)
{
int i,j,k,count=0;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{ //遍历m个物理块
if(a[i]==b[j])
{ //判断物理块中是否存在该页面
break;
}
}
if(j==m)
{ //如果物理块中不存在该页面
for(k=0;k<m-1;k++)
{
b[k]=b[k+1];
}
b[k]=a[i];//替换最先进入物理块的页面,即数组索引为0的页面
count++;
}
}
return count;
}
int main(){
int n,m; //m:系统分配给进程物理页框数
int a[n]; //页面访问序列
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&m);
int b[m]; //页面框
for(int i=0; i<m; i++)
{
b[i]=32767;
}
int count=FIFO(a,b,n,m);
printf("%d",count);
return 0;
}
题目8:存储管理1
问题描述:现有一个8*8的存储器,要对其空间进行分配。(下标从0开始,最后一个内存块下标为63)。现已有块号为1、7、13、23、47、59的几个内存块被占用。现操作系统要求申请N块内存空间(0<N<=64),当输入的块数N超出其剩余空闲块数的时候,输出为“false”,当输入为合理范围的时候,就输出其以行主序分配的最后一个内存空间的下标。
输入格式:程序要求输入一个整型数N,表示要申请分配空间的大小。
输出格式:输出为一个整型数,表示最后一个被分配空间的下标。
样例输入1:
3
样例输出1:
3
样例输入2:
100
样例输出2:
false
#include <stdio.h>
int main()
{
int s_c[64]={0};
int i,n,count=0;
s_c[1]=1;
s_c[7]=1;
s_c[13]=1;
s_c[23]=1;
s_c[47]=1;
s_c[59]=1;
scanf("%d",&n);
if(n==1)
printf("0");
else if(n>58)
printf("false");
else
{
for(i=0;i<n+1;i++)
{
if (s_c[i]==1)
{
count++;
}
}
printf("%d", count+n-1);
}
return 0;
}
题目9:存储管理2
问题描述:现有一个8*8的存储器,要对其空间进行分配。(下标从0开始,最后一个内存块下标为63)。现已有块号为2、7、13、23、37、47、59、61的几个内存块被占用。要求输入需分配的进程数M(0<M<=56),接下来输入为M个整型数,每个数为各个进程需占用的内存块数。当分配到某进程时,其剩余空闲块数可以分配,就输出当前进程分配的最后一个内存空间的下标。当分配到某进程时,其进程块数超出剩余空闲块数无法分配,输出为“false”(不含双引号,且为全小写)。输出的多个下标(或"false")之间用空格隔开。
输入格式:程序输入分为两行,第一行要求输入一个整型数M,表示要所需分配空间的进程数,接下来的第二行输入M个整型数,每个数之间用空格隔开,表示M个进程每个进程占用的内存空间大小。
输出格式:输出为M组整型数(或"false"),每个整型数表示该进程最后一个被分配的内存空间的下标(或"false"),下标(或"false")之间用空格隔开。
样例输入1:
3
3 3 3
样例输出1:
3 6 10
样例输入2:
4
3 3 64 3
样例输出2:
3 6 false 10
#include <stdio.h>
#include <string.h>
void management(int space,int s_c[64],int residue)
{
int i=0,count=0,index=0,Final_Index=0;
if (space>residue) //申请的内存大于剩余的空间,输出false
{
printf("false ");
}
else
{
if(space==54)
{
Final_Index = 60;
printf("%d ",Final_Index);
s_c[Final_Index]=1;
}
else if(space>=55)
{
Final_Index = space+7;
printf("%d ",Final_Index);
for(i=Final_Index-1;i<Final_Index;i++)
{
s_c[Final_Index]=1;
}
}
else
{
for (i = 0; i < 64; i++)
{
if (s_c[i]==0)
{
index=i;
goto Next_Process;
}
}
Next_Process:
for(i=index;i<index+space;i++)
{
if (s_c[i]==1)
{
count++;
}
}
for (i = index; i < index+count+space; i++)
{
if (s_c[i]==0)
{
Final_Index=i;
s_c[i]=1;
}
}
printf("%d ", Final_Index);
}
}
}
int main()
{
int s_c[64]={0};
//初始化内存块
s_c[2]=1;
s_c[7]=1;
s_c[13]=1;
s_c[23]=1;
s_c[37]=1;
s_c[47]=1;
s_c[59]=1;
s_c[61]=1;
int M; //需分配的进程数M(0<M<=56)
int max_process_number=56;
int space[M]; //进程占用的内存空间大小
int residue[M];
int i;
scanf("%d",&M);
for (i = 0; i < M; i++)
{
scanf("%d",&space[i]);
residue[i]=max_process_number;
if (max_process_number>space[i])
{
max_process_number-=space[i];
}
}
for (i = 0; i < M; i++)
{
management(space[i],s_c,residue[i]);
}
return 0;
}
题目10:存储管理3
问题描述:现有一个8*8的存储器,要对其已分配的空间进行分配及回收。(下标从0开始,最后一个内存块下标为63)。现已有块号为2、7、13、23、37、41、47、59、61的几个内存块被占用。要求输入需分配的进程数M(0<M<=55),接下来输入为M个整型数,每个数为各个进程需占用的内存块数。当分配到某进程时,其剩余空闲块数可以分配,就输出当前进程分配的最后一个内存空间的下标。当分配到某进程时,其进程块数超出剩余空闲块数无法分配,输出为“false”(不含双引号,且为全小写)。输出的多个下标(或"false")之间用空格隔开。以上进程不管是否分配成功,按照输入顺序依次命名为p1、p2、p3………pM。回收的时候输入进程名pN,则返回进程名为pN的所有占用内存块号下标,如果该进程名不存在或输入的数值为不合理范围,则返回“false”。
输入格式:程序输入分为三行,第一行是一个整型数M,表示要所需分配空间的进程数,第二行为M个整型数,每个数之间用空格隔开,表示M个进程每个进程占用的内存空间大小。第三行为需要回收的进程名pN,p为小写字母,N为正整型数。
输出格式:输出为两行,第一行为一组整型数,每个整型数表示该进程最后一个被分配的内存空间的下标,下标之间用空格隔开。第二行为一组整型数,表示被回收的进程的内存块下标,多个下标之间用空格隔开。
样例输入1:
3
3 3 3
p3
样例输出1:
3 6 10
8 9 10
样例输入2:
4
3 3 64 3
p3
样例输出2:
3 6 false 10
false
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct Process
{
int space; //进程申请的内存
int process_number; //进程编号
};
/*
*@space 申请的内存
*@s_c[] 已分配的空间表1
*@s_c1[][55] 记录当前程序占用的内存的下标
*@residue 当前剩余的内存空间
*@process_num 当前程序的编号
*/
int management(int space,int s_c[],int s_c1[][55],int residue,int process_num)
{
int i=0,j=0,k=0,count=0,index=0,Final_Index=0;
if (space>residue) //申请的内存大于剩余的空间,输出false
{
printf("false ");
return 0;
}
else
{
if(space==53)
{
printf("%d\n",60);
for(i=0;i<=60;i++)
{
if (s_c[i]==0)
{
s_c1[process_num][j]=i;
j++;
s_c[i]=1;
}
}
}
else if(space>=54)
{
Final_Index = space+8;
printf("%d ",Final_Index);
for(i = 0;i <= Final_Index;i++)
{
if (s_c[i]==0)
{
s_c1[process_num][j]=i;
j++;
s_c[i]=1;
}
}
}
else
{
for (i = 0; i < 64; i++)
{
if (s_c[i]==0)
{
index=i;
goto Next_Process;
}
}
Next_Process:
for(i = index;i < index+space+1;i++)
{
if (s_c[i]==1)
{
count++;
}
}
for (i = index; i < index+count+space; i++)
{
if (s_c[i]==0)
{
Final_Index=i;
s_c1[process_num][j]=i;
j++;
s_c[i]=1;
}
}
printf("%d ", Final_Index);
}
return 1;
}
}
int main()
{
int s_c[64]={0};
//初始化内存块
s_c[2]=1;
s_c[7]=1;
s_c[13]=1;
s_c[23]=1;
s_c[37]=1;
s_c[41]=1;
s_c[47]=1;
s_c[59]=1;
s_c[61]=1;
int M; //需分配的进程数M(0<M<=55)
scanf("%d",&M);
int s_c1[M][55]; //进程占内存的号码
int max_process_number=55;
int residue[M];
char reclaim_process[10]; //需回收的进程名
int i;
struct Process process[M];
int flag[M][1]; //函数返回值
for (i = 0; i < M; i++)
{
scanf("%d",&process[i].space);
residue[i]=max_process_number;
if (max_process_number>process[i].space)
{
max_process_number-=process[i].space;
}
process[i].process_number = i+1;
}
scanf("%s",&reclaim_process);
for (i = 0; i < M; i++)
{
flag[i][0] = management(process[i].space,s_c,s_c1,residue[i],i);
}
printf("\n");
int reclaim_process_num = reclaim_process[1]-48;
for(int i=reclaim_process_num-1;;)
{
if(flag[reclaim_process_num-1][0]==0)
{
printf("false");
}
else
{
for(int j=0;j<process[i].space;j++)
{
int k = s_c1[i][j];
s_c[k] = 0;
printf("%d ",k);
}
}
break;
}
return 0;
}
题目11:带存储管理的处理器调度4
问题描述:现有一个内存为100K的采用位示图进行页面管理的道数不受限制的多道程序设计系统,若作业调度采用高优先级(优先数越大优先级越大)调度算法(如果遇到优先级一样且只能调入一道作业时,按照输入顺序选择调度对象。),进程调度采用非剥夺式的SJF调度算法(如果遇到运行时间相同的进程,按照输入顺序选择调度对象。)。要求输入3个进程信息,输出当三个作业同时提交进入调度时进程的运行顺序。
输入格式:程序要求输入3行,以回车符号作为分隔,每行有4个数据,以空格作为分隔。首先输入一个字符串(长度小于等于10),为进程名;第2个数据类型为整型,表示进程所需的内存空间;第3个数据类型为整型,表示进程的运行时间;第4个数据类型为整型,表示进程的优先数。
输出格式:输出1行,M个字符串,字符串之间用空格作为分隔。
样例输入1:
P1 20 2 1
P2 60 3 2
P3 30 4 3
样例输出1:
P2 P1 P3
样例输入2:
P1 80 2 2
P2 30 5 3
P3 40 3 1
样例输出2:
P3 P2 P1
def HRRF(Storage): # 高优先级作业调度
for s in Storage:
global space # space:内存空间
if int(s[1])+space <= 100:
space += int(s[1])
Memory.append(s)
def SJF(Memory): # 短作业优先进程调度
Memory.sort(key=lambda Memory: [Memory[2], Memory[0]], reverse=False)
for M in Memory:
if M in Storage:
Storage.remove(M)
job = Memory.pop(0)
global count # 已完成进程的个数
count += 1
global space
space -= int(job[1])
print(job[0], end=' ')
if __name__ == '__main__':
Storage = [] # 外存中的进程
Memory = [] # 内存中的进程
for i in range(3):
Storage.append(input().split())
Storage.sort(key=lambda Storage: Storage[3], reverse=True) # 按优先级降序排序
space = 0
count = 0
while count < 3:
HRRF(Storage)
SJF(Memory)
题目12:驱动调度—采用电梯调度算法排列出磁盘请求响应次序
问题描述:要求输入一个柱面访问请求序列以及当前磁头所在柱面号和移动方向,输出采用电梯调度算法时移动臂响应的柱面访问序列。
输入格式:程序要求输入3行,以回车符号作为分隔,第一行是2个整数n、m,之间用空格隔开,n表示当前磁头所在的柱面号;m表示第二行输入m个数;第二行是m个整数,数之间以空格作为分隔,表示柱面访问请求序列;第三行是数字-1或1,当为-1时表示移动臂向柱面号减小方向移动,当为1时表示移动臂向柱面号增大方向移动。
输出格式:输出m个整数,数之间以空格作为分隔,采用电梯调度算法时移动臂响应的柱面访问序列。
样例输入1:
15 10
24 38 2 110 43 36 5 11 6 180
-1
样例输出1:
11 6 5 2 24 36 38 43 110 180
样例输入2:
15 10
24 38 2 110 43 36 5 11 6 180
1
样例输出2:
24 36 38 43 110 180 11 6 5 2
#include <stdio.h>
#include <stdlib.h>
#define maxnum 100
void LOOK(int visitlist[maxnum],int list[maxnum],int n,int direct,int m)
{
int flag,k=0;
for(int i=0; i<m; i++)
{
if(visitlist[i]>=n)
{
flag = i;
break;
}
}
if(direct == -1)
{
for(int i=flag-1; i>-1; i--)
{
list[k] = visitlist[i];
k++;
}
for(int j=flag; j<m; j++)
{
list[k] = visitlist[j];
k++;
}
}
else
{
for(int i=flag; i<m; i++)
{
list[k] = visitlist[i];
k++;
}
for(int j=flag-1; j>-1; j--)
{
list[k] = visitlist[j];
k++;
}
}
}
//对柱面号序列进行从小到大的排序
void bubblesort(int visitlist[],int m)
{
for(int i=0; i<m; i++)
{
int temp;
for(int j=0; j<m-i-1; j++)
{
if(visitlist[j]>visitlist[j+1])
{
temp = visitlist[j+1];
visitlist[j+1] = visitlist[j];
visitlist[j] = temp;
}
}
}
}
int main()
{
int n,m; //n表示当前磁头所在的柱面号;m表示第二行输入m个数
scanf("%d %d",&n,&m);
int i,direct;
int visitlist[maxnum];
int list[maxnum];
for(i = 0;i < m;i++)
scanf("%d",&visitlist[i]); //柱面访问请求序列
scanf("%d",&direct); //移动臂移动方向,-1表示移动臂向柱面号减小方向移动,1表示移动臂向柱面号增大方向移动
bubblesort(visitlist,m);
/*for(int i=0;i<m;i++)
{
printf("%d ",visitlist[i]);
}
printf("\n");
*/
LOOK(visitlist,list,n,direct,m);
for(i = 0;i < m;i++)
printf("%d ",list[i]);
return 0;
}