Ker, win

[Michael David WINIKOFF]

Hi everyone -- as promised my sketch for a simple kernel.
feel free to flame, comment, criticise, compliment (:-) or suggest additions
or changes.


The kernel has the following system calls:

contextswitch()
pid = self()
pid = spawn(ptr to code, ptr to stack, initial pc)
kill(pid)

send(pid, message)
mesg = receive()
bool = poll()

ptr = alloc(size)
free(ptr, size)

reqid = service(devid, service_number, ptr to result/arg buffer, flags)
bool = ready(reqid)

getdev(devid, service_number, var pid, var code)
setdev(devid, service_number, pid, code)


-----
contextswitch: Calls the scheduler. This is not likely to be used from within
user code.

self: Returns the current process/task's id, useful for exit() = kill(self())
[And also for sending messages to self. ??]

spawn -- this creates another task/process.
The details here are very hazy. The current call is meant to be very light
weight -- all it does is add an entry in the scheduler, allocating the memory,
loading the code (and setting up virtual memory) is done somewhere else.

send and receive work as expected (rec. blocks if no message is available.
It is an open question whether we have a buffer and if so how large is it
-- or possibly unbounded?)

A comment on messages: Sending large message raises issues.
We can either just copy them or fiddle with address spaces so they're accessible.
(possibly using copy on write??)

Currently think of mesg as being a single atomic value. 
This can be a pointer -- setting up he VM / copying data can be done elsewhere.

poll returns TRUE if there is a waiting message.

allocate and free dish out (physical) memory. 

The kernel has a device table. This is simply a mapping from
(devid, service_number) to (pid, code)

The system call "service" looks up the appropriate location and calls the
result process passing on the code.

Note that service is asynchronous -- it returns a reqid.
This can be used for determining when the operation has been carried out.
I feel that asynchronous IO is better in that you can simulate sunchonous 
IO using it but not the other way around (at least not without creating extra
processes ...)

One of the flags to the device could be whether the process wishes a message
to be sent to it when the operation has been carried out.

The caller could do:

reqid = service(....)
a:
mesg = receive(...)
IF not(ready(reqid)) THEN
	remember mesg
	GOTO a
ENDIF
getdev and setdev are used for querying the table and for changing it.
Obviously some notion of priviliege is needed -- we don't want all processes
to be able to read and modify the dev-table.

I'd envisage devicees as being reasonably high levelinterfaces to hard ware.

Eg the disk would provide seek, block read and block write but not a file system

Some devices include:
	disk (floppy and hard), ports (serial and parallel)
	clock, screen, sound, mouse, joystick, keyboard.


-------
An initial "shell" could be a program that lets you make system calls ...
This would be more like a system debugger/monitor ...

-------

A sample implementation
~~~~~~~~~~~~~~~~~~~~~~~~~

Note: This is (very!) simplistic. 
It illustrates one possible implementation.

There is a ticker that generates an intterupt every n milliseconds.
(how else can you do preemption? :-)

THis forces a call to contextswitch()

The scheduler can use simple round robin 

Process table:

next_free
running-process

for each process:
	state: waiting / ready / running / invalid
	pid: int
	pc
	registers
	current message
	message valid : bool

----------
IMPORTANT: Except when a system call has a call to contextswitch it will
be assumed to run atomically.
(eg. on a single procesor implementation system calls disable interupts)

contextswitch: changes state of running-process to ready
	finds next ready process, sets it to running, sets running-process
	to it.
	load registers and pc.

kill: removes an entry from the table (set state to invalid)

self: return running-process

spawn: Find an invalid entry. Change it to ready and initialise it

send: 
	a:
	if target of send is invalid return error
	if the message_valid is false then
		message_valid = true
		current_message = mesg (passed as argument to call)
		return
	else
		contextswitch()
		goto a
	endif
	
	/* note that we don't have a facility for waiting. 
	** due to the context switch this should be reasonable efficient.
	** if message sending is a bottleneck we should have a queue of 
	** messages rather then a single entry
	*/

receive:
	if message_valid then
		message_valid = false
		return current_message
	else
		state = waiting
		contextswitch()
	endif

poll: return message_valid

-----
Memory allocation:

A simple way of managing memory is with a bitmap.
If we have 1 bit = 1K byte then the amount of memory taken by the bitmap is
0.1% -- this is fine if we are managing physical memory.

alloc(size) 
	round size upto next kilobyte
	search bitmap for next free chunk of that size
	set the region to taken
	return pointer

free(ptr,size)
	reset bits in bitmap

Note: We can't compact physical memory without using virtual memory ...

-----

We also have a device table.
The "ready" call could be implemented either in the kernel or  in the device
drivers.



--------------------------------------------------------------------------------
Michael Winikoff
winikoff@cs.mu.oz.au
Computer science honours. University of Melbourne, Australia.