BF
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define pt putchar(10)
#define mem(x, y) memset(x, y, sizeof(x))
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;
struct node1
{
int address; //存储分区起始地址
int length; //存储分区长度
int flag; //存储分区标志,0 为空闲,1 为被作业占据
string s; //当 flag==1 时存储分区占用标志作业名,否则存储空 nil
bool operator<(const node1& x) const
{
return address > x.address; //从小到大排序
}
};
struct node2
{
int address;
int length;
int flag;
string s;
bool operator<(const node2 &x) const
{
return length>x.length;
}
};
priority_queue<node1> dtable1,dtable2;
priority_queue<node2> ftable1,ftable2;
void create1()
{
puts("address length flag(0 or 1) end with 0 0 0");
while(1)
{
int add,len,fl;
cin>>add>>len>>fl;
if(!add&&!len&&!fl) break;
node1 tmp;
tmp.address=add,tmp.flag=fl,tmp.length=len;
printf("input job_name:");
cin>>tmp.s;
dtable1.push(tmp);
pt;
puts("address length flag(0 or 1) end with 0 0 0");
}
}
void create2()
{
puts("address length flag(0 or 1) end with 0 0 0");
while(1)
{
int add,len,fl;
cin>>add>>len>>fl;
if(!add&&!len&&!fl) break;
node2 tmp;
tmp.address=add,tmp.flag=fl,tmp.length=len;
tmp.s="nil";
ftable1.push(tmp);
pt;
puts("address length flag(0 or 1) end with 0 0 0");
}
pt;
}
void show()
{
pt;
puts("The free table is :");
while(ftable1.size())
{
node2 tmp=ftable1.top();
ftable1.pop();
cout<<tmp.address<<", "<<tmp.length<<", "<<tmp.flag<<", "<<tmp.s<<endl;
ftable2.push(tmp);
}
pt;
puts("The distributed table is :");
while(dtable1.size())
{
node1 tmp=dtable1.top();
dtable1.pop();
cout<<tmp.address<<", "<<tmp.length<<", "<<tmp.flag<<", "<<tmp.s<<endl;
dtable2.push(tmp);
}
pt;
}
bool chk(int len,string s)
{
int jude=0;
int flag=1;
int minn=INT_MAX;
while(ftable2.size())
{
node2 tmp1=ftable2.top();
ftable2.pop();
if(flag&&tmp1.length>=len)
{
node1 tmp2;
tmp2.length=len,tmp2.flag=1,tmp2.s=s;
tmp2.address=tmp1.address;
dtable1.push(tmp2);
jude=1;
flag=0;
if(tmp1.length-len!=0)
{
tmp1.address+=len;
tmp1.length-=len;
ftable1.push(tmp1);
}
}
else if(!flag||tmp1.length<len)
{
ftable1.push(tmp1);
}
}
while(dtable2.size())
{
node1 tmp=dtable2.top();
dtable2.pop();
dtable1.push(tmp);
}
return jude;
}
int main()
{
puts("The distributed table is:");
create1();
puts("The free table is:");
create2();
show();
while(1)
{
printf("The length of worked job is:");
int tmpl;
cin>>tmpl;
printf("The name of worked job is:");
string tmps;
cin>>tmps;
if(chk(tmpl,tmps))
{
puts("distributing is successful");
show();
}
else
{
puts("distributing is not successful");
show();
}
}
}
/*
0 60 1
OS
60 40 1
Task1
132 40 1
Task2
626 174 1
Task6
438 92 1
Task5
205 15 1
Task4
160 40 1
Task3
0 0 0
100 32 0
150 10 0
200 5 0
530 96 0
220 218 0
0 0 0
*/
内存回收
//内存回收
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define pt putchar(10)
#define mem(x, y) memset(x, y, sizeof(x))
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;
int flagtype[5];
// 1 上空
// 2 下空
int ty = -1;
struct node {
int address; //存储分区起始地址
int length; //存储分区长度
int flag; //存储分区标志,0 为空闲,1 为被作业占据
string s; //当 flag==1 时存储分区占用标志作业名,否则存储空 nil
bool operator<(const node &x) const {
return address > x.address; //从小到大排序
}
};
priority_queue<node> dtable1, ftable1, dtable2, ftable2;
void create1() {
puts("address length flag(0 or 1) end with 0 0 0");
while (1) {
int add, len, fl;
cin >> add >> len >> fl;
if (!add && !len && !fl)
break;
node tmp;
tmp.address = add, tmp.flag = fl, tmp.length = len;
printf("input job_name:");
cin >> tmp.s;
dtable1.push(tmp);
pt;
puts("address length flag(0 or 1) end with 0 0 0");
}
}
void create2() {
puts("address length flag(0 or 1) end with 0 0 0");
while (1) {
int add, len, fl;
cin >> add >> len >> fl;
if (!add && !len && !fl)
break;
node tmp;
tmp.address = add, tmp.flag = fl, tmp.length = len;
tmp.s = "nil";
ftable1.push(tmp);
pt;
puts("address length flag(0 or 1) end with 0 0 0");
}
pt;
}
void show() {
pt;
puts("The free table is :");
while (ftable1.size()) {
node tmp = ftable1.top();
ftable1.pop();
cout << tmp.address << "," << tmp.length << "," << tmp.flag << ","
<< tmp.s << endl;
ftable2.push(tmp);
}
pt;
puts("The distributed table is :");
while (dtable1.size()) {
node tmp = dtable1.top();
dtable1.pop();
cout << tmp.address << "," << tmp.length << "," << tmp.flag << ","
<< tmp.s << endl;
dtable2.push(tmp);
}
pt;
}
int findtype() {
if (flagtype[1] && flagtype[2])
return 3;
else if (!flagtype[1] && !flagtype[2])
return 4;
else if (flagtype[1] && !flagtype[2])
return 1;
else
return 2;
}
bool chk(string s) {
int flag = 1;
int judge = 0;
int preadd = -1; //上一个占用分区的
int endadd = -1; //
int posadd = -1;
node tmp2;
while (dtable2.size()) {
node tmp1 = dtable2.top();
dtable2.pop();
if (tmp1.s == s && flag) {
flag = 0;
judge = 1;
if (endadd != tmp1.address) // 上空
flagtype[1] = 1;
if (dtable2.size()) {
node tmp3 = dtable2.top();
dtable2.pop();
if (tmp1.address + tmp1.length != tmp3.address)
flagtype[2] = 1; //下空
dtable1.push(tmp3);
} else {
if (tmp1.address + tmp1.length != 800)
flagtype[2] = 1; //下空
}
tmp2.address = tmp1.address;
tmp2.flag = 0;
tmp2.length = tmp1.length;
tmp2.s = "nil";
} else if (flag) {
endadd = tmp1.address + tmp1.length;
dtable1.push(tmp1);
} else if (!flag) {
dtable1.push(tmp1);
}
}
ty = findtype();
if (ty == 4) {
ftable1.push(tmp2);
while (ftable2.size()) {
node tmp1 = ftable2.top();
ftable2.pop();
ftable1.push(tmp1);
}
} else if (ty == 1) {
while (ftable2.size()) {
node tmp1 = ftable2.top();
ftable2.pop();
if (tmp1.address + tmp1.length == tmp2.address) {
tmp1.length += tmp2.length;
}
ftable1.push(tmp1);
}
} else if (ty == 2) {
while (ftable2.size()) {
node tmp1 = ftable2.top();
ftable2.pop();
if (tmp2.address + tmp2.length == tmp1.address) {
tmp1.address = tmp2.address;
tmp1.length += tmp2.length;
}
ftable1.push(tmp1);
}
} else if (ty == 3) {
while (ftable2.size()) {
node tmp1 = ftable2.top();
ftable2.pop();
if (tmp1.address + tmp1.length == tmp2.address) {
node tmp3 = ftable2.top();
ftable2.pop();
tmp1.length += tmp2.length + tmp3.length;
}
ftable1.push(tmp1);
}
}
return judge;
}
char aa[] = {"ABCD"};
int main() {
puts("The distributed table is:");
create1();
puts("The free table is:");
create2();
show();
puts("Input the released work segment sum:");
int nn;
cin >> nn;
For(iii, 1, nn) {
mem(flagtype, 0);
ty = -1;
cout << iii << ": input the released work segment name:";
string tmp;
cin >> tmp;
if (chk(tmp)) {
puts("Exists !");
cout << "The type of release is " << aa[ty - 1] << "!";
pt;
pt;
show();
} else {
puts("Not Exists !");
pt;
show();
}
}
}
/*
0 60 1
OS
60 40 1
Task1
100 32 1
Task2
132 18 1
Task3
160 40 1
Task4
200 5 1
Task5
205 15 1
Task6
438 92 1
Task7
626 174 1
Task8
0 0 0
150 10 0
220 218 0
530 96 0
0 0 0
*/
/*
int judge = 0;
int flag = 1;
int preadd = -1;
int posadd = -1;
int endadd = -1;
int lentmp = -1;
while (dtable2.size()) {
node tmp1 = dtable2.top();
dtable2.pop();
if (flag && tmp1.s == s) {
judge = 1;
flag = 0;
posadd = tmp1.address;
lentmp = tmp1.length;
endadd = posadd + lentmp;
if (preadd == posadd) { // up is not free
flagtype[0] = 1;
flagtype[2] = 1;
} else {
flagtype[1] = 1;
flagtype[3] = 1;
}
} else if (!flag) {
if (endadd == address) { // down is not free
flagtype[1] = 1;
flagtype[2] = 1;
}
dtable1.push(tmp);
}
preadd = tmp1.address += tmp1.length;
}
while (ftable2.size()) {
node tmp1 = ftable2.top();
ftable2.pop();
ftable1.push(tmp1);
}
return judge;
*/
第五章 实验四 模拟先进先出(FIFO)页面置换算法
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define mem(x, y) memset(x, y, sizeof(x))
#define pt putchar(10)
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;
const int N = 20;
const int M = 3;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
ll a[M]; //已装入内存
ll b[N]; //存放作业号序列
ll c[N]; //存放淘汰的页号
ll cnt; //缺页次数
bool flag; //表示该页是否在内存
bool find(int tmp) {
For(i, 0, 2) {
if (a[i] == tmp)
return true;
}
return false;
}
int p = 0;
void move(int tmp) {
if (a[2] != -1)
c[p++] = a[2];
a[2] = a[1];
a[1] = a[0];
a[0] = tmp;
}
int main() {
mem(a, -1);
cout << "Please enter the job number : ";
For(i, 1, 20) {
int tmp;
cin >> tmp;
if (!find(tmp)) {
move(tmp);
cnt++;
}
}
cout << "Number of missing pages : " << cnt;
pt;
pt;
printf("Page missing interrupt rate : %.2lf\%",
(double)(cnt * 100.0 / 20.0));
putchar('%');
pt;
pt;
cout << "The page numbers of resident memory are : ";
For(i, 0, 2) { cout << a[i] << ",\t"; }
pt;
pt;
cout << "The eliminated page numbers are : ";
For(i, 0, p - 1) { cout << c[i] << ",\t"; }
return 0;
}
/*
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
*/
第五章 实验五 模拟最近最久未使用(LRU)页面置换算法
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define mem(x, y) memset(x, y, sizeof(x))
#define pt putchar(10)
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;
const int N = 20;
const int M = 3;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
ll a[M]; //已装入内存
ll b[N]; //存放作业号序列
ll c[N]; //存放淘汰的页号
ll cnt; //缺页次数
bool find(int tmp) {
int flag = 0;
int pos = -1;
For(i, 0, 2) {
if (a[i] == tmp) {
flag = 1;
pos = i;
}
}
if (flag)
For(i, pos, 1) swap(a[i], a[i + 1]);
return flag;
}
int p = 0;
void move(int tmp) {
if (a[0] != -1)
c[p++] = a[0];
a[0] = a[1];
a[1] = a[2];
a[2] = tmp;
}
int main() {
mem(a, -1);
cout << "Please enter the job number : ";
For(i, 1, 20) {
int tmp;
cin >> tmp;
if (!find(tmp)) {
move(tmp);
cnt++;
}
}
cout << "Number of missing pages : " << cnt;
pt;
pt;
printf("Page missing interrupt rate : %.2lf\%",
(double)(cnt * 100.0 / 20.0));
putchar('%');
pt;
pt;
cout << "The page numbers of resident memory are : ";
For(i, 0, 2) { cout << a[i] << ",\t"; }
pt;
pt;
cout << "The eliminated page numbers are : ";
For(i, 0, p - 1) { cout << c[i] << ",\t"; }
return 0;
}
/*
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
*/
模拟缓冲池
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define mem(x, y) memset(x, y, sizeof(x))
#define pt putchar(10)
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;
const int N = 10;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const int INF = -32768;
inline ll read() {
ll s = 0, f = 1;
char ch;
do {
ch = getchar();
if (ch == '-')
f = -1;
} while (ch < 48 || ch > 57);
while (ch >= 48 && ch <= 57)
s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * f;
}
queue<int> emq, inq, outq;
void show() {
pt;
pt;
printf("The content of the free buffer queue emq:\n");
if (emq.empty())
printf("Empty buffer is empty.");
else
For(i, 1, emq.size()) {
int tmp = emq.front();
emq.pop();
printf("%d\t", tmp);
emq.push(tmp);
}
pt;
pt;
printf("Input buffer queue inq:");
pt;
if (inq.empty())
printf("Input buffer is empty.");
else
For(i, 1, inq.size()) {
int tmp = inq.front();
inq.pop();
printf("%d\t", tmp);
inq.push(tmp);
}
pt;
pt;
printf("output buffer queue outq:");
pt;
if (outq.empty())
printf("Output buffer is empty.");
else
For(i, 1, outq.size()) {
int tmp = outq.front();
outq.pop();
printf("%d\t", tmp);
outq.push(tmp);
}
pt;
pt;
}
void create() { For(i, 1, N) emq.push(INF); }
void menu() {
printf("what do you want to do?\n");
printf("1. Containment input\n");
printf("2. Extract input\n");
printf("3. Containment output\n");
printf("4. Extract output");
printf("5. drop out\n");
pt;
printf("Input your choice: ");
}
void solve1() {
if (emq.empty())
printf("Empty buffer is empty! Error");
else {
printf("\nContainment input--Please input data\n");
int d = read();
inq.push(d);
emq.pop();
}
show();
}
void solve2() {
if (inq.empty())
printf("Input buffer is empty! Error");
else {
printf("Extract input--Output 'extracted data': ");
int d = inq.front();
inq.pop();
emq.push(INF);
printf("%d\n", d);
}
show();
}
void solve3() {
if (emq.empty())
printf("Empty buffer is empty! Error");
else {
printf("\nContainment input--Please input data\n");
int d = read();
outq.push(d);
emq.pop();
}
show();
}
void solve4() {
if (outq.empty())
printf("Output buffer is empty! Error");
else {
printf("Extract output--Output 'extracted data': ");
int d = outq.front();
outq.pop();
emq.push(INF);
printf("%d\n", d);
}
show();
}
int main() {
pt;
create();
show();
int op;
while (1) {
menu();
op = read();
if (op == 1)
solve1();
else if (op == 2)
solve2();
else if (op == 3)
solve3();
else if (op == 4)
solve4();
else if (op == 5)
break;
}
return 0;
}
/*
2
1
12
1
24
2
4
3
-12
3
-24
4
*/
第六章 实验二 模拟最短寻道时间优先 SSTF 算法
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define mem(x, y) memset(x, y, sizeof(x))
#define pt putchar(10)
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
int a[N], vis[N];
char s[N];
inline ll read() {
ll s = 0, f = 1;
char ch;
do {
ch = getchar();
if (ch == '-')
f = -1;
} while (ch < 48 || ch > 57);
while (ch >= 48 && ch <= 57)
s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * f;
}
int main() {
printf("Enter the total number of magnetic cylinders : ");
int len = read();
pt;
printf("Enter the total number of disk read / write requests : ");
int num = read();
pt;
printf("Input disk read / write request cylinder number sequence : ");
For(i, 1, num) a[i] = read();
pt;
printf("Enter the current location of the disk as : ");
int add = read();
pt;
printf("The cylinder numbers accessed in turn are : ");
int cnt = 0;
For(i, 1, num) {
int minn = INT_MAX;
int pos = -1;
For(j, 1, num) {
if (!vis[j]) {
if (minn > abs(a[j] - add)) {
pos = j;
minn = abs(a[j] - add);
}
}
}
printf("%d\t", a[pos]);
cnt += abs(a[pos] - add);
add = a[pos];
vis[pos] = 1;
}
pt;
double avecnt = (double)cnt / num;
printf("\n Total number of times to move cylinder:%d\n ", cnt);
printf("\n The average number of moves is : %.2f \n", avecnt);
return 0;
}
/*
200
9
55 58 39 18 90 160 150 38 184
100
*/
第六章 实验三 模拟电梯调度算法
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define mem(x, y) memset(x, y, sizeof(x))
#define pt putchar(10)
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
int a[N], vis[N];
char s[N];
inline ll read() {
ll s = 0, f = 1;
char ch;
do {
ch = getchar();
if (ch == '-')
f = -1;
} while (ch < 48 || ch > 57);
while (ch >= 48 && ch <= 57)
s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * f;
}
int main() {
printf("Enter the total number of magnetic cylinders : ");
int len = read();
pt;
printf("Enter the total number of disk read / write requests : ");
int num = read();
pt;
printf("Input disk read / write request cylinder number sequence : ");
For(i, 1, num) a[i] = read();
pt;
printf("Enter the current location of the disk as : ");
int add = read();
printf("Enter the direction of disk movement (1 means move from inside to "
"outside, - 1 means move from outside to inside) : ");
int dir = read();
pt;
printf("The cylinder numbers accessed in turn are : ");
int cnt = 0;
sort(a + 1, a + num + 1);
int pos = -1;
For(i, 1, num - 1) {
if (a[i] <= add && a[i + 1] >= add) {
pos = i + 1;
break;
}
}
if (dir == 1) {
For(i, pos, num) {
cnt += abs(add - a[i]);
add = a[i];
printf("%d\t", a[i]);
}
Rep(i, pos - 1, 1) {
cnt += abs(add - a[i]);
add = a[i];
printf("%d\t", a[i]);
}
} else {
Rep(i, pos - 1, 1) {
cnt += abs(add - a[i]);
add = a[i];
printf("%d\t", a[i]);
}
For(i, pos, num) {
cnt += abs(add - a[i]);
add = a[i];
printf("%d\t", a[i]);
}
}
pt;
double avecnt = (double)cnt / num;
printf("\n Total number of times to move cylinder:%d\n ", cnt);
printf("\n The average number of moves is : %.2f \n", avecnt);
return 0;
}
/*
200
9
55 58 39 18 90 160 150 38 184
100
1
*/