-- FIFOSchedulerImpl.mesa
-- last edited:  July 13, 1981  8:25 AM

DIRECTORY
	FIFOScheduler,
	Process,
	RandomCard,
	SystemDefs,
	WF;

FIFOSchedulerImpl: MONITOR
	IMPORTS Process, RandomCard, SystemDefs, WF
	EXPORTS FIFOScheduler = {

currentProcessSize: CARDINAL;

Pool: TYPE = RECORD [
	cond: CONDITION, free: POINTER TO Pool];
MaxCond: CARDINAL = 100;
ConditionPool: ARRAY [0..MaxCond) OF Pool;
FreePool: POINTER TO Pool;
UniversalTime: LONG CARDINAL;

TimeQueue: TYPE = RECORD [
	next: POINTER TO TimeQueue,
	time: LONG CARDINAL,
	size: CARDINAL,
	events: POINTER TO Pool];
AllTime: POINTER TO TimeQueue _ NIL;

Fork: PUBLIC PROC[newProcess: PROC] RETURNS[PROCESS] = {
	p: PROCESS _ FORK newProcess[];
	IncCurrent[];
	Process.Yield[];
	RETURN[p]
	};

Join: PUBLIC PROC[process: PROCESS] = {
	[] _ JOIN process;
	};

ProcessEnd: PUBLIC ENTRY PROC = {
	DecCurrentInternal[];
	IF AllTime = NIL THEN RETURN;
	IF ~CurrentMore[] THEN NotifyEarliest[];
	};

GetProcessSize: PUBLIC ENTRY PROC RETURNS[CARDINAL] = {
	RETURN[currentProcessSize]};

Delay: PUBLIC PROC [max: CARDINAL] = {
	DelayInternal[RandomCard.Choose[1, max+1]]
	};

DelayInternal: ENTRY PROC [max: CARDINAL] = {
	index: CARDINAL;
	startTime: LONG CARDINAL _ UniversalTime+max;
	DecCurrentInternal[];
	IF currentProcessSize#0 THEN {
		PutThisProcess[startTime];
		RETURN};
	IF startTime<Earliest[] THEN {
		IncCurrentInternal[];
		UniversalTime _ startTime; RETURN};
	IF startTime>Earliest[] THEN {
		NotifyEarliest[];
		PutThisProcess[startTime];
		RETURN};
	index _ RandomCard.Choose[0,EarliestSize[]];
	IF index=0 THEN {
		IncCurrentInternal[];
		UniversalTime _ startTime; RETURN};
	NotifyEarliestAt[index-1];
	PutThisProcess[startTime]
	};

StandardDelay: PUBLIC PROC = {
	DelayInternal[RandomCard.Choose[1, 2]]
	};

NotifyQueue: PUBLIC ENTRY PROC = {
	IF currentProcessSize = 0 THEN ERROR;
	currentProcessSize _ currentProcessSize-1;
	IF AllTime=NIL THEN RETURN;
	IF currentProcessSize = 0 THEN NotifyEarliest[];
	};

IncCurrent: PUBLIC ENTRY PROC = {
	currentProcessSize _ currentProcessSize+1;
	};

-- Current process size manipulation

