Calid OS - Process Managment

File: process.cf

Each process has a process-control block (PCB). Only one process is executed at a time and its PCB is referenced from the kernel variable activepcb.

The contents of the PCB will change over time as new  facilities are compiled into the kernel. As new features are described, the phrase "data structure rooted in the PCB" means that a new field is added to the PCB structure. However, the PCB structure is also compiled into the debugger, so changes must occur in both places. Also, the regSP field is used in context-switching code and must remain at offset zero within the PCB.

The process structures are initialized by a thread of control rooted in the non-maskable interrupt at process reset. After initialization, this thread becomes the null process. During initialization,

• a termination stack is created for use during address-space cleanup
• all PCBs are marked as available
• the null process is created and given an address space
• address translation is enabled
• a second process is created from a hard-coded filename

void processInit() {
	
	// initialize process-related data structures
	terminationstack = (int *)((int)mmAlloc(256) + 256);
	interruptVector[iv_stack] = terminationstack;
	
	for (int i = 0; i < pcbsize; i++)
		pcblist[i].state = st_avail;

	// create null process 
	PCB *nullpcb = newPCB();
	createAddressSpace(nullpcb, kernelPageMax);
	
	// turn on address translation 
	activepcb = nullpcb;
	setPTLR(activepcb->regPTLR);
	setPTBR(activepcb->regPTBR);
	enablevm();
	
	// create shell process
	PCB *PCB = createProcessFromFile("shell.image");
	addQueue(readyTail, PCB);
	
	// ... and become null process
	nullprocess();
}

The pcblist is managed as an array of PCBs. newPCB() finds an available PCB at process-creation time, but there is no corresponding freePCB(). An available PCB is one whose state is st_avail. Freeing a PCB is a simple matter of setting the PCB 's state to that value.

When a PCB is allocated, its state is marked as st_new and its processid is set to the value of an incrementing counter concatenated with the PCB's index in pcblist. With this technique, processids can be mapped directly into PCBs by masking off the counter, and stale processids can also be detected.

static PCB *newPCB() {
	for (int i = 0; i < pcbsize; i++)
		if (pcblist[i].state == st_avail) {
			kmemset((char *)(pcblist+i), 0, sizeof(PCB));
			pcblist[i].state = st_new;
			pcblist[i].processid = nextprocessid++ * 256 + i;
			return pcblist + i;
		}
	return NULL;
}

Creating an address space consists of allocating a page table from the kernel heap, mapping the first part of the page table one-to-one with kernel frames, and mapping the remainder of the page table to frames acquired from the frame allocator.

static void createAddressSpace(PCB *PCB, int pagecount) {
	PCB->pagetable = (int *)mmAlloc(sizeof(int) * pagecount);
	PCB->pagecount = pagecount;
	PCB->regPTBR = PCB->pagetable;
	PCB->regPTLR = pagecount * 256;
	
	// first part
	for (int i = 0; i < kernelPageMax; i++) 
		PCB->pagetable[i] = i * 256 | 1;
	
	// second part
	for (i = kernelPageMax; i < PCB->pagecount; i++)
		PCB->pagetable[i] = (int)mmAllocFrame() | 1;
}

The low-order bit of a page table entry is the page-valid bit. The high-order 24 bits, concatenated with 8 bits of zeroes, are the address of the first byte of a frame in real memory after translation.

The process life cycle is managed by processCreate(), processWait(), and processTerminate().

processCreate() constructs a process from a file image and adds the PCB to the ready queue.

int processCreate(char *filename) {
	PCB *PCB = createProcessFromFile(filename);
	if (PCB == (PCB *)0)
		return -1;
	else {
		addQueue(readyTail, PCB);
		return PCB->processid;
	}
}

createProcessFromFile(), called from processCreate(), allocates and initializes a PCB, maps a page table and initializes the stack in such a way that on first dispatch the process begins executing at processStartup(). The remaining initialization is accomplished by callOnStack(), explained below

static PCB *createProcessFromFile(char *filename) {
	PCB *PCB = newPCB();
	PCB->start = (void *)(kernelPageMax * 256); 
	semaI(PCB->semaWait, 0);
	PCB->filename = mmAlloc(kstrlen(filename) + 1);
	kstrcpy(PCB->filename, filename);

	createAddressSpace(PCB, processPageMax);
	callOnStack((void *)initializeStack, terminationstack, PCB, (void *)(processPageMax * 256));
	return PCB;
}

processTerminate() switches to the termination stack and turns off address translation. The real-memory frames used by the process are recycled. However, the PCB cannot be recycled until the exit code has been retrieved. This is done when some other process calls processWait(). The synchronization between the terminating process and waiting process is done by means of a semaphore in the PCB.

void processTerminate(int exitcode) {
	activepcb->exitcode = exitcode;
	asm {
		push	terminationstack;
		popr	sp;
		disablevm;
	}
	processDestroyAddressSpace(activepcb);
	mmDealloc(activepcb->filename);
	activepcb->state = st_terminated;
	semaV(activepcb->semaWait);
	activepcb = (void *)0;
	dispatch();
}

