logo

drewdevault.com

[mirror] blog and personal website of Drew DeVault git clone https://hacktivis.me/git/mirror/drewdevault.com.git

Process-scheduling-in-KnightOS.md (6386B)

    

  1. ---
  2. date: 2014-09-02
  3. # set tw=80
  4. layout: post
  5. title: Process scheduling and multitasking in KnightOS
  6. tags: [KnightOS, kernel hacking]
  7. ---
  9. I'm going to do some blogging about technical decisions made with
  10. [KnightOS](http://knightos.org). It's an open-source project I've been working
  11. on for the past four years to build an open-source Unix-like kernel for TI
  12. calculators (in assembly). It's been a cool platform on top of which I can
  13. research low level systems concepts and I thought I'd share some of my findings
  14. with the world.
  16. So, first of all, what is scheduling? For those who are completely out of the
  17. loop, I'll explain what exactly it is and why it's neccessary. Computers run on
  18. a CPU, which executes a series of instructions in order. Each core is not
  19. capable of running several instructions concurrently. However, you can run
  20. hundreds of processes at once on your computer (and you probably are doing so
  21. as you read this article). There are a number of ways of accomplishing, but the
  22. one that suits the most situations is *preemtive multitasking*. This is what
  23. KnightOS uses. You see, a CPU can only execute one instruction after another,
  24. but you can "raise an interrupt". This will halt execution and move to some
  25. other bit of code for a moment. This can be used to handle various events (for
  26. example, the GameBoy raises an interrupt when a button is pressed). One of
  27. these events is often a timer, which raises an interrupt at a fixed interval.
  28. This is the mechanism by which preemptive multitasking is accomplished.
  30. Let's say for a moment that you have two programs loaded into memory and
  31. running, at addresses 0x1000 and 0x2000. Your kernel has an interrupt handler
  32. at 0x100. So if program A is running and an interrupt fires, the following
  33. happens:
  35. 1. 0x1000 is pushed to the stack as the return address
  36. 2. The program counter is set to 0x100 and the interrupt runs
  37. 3. The interrupt concludes and returns, which pops 0x1000 from the stack and
  38.    into the program counter.
  40. Once the interrput handler runs, however, the kernel has a chance to be sneaky:
  42. 1. 0x1000 is pushed to the stack as the return address
  43. 2. The program counter is set to 0x100 and the interrupt runs
  44. 3. The interrupt removes 0x1000 from the stack and puts 0x2000 there instead
  45. 3. The interrupt concludes and returns, which pops 0x2000 from the stack and
  46.    into the program counter.
  48. Now the interrupt has switched the CPU from program A to program B. And the
  49. next time an interrupt occurs, the kernel can switch from program B to program
  50. A. This event is called a "context switch".  This is the basis of preemptive
  51. multitasking. On top of this, however, there are lots of ideas around which
  52. processes should get CPU time and when. Some systems have more complex
  53. schedulers, but KnightOS runs on limited hardware and I wanted the context
  54. switch to be short and sweet so that the running processes get as much of the
  55. CPU as possible. I'll explain the simple KnightOS scheduling algorithm here.
  56. First, its goals:
  58. * Short and simple context switches
  59. * Ability to suspend processes when not in foreground
  60. * Ability to run background processes
  62. What KnightOS uses is a simple round robin with the ability to suspend threads.
  63. That is, we have a list of processes and then some flags, among which is
  64. whether or not the processes is currently suspended. So say we have this list
  65. of processes in memory:
  67. * 1: PC=0x2000, not suspended
  68. * 2: PC=0x2000, not suspended
  69. * 3: PC=0x2000, suspended
  70. * 4: PC=0x2000, not suspended
  72. As process 1 is running and an interrupt fires, the kernel looks at this table
  73. and picks the next non-suspended process to run - process 2. On the next
  74. interrupt, it does it again, skipping process 3 and giving time to process 4.
  76. To actually implement this, we have to think about the stack. KnightOS runs on
  77. z80 processors, which have a single stack and a shared memory space. The CPU
  78. uses the PC register to keep track of which address the current instruction is
  79. at. That is, say you compile this code:
  81. ```
  82. ld a, 10
  83. inc a
  84. ld (hl), a
  85. ```
  87. This compiles to the machine code 3E 0A 3C 77. Say we load this program at
  88. 0x8000 - then 0x8000 will point to `ld a, 10`. When the CPU finishes executing
  89. this instruction, it advances PC to 0x8002 (since `ld a, 10` is a two-byte
  90. instruction). The next instruction it executes will be `inc a`, and then PC
  91. advances to 0x8003.
  93. The stack is used for a lot of things. It can be used to save values, and it is
  94. used to call subroutines. It is also used for interrupts. It's like the same
  95. stacks you use in higher level applications, but it's at a very low level. When
  96. an interrupt fires, the current value of PC is pushed to the stack. Then PC is
  97. set to the interrupt routine, and then when that's done the top of the stack is
  98. removed and placed into PC (effectively returning control to the original
  99. location). However, since the stack is used for much more than that, we have
  100. additional things to consider.
  102. In KnightOS, when a new process starts, it's allocated a stack in memory and
  103. the CPU's stack pointer (SP) is set to its address. When an interrupt happens,
  104. we need to change the stack to point at some other process so it has time to
  105. run (since that's where its PC is). However, we need to make sure that the
  106. first processes stack is left intact. Since we allocate a new stack for the
  107. next process, we can simply change SP to that processes stack. This will leave
  108. behind the value of PC that was pushed during the interrupt for the previous
  109. process, and lo and behlod a similar value of PC is waiting on top of the other
  110. processes stack.
  112. So that's it! We do a simple round robin, skipping suspended processes and
  113. following the procedure outlined above to switch between them. This is how
  114. KnightOS shares one CPU with several "concurrent" processes. Operating systems
  115. like Linux use more complicated schedulers with more interesting theory if
  116. you'd like some additional reading. And of course, since KnightOS is open
  117. source, you may enjoy reading all of our code for handling this stuff (in
  118. assembly):
  120. [Context switching](https://github.com/KnightOS/kernel/blob/master/src/00/interrupt.asm)
  122. [Stack allocation during process creation](https://github.com/KnightOS/kernel/blob/master/src/00/thread.asm#L72)
  124. We're hanging out on #knightos on Freenode if you want to chat about cool
  125. low-level stuff like scheduling and memory management.