aboutsummaryrefslogtreecommitdiff
path: root/Scheduler-explained.txt
diff options
context:
space:
mode:
Diffstat (limited to 'Scheduler-explained.txt')
-rw-r--r--Scheduler-explained.txt33
1 files changed, 33 insertions, 0 deletions
diff --git a/Scheduler-explained.txt b/Scheduler-explained.txt
new file mode 100644
index 0000000..efaf2c0
--- /dev/null
+++ b/Scheduler-explained.txt
@@ -0,0 +1,33 @@
+An operating system has to manage user processes. Our system only has one process right now, but usual actions, such as context saving or context restoring, are implemented anyways. The following few paragraphs contain information on how process management looks like in operating systems in general.
+
+Process might return control to the system by executing the svc (eariler called swi) instruction. System would then perform some action on behalf of the process and either return from the supervisor call exception or attempt to schedule another process to run, in which case context of the old process would need to be saved for later and context of the new process would need to be restored.
+
+Process has data in memory (such as it's stack, code) as well as data in registers (r0-r15, CPSR). Together they constitute process' context. From process' perspective, context should not unexpectedly change, so when control is taken away from user mode code (via an exception) and later (possibly after execution of some other processes) given back, it should be transparent to the process (except when kernel does something for the process in terms of supervisor call). In particular, the contents of core registers should be the same as before. For this to be achievable, the operating system has to back up process' registers somewhere in memory and later restore them from that memory.
+
+Operating system kernel maitains a queue of processes waiting for execution. When a process blocks (for example by waiting for IO), it is removed from the queue. If a process unblocks (for example because IO completed) it is added back to the queue. In general, some systems might complicate it, for example by having more queues, but discussing those variations is out of scope of this documentation. When processor is free, one of the processes from the queue (determined by some scheduling algorithm <link to wikipedia??> implemented in the kernel) gets chosen and run on the processor.
+
+As one process could never use a supervisor call, it could occupy the processor forever. To remedy this, timer interrupts can be used by the kernel to interrupt the execution of a process after some time. The process would then have it's context saved and go to the end of the queue. Another process would be scheduled to run.
+
+Other exceptions might occur when process is running. Depending on kernel design, handler of an exception (such as IRQ) might return to the process or cause another one to be scheduled.
+
+If at some time all processes are blocked waiting, the kernel can wait for some interrupt to happen, which could possibly unblock some process (i.e. because IO completed).
+
+While not mentioned earlier, switching between processes' contexts involves not only saving and restoring of registers, but also changing the translation table entries to properly map memory regions used by current process.
+
+In our project, process management is implemented in src/arm/PL1/kernel/scheduler.c.
+
+A "queue" contains data of the only process (variables PL0_regs[], PL0_sp, PL0_lr and PL0_PSR).
+
+Function setup_scheduler_structures is supposed to be called before scheduler is used in any way.
+Function schedule_new() creates and runs a new process.
+Function schedule_wait_for_output() causes the current process to have it's context saved and get blocked waiting for UART to send data. It is called from supervisor call handler. Function schedule_wait_for_input() is simillar, but process waits for UART to receive data.
+Function schedule() attempts to select a process (currently the only one) and run it. If process cannot be run, schedule() waits for interrupt, that could unblock the process. The interrupt handler would not return in this case, but rather call schedule() again.
+Function scheduler_try_output() is supposed to be called by IRQ handler when UART is ready to transmit more data. It can cause a process to get unblocked. scheduler_try_input() is simillar, but relates to receiving data.
+
+The following are assured in our design:
+1. When processor is in user mode, interrupts are enabled.
+2. When processor is in system mode, interrupts are disabled, except when explicitly waiting for the interrupt when process is blocked.
+3. When a process is waiting for input/output, the corresponding IRQ is unmasked. Otherwise, that IRQ is masked.
+4. If an interrupt from UART occurs during execution of user mode code (not possible here, as we only have one process, but shall become possible when proper processes are implemented), the handler shall return. If that interrupt occurs during execution of PL1 code, it means it occured in scheduler, that was implicitly waiting for it and the handler calls scheduler() again instead of returning.
+5. Interrupt from timer is unmasked and set to come whenever a process gets scheduled to run. Timer interrupt is disabled when in PL1 (when scheduler is waiting for interrupt, only UART one can come).
+6. A supervisor call requesting an UART operation, that can not be completed immediately, causes the process to block.