processWait() completes the life cycle of a process. If the process has not yet terminated, processWait() waits on the process's termination semaphore. The exitcode is retrieved from the PCB and PCB itself is recycled simply by marking its state as available.

int processWait(int pid) {
	for (int i = 0; i < pcbsize; i++)
		if (pid == pcblist[i].processid)
			break;
	if (i == pcbsize)
		return -1;
	PCB *PCB = pcblist+i;
	semaP(PCB->semaWait);
	int result = PCB->exitcode;
	if (PCB->semaWait.count == 0) 
		PCB->state = st_avail;
	else
		semaV(pcb->semaWait);
	return result;
}

Process creation, revisited

Process creation takes place in two stages. In the first stage, processCreate() constructs an address space, allocates a PCB, and prepares the stack for execution. The second phase, executed in kernel code in the context of the new process, loads an image and passes control to it. The treatment of processCreate() given above described the first two sub stages of the first stage. We continue here with the third sub stage.

callOnStack() calls a function on a separate temporary stack. The purpose of this is to allow initializeStack(), the function passed as f, to use the temporary stack while preparing the real stack, passed in vsp. The parameters are accessed by assembly-language instructions. The following table is useful in establishing a map of parameters to callOnStack().

• The body of the function is bracket by code to save and restore the fp. However, the fp is pushed onto the temporary stack and will be restored from there.
• The temporary stack receives a parameter list consisting of (pcb, vsp).
• The address f is also pushed on the stack; it will be popped and used in the calltos instruction.
• The tsp parameter is loaded into the sp register. Now f is at the top of the stack.
• f is called and the pcb and vsp parameters are removed. Now fp is at the top of the stack
• fp is popped and the normal return sequence follows.

static callOnStack(void *f, int *tsp, PCB *pcb, void *vsp) {
	--tsp;
	asm {
		pushr 	fp;
		pushrell fp, 12;
		storel;
		deallocs 4;
	}
		
	*--tsp = (int)vsp;
	*--tsp = (int)pcb;
	*--tsp = (int)f;
	
	asm {
		pushrell fp, 12;
		popr	sp;
		calltos;
		deallocs 8;
	}
	asm {
		popr	fp;
	}

In the diagram, solid lines show the situation at entry to callOnStack. Initially, sp = fp and arguments are referenced by positive offsets from fp. Dotted lines show the situation just before calltos.

The operation performed by calltos moves the value at the top of the stack into the pc and replaces it with the old value of the pc, i.e., the return value, effectively popping and calling f. When the call returns, st and pcb are removed from the stack by the deallocs instruction and fp is popped. This recreates the fp = sp situation that existed at entry to callOnStack, allowing callOnStack, to return to its caller.

initializeStack() is called on a temporary stack with a PCB and a vsp. It is important to note where in memory the various objects are located. The code for initializeStack, the temporary stack and the PCB are all located in kernel space. vsp, on the other hand is a virtual address in the address space allocated to the PCB.

The local variable rsp contains the translated value of stackaddress. That is, rsp contains a real address. Disabling address translation is transparent to the code, because kernel code is in a V=R portion of the address space, and allows the new stack to be accessed from "outside" the new address space.

The point of initializeStack is to construct a stack frame that appears as it would in the middle of the context-switching transfer() operation. When this PCB is dispatched, it will switch correctly.

static void initializeStack(PCB *pcb, void *vsp) {	
	// set up stack
	int *rsp = (int *)translate(
		pcb->pagetable, (void *)((int *)vsp - 1)) + 1;
	disablevm();	
	*--rsp = 0; // dst pcb
	*--rsp = (int)pcb; // src pcb; see transfer()
	*--rsp = (int)processStartup;
	*--rsp = 0; // fp
	enablevm();
	pcb->regSP = pcb->regSP - 4; // misleading: is really sp - 4 * 4
}

The last thing that createProcess() does is to thread the process into the ready queue.

When the process is first dispatched, it "returns to" the first instruction of processStartup(), initiating the second phase of process creation. processStartup() is another function that performs unusual operations on the stack. Notice that processStartup() has the interrupt attribute, which means that it returns via an iret instruction. The unusual stack operations construct a stack frame suitable for return from an interrupt handler and then modify the fp so the stack frame will be used. The goal here is to have the processor execute callProcessStart() with interrupts enabled. Almost incidentally, processStartup() also loads an image.

static void interrupt processStartup() {
	if (loadImage() == -1)
		processTerminate(-1);
	int flags;
	void *ret;
	int fp;
	flags = 5; // interrupts enabled, not supervisor, address translation enabled
	ret = (void *)callProcessStart;
	fp = 0;
	asm {movr fp, sp;}
}

callProcessStart is almost anticlimactic. It calls the function whose address was stored in the start field of the PCB. When that function returns, callProcessStart() calls processTerminate() to terminate the process and recycle the resources.

static void callProcessStart() {
	activepcb->start();
	processTerminate(0);
}

On second thought, it makes more sense to loadImage() in callProcessStart() rather than processStartup(). This would require implementing an exec-like kernel call because callProcessStart(), even though located in kernel code, runs in user mode.