第二章
双链表
template <class T>
struct Queue_Node {
Queue_Node<T>* prev;
Queue_Node<T>* next;
T data;
};
template <class T>
class Queue {
public:
class iterator {
public:
Queue_Node<T>* node;
iterator() {}
iterator(Queue_Node<T>* x) : node(x) {}
iterator(const iterator& x) : node(x.node) {}
bool operator==(const iterator& x) const { return node == x.node; }
bool operator!=(const iterator& x) const { return node != x.node; }
T& operator*() const { return (node->data); }
T* operator->() const { return &(operator*()); }
iterator& operator++() {
node = node->next;
return *this;
}
iterator& operator--() {
node = node->prev;
return *this;
}
iterator operator++(int) {
iterator tmp = *this;
node = node->next;
return tmp;
}
iterator operator--(int) {
iterator tmp = *this;
node = node->prev;
return tmp;
}
};
protected:
Queue_Node<T>* node;
protected:
void initialize() {
node = new Queue_Node<T>();
node->prev = node;
node->next = node;
}
public:
iterator begin() { return node->next; }
iterator end() { return node; }
bool empty() const { return node->next == node; }
T& front() { return *begin(); }
T& back() { return *(--end()); }
Queue() { initialize(); }
iterator insert(iterator it, const T& x) {
Queue_Node<T>* tmp = new Queue_Node<T>();
tmp->data = x;
tmp->next = it.node;
tmp->prev = it.node->prev;
it.node->prev->next = tmp;
it.node->prev = tmp;
return tmp;
}
void push_back(const T& x) { insert(end(), x); }
void push_front(const T& x) { insert(begin(), x); }
iterator erase(iterator it) {
it.node->next->prev = it.node->prev;
it.node->prev->next = it.node->next;
iterator tmp = it.node->next;
delete it.node;
return tmp;
}
void pop_back() { erase(--end()); }
void pop_front() { erase(begin()); }
void clear() {
Queue_Node<T>* cur = node->next;
while (cur != node) {
cur = cur->next;
delete cur->prev;
}
node->prev = node;
node->next = node;
}
void remove(const T& value) {
iterator first = begin();
iterator last = end();
while (first != last) {
iterator next = first;
++next;
if (*first == value) erase(first);
first = next;
}
}
}; 线程
#include "optsys.hpp"
struct data { //信号量结构体
sem_t empty; //记录空缓冲区个数
sem_t full; //记录装满数据缓冲区个数
Queue<int> q; //缓冲仓库：队列
} sem;
pthread_mutex_t mutex; //互斥锁
int num = 0;
void* Producer(void* arg) {
while (1) {
Sleep(300); //随机睡眠
sem_wait(&sem.empty); //信号量的 P 操作
pthread_mutex_lock(&mutex); //互斥锁上锁
num++;
printf("Producer produced a piece of data %d\n input data:", num);
int x;
scanf("%d", &x);
sem.q.push_back(x);
pthread_mutex_unlock(&mutex); //互斥锁解锁
sem_post(&sem.full); //信号量的 V 操作
}
}
void* Consumer(void* arg) {
while (1) {
Sleep(500); //随机睡眠
sem_wait(&sem.full); //信号量的 P 操作
pthread_mutex_lock(&mutex); //互斥锁上锁
num--;
printf("Consumer consumes a piece of data: %d\n", num);
printf("consumes data: %d\n", sem.q.front());
sem.q.pop_front();
pthread_mutex_unlock(&mutex); //互斥锁解锁
sem_post(&sem.empty); //信号量的 V 操作
}
}
int main() {
sem_init(&sem.empty, 0, 10);
//信号量初始化（做多容纳 10 条消息，容纳了 10 条生产者将不会生产消息）
sem_init(&sem.full, 0, 0);
pthread_mutex_init(&mutex, NULL); //互斥锁初始化
pthread_t producid;
pthread_t consumid;
pthread_create(&producid, NULL, Producer, NULL); //创建生产者线程
pthread_create(&consumid, NULL, Consumer, NULL); //创建消费者线程
pthread_join(
consumid,
NULL); //线程等待，如果没有这一步，主程序会直接结束，导致线程也直接退出。
sem_destroy(&sem.empty); //信号量的销毁
sem_destroy(&sem.full);
pthread_mutex_destroy(&mutex); //互斥锁的销毁
return 0;
} #include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <windows.h>
struct data { //信号量结构体
sem_t empty; //记录空缓冲区个数
sem_t full; //记录装满数据缓冲区个数
int buffer; //缓冲区
};
pthread_mutex_t mutex; //互斥锁
int num = 0; //记录缓冲区数据的个数
struct data sem; //信号量
void* Producer(void* arg) {
while (1) {
Sleep(rand() % 100); //随机睡眠
sem_wait(&sem.empty); //信号量的 P 操作
pthread_mutex_lock(&mutex); //互斥锁上锁
num++;
printf("Producer produced a piece of data %d\n input data:", num);
scanf("%d", &sem.buffer);
pthread_mutex_unlock(&mutex); //互斥锁解锁
sem_post(&sem.full); //信号量的 V 操作
}
}
void* Consumer(void* arg) {
while (1) {
Sleep(rand() % 100); //随机睡眠
sem_wait(&sem.full); //信号量的 P 操作
pthread_mutex_lock(&mutex); //互斥锁上锁
num--;
printf("Consumer consumes a piece of data: %d\n", num);
printf("consumes data: %d\n", sem.buffer);
pthread_mutex_unlock(&mutex); //互斥锁解锁
sem_post(&sem.empty); //信号量的 V 操作
}
}
int main() {
sem_init(&sem.empty, 0, 1); //信号量初始化
sem_init(&sem.full, 0, 0);
pthread_mutex_init(&mutex, NULL); //互斥锁初始化
pthread_t producid;
pthread_t consumid;
pthread_create(&producid, NULL, Producer, NULL); //创建生产者线程
pthread_create(&consumid, NULL, Consumer, NULL); //创建消费者线程
pthread_join(
consumid,
NULL); //线程等待，如果没有这一步，主程序会直接结束，导致线程也直接退出。
sem_destroy(&sem.empty); //信号量的销毁
sem_destroy(&sem.full);
pthread_mutex_destroy(&mutex); //互斥锁的销毁
return 0;
} 哲学家就餐
#include <errno.h>
#include <math.h>
#include <memory.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <iostream>
//筷子作为mutex
pthread_mutex_t chopstick[6];
void *eat_think(void *arg) {
char phi = *(char *)arg;
int left, right; //左右筷子的编号
switch (phi) {
case 'A':
left = 5;
right = 1;
break;
case 'B':
left = 1;
right = 2;
break;
case 'C':
left = 2;
right = 3;
break;
case 'D':
left = 3;
right = 4;
break;
case 'E':
left = 4;
right = 5;
break;
}
// int i;
for (;;) {
Sleep(rand() % 1000); //思考
pthread_mutex_lock(&chopstick[left]);
pthread_mutex_lock(&chopstick[right]);
//补充拿起左右筷子的程序段
printf("Philosopher %c is eating.\n", phi);
Sleep(rand() % 1000); //吃饭
pthread_mutex_unlock(&chopstick[left]); //放下左手的筷子
printf("Philosopher %c release chopstick %d\n", phi, left);
pthread_mutex_unlock(&chopstick[right]); //放下右手的筷子
printf("Philosopher %c release chopstick %d\n", phi, right);
}
}
int main() {
pthread_t A, B, C, D, E; // 5个哲学家
char p1, p2, p3, p4, p5;
p1 = 'A';
p2 = 'B';
p3 = 'C';
p4 = 'D';
p5 = 'E';
int i;
for (i = 0; i < 5; i++) pthread_mutex_init(&chopstick[i], NULL);
pthread_create(&A, NULL, eat_think, &p1);
pthread_create(&B, NULL, eat_think, &p2);
pthread_create(&C, NULL, eat_think, &p3);
pthread_create(&D, NULL, eat_think, &p4);
pthread_create(&E, NULL, eat_think, &p5);
pthread_join(A, NULL);
pthread_join(B, NULL);
pthread_join(C, NULL);
pthread_join(D, NULL);
pthread_join(E, NULL);
return 0;
} 第三章
银行家算法
#include "optsys.hpp"
#define M 3
#define N 5
int Resource[M]; //每种资源的总量
int Max[N][M]; // n个进程每一个进程对m类资源的最大需求
int Allocation[N][M]; //系统中每一类资源当前已分配给每一进程的资源数
int Need[N]
[M]; //每一个进程尚需的各类资源数 need[i][j]=Max[i][j]-Allocation[i][j]
int Available[M];
int Work[M];
bool Finish[N];
int List[N]; //存放安全序列的下标序列
void initial() {
//创建初始状态：先输入 Resource、Max 和 Allocation，
//再计算出Need、Available。
for (int i = 0; i < M; ++i) cin >> Resource[i], Available[i] = Resource[i];
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j) cin >> Max[i][j];
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j) cin >> Allocation[i][j];
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j) Need[i][j] = Max[i][j] - Allocation[i][j];
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j) Available[j] -= Allocation[i][j];
}
void printState() {
//输出当前的状态表|Process |Max |Allocation |Need |Available |
putchar('\n');
printf("|Process\t|\tMax\t\t|\tAllocation\t|\tNeed\t\t|\tAvailable\t|\n");
printf("|\t\t|A\tB\tC\t|A\tB\tC\t|A\tB\tC\t|A\tB\tC\t|\n");
for (int i = 0; i < N; ++i) {
printf("|P%d\t\t|", i);
for (int j = 0; j < M; ++j) printf("%d\t", Max[i][j]);
putchar('|');
for (int j = 0; j < M; ++j) printf("%d\t", Allocation[i][j]);
putchar('|');
for (int j = 0; j < M; ++j) printf("%d\t", Need[i][j]);
putchar('|');
for (int j = 0; j < M; ++j) printf(i ? "\t" : "%d\t", Available[j]);
putchar('|'), putchar('\n');
}
putchar('\n');
}
int isfinish() {
//返回同时满足两个条件{①Finish[i]=false; ②Need[i][j]≤Work[j]}的进程下标
// i(修改 Finish[i]=true)，否则返回-1。
for (int i = 0; i < N; ++i)
if (Finish[i] == false) {
for (int j = 0; j < M; ++j)
if (Need[i][j] > Work[j]) return -1;
Finish[i] = true;
}
for (int i = 0; i < N; ++i)
if (Finish[i] == false) return 0;
return 1;
}
bool issafe() {
//判定当前状态是否为安全状态（返回 true 或 false），
//把安全序列的下标放入 List[N]数组。
int cnt = 0;
for (int i = 0; i < M; ++i) Work[i] = Available[i];
for (int i = 0; i < N; ++i) Finish[i] = false;
bool check_status = false, flag = true;
while (flag) { //直到找不到任意一组满足两个条件的进程才退出循环
for (int i = 0; i < N; ++i) { //找一组进程
flag = true;
if (Finish[i] == false) { //满足1.未完成
for (int j = 0; j < M; ++j) { // 2.Need_i<=Work
if (Need[i][j] > Work[j]) flag = false;
}
if (flag) { //如果找到
check_status = true;
List[cnt++] = i;
for (int j = 0; j < M; ++j) Work[j] += Allocation[i][j];
Finish[i] = true;
}
} else
flag = false;
}
}
if (check_status == false) //找不到满足条件的进程
for (int i = 0; i < N; ++i) //有进程尚未执行完则不安全
if (Finish[i] == false) return false;
return true; //所有进程都已执行完毕，则系统状态安全
}
void printList() {
//输出安全序列表|Process |Work |Need |Allocation |Work+Alloc |Finish |
putchar('\n');
printf(
"|Process\t|\tWork\t\t|\tNeed\t\t|\tAllocation\t|\tWork+Alloc\t|"
"Finish |\n");
printf("|\t\t|A\tB\tC\t|A\tB\tC\t|A\tB\tC\t|A\tB\tC\t|\t|\n");
for (int i = 0; i < N; ++i) {
printf("|P%d\t\t|", i);
for (int j = 0; j < M; ++j) printf("%d\t", Work[j]);
putchar('|');
for (int j = 0; j < M; ++j) printf("%d\t", Need[i][j]);
putchar('|');
for (int j = 0; j < M; ++j) printf("%d\t", Allocation[i][j]);
putchar('|');
for (int j = 0; j < M; ++j) printf("%d\t", Work[j] + Allocation[i][j]);
puts(Finish[i] ? "| True |" : "| False |");
}
putchar('\n');
}
void reqresource(int i,
int request[M]) { //表示第 i 个进程请求 M 类资源 request[M]
bool flag = true;
// Step1: 判断条件 Request[j]≤Need[i][j]
for (int j = 0; j < M and flag; ++j)
if (request[j] > Need[i][j]) flag = false;
if (flag == false) {
puts("Error : request is greater than need.");
return;
}
// Step2: 判断条件 Request[j]≤Available[j]
for (int j = 0; j < M and flag; ++j)
if (request[j] > Available[j]) flag = false;
if (flag == false) {
puts("Error : request is greater than available.");
return;
}
// Step3: 预先分配
for (int j = 0; j < M; ++j) {
Available[j] -= request[j];
Allocation[i][j] += request[j];
Need[i][j] -= request[j];
}
// Step4:检测是否为安全状态
if (issafe() == false) {
puts(
"The system will be in an insecure state and no resources will "
"be allocated.");
for (int j = 0; j < M; ++j) {
Available[j] += request[j];
Allocation[i][j] -= request[j];
Need[i][j] += request[j];
}
} else {
puts("The system is secure and resources have been allocated.");
puts("There is a security sequence: ");
for (int i = 0; i < N; ++i) cout << List[i] << ' ';
putchar('\n');
}
}
int main() {
freopen("tb.txt", "r", stdin);
initial();
printState();
if (issafe() == false) {
printf("\nInitial state is unsafe!\n");
} else {
printf("\nInitial state is safe!\n");
cout << "\nExisting safety sequence : ";
for (int i = 0; i < N; ++i) cout << List[i] << ' ';
printList();
freopen("con", "r", stdin);
int reqid = -1, req[M];
do {
printf("\nInput the id of request process:");
scanf("%d", &reqid);
if (reqid < 0 or reqid >= N) break;
printf("\nInput request resources:");
for (int j = 0; j < M; j++) scanf("%d", &req[j]);
reqresource(reqid, req);
printState();
} while (reqid >= 0 && reqid < N); //输入进程 id 是否合法
}
return 0;
}
/*
1
1 0 2
4
3 3 0
0
0 2 0
*/ 第四章
#include "optsys.hpp"
struct TableNode {
int key; //进程id
int sequence; //顺序
string message; //信息
int run_time; //运行时间
int end_time = 0; //周转时间
};
Queue<TableNode> table;
void Init() {
puts(
"Please input key sequence and message in order, split with space and "
"end with 0:");
TableNode now;
while (cin >> now.key, now.key) {
cin >> now.sequence >> now.message >> now.run_time;
table.push_back(now);
}
}
void OutputTable() {
cout << "\nkey\t"
<< "sequence\t"
<< "message\t"
<< "\trun_time" << endl;
for (Queue<TableNode>::iterator it = table.begin(); it != table.end(); ++it)
cout << (*it).key << '\t' << (*it).sequence << "\t\t" << (*it).message
<< "\t" << (*it).run_time << endl;
cout << endl;
}
void Deal(Queue<TableNode> table) {
int cnt = 0, now_time = 0, sum_time = 0;
double turnaround_sum = 0;
for (Queue<TableNode>::iterator it = table.begin(); it != table.end();
++it) {
cout << "The process of number " << ++cnt << " for team out is\n";
cout << "key = " << (*it).key << ',' << "sequence = " << (*it).sequence
<< ',' << "message = " << (*it).message;
cout << "\nIts turnaround time is " << (now_time += (*it).run_time)
<< "s. " << endl;
printf("Turnaround time with weight : %.2f s. \n",
now_time * 1.0 / (*it).run_time);
turnaround_sum += now_time * 1.0 / (*it).run_time;
cout << endl;
sum_time += now_time;
}
printf("The average turnaround time for all programs is %.2f s.\n",
sum_time * 1.0 / cnt);
printf("Average turnaround time with weight : %.2f s. \n",
turnaround_sum / cnt);
}
int main(void) {
freopen("4-1tb.txt", "r", stdin);
Init();
OutputTable();
Deal(table);
return 0;
} #include "optsys.hpp"
struct TableNode {
int key;
int priority;
string message;
int run_time;
bool operator<(const TableNode& x) const { return priority < x.priority; }
};
priority_queue<TableNode> table;
typedef priority_queue<TableNode> HEAP;
void Init() {
freopen("4-2tb.txt", "r", stdin);
puts(
"Please input key priority and message in order, split with space and "
"end with 0:");
TableNode now;
while (cin >> now.key, now.key) {
cin >> now.priority >> now.message >> now.run_time;
table.push(now);
}
}
void OutputTable() {
cout << "\nkey\t"
<< "priority\t"
<< "message\t"
<< "\trun_time" << endl;
HEAP tmp = table;
while (!tmp.empty()) {
TableNode it = tmp.top();
tmp.pop();
cout << it.key << '\t' << it.priority << "\t\t" << it.message << "\t"
<< it.run_time << endl;
}
cout << endl;
}
void Deal(HEAP table) {
int now_time = 0, sum_time = 0, cnt = 1;
double turnaround_sum = 0;
for (; !table.empty(); ++cnt) {
TableNode it = table.top();
table.pop();
cout << "The process of number " << cnt << " for team out is\n";
cout << it.key << " , " << it.priority << " , " << it.message << endl;
cout << "Its turnaround time is " << (now_time += (it).run_time)
<< "s. \n";
printf("Turnaround time with weight : %.2f s. \n\n",
now_time * 1.0 / it.run_time);
sum_time += now_time;
turnaround_sum += now_time * 1.0 / it.run_time;
}
printf("The average waiting time for all programs is %.2f s.\n",
sum_time * 1.0 / cnt);
printf("Average turnaround time with weight : %.2f s. \n\n",
turnaround_sum / cnt);
}
int main() {
Init();
OutputTable();
Deal(table);
return 0;
} #include "optsys.hpp"
struct TableNode {
int key; //进程id
int sequence; //顺序
string message; //信息
int run_time; //运行时间
int ta_time = 0; //周转时间
};
Queue<TableNode> table;
void Init() {
puts(
"Please input key sequence and message in order, split with space and "
"end with 0:");
TableNode now;
while (cin >> now.key, now.key) {
cin >> now.sequence >> now.message >> now.run_time;
table.push_back(now);
}
}
void OutputTable() {
cout << "\nkey\t"
<< "sequence\t"
<< "message\t"
<< "\trun_time" << endl;
for (Queue<TableNode>::iterator it = table.begin(); it != table.end(); ++it)
cout << (*it).key << '\t' << (*it).sequence << "\t\t" << (*it).message
<< "\t" << (*it).run_time << endl;
cout << endl;
}
void Deal(Queue<TableNode> tb) {
int cnt = 0, now_time = 0, sum_time = 0, flag = 1;
Queue<TableNode> EndQue;
while (flag) {
flag = 0;
for (Queue<TableNode>::iterator it = tb.begin(); it != tb.end(); ++it) {
if ((*it).run_time) (*it).run_time -= 1, now_time += 1, flag = 1;
if (!(*it).run_time) {
TableNode now = (*it);
for (Queue<TableNode>::iterator i = table.begin();
i != table.end(); ++i)
if ((*i).key == now.key) now.run_time = (*i).run_time;
EndQue.push_back(now);
Queue<TableNode>::iterator tmp = it;
}
}
}
for (Queue<TableNode>::iterator it = EndQue.begin(); it != EndQue.end();
++it) {
cout << "The process of number " << ++cnt << " for team out is\n";
cout << "key = " << (*it).key << ',' << "sequence = " << (*it).sequence
<< ',' << "message = " << (*it).message;
cout << "\nIts turnaround time is " << (now_time += (*it).run_time)
<< "s. " << endl;
printf("Average turnaround time with weight : %.2f s. \n",
now_time * 1.0 / cnt);
cout << endl;
sum_time += now_time;
}
printf("The average waiting time for all programs is %.2f s.\n",
sum_time * 1.0 / cnt);
}
int main(void) {
freopen("4-1tb.txt", "r", stdin);
Init();
OutputTable();
Deal(table);
return 0;
} 第五章
FF&BF
#include "optsys.hpp"
struct work {
string name;
int size;
};
Queue<work> T;
struct block {
int size;
int begin_address;
} Available_Block[10];
struct Allocate {
string name;
int size, begin_address;
};
Queue<Allocate> work_table;
void Load() {
freopen("5-1tb.txt", "r", stdin);
for (int i = 1; i <= 5; ++i)
cin >> Available_Block[i].size >> Available_Block[i].begin_address;
work now;
for (int i = 0; i < 3; ++i) {
cin >> now.name >> now.size;
T.push_back(now);
}
Allocate tmp;
for (int i = 0; i < 7; ++i) {
cin >> tmp.name >> tmp.size >> tmp.begin_address;
work_table.push_back(tmp);
}
}
void ShowQueue(Queue<work> T) {
putchar(10);
Queue<work>::iterator it;
for (it = T.begin(); it != T.end(); ++it) {
cout << (*it).name << '\t' << (*it).size << endl;
}
putchar(10);
}
void show_work_table() {
putchar(10);
Queue<Allocate>::iterator it;
for (it = work_table.begin(); it != work_table.end(); ++it) {
cout << (*it).name << '\t' << (*it).size << '\t' << (*it).begin_address
<< endl;
}
putchar(10);
}
void Insert_Wort_Table(work a, int pos) {
Allocate now = {a.name, a.size, Available_Block[pos].begin_address};
Queue<Allocate>::iterator it;
for (it = work_table.begin(); it != work_table.end(); ++it) {
if ((*it).begin_address > now.begin_address) {
work_table.insert(it, now);
break;
}
}
show_work_table();
}
int FirstFit() {
while (!T.empty()) {
bool vis = 0;
work now = T.front();
for (int i = 1; i <= 5; ++i) {
if (Available_Block[i].size >= now.size) {
vis = 1;
Insert_Wort_Table(now, i);
Available_Block[i].size -= now.size;
Available_Block[i].begin_address += now.size;
T.pop_front();
break;
}
}
if (!vis)
return puts(
"Out of memory, no available memory blocks can be "
"found."),
-1;
}
return 0;
}
int BestFit() {
while (!T.empty()) {
work now = T.front();
int tar = 0;
for (int i = 1; i <= 5; ++i) {
if (Available_Block[i].size >= now.size) {
if (tar == 0 ||
Available_Block[i].size < Available_Block[tar].size)
tar = i;
}
}
Insert_Wort_Table(now, tar);
Available_Block[tar].size -= now.size;
Available_Block[tar].begin_address += now.size;
T.pop_front();
if (!tar)
return puts(
"Out of memory, no available memory blocks can be "
"found."),
-1;
}
return 0;
}
int main() {
Load();
ShowQueue(T);
show_work_table();
FirstFit();
return 0;
} 内存管理
#include "optsys.hpp"
struct work {
string name = "";
int size, begin_address;
};
Queue<work> work_table;
Queue<work> free_table;
void init() {
work now;
for (int i = 0; i < 9; ++i) {
cin >> now.name >> now.size >> now.begin_address;
work_table.push_back(now);
}
now = {"", 0, 0};
for (int i = 0; i < 3; ++i)
cin >> now.size >> now.begin_address, free_table.push_back(now);
}
void show_table(Queue<work> table) {
putchar(10);
Queue<work>::iterator it;
for (it = table.begin(); it != table.end(); ++it) {
if ((*it).name != "") cout << (*it).name << '\t';
cout << (*it).size << '\t' << (*it).begin_address << endl;
}
putchar(10);
}
void add_into_free_table(work now) {
now.name = "";
Queue<work>::iterator it = free_table.begin(), i = it;
for (++i; it != free_table.end(); ++it, ++i) {
if ((*it).begin_address + (*it).size == now.begin_address) { //三段合并
puts("chk");
if (i != free_table.end() &&
now.begin_address + now.size == (*i).begin_address) {
puts("Situation C");
(*it).size += (now.size + (*i).size);
free_table.erase(i);
} else
puts("Situation A"), (*it).size += now.size; //合并到前面
return;
} else if (i != free_table.end() &&
now.begin_address + now.size ==
(*i).begin_address) { //合并后面的
puts("Situation B");
now.size += (*i).size;
free_table.insert(i, now);
free_table.erase(i);
return;
} else if ((*it).begin_address > now.begin_address) {
puts("Situation D");
free_table.insert(it, now);
return;
}
}
free_table.insert(it, now);
}
void free_work(string name) {
work tmp;
Queue<work>::iterator it;
bool vis = 0;
for (it = work_table.begin(); it != work_table.end(); ++it) {
if ((*it).name == name) {
vis = 1;
tmp = (*it);
work_table.erase(it);
add_into_free_table(tmp);
break;
}
}
if (!vis)
cout << "Can't find the task named " << name << "." << endl;
else
puts("Free successfully."), show_table(work_table),
show_table(free_table);
}
int main() {
freopen("5-3tb.txt", "r", stdin);
init();
show_table(work_table), show_table(free_table);
free_work("Task2"); // D
free_work("Task4"); // A
free_work("Task6"); // B
free_work("Task7"); // C
free_work("Task9");
return 0;
} #include "optsys.hpp"
const int M = 3;
const int N = 20;
bool chk(int x, int a[]) {
for (int i = 0; i < M; ++i) {
if (a[i] == x) return 1;
}
return 0;
}
int record[N][M + 1];
int main(void) {
int a[M] = {-1, -1, -1};
//存放已装入内存的页号序列，M 为系统分配给作业的主存页面数
int b[N] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3,
0, 3, 2, 1, 2, 0, 1, 7, 0, 1}; //存放作业页号序列
int c[N]; //存放被淘汰的页号序列
int counter = 0; //缺页总次数
int pos = 0, tot = 0;
for (int i = 0; i < N; ++i) {
if (record[i][M] = !chk(b[i], a)) {
++counter;
if (pos == 3) {
c[tot++] = a[0]; //丢弃
a[0] = a[1], a[1] = a[2], a[2] = b[i]; // 维护队列
} else
a[pos++] = b[i];
}
for (int j = 0; j < M; ++j) record[i][j] = a[j];
}
putchar(10);
for (int i = 0; i < N; ++i) cout << b[i] << ' ';
putchar(10), putchar(10);
for (int j = 0; j <= M; ++j) {
for (int i = 0; i < N; ++i)
if (record[i][j] != -1)
cout << record[i][j] << ' ';
else
cout << " ";
cout << '\n';
}
putchar(10);
cout << counter << endl;
printf("%.2f%%\n", counter * 100.0 / N);
return 0;
} #include "optsys.hpp"
const int M = 3;
const int N = 20;
bool chk(int x, int a[]) {
for (int i = 0; i < M; ++i) {
if (a[i] == x) return 1;
}
return 0;
}
void adjust(int a[], int x) {
for (int i = 0; i < M; ++i)
if (a[i] == x) {
for (int j = i + 1; j < M; ++j) a[j - 1] = a[j];
a[M - 1] = x;
return;
}
}
int record[N][M + 1];
int main(void) {
int a[M] = {-1, -1, -1};
//存放已装入内存的页号序列，M 为系统分配给作业的主存页面数
int b[N] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3,
0, 3, 2, 1, 2, 0, 1, 7, 0, 1}; //存放作业页号序列
int c[N]; //存放被淘汰的页号序列
int counter = 0; //缺页总次数
int pos = 0, tot = 0;
for (int i = 0; i < N; ++i) {
if (record[i][M] = !chk(b[i], a)) {
++counter;
if (pos == 3) {
c[tot++] = a[0]; //丢弃
a[0] = a[1], a[1] = a[2], a[2] = b[i]; // 维护队列
} else
a[pos++] = b[i];
} else {
adjust(a, b[i]);
}
for (int j = 0; j < M; ++j) record[i][j] = a[j];
}
putchar(10);
for (int i = 0; i < N; ++i) cout << b[i] << ' ';
putchar(10), putchar(10);
for (int j = 0; j <= M; ++j) {
for (int i = 0; i < N; ++i)
if (record[i][j] != -1)
cout << record[i][j] << ' ';
else
cout << " ";
cout << '\n';
}
putchar(10);
cout << counter << endl;
printf("%.2f%%\n", counter * 100.0 / N);
return 0;
} 第六章
缓冲池
#include "optsys.hpp"
#define Print(t) cout << (#t) << ":\n", print_queue(t)
Queue<int> emq, inq, outq;
void accept_in() {
if (emq.empty()) {
puts("error : emq is empty");
return;
}
int hin = emq.front();
emq.pop_front();
cout << "收容输入——请输入“输入数据”：";
cin >> hin;
inq.push_back(hin);
cout << endl;
}
void extract_in() {
if (inq.empty()) {
puts("error : inq is empty");
return;
}
int sin = inq.front();
cout << "提取输入——输出“提取数据”：" << sin << '\n' << endl;
inq.pop_front();
emq.push_back(INT16_MIN);
}
void accept_out() {
if (emq.empty()) {
puts("\nerror : emq is empty\n");
return;
}
int hout = emq.front();
puts("收容输出——请输入“输出数据”：");
cin >> hout;
emq.pop_front();
outq.push_back(hout);
cout << endl;
}
void extract_out() {
if (outq.empty()) {
puts("error : outq is empty");
return;
}
int sout = outq.front();
cout << "提取输出——输出“提取数据”：" << sout << '\n' << endl;
outq.pop_front();
emq.push_back(INT16_MIN);
}
void print_queue(Queue<int> q) {
if (q.empty()) cout << "Queue is empty now.";
Queue<int>::iterator it = q.begin();
for (; it != q.end(); ++it) cout << (*it) << ' ';
cout << endl << endl;
}
void show() { putchar(10), Print(emq), Print(inq), Print(outq); }
int ask() {
cout << "请选择操作选项" << endl;
cout << "1. 收容输入" << endl;
cout << "2. 提取输入" << endl;
cout << "3. 收容输出" << endl;
cout << "4. 提取输出" << endl;
cout << "5. 退出" << endl << endl;
int x;
cin >> x;
if (x == 1)
accept_in();
else if (x == 2)
extract_in();
else if (x == 3)
accept_out();
else if (x == 4)
extract_out();
return x != 5;
}
int main() {
for (int i = 0; i < 10; ++i) emq.push_back(INT16_MIN);
do {
show();
} while (ask());
return 0;
} 最短距离调度
#include "optsys.hpp"
vector<int> arr = {55, 58, 39, 18, 90, 160, 150, 38, 184};
set<int> track;
int main() {
for (int x : arr) track.insert(x);
int now = 100, ans = 0;
while (track.size()) {
if (track.lower_bound(now) == track.begin()) {
int R = *(track.upper_bound(now));
int dr = abs(now - (R));
track.erase(R), cout << R << '\t' << dr << endl, ans += dr, now = R;
continue;
} else if (track.upper_bound(now) == track.end()) {
int L = *(--track.lower_bound(now));
int dl = abs(now - (L));
track.erase(L), cout << L << '\t' << dl << endl, ans += dl, now = L;
continue;
}
int L = *(--track.lower_bound(now));
int R = *(track.upper_bound(now));
int dl = abs(now - (L));
int dr = abs(now - (R));
if (dl < dr)
track.erase(L), cout << L << '\t' << dl << endl, ans += dl, now = L;
else
track.erase(R), cout << R << '\t' << dr << endl, ans += dr, now = R;
}
cout << ans << endl;
cout << ans * 1.0 / arr.size() << '\%' << endl;
return 0;
} 电梯调度
#include "optsys.hpp"
vector<int> arr = {55, 58, 39, 18, 90, 160, 150, 38, 184};
set<int> track;
int main() {
for (int x : arr) track.insert(x);
int now = 100, ans = 0, directon = 1;
while (track.size()) {
if (track.lower_bound(now) == track.begin()) {
int R = *(track.upper_bound(now));
int dr = abs(now - (R));
track.erase(R), cout << R << '\t' << dr << endl, ans += dr, now = R;
continue;
} else if (track.upper_bound(now) == track.end()) {
int L = *(--track.lower_bound(now));
int dl = abs(now - (L));
track.erase(L), cout << L << '\t' << dl << endl, ans += dl, now = L;
continue;
}
int L = *(--track.lower_bound(now));
int R = *(track.upper_bound(now));
int dl = abs(now - (L));
int dr = abs(now - (R));
if (!directon)
track.erase(L), cout << L << '\t' << dl << endl, ans += dl, now = L;
else
track.erase(R), cout << R << '\t' << dr << endl, ans += dr, now = R;
}
cout << ans << endl;
cout << ans * 1.0 / arr.size() << '\%' << endl;
return 0;
} 
京公网安备 11010502036488号