gnu1987/gnucmds/info/wegrzyn.kernel

Received: from UCB-VAX.ARPA by MIT-MC.ARPA; MON  4 MAR 1985 2321 EST
Received: by UCB-VAX.ARPA (4.24/4.42)
	id AA15228; Mon, 4 Mar 85 20:15:57 pst
Return-Path: <decvax!encore!wegrzyn>
Received: by decvax.UUCP (4.12/1.0)
	id AA02212; Mon, 4 Mar 85 12:25:14 est
Received: by encore.UUCP (4.12/4.7)
	id AA02746; Mon, 4 Mar 85 11:47:22 est
Date: Mon, 4 Mar 85 11:47:22 est
From: decvax!encore!wegrzyn@Berkeley (Chuck Wegrzyn)
Message-Id: <8503041647.AA02746@encore.UUCP>
To: RMS@MIT-MC.ARPA
Subject: Re: o.s overview


	Richard,

		Here is the overview document for the operating 
	system I have built, and am building. It is rather sketchy
	since the bulk of the document is in hand written form. Tell
	me if it looks okay for the heart of GNU. I'll call you up
	in a few days.

1. Overview
-----------

	The operating system is broken down into a number of components,
	some of which are separated processes, and others are imbedded
	in the kernel. The operating system is logically broken down into
	the following components :

		directory server	maps 'file' names into directory
						entries (aka information
						entries);
		file server		a repository of data collected into
						blocks on a disk (or disk-
						like device);
		kernel manager		a program that controls the allocation
						of resources;
		process manager		a program that schedules user
						processes;
		memory manager		a program that provides the memory
						management features of the
						system;
		kernel			a small, monolithic piece of code
						that controls i/o, provides
						lower level hardware support,
						and provides the send and
						receive message operations;
		init server		a small program the initializes the
						system and handles major
						catastrophies;
		login manager		a small program that allows users
						access to the system;
		network manager		a program that provides the
						interface between the system
						and network services.

	A process is a separately scheduled piece of code that has it's
	own address space and machine state. A process that runs inside
	the address space of the kernel is called a 'manager'; one that
	runs outside is called a 'server'.


