【模拟+数据结构】操作系统

第二题：操作系统

(sys.exe)

写一个程序来模拟操作系统的进程调度。假设该系统只有一个CPU，每一个进程的到达时间，执行时间和运行优先级都是已知的。其中运行优先级用自然数表示，数字越大，则优先级越高。

如果一个进程到达的时候CPU是空闲的，则它会一直占用CPU直到该进程结束。除非在这个过程中，有一个比它优先级高的进程要运行。在这种情况下，这个新的（优先级更高的）进程会占用CPU，而老的只有等待。

如果一个进程到达时，CPU正在处理一个比它优先级高或优先级相同的进程，则这个（新到达的）进程必须等待。

一旦CPU空闲，如果此时有进程在等待，则选择优先级最高的先运行。如果有多个优先级最高的进程，则选择到达时间最早的。

输入格式:

l        输入文件名：sys.in

l        输入文件包含若干行，每一行有四个自然数（均不超过108），分别是进程号，到达时间，执行时间和优先级。不同进程有不同的编号，不会有两个相同优先级的进程同时到达。输入数据已经按到达时间从小到大排序。输入数据保证在任何时候，等待队列中的进程不超过15000个。

输出格式：

l        输出文件名：sys.out

l        按照进程结束的时间输出每个进程的进程号和结束时间。

输入输出示例：

sys.in

1 1 5 3

2 10 5 1

3 12 7 2

4 20 2 3

5 21 9 4

6 22 2 4

7 23 5 2

8 24 2 4

sys.out

1 6

3 19

5 30

6 32

8 34

4 35

7 40

2 42

就是一个模拟，加上堆，思路很简单，只是中间的细节要考虑仔细。

我的想法是，既然当前的任务只能有一个，那么我就用i,s,t,l四个变量表示即可。

而未到来的任务暂时不用考虑。而之前中断的任务，放到一个堆中表示待办任务。

考虑一个任务完成时：

如果堆中还有任务剩余，就把它取出来继续做，时间不改变。（注意这里如果对输入不进行处理，这条任务就被忽略掉了，应该把它放回缓冲区）

如果堆中没有剩余，则把新进入的任务拿来做，时间直接跳跃到新任务的起始时间。

当新来了一个任务，而当前任务不能够完成：

如果新任务的等级高：我们把剩余的时间减少，并把它放入堆中。修改当前时间为新的开始时间，并处理新任务

如果当前任务等级高：我们直接把新任务放入堆中。

另外要考虑的是，当没有新任务进来的时候：

我们先把当前任务处理完，然后依次把堆中的任务处理完。

本以为自己已经细心再细心不能更细心了，结果，还是被3个犯二的错给坑了。

提交次数：4

1、如果前一个认为在t时课完成，下一个任务就可以在t时刻开始，而不用等到t+1时刻。

2、手动的输入缓冲区开小了，只开了100，我以为这个东西根本用处不大，结果直开到了1000000才终于过的。

3、堆中首先按等级的降序排，再按进入时间的升序排。一开始把进入时间弄成了剩余时间，然后又弄成了降序。。。

于是我明白，没有最仔细，只有更仔细。

#include <queue>
#include <cstdio>

struct task
{
	long i,s,t,l;
	bool operator<(const task& t2)const
	{
		if (l == t2.l)
			return s>t2.s;
		return l<t2.l;
	}
	task(long ii,long ss,long tt,long ll):i(ii),s(ss),t(tt),l(ll){}
	task(){}
};

using std::priority_queue;
priority_queue<task> heap;

long floati[1000000];
long floats[1000000];
long floatt[1000000];
long floatl[1000000];
long fl = 1;
long fr = 1;

int main()
{
	freopen("sys.in","r",stdin);
	freopen("sys.out","w",stdout);
	long i=0,s=-1,t=10000000,l=-1;
	long ni,ns,nt,nl;
	long last = 0;
	task now;
	while (1)
	{
		if (fl < fr)
		{
			fl++;
			ni = floati[fl];
			ns = floats[fl];
			nt = floatt[fl];
			nl = floatl[fl];
		}
		else
		{
			if(scanf("%ld%ld%ld%ld",&ni,&ns,&nt,&nl) <= 0)
				break;
		}
		if (ns >= last+t)
		{
			printf("%ld %ld\n",i,last+t);
			if (!heap.empty())
			{
				fr ++;
				floati[fr] = ni;
				floats[fr] = ns;
				floatt[fr] = nt;
				floatl[fr] = nl;
				last = last+t;
				now = heap.top();
				heap.pop();
				i = now.i;
				s = now.s;
				t = now.t;
				l = now.l;
			}
			else
			{
				i = ni;
				s = ns;
				t = nt;
				l = nl;
				last = ns;
			}
			continue;
		}
		t -= ns-last;
		last = ns;
		if (nl > l)
		{
			if (s > 0)
			{
				heap.push(task(i,s,t,l));
			}
			i = ni;
			s = ns;
			t = nt;
			l = nl;
		}
		else
		{
			heap.push(task(ni,ns,nt,nl));
		}
	}
	printf("%ld %ld\n",i,last+t);
	last += t;
	while (!heap.empty())
	{
		now = heap.top();
		printf("%ld %ld\n",now.i,last+now.t);
		heap.pop();
		last = last+now.t;
	}
	return 0;
}