CurrentMore: INTERNAL PROC RETURNS[BOOLEAN] = {
	RETURN[currentProcessSize#0]
	};

DecCurrentInternal: INTERNAL PROC = {
	IF currentProcessSize = 0 THEN ERROR;
	currentProcessSize _ currentProcessSize-1;
	};

IncCurrentInternal: INTERNAL PROC = {
	currentProcessSize _ currentProcessSize+1;
	};

-- Time queue manipulation

Earliest: INTERNAL PROC RETURNS[LONG CARDINAL] = {
	IF AllTime=NIL THEN RETURN[LAST[LONG CARDINAL]];
	RETURN[AllTime.time]};

EarliestSize: INTERNAL PROC RETURNS[CARDINAL] = {
	RETURN[AllTime.size]};

NotifyEarliest: INTERNAL PROC = {
	index: CARDINAL _ RandomCard.Choose[0,AllTime.size-1];
	NotifyEarliestAt[index]
	};

NotifyEarliestAt: INTERNAL PROC [index: CARDINAL] = {
	eventQueue: POINTER TO Pool _ AllTime.events;
	back: POINTER TO Pool;
	IncCurrentInternal[];
	UniversalTime _ AllTime.time;
	IF index=0 THEN {
		AllTime.events _ eventQueue.free;
		NOTIFY eventQueue.cond;
		eventQueue.free _ FreePool;
		FreePool _ eventQueue;
		IF AllTime.size=1 THEN {
			time: POINTER TO TimeQueue _ AllTime;
			AllTime _ AllTime.next;
			SystemDefs.FreeHeapNode[time]}
		ELSE AllTime.size _ AllTime.size-1;
		RETURN};
	THROUGH [0..index-1) DO
		eventQueue _ eventQueue.free;
	ENDLOOP;
	back _ eventQueue;
	eventQueue _ eventQueue.free;
	NOTIFY eventQueue.cond;
	back.free _ eventQueue.free;
	eventQueue.free _ FreePool;
	FreePool _ eventQueue;
	AllTime.size _ AllTime.size-1;
	};

PutToQueue: PROC[newProcess: PROC] = {
	LockAndPutThisProcess[UniversalTime];
	newProcess[]
	};

LockAndPutThisProcess: ENTRY PROC[startTime: LONG CARDINAL] = {
	PutThisProcess[startTime]
	};

PutThisProcess: INTERNAL PROC[startTime: LONG CARDINAL] = {
	timeQueue: POINTER TO TimeQueue;
	{IF AllTime=NIL OR AllTime.time>startTime THEN GOTO PutFront;
	timeQueue _ AllTime;
	IF AllTime.time=startTime THEN GOTO PutHere;
	FOR timeQueue_ AllTime, timeQueue.next UNTIL timeQueue.next=NIL DO
		IF timeQueue.time=startTime THEN GOTO PutHere;
		IF timeQueue.next.time>startTime THEN GOTO PutAfter
	REPEAT
		FINISHED => 
			IF timeQueue.time=startTime THEN GOTO PutHere
			ELSE GOTO PutAfter
	ENDLOOP;
	EXITS
		PutFront => {
			time: POINTER TO TimeQueue _ SystemDefs.AllocateHeapNode[SIZE[TimeQueue]];
			time.next _ AllTime;
			AllTime _ time;
			time.time _ startTime;
			time.size _ 1;
			time.events _ FreePool;
			IF FreePool = NIL THEN ERROR;
			FreePool _ FreePool.free;
			time.events.free _ NIL;
			WAIT time.events.cond};
		PutHere => {
			pool: POINTER TO Pool _ FreePool;
			IF FreePool=NIL THEN ERROR;
			FreePool _ FreePool.free;
			pool.free _ timeQueue.events;
			timeQueue.events _ pool;
			timeQueue.size _ timeQueue.size+1;
			WAIT pool.cond};
		PutAfter => {
			time: POINTER TO TimeQueue _ SystemDefs.AllocateHeapNode[SIZE[TimeQueue]];
			time.next _ timeQueue.next;
			timeQueue.next _ time;
			time.time _ startTime;
			time.size _ 1;
			time.events _ FreePool;
			IF FreePool = NIL THEN ERROR;
			FreePool _ FreePool.free;
			time.events.free _ NIL;
			WAIT time.events.cond};
	}};

-- Main part

[] _ RandomCard.InitRandom[seed: -1];
FreePool _ @ConditionPool[0];
{i: CARDINAL;
FOR i IN [0..MaxCond) DO
	Process.DisableTimeout[@ConditionPool[i].cond];
ENDLOOP;
FOR i IN [0..MaxCond-1) DO
	ConditionPool[i].free _ @ConditionPool[i+1]
ENDLOOP};
ConditionPool[MaxCond-1].free _ NIL;
UniversalTime _ 0;
currentProcessSize _ 0;
}.