2. The Kernel
-------------

	The kernel, written in a machine protable manner, is the only
	(hopeful) piece of code that needs to be modified when the
	system is ported from one machine to another. Further, since
	it is monolithic, i.e. runs with interrupts disabled, it should
	be easy to maintain. 

	The kernel supports the following features,

		o multiple processors in a tightly coupled environment,
		o message passing : the basic means of communication and
			synchronization in the system,
		o interrupt handling and forwarding,
		o support for i/o,
		o low level scheduling and processor management.


	In the support of processes and scheduling, the kernel uses the
	following algorithm to determine the next process to run :

		Since the kernel can run on any machine, it will first
		lock the microscheduler queue. Once access is gained
		to this queue, the kernel looks for any manager ready
		to run; there will always be at least one manager ready
		to run : the process manager. After finding the manager
		ready to run, it marks it as running and release access
		to the microscheduler queue. The only exception to the
		"marking of the running manager" is the process manager.
		This single manager can have multiple instances of itself
		running : one on each processor. (Further information is
		presented below). Once the manager has been selected the
		kernel will load up the machine state and start execution
		of it. The system is fully capable of providing time
		slice interrupts, priority preemption, etc.

	To support the need for communication between processes, the kernel
	provides the concept of a message queue and message packets. A
	'message queue' is a channel for the transmission of 'message
	packets'. A message packet contains raw, uninterpreted data, and
	references to other message queues. These message queue references
	allow processes to send, and receive information on other message
	queues. The fact that message queue references can be communicated
	between processes allows a simple means of resource passing:

		Each resource in the system, such as an open file, can
		be represented by a message queue reference. Any message
		sent on the message queue will implicitly refer to a
		particular file (only if the file server interprets it
		that way), and any message received on the message queue
		could refer to a specific file. This notion, though
		very simple allows powerful servers to be built.


	The kernel also supports interrupt handling and i/o control in
	two manners. It can support the traditional view : i/o can only
	be handled by a 'privileged' piece of code. The kernel can also
	provide a second style : managers that support i/o. Since managers
	run inside the kernel and are as privileged as the kernel, i/o
	services and interrupt handling can be provided in a very clean
	and simple scheme :

		i/o drivers and interrupt handlers are independently
		scheduled processes that run inside the kernel, i.e.
		they are managers.

	This allows the configuration of the system to be changed rather
	easily : by a simple edit of a 'configuration file' and a reboot
	of the system. It is also possible to provide a completely dynamic
	environment : managers could be dynamically created and destroyed,
	though on the first pass this isn't being supported.

	There are three interfaces to the kernel :

		o the server level interface,
		o the manager level interface, and
		o the hardware level interface.

	The server level interface is very simple, only two system calls
	are directly supported :

		SendMsg(msgptr,msgsize,fullqueuetimeout)
		 	 char *msgptr;
		 unsigned int  msgsize,
			       fullqueuetimeout;

	and

		RcvMsg(msgptr,emptyqueuetimeout)
			 char *msgptr;
		 unsigned int  emptyqueuetimeout;

	The first call will take a message, pointed to by msgptr and whose
	size is msgsize, and transmit it to a specific message queue. If the
	message queue is full, the process will wait for fullqueuetimeout
	ticks. The second call will wait for a message and place it in
	the callers address space. If no message is immediately available
	the process will wait for at least emptyqueuetimeout ticks.

	The second interface to the kernel is similar to the server inter-
	face with a few exceptions. Unlike the server interface, the
	manager interface assumes that messages are part of the kernel
	address space. The manager interface also supports a few more
	requests. The calls for message handling are

		XmitMsg(msgptr,msgsize)
			 char *msgptr;
		 unsigned int  msgsize;

	and
		GetMsg(msgptr)
		 char *msgptr;

	There is no need for timeout support since all manager requests
	bypass the full queue check logic. The calls to support interrupt
	handling are

		WaitforInt(intlev,timeout)
		 unsigned int intlev,
			      timeout;

	and
		SimulateInt(intlev)
		 unsigned int intlev;

	The first call forces a manager to wait for an I/O interrupt from
	level, intlev. The second call simulates (forces) an interrupt to
	occur. The timeout value on the first call is the amount of time
	to wait for the interrupt to 'naturally' occur before waking the
	manager with a SimulateInt call. The time is in clock ticks.
	Also supported at this level are synchronization locks. The locks
	are spinlocks. The calls for these services are

		Lock(lockid)
		 unsigned int lockid;

	and
		UnLock(lockid)
		 unsigned int lockid;

	The first call will wait for access to the specific lock, while
	the second call will free it. Note that lockids are "hardwired"
	into the system.
	
	The final interface to the kernel is that presented between it
	and the hardware support. It is assumed that the hardware support
	interface provides a certain number of features or routines. These
	include the ability to "loadup" the machine state of a process,
	manage the memory maps needed for a process, and intercept all
	interrupts. To this end, the interface needed by the kernel
	includes :

		SwapContext(oldcontext,newcontext)
		 struct PROCESS *oldcontext,*newcontext;

		SetTimeSlice(timevalue)
		 unsigned int timevalue;

		AddMemorytoContext(context)
		 struct PROCESS *context;

		RmvMemoryfromContext(context)
	 	 struct PROCESS *context;

		TestAndSet(addr)
		 unsigned int *addr;

		Clr(addr)
		 unsigned int *addr;

	The first call, SwapContext, is used to force the processor to
	save the current state and switch to a new one. The second call
	is used to set the time slice value and prime the clock, if
	necessary. The next two calls are used to manage the memory maps
	to the particular process contexts. Finally, the last two calls
	are used to provide a certain amount of multi-processor
	synchonization. In addition to the above calls, the kernel makes
	available to the hardware interface a routine call

		Intr(intlev)
		 unsigned int intlev;

	This routine is the hardware levels way of telling the kernel that
	an interrupt has occurred. The 'intlev' are assigned by convention,
	and are not arbitrary.
		

3. The Process Manager
----------------------

	The process manager is a process that runs inside the kernel
	and is responsible for scheduling all user level processes.
	The process manager is also responsible for providing the
	support for such user level services as starting and stopping
	processes, and destroying them. The process manager is really
	composed of two separate kernel processes :

		o process scheduler,
		o process management.

	The process scheduler is responsible for finding a process
	ready to run and starting it. The process management phase
	is responsible for making a process 'known' to the scheduler,
	starting and stopping processes, and removing processes from
	the domain of the scheduler. No process has direct access
	to either of the processes contained in the process manager.

	The process scheduler is invoked for every idle processor
	in the system : there can be multiple copies of the scheduler
	running at a single time. The process scheduler is a program
	that selects one process out of possibly many and runs it. The
	program selected to run is based on the current priority of
	process and some other attributes, such as whether the process
	is real time, the amount of computation to i/o time, etc.

	The process management phase is a process that waits for requests
	from the kernel manager. These requests include the following

		o allow a process to compete for a processor,
			also known as starting a process;
		o prevent a process from competing for a processor,
			also known as stopping a process;
		o add a process to the known process list;
		o remove a process from the known process list;

	These requests are sent via the normal XmitMsg facility.

	The processes that make up the process manager share a number
	of tables and variables. To use any of them, the particular
	process must first issue a Lock() request. Once granted, the
	process can modify the tables as necessary.


