题目描述
内存是计算机重要的资源之一,程序运行的过程中必须对内存进行分配。
经典的内存分配过程是这样进行的:
1、 内存以内存单元为基本单位,每个内存单元用一个固定的整数作为标识,称为地址。地址从0开始连续排列,地址相邻的内存单元被认为是逻辑上连续的。我们把从地址i开始的s个连续的内存单元称为首地址为i长度为s的地址片。
2、 运行过程中有若干进程需要占用内存,对于每个进程有一个申请时刻T,需要内存单元数M及运行时间P。在运行时间P内(即T时刻开始,T+P时刻结束),这M个被占用的内存单元不能再被其他进程使用。
3、假设在T时刻有一个进程申请M个单元,且运行时间为P,则:
若T时刻内存中存在长度为M的空闲地址片,则系统将这M个空闲单元分配给该进程。若存在多个长度为M个空闲地址片,则系统将首地址最小的那个空闲地址片分配给该进程。
如果T时刻不存在长度为M的空闲地址片,则该进程被放入一个等待队列。对于处于等待队列队头的进程,只要在任一时刻,存在长度为M的空闲地址片,系统马上将该进程取出队列,并为它分配内存单元。注意,在进行内存分配处理过程中,处于等待队列队头的进程的处理优先级最高,队列中的其它进程不能先于队头进程被处理。
现在给出一系列描述进程的数据,请编写一程序模拟系统分配内存的过程。
样例
输入样例:
10
1 3 10
2 4 3
3 4 4
4 1 4
5 3 4
0 0 0
输出样例:
12
2
算法1
(模拟) $O(n)$
等待队列:(first : 请求长度, second: 占用时间)
插入,删除进程的话用set(first:起始地址, second:长度)
释放队列 小根堆 (first: 释放时间 second: 起始下标 )
思路:
新来一个请求(T, M, P)
1.释放掉所有 释放时间<= T的内存, 每次释放之后,都要判断等待队列头是否可以加入内存
2.判断(T,M, P)是否可以满足, 如果不可以, 则插入等待队列。
C++ 代码
#include <iostream>
#include <queue>
#include <vector>
#include <set>
using namespace std;
typedef pair<int, int> PII;
int n, t, m, p;
queue<PII> waits; //first : 长度, second :释放时间
set<PII> runs; // first : 起始地址, second :长度
priority_queue<PII, vector<PII>, greater<PII>> endts; // (first : 释放时间, second: 起始时间)
int tm, cnt;
bool give(int t, int m, int p){
for (auto it = runs.begin(); it != runs.end(); it ++){
auto jt = it;
jt ++;
if (jt != runs.end()){
if (m <= jt->first - (it->first + it->second - 1) - 1){
int start = it->first + it->second;
runs.insert({start, m});
endts.push({t + p, start});
return true;
}
}
}
return false;
}
void finish(int t){
while (endts.size() && endts.top().first <= t){
int f = endts.top().first;
while (endts.size() && endts.top().first == f){//可能有好几个任务,是t时刻释放的,所以得循环
auto top = endts.top();
endts.pop();
auto it = runs.lower_bound({top.second, 0});//由于priority_queue 和 set 是一一对应的,所以必定通过起始地址找到对应的进程,因此可以删除对应的进程
runs.erase(it);
}
//每次释放完成后,看看队列头部能否加入运行
tm = f;
while (waits.size()){
auto front = waits.front();
if (give(f, front.first, front.second)){
waits.pop();
}
else break;
}
}
}
int main(){
cin >> n;
runs.insert({-1, 1}), runs.insert({n, 1});//预先插入哨兵,方便计算第一个插入内存的情况
while (cin >> t >> m >> p, t || m || p){
//先在内存中释放
finish(t);
if (!give(t, m, p)){
waits.push({m, p});
cnt ++;
}
}
finish(2e9);
cout << tm << endl << cnt << endl;
return 0;
}