#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;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
#define M 100
#define N 200
int n, m;
int Resource[M];
int Max[N][M];
int Allocation[N][M];
int Need[N][M];
int Available[M];
int Work[M];
bool Finish[N];
int List[N]; //存放安全序列的下标序列
void initial() {
//创建初始状态：先输入 Resource、Max 和 Allocation
//再计算出 Need、Available。
//填补程序
puts("How many processes and how many resources are there");
cin >> n >> m;
cout << n << "\t" << m << "\n";
puts("Resourse,Total amount of each resource(m)");
For(i, 0, m - 1) cin >> Resource[i], Available[i] = Resource[i];
For(i, 0, m - 1) cout << Resource[i] << "\t";
pt;
puts("The maximum demand of each resource for n processes");
For(i, 0, n - 1) For(j, 0, m - 1) cin >> Max[i][j];
For(i, 0, n - 1) {
For(j, 0, m - 1) cout << Max[i][j] << "\t";
pt;
}
puts("How many resources are currently allocated to each process");
For(i, 0, n - 1) For(j, 0, m - 1) cin >> Allocation[i][j];
For(i, 0, n - 1) {
For(j, 0, m - 1) cout << Allocation[i][j] << "\t";
pt;
}
// puts("How much does each process need for each resource to run now");
For(i, 0, n - 1) For(j, 0, m - 1) Need[i][j] = Max[i][j] - Allocation[i][j];
puts("Show the resources needed by each process currently");
For(i, 0, n - 1) {
For(j, 0, m - 1) { cout << Need[i][j] << "\t"; }
cout << "\n";
}
For(i, 0, n - 1) For(j, 0, m - 1) Available[j] -= Allocation[i][j];
puts("Current number of resources remaining");
For(i, 0, m - 1) cout << Available[i] << "\t";
pt;
}
void printState() {
//输出当前的状态表|Process |Max |Allocation |Need |Available|
//填补程序
pt;
pt;
puts("Current state");
cout << "|Process"
<< "|Max\t\t\t"
<< "|Allocation\t\t"
<< "|Need\t\t\t"
<< "|Available\t\t|";
pt;
For(i, 0, n - 1) {
cout << "|P" << i << "\t|";
For(j, 0, m - 1) cout << Max[i][j] << "\t";
cout << "|";
For(j, 0, m - 1) cout << Allocation[i][j] << "\t";
cout << "|";
For(j, 0, m - 1) cout << Need[i][j] << "\t";
cout << "|";
if (!i)
For(j, 0, m - 1) cout << Available[j] << "\t";
if (!i)
cout << "|";
else
cout << "\t\t\t|";
pt;
}
pt;
pt;
}
// int isfinish() {
//返回同时满足两个条件;
//{1.Finish[i]=false 2.Need[i][j]≤Work[j]}
//的进程下标i(修改Finish[i]=true)，否则返回-1
//填补程序
//}
bool issafe() {
//判定当前状态是否为安全状态
//（返回 true 或 false），把安全序列的下标放入List[N]数组。
//填补程序
For(i, 0, n - 1) Work[i] = Available[i], Finish[i] = 0;
int cnt = 0;
For(i, 0, n - 1) {
For(j, 0, n - 1) {
int flag = 1;
if (Finish[j])
continue;
For(k, 0, m - 1) if (Work[k] < Need[j][k]) flag = 0;
if (flag) {
Finish[j] = 1, List[cnt++] = j;
For(k, 0, m - 1) Work[k] += Allocation[j][k];
// cout << "j=" << j << " " << cnt << "\n";
}
}
// cout << "i=" << i << "\n";
if (cnt == n)
return true;
}
return false;
}
void printList() {
//输出安全序列表|Process |Work |Need |Allocation |Work+Alloc |Finish |
//填补程序
pt;
pt;
For(i, 0, m - 1) Work[i] = Available[i];
puts("Current security sequence");
cout << "|Process|Work\t\t\t|Need\t\t\t|Allocation\t\t|Work+"
"Alloc\t\t|Finish\t|"
<< "\n";
For(i, 0, n - 1) {
cout << "|P" << List[i] << "\t|";
For(j, 0, m - 1) cout << Work[j] << "\t";
cout << "|";
For(j, 0, m - 1) cout << Need[i][j] << "\t";
cout << "|";
For(j, 0, m - 1) cout << Allocation[List[i]][j] << "\t";
cout << "|";
For(j, 0, m - 1) {
Work[j] += Allocation[List[i]][j];
cout << Work[j] << "\t";
}
cout << "|";
cout << "true\t"
<< "|";
pt;
}
pt;
pt;
}
void reqresource(int pos, int request[M]) {
//表示第 i 个进程请求 M 类资源 request[M]
// bool flag;
// int j;
// Step1: 判断条件 Request[j]≤Need[i][j]
//填补程序
// Step2: 判断条件 Request[j]≤Available[j]
//填补程序
// Step3: 预先分配
//填补程序
// Step4: 检测是否为安全状态
//填补程序
int flag = 1;
For(i, 0, m - 1) {
if (request[i] > Need[pos][i]) {
puts("Request error:Request greater than the demand");
cout << request[i] << " " << Need[i] << "\n";
return;
}
if (request[i] > Available[i]) {
puts("Request error:Request greater than available");
cout << request[i] << " " << Available[i] << "\n";
return;
}
}
For(i, 0, m - 1) {
Need[pos][i] -= request[i];
Available[i] -= request[i];
Allocation[pos][i] += request[i];
}
if (!issafe()) {
puts("Resource request failed! Security check: enter unsafe state! ");
puts("Restore previous state");
For(i, 0, m - 1) {
Need[pos][i] += request[i];
Available[i] += request[i];
Allocation[pos][i] -= request[i];
}
} else {
puts("Successful resource application");
puts("Show current security sequence");
printList();
}
}
int main() {
// freopen("blank.in", "r", stdin);
int reqid = -1, j, req[M];
initial();
printState();
// cout << issafe() << endl;
if (!issafe())
puts("Initial state is unsafe!");
// printf("Initial state is unsafe!\n");
else {
pt;
puts("Initial state is safe!");
// printf("\nInitial state is safe!\n");
// For(i, 0, n - 1) cout << List[i] << " ";
// pt;
printList();
puts("Input the id of request process: ( When input - 1 stops");
while (cin >> reqid) {
if (reqid == -1)
break;
if (reqid < 0 || reqid >= n)
puts("Illegal input process ID");
puts("Input request resources:");
For(i, 0, m - 1) cin >> req[i];
reqresource(reqid, req);
printState();
puts("Input the id of request process: ( When input - 1 stops");
}
// scanf("%d", &reqid);
// while (reqid >= 0 && reqid < n) { //输入进程 id 是否合法
// printf("Input request resources:");
// for (j = 0; j < M; j++)
// scanf("%d", &req[j]);
// reqresource(reqid, req);
// printState();
// printf("Input the id of request process:");
// scanf("%d", &reqid);
// }
}
return 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;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
char s[N];
struct node {
int key; //进程ID
int sequence; //进程进入队列顺序号
string massage; //进程说明信息
};
int main() {
int count = 0;
int n;
puts("How many processes");
cin >> n;
// node *p,*q;
puts("The new process control table:");
puts("keysequence message");
queue<node> que;
For(i, 0, n - 1) {
node tmp;
cin >> tmp.key >> tmp.sequence >> tmp.massage;
que.push(tmp);
}
puts("The table is:");
queue<node> p;
For(i, 0, n - 1) {
node tmp = que.front();
que.pop();
cout << tmp.key << "\t" << tmp.sequence << "\t" << tmp.massage << "\n";
p.push(tmp);
}
For(i, 0, n - 1) {
pt;
node tmp = p.front();
p.pop();
cout << "The " << ++count << "th scheduled process:\nkey = " << tmp.key
<< ", sequence = " << tmp.sequence << ", message = " << tmp.massage
<< "\n";
}
return 0;
}
/*
4
22 1 process22
30 2 process30
13 3 process13
90 4 process90
*/
#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;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
char s[N];
struct node {
int key; //进程ID
int priority; //进程进入队列顺序号
string massage; //进程说明信息
bool operator<(const node &a) const { return priority < a.priority; }
};
int main() {
int count = 0;
int n;
puts("How many processes");
cin >> n;
// node *p,*q;
puts("The new process control table:");
puts("keysequence message");
priority_queue<node> q;
For(i, 0, n - 1) {
node tmp;
cin >> tmp.key >> tmp.priority >> tmp.massage;
q.push(tmp);
}
puts("The table is:");
priority_queue<node> p;
For(i, 0, n - 1) {
node tmp = q.top();
q.pop();
cout << tmp.key << "\t" << tmp.priority << "\t" << tmp.massage << "\n";
p.push(tmp);
}
For(i, 0, n - 1) {
pt;
node tmp = p.top();
p.pop();
cout << "The " << ++count << "th scheduled process:\nkey = " << tmp.key
<< ", sequence = " << tmp.priority << ", message = " << tmp.massage
<< "\n";
}
return 0;
}
/*
5
1 20 process1
2 50 process2
3 30 process3
4 10 process4
5 40 process5
*/
#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 node {
int key; //进程ID
string massage; //进程说明信息
int run_time; //进程需要运行时间
};
queue<node> q;
void PrintCurrentState(int num) {
if(num<=0) return;
while(num--) {
node tmp = q.front();
q.pop();
cout << tmp.key << "\t" << tmp.run_time << "\t" << tmp.massage << "\n";
q.push(tmp);
}
}
int main() {
int count = 0;
int n;
int WaitTime = 0, cnt = 0;
puts("How many processes");
cin >> n;
int num = 0;
puts("The new process control table:");
puts("keysequence message");
For(i, 0, n - 1) {
node tmp;
cin >> tmp.key >> tmp.run_time >> tmp.massage ;
q.push(tmp);
}
puts("The table is:");
while(num--) {
node tmp = q.front();
q.pop();
cout << tmp.key << "\t" << tmp.run_time << "\t" << tmp.massage << "\n";
q.push(tmp);
}
while(q.size()) {
pt;
pt;
node tmp = q.front();
q.pop();
cout << "The " << ++count << "th scheduled process:\nkey = " << tmp.key
<< ", run_time = " << tmp.run_time << ", message = " << tmp.massage;
pt;
pt;
if(tmp.run_time == 1) WaitTime++, tmp.run_time = 0;
else WaitTime += 2, tmp.run_time -= 2;
if(tmp.run_time) q.push(tmp);
else n--;
puts("Recent table is:");
cout<<n<<"\n";
PrintCurrentState(n);
// int start_time = WaitTime;
// cnt++;
// WaitTime += tmp.run_time;
// cout << "The " << ++count << "th scheduled process:\nkey = " << tmp.key
// << ", sequence = " << tmp.sequence << ", message = " << tmp.massage
// << ", AverageWaiting = " << (double) WaitTime / cnt << ", StartTime = "
// << start_time << ", EndTime = " << WaitTime << ", RunTime = " << tmp.run_time
//
// << "\n";
}
}
/*
4
1 2 process1
2 4 process2
3 6 process3
4 3 process4
*/#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 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;
}
bool chk(int len,string s)
{
int jude=0;
int flag=1;
while(ftable2.size())
{
node tmp1=ftable2.top();
ftable2.pop();
if(flag&&tmp1.length>=len)
{
node 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())
{
node 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)
{
puts("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 50 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
*/
京公网安备 11010502036488号