💾 Archived View for vierkantor.com › xukut › manual › process.gmi captured on 2024-05-26 at 14:49:24. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2024-05-10)
-=-=-=-=-=-=-
Processes are the abstraction through which XukutOS tracks what the computer is actually doing at the moment. For example, there is a process that arranges the graphics that get drawn on the screen, there is a process that determines the new location of the cursor when you move the mouse, and many more. Within a process, there is a single thread of execution; by running multiple processes, XukutOS can perform multiple tasks at the same time. Processes also serve as a useful abstraction and isolation mechanism: each purpose of the computer can have its own process, and when that process cannot recover from an error, the process should be restartable without too much damage to the rest of the system. Each process has an id for uniquely identifying it within one computer, until the computer is reset, and an address for identifying it within a larger network of computers.
It is important to distinguish between a process and a continuation: each thread execution belongs to a single process, but many continuations can be in scope at the same time. Only one continuation can execute at one time, while processes (behave like) many are running at once.
Processes are isolated from each other and run simultaneously, but often you can't let one process run until it has some results computed by another process. The main mechanism for achieving this in XukutOS is message passing. Processes that need a message from another process to continue are considered "blocked". (TODO: currently, a process will wait indefinitely, this should also be controlled by a timer!)
XukutOS manual → Messages: how to send and receive messages between processes
Sometimes your process needs to wait until a specified period of time has elapsed. The `sleep' and `wait' family of functions will suspend execution of the current process until the time has come. Processes that resume running only when a specified time occurs are considered "waiting".
XukutOS manual → Sleeping and waiting
In the above, we distinguished a few process states: running (code is currently being executed on a processor), suspended (the process could run but there is no processor available for it), waiting (the process will start running again when a certain time has passed) and blocked (the process will start running when it receives a message). It is also possible that the process stops completely, when it has done its job or encounters an unfixable error. Once a process stops, it is no longer available as a process.
Processes are currently identified by a number which increments for each process started after the computer has been reset. This process address is used to send messages.
Once networking gets implemented, we'll design a nicer way to identify processes running on different computers.
The scheduler is the part of the kernel that decides which process will be run when. It has a list of all the processes that are currently running on the computer and all the processes that are waiting for a timer. If there is a process whose timer is almost up, that process will be scheduled, otherwise the suspended process that has waitest the longest to be scheduled. When a process is scheduled, it replaces the currently running process on that processor (that process will be descheduled and end up in the suspended, waiting or blocked state depending on the reason for descheduling.) The thread of execution in a processor is divided into time slices, one slice for each process that gets scheduled. The scheduler ensures that the slices are not too short (or you waste time by switching between processes so much, at least `xukut:process:min-slice') and not too long (or processes don't get a chance to run, at most `xukut:process:max-slice').
The scheduler chooses the first process out of these options, if the process is not already running on another processor:
* processes whose timer is less than `min-slice' in the future, earlier timers first
* processes whose timeslice was over (and don't have a timer), longer-waiting processes first
* a special wait process that does nothing (but efficiently, so we don't use too much power when nothing needs to be done)
In effect, there is a priority queue of processes, consisting of the waiting processes whose timer is almost up, then all the non-waiting suspended processes, then an infinite list of copies of the wait process.
The scheduler runs in kernel mode when an exception (e.g. timer interrupt, syscall or memory error) occurs. The code to handle this exception will determine that the current process needs to be replaced, and will deschedule it and schedule the next process, selecting the next process in the way described above.
Monitors detect whether a process terminates. When a process monitors another, and the monitored process is terminated, the monitoring process receives message id 18 from the kernel.
Describes message id 18. Also more details on receiving messages.
It's important to realize that monitors are very limited in their application: they only send a message when a process *stops*. A process that gets stuck on an infinite loop, or that is blocked on some condition that never comes true, or otherwise doesn't respond, is just as useless in practice as an actually terminated process. Monitors are local-only: the kernel can't monitor across the network (although you should be able to adapt the system to be network-capable). In summary, it's often better to use timeouts to detect when a process is down.
This is an explanation of low-level design in XukutOS. We hope that the design works well enough that you can stick to higher-level stuff for day to day activities.
There are really 4 modes a processor can be running in: the previously mentioned process and kernel mode, init mode and boot mode. In process and kernel mode, there is a currently scheduled process (although a new process can be scheduled in kernel mode), and if you inspect the state of the system, it is as if that process is running. Making it appear that the processor is never running in kernel mode is called PCLSR'ing. When switching from process mode to kernel mode, the process state needs to be saved somewhere: this is done on the (per-processor) kernel stack, and when going back to process mode from kernel mode, this information is retrieved again from the stack. So to schedule a process to run, two things need to happen: some variables shared between processors get updated to indicate what this processor is doing, and the process state stored on the stack is replaced.
XukutOS manual → How init and boot mode work
If process state is removed from the stack, it must be saved in a process object. In fact, all processes, running, waiting, suspended or blocked, have their own process object that stores the state as of the last time they were descheduled. Process objects are created when the process is created, and deleted when the process stops. Making a process object available outside of the kernel can result in difficult concurrency bugs and breaking the PCLSR'ing abstraction, so we try to keep them private.
Since we want to avoid allocations in the kernel, while keeping the ability to run many processes, the various lists of processes are implemented as internal, double-linked lists. This means each process object has a field for the previous and next process, per list that it is included in. There are of course functions for manipulating these lists correctly.
A process object is used by the kernel to store the state of a process. It is a flat object (the garbage collector has special handling for the stacks in this object), with the following fields
* `messages': A list of messages received by the process since the last `receive' syscall. The messages are stored in the same order as they are returned by the `receive' syscall, i.e. the oldest message is last.
* `os' and `ns': The stacks of this process, respectively a tuple and a span. (These objects must be allocated as permanent blocks.) The corresponding pointers are stored as fields further on in the data structure.
* `o0' ... `o14': The object registers.
* `n0' ... `n14': The number registers.
* `osp', `nsp': The stack pointers, which point into the `os' and `ns' blocks. (They are not offsets from `os' and `ns'!)
* `elr': The next instruction to execute in this process.
* `psr': The program status register.
* `id': A number identifying this process, unique within one computer and one reset.
* `state': A number identifying the state of this process. `0': running, `1': suspended, `2': waiting, `3': blocked, `4': stopped. Should be updated atomically with the sets of `prev' and `next' pointers.
* `timer': The time at which this process goes from waiting to running. Only relevant if the `state' is waiting.
* `suspended_prev' and `suspended_next': the previous and next process that were suspended. Only relevant if the `state' is suspended.
* `waiting_prev' and `waiting_next': the previous and next waiting process, in order of `timer'. Only relevant if the `state' is waiting.
There is quite a bit of concurrency going on with these objects, so make sure you correctly apply one of the below functions instead of directly modifying the slots.
Returns the list of messages received by the process since the last `receive' syscall. Does not modify the list.
Returns the list of messages received by the process since the last `receive' syscall. Replaces the list with `nil', modifying the process object.
Add a new message to (the front of) the list of messages received by the process, modifying the process object. Does not unblock the process, use `process:locking-write-message!' to do so.
Obtains and releases the memory lock.
Set the ID of the process to a new, unique number. Modifies the process object.
Update the process state based on the current exception state and the saved number `ns' and object `os' registers.
`ns' points to the following words: `n0', `n1', ..., `n13', `lr', `osp'.
`os' points to the following words: `val', `env', `args', `o3', `o4', ..., `o14'.
`elr' is in the machine register `elr_el1', `nsp' is in the machine register `sp_el0', `psr' in the machine register `spsr_el1'
Does not update the current process for this processor.
Replace the exception state, saved number `ns' and object `os' registers with values from the given process.
Don't forget to call `process:save!'!
`ns' will point to the following words: `n0', `n1', ..., `n13', `lr', `osp'.
`os' will point to the following words: `val', `env', `args', `o3', `o4', ..., `o14'.
`elr' will be in the machine register `elr_el1', `nsp' in the machine register `sp_el0', `psr' in the machine register `spsr_el1'
Does not update the current process for this processor.
Immediately start executing the given process (updating the value of the current process). Should not be used in kernel mode, since it does not clean up the state of the currently running process. Useful for going from boot mode to process mode.
To run a (different) process when in kernel mode, save and deschedule the current process, schedule and load the other process, and return from the exception.
There is a tuple of current processes, one per cpu. We need to be able to determine which process belongs to which cpu, for various bookkeeping purposes. The following internal functions help with that.
Return the current process for this processor.
Set the current process for this processor. Does not modify the values in the process itself.
Most of these functions require that the scheduler lock is held, otherwise you'll get concurrency issues.
The overall procedure for invoking the scheduler looks as follows:
* exception call, process state is saved on the kernel stack
* ...
* call `process:save!' on the current process
* acquire the scheduler lock
* deschedule the current process using `deschedule-suspended!', `deschedule-blocked!', `deschedule-waiting!' or `deschedule-stopping!' as appropriate
* automatically schedule the next process to run using `schedule-next!', or manually choose a process to schedule and call `schedule-desuspend!' or `schedule-dewait!' as appropriate.
* release the scheduler lock
* call `process:load!' on the current process (which has been set to the next process by one of the `schedule!' functions)
* ...
* exception return, process state is loaded from the kernel stack
Initializes a few data structures after reset. Should be called once, before any of the scheduler functions are called.
Adds the process to the list of active processes, setting it to suspended state.
Allocates memory and then obtains + releases the scheduler lock.
Deschedules the given running process by setting it to suspended. Updates the appropriate process lists.
(Does not modify the current process.)
Requires that the scheduler lock is held.
Deschedules the given running process by setting it to wait for the timer. Updates the appropriate process lists.
(Does not modify the current process.)
Requires that the scheduler lock is held.
Deschedules the given running process by setting it to be blocked. Updates the appropriate process lists.
(Does not modify the current process.)
Requires that the scheduler lock is held.
Deschedules the given running process by stopping it completely. Updates the appropriate process lists.
(Does not modify the current process.)
Requires that the scheduler lock is held.
Allows the given process to start running again, switching it from suspended state to running. Updates the appropriate process lists, including the current process.
Requires that the scheduler lock is held.
Allows the given process to start running again, switching it from waiting state to running. Updates the appropriate process lists, including the current process.
Requires that the scheduler lock is held.
Allows the given process to start running again, switching it from blocked state to suspended. Updates the appropriate process lists.
Requires that the scheduler lock is held.
If you want to switch a process from blocked to running, you should follow `deblock!' by `schedule-desuspend!'.
Returns the waiting process that has the earliest timer, if there is one whose timer is less than `now + xukut:process:min-slice'. Otherwise, returns `nil'.
Requires that the scheduler lock is held.
Determines the next timestamp that the timer interrupt should fire, to schedule a waiting or suspended process.
The value of `next-timer' is determined as follows:
- if `get-waiting-soon' returns a process, return (+ now min-slice) (which is guaranteed to be after the timer of `get-waiting-soon'
- otherwise, return (+ now max-slice)
Requires that the scheduler lock is held.
Returns the waiting or suspended process that should run next. Updates the appropriate process lists, including the current process, by calling `schedule-desuspend!' or `schedule-dewait!' as appropriate.
Sets the timer interrupt to fire at the appropriate time (namely `(next-timer)')
Requires that the scheduler lock is held.
Add a new message to (the front of) the list of messages received by the process, modifying the process object. Unblocks the process if its state is blocked.
Allocates memory, then acquires and releases the scheduler lock.
Any questions? Contact me:
By email at vierkantor@vierkantor.com