-- 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;
}.