4. Memory Manager
-----------------

	The memory manager is a process that handles all memory for
	the system. It is involved whenever a process requires more
	memory, or the system needs more memory. The first type of
	request occurs when a process asks for more memory. The
	second type of request occurs when another process is created
	and memory must be allocated for it. Like the process manager,
	the memory manager is broken down into two separate components :

		o memory request process, and
		o memory support process.

	The memory request process is responsible for handling user
	request. It supports two features :

		AllocMem		allocate some memory
		LiberMem		return some memory.

	The AllocMem request allows the user to request 'chunks' of
	memory, and optionally indicate where the memory should be
	placed. The LiberMem request is used to return some 'chunks'
	of memory to the system. The memory request process works in
	conjunction with the memory support process and the process
	management process to do it's job.

	The memory support process is directly responsible for allocating
	physical memory, supporting the memory management of a process
	and swapping or demand paging. This process has no direct path
	between the user level processes and it : access is gained only
	through action of the memory request process and the process
	manager processes.


5. Kernel Manager
-----------------

	The kernel manager is a process that is the single 'thread'
	through which all user process requests get funneled. It is
	responsible for collecting the message in another process'
	memory and mapping it into the kernel's address space; it
	determines which server is to get the message; verifies a
	few of the arguments; and a few other things. It is also
	responsible for the creation of new message queues, the
	mapping of message queue references from the external
	reference to the global, internal reference, etc.

	The services provided to the user process level include

		o create a new message queue,
		o destroy a message queue,
		o change a message queue's characteristics,
		o intercept a message queue,
		o fork a process,
		o terminate a process,
		o suspend or resume a process,
		o examine a process' state,
		o change a process' state, and
		o generate a 'soft' interrupt.


6. File Server
--------------

	The file server is a process that provides a 'flat' file system
	for the operating environment. It provides, in addition, an
	number of other features :

		o all control data on the disk is independent of
			cpu format, i.e. all disks can be inter-
			changed with all disk drives, so long as
			the media is supported;
		o a two level file deletion mechanism is supported.
			Files can be deleted and recovered, if
			necessary;
		o an automatic part of the file system will permanently
			remove files, as the second stage of the
			deletion;
		o security is built in to the system - the file system
			supports access control lists, called ACLs.
			The ACLs provide for more than read, write
			and execute access - they also provide for 
			deletion, recover, destroy, etc.
		o access to a file can be retracted - if a user has
			retract privileges to a file, they can take
			away access to the file from others;
		o files can have vary cluster allocation sizes;
		o it provides for the 'dynamic' connection of disks
			to itself; and
		o provides for overlapped operation.


7. Directory Server
-------------------

	The directory server is a process that maps strings of characters
	into directory entries. In a sense, it is a simple little database.
	Access to a directory entry is guaranteed to happen in one disk
	access - through a unique hashing scheme names and a small
	internal table, the needed entry is found. Unlike most directory
	systems, the one provided doesn't hold only information about
	files. The directory entry is capable of holding any information :
	pointers to files on disks, process identifiers, and the like.
	Furthermore, the directory entries can hold a number of other
	things, such as the type of file being referenced (text, C source,
	etc). This makes it a general purpose directory system.

	The services supported by the directory server include :

		o creating a new directory entry,
		o destroying a directory entry,
		o modifying a directory entry, and
		o reading a directory entry.

	Filename, unlike most other systems have no significance to the
	directory server. These filenames can be any length and can hold
	any characters. The interpretation of these names, and any
	significance of characters, are left to the caller. As an example,
	two different file names are

			/a/b/c
			/a/b/c/d

	This gives the impression of a hierarchical directory, when in
	reality it is just a simple directory system. The difference
	is that the file a/b/c is not a directory holding 'hidden' pointers
	to files like d. It is really just a file; this gives the
	appearance that directories are really hidden from the caller.
	In actuality, the arguments to the directory server include a
	wildcard feature which once again gives the appearance of a true
	directory system.

8. The Init Server
------------------

	The init server is the first process that is brought up when the
	system is first initialized. It is responsible for starting the
	login processes, the network server and any other servers. It is
	also responsible for connecting the correct device managers to
	the kernel, and a number of other kernel related functions.


9. The Login Manager
--------------------

	The login server process is used to allow users access to the
	system. It provides such necessary functions as user validation,
	connecting the user to the correct directory and program. The
	login server uses the directory server to hold information about
	each user. The information includes :

		o user's login identifier,
		o user's password,
		o user's security level,
		o user's classification categories,
		o starting directory, and
		o starting program.


10. The Network Manager
-----------------------


	The network manager is a collection of process that convert
	internal kernel requests, sends and receives, to network
	requests. Because of it's unique structure it also allows
	support for multiple types of protocols, such as delta-t,
	IP/TCP, etc. Furthermore, it also contains a dynamic router,
	time synchronization support and node failure support.

	Because the network manager is 'hidden', user processes do
	not have direct access to it. They also don't have knowledge
	that a network exists.


		As you can see it includes a lot of stuff. That
	makes it somewhat flexible. I don't particularly care for
	Unices, and have tended to stay away from stupid things like
	chmod, etc. The file system I've built depends on ACLs and
	detail privileges; for this reason I'm not sure if chmod
	makes sense. There are a few other differences, as well.

		What is the status of Emacs? Could I get a copy
	of it within a week or so? I would like to 'play' around
	with it; sort of a beta test.

			chuck
		ucbvax!decvax!encore!wegrzyn