How to write your own Operating System (x86_64): Multitasking
Πως να γράψετε το δικό σας Λειτουργικό Σύστημα (x86_64): Πολυδιεργασία
IntroductionΕισαγωγή
In our previous articles, we showed how to implement a bootloader, how to enter the long mode and how to deal with interrupts. In this part, we will talk about Multitasking. There are two basic forms of multitasking: Cooperative Multitasking and Preemptive Multitasking.
Σε προηγούμενα άρθρα μας, είδαμε πώς να υλοποιήσουμε έναν εκκινητή, πώς να μπούμε στη λειτουργία μακράς κατάστασης και πως να διαχειριστούμε τις Διακοπές. Σε αυτό το μέρος, θα συζητήσουμε την Πολυδιεργασία (Multitasking). Υπάρχουν δύο βασικοί τύποι Πολυδιεργασίας: η Συνεργατική Πολυδιεργασία (Cooperative Multitasking) και η Προεκτοπιστική Πολυδιεργασία (Preemptive Multitasking).
For cooperative multitasking, a task uses the CPU until it voluntarily gives up the CPU (e.g. Windows 3.x or pre-X MacOS).
Για τη Συνεργατική Πολυδιεργασία, μια διεργασία χρησιμοποιεί τον επεξεργαστη μέχρις ότου τον παραδόσει εθελοντικά (λ.χ. αυτό συνέβαινε στα Windows 3.x ή στα pre-X MacOS).
In a preemptive multitasking system (i.e. most modern operating systems), task switches are caused by an external actor (usually the Κernel) and are done for one or more reasons (e.g. when the task consumed its timeframe and/or when a higher priority task needed the CPU). We can further subdivide these systems into those who can preempt only user tasks (e.g. pre-2.6 kernel Linux), and those who can preempt the Kernel itself. This is a major concern for any real-time system or multimedia applications because a non-preemptive Kernel may cause significant latencies and reduced responsiveness.
Σε ένα σύστημα Προεκτοπιστικής Πολυδιεργασίας (όπως ειναι τα περισσότερα μοντέρνα λειτουργικά συστήματα), οι εναλλαγές των διεργασιών προκαλούνται από έναν εξωτερικό παράγοντα (συνήθως τον Πυρήνα) και γίνονται για έναν ή περισσότερους λόγους (π.χ. όταν η διεργασία έχει εξαντλήσει το χρονικό πλαίσιο που της αναλογεί ή/και όταν μια διεργασία υψηλότερης προτεραιότητας χρειάζεται τον επεξεργαστή). Μπορούμε να υποδιαιρέσουμε περαιτέρω αυτά τα συστήματα, σε εκείνα που μπορούν να προεκτοπίζουν μόνο διεργασίες των χρηστών και σε εκείνα που μπορούν να προεκτοπίζουν και τις διεργασίες του ίδιου του Πυρήνα. Αυτό αποτελεί ένα σημαντικό ζήτημα για οποιοδήποτε σύστημα Πραγματικού Χρόνου (real-time system) ή για εφαρμογές Πολυμέσων (Multimedia applications), επειδή ένας μη προεκτοπιστικός Πυρήνας ενδέχεται να προκαλεί σημαντικές καθυστερήσεις και μειωμένη αποκρισιμότητα.
Another important fact you need to know: Even though there are mechanisms in the hardware to facilitate the task / context switching, they come with significant performance considerations. The hardware mechanisms save almost all of the CPU state and consequently, they can be slower than it is necessary. For example, when the CPU loads segment registers, a lot of access and permission checks are involved. As the long mode doesn't use segmentation anymore, loading the segment registers during context switches may not be required. In any case, CPU manufacturers do not seem eager to improve the hardware switching mechanisms. Therefore, modern operating systems prefer to implement the switching in software (as we will do).
Ένα ακόμη σημαντικό γεγονός που πρέπει να γνωρίζετε: Αν και υπάρχουν μηχανισμοί στο υλικό που διευκολύνουν την εναλλαγή διεργασιών / πλαισίου, αυτοί συνοδεύονται από σοβαρές επιφυλάξεις όσον αφορά την απόδοσή τους. Οι μηχανισμοί του υλικού αποθηκεύουν σχεδόν όλη την κατάτασταση του επεξεργαστή με συνέπεια τις περισσότερες φορές να είναι πιο αργοί από όσο χρειάζεται. Για παράδειγμα, όταν ο επεξεργαστής φορτώνει τους καταχωρητές τμημάτων, επιτελεί και όλους τους σχετικούς ελέγχους πρόσβασης και δικαιωμάτων. Αλλά, καθώς η λειτουργία μακράς κατάστασης δε χρησιμοποιεί πια την κατάτμηση (segmentation), η φόρτωση των καταχωρητών τμήματος κατά την εναλλαγή πλαισίου μπορεί να μη χρειάζεται. Σε κάθε περίπτωση, οι κατασκευαστές επεξεργαστών δε φαίνονται ιδιαίτερα ενθουσιώδεις στο να βελτιώσουν τους μηχανισμούς εναλλαγής στο υλικό. Οπότε, τα σύγχρονα λειτουργικά συστήματα προτιμούν να υλοποιούν την εναλλαγή στο λογισμικό (όπως θα κάνουμε κι εμείς).
Kernel Code: MultitaskingΚώδικας του Πυρήνα: Πολυδιεργασία
kernel/tasking.asm
In this file, we define a struct named TS where we are gonna save the task state (i.e. the register values and other important information for the task). For the time being, because we don't have implement a memory manager yet, we allocate and initialize statically three such structs (task state "slots"). As we can see, we also have some functions to save and load a task state and to create a new task (note that in order to create a new task, it's important to allocate a new stack for it):
Σε αυτό το αρχείο, ορίζουμε μια δομή που λέγεται TS, στην οποία πρόκειται να αποθηκεύουμε την κατάσταση μιας διεργασίας (δηλαδή τις τιμές των καταχωρητών και άλλες σημαντικές πληροφορίες για τη διεργασία). Προς το παρόν, επειδή δεν έχουμε υλοποιήσει ακόμη κάποιον διαχειριστή μνήμης, θα δεσμεύσουμε και θα αρχικοποιήσουμε στατικά τρείς τέτοιες δομές ("θέσεις αποθήκευσης" της κατάστασης των διεργασιών). Όπως μπορούμε να δούμε, έχουμε επίσης κάποιες συναρτήσεις για την αποθήκευση και την ανάκτηση της κατάστασης μιας διεργασίας καθώς και για τη δημιουργία μιας νέας διεργασίας (σημείωστε ότι για να δημιουργήσουμε μια νέα διεργασία είναι σημαντικό να δεσμεύσουμε μια νέα στοίβα για αυτήν):
BITS 64
;---Define----------------------------------------------------------------------
STRUC TS
.status resw 1
.rip resq 1
.rax resq 1
.rbx resq 1
.rcx resq 1
.rdx resq 1
.rbp resq 1
.rsi resq 1
.rdi resq 1
.rsp resq 1
.r8 resq 1
.r9 resq 1
.r10 resq 1
.r11 resq 1
.r12 resq 1
.r13 resq 1
.r14 resq 1
.r15 resq 1
.cs resw 1
.ds resw 1
.es resw 1
.fs resw 1
.gs resw 1
.ss resw 1
.cr3 resq 1
.rflags resq 1
ENDSTRUC
;---Initialized data----------------------------------------------------------
num_tasks dq 0
active_task_slot dq 0
stack_allocation dq 0
code_segment dq 0
return_address dq 0
stack_segment dq 0
stack_pointer dq 0
rflags dq 0
; Task Slot 0
TS0: ISTRUC TS
at TS.status, dw 0
at TS.rip, dq 0
at TS.rax, dq 0
at TS.rbx, dq 0
at TS.rcx, dq 0
at TS.rdx, dq 0
at TS.rbp, dq 0
at TS.rsi, dq 0
at TS.rdi, dq 0
at TS.rsp, dq 0
at TS.r8, dq 0
at TS.r9, dq 0
at TS.r10, dq 0
at TS.r11, dq 0
at TS.r12, dq 0
at TS.r13, dq 0
at TS.r14, dq 0
at TS.r15, dq 0
at TS.cs, dw 0
at TS.ds, dw 0
at TS.es, dw 0
at TS.fs, dw 0
at TS.gs, dw 0
at TS.ss, dw 0
at TS.cr3, dq 0
at TS.rflags, dq 0
IEND
; Task Slot 1
TS1: ISTRUC TS
at TS.status, dw 0
at TS.rip, dq 0
at TS.rax, dq 0
at TS.rbx, dq 0
at TS.rcx, dq 0
at TS.rdx, dq 0
at TS.rbp, dq 0
at TS.rsi, dq 0
at TS.rdi, dq 0
at TS.rsp, dq 0
at TS.r8, dq 0
at TS.r9, dq 0
at TS.r10, dq 0
at TS.r11, dq 0
at TS.r12, dq 0
at TS.r13, dq 0
at TS.r14, dq 0
at TS.r15, dq 0
at TS.cs, dw 0
at TS.ds, dw 0
at TS.es, dw 0
at TS.fs, dw 0
at TS.gs, dw 0
at TS.ss, dw 0
at TS.cr3, dq 0
at TS.rflags, dq 0
IEND
; Task Slot 2
TS2: ISTRUC TS
at TS.status, dw 0
at TS.rip, dq 0
at TS.rax, dq 0
at TS.rbx, dq 0
at TS.rcx, dq 0
at TS.rdx, dq 0
at TS.rbp, dq 0
at TS.rsi, dq 0
at TS.rdi, dq 0
at TS.rsp, dq 0
at TS.r8, dq 0
at TS.r9, dq 0
at TS.r10, dq 0
at TS.r11, dq 0
at TS.r12, dq 0
at TS.r13, dq 0
at TS.r14, dq 0
at TS.r15, dq 0
at TS.cs, dw 0
at TS.ds, dw 0
at TS.es, dw 0
at TS.fs, dw 0
at TS.gs, dw 0
at TS.ss, dw 0
at TS.cr3, dq 0
at TS.rflags, dq 0
IEND
; Array of pointers to the task slots
TS_ARRAY dq TS0, TS1, TS2
;---Code------------------------------------------------------------------------
Save_task_state:
;**********************************************************************************;
; Save task state to the active task slot ;
;**********************************************************************************;
push r15
push r15
push rax
mov rax, [active_task_slot]
mov r15, [TS_ARRAY+rax*8]
mov rax, [code_segment]
mov [r15+TS.cs], rax
mov rax, [return_address]
mov [r15+TS.rip], rax
mov rax, [stack_segment]
mov [r15+TS.ss], rax
mov rax, [stack_pointer]
mov [r15+TS.rsp], rax
mov rax, [rflags]
mov [r15+TS.rflags], rax
pop rax
mov [r15+TS.rax], rax
mov [r15+TS.rbx], rbx
mov [r15+TS.rcx], rcx
mov [r15+TS.rdx], rdx
mov [r15+TS.rbp], rbp
mov [r15+TS.rsi], rsi
mov [r15+TS.rdi], rdi
mov [r15+TS.r8], r8
mov [r15+TS.r9], r9
mov [r15+TS.r10], r10
mov [r15+TS.r11], r11
mov [r15+TS.r12], r12
mov [r15+TS.r13], r13
mov [r15+TS.r14], r14
pop qword [r15+TS.r15]
pop r15
ret
Load_task_state:
;**********************************************************************************;
; Load task state from the active task slot ;
;**********************************************************************************;
mov rax, [active_task_slot]
mov r15, [TS_ARRAY+rax*8]
mov rax, [r15+TS.rip]
mov [return_address], rax
mov rax, [r15+TS.cs]
mov [code_segment], rax
mov rax, [r15+TS.ss]
mov [stack_segment], rax
mov rax, [r15+TS.rsp]
mov [stack_pointer], rax
mov rax, [r15+TS.rflags]
mov [rflags], rax
mov rax, [r15+TS.rax]
mov rbx, [r15+TS.rbx]
mov rcx, [r15+TS.rcx]
mov rdx, [r15+TS.rdx]
mov rbp, [r15+TS.rbp]
mov rsi, [r15+TS.rsi]
mov rdi, [r15+TS.rdi]
mov r8, [r15+TS.r8]
mov r9, [r15+TS.r9]
mov r10, [r15+TS.r10]
mov r11, [r15+TS.r11]
mov r12, [r15+TS.r12]
mov r13, [r15+TS.r13]
mov r14, [r15+TS.r14]
push qword [r15+TS.r15]
pop r15
ret
Create_task:
;**********************************************************************************;
; Crate a new task ;
;----------------------------------------------------------------------------------;
; rsi: pointer to the address of the first instruction of the task ;
;**********************************************************************************;
push rax
push r15
; Trick to save RFLAGS to [rflags]
pushfq
mov rax, [rsp]
mov [rflags], rax
add rsp, 8 ; Instead of popfq
; Save code and stack selectors
mov [code_segment], cs
mov [stack_segment], ss
;Set active task slot equal to the number of tasks.
;This means we make active an emply slot (as we count task slots from 0).
mov rax, [num_tasks]
mov qword [active_task_slot], rax
; Init task state.
call Save_task_state
; Set rip (in the state of task) equal to rsi (i.e. the task address).
mov r15, [TS_ARRAY+rax*8]
mov qword [r15+TS.rip], rsi
; Allocate a new stack of 1000 bytes for the task.
sub qword [stack_allocation], 1000
mov rax, [stack_allocation]
; Set rsp (in the state of task) to point to the new stack for the task.
mov qword [r15+TS.rsp], rax
; Increase number of tasks by one.
inc qword [num_tasks]
pop r15
pop rax
retkernel/isr.asm
In order to implement the Preemptive Multitasking, we will modify our previously written handler (i.e. the Interrupt Service Routine) for the IRQ0 (timer). The trick is that, when an interrupt occurs in long mode, the processor pushes in the stack the interrupted program's stack pointer (SS:RSP), the RFLAGS value, and the return pointer (CS:RIP). When we want to switch tasks (let's say every x ticks), we can replace these values with the corresponding values for the next task. The instruction IRETQ will load these values to the proper registers and thus, we will switch to the next task:
Για να υλοποιήσουμε την Προεκτοπιστική Πολυδιεργασία, θα τροποποιήσουμε τον προηγούμενο χειριστή (δηλαδή τη Ρουτίνα Εξυπηρέτησης Διακοπής) που είχαμε γράψει για το IRQ0 (χρονιστή). Το κόλπο είναι ότι, όταν συμβεί μια διακοπή στη λειτουργία μακράς κατάστασης, ο επεξεργαστής φορτώνει στη στοίβα τον δείκτη στοίβας του διακοπτόμενου προγράμματος (SS:RSP), την τιμή των RFLAGS, και τον Δείκτη Επιστροφής (CS:RIP). Οπότε, όταν θέλουμε να αλλάζουμε διεργασία (ας πούμε κάθε χ παλμούς του χρονιστή), μπορούμε να αντικαθιστούμε τις τιμές αυτές με τις αντίστοιχες τιμές για την επόμενη διεργασία. Η εντολή IRETQ θα φορτώνει αυτές τις τιμες στους κατάλληλους καταχωρητές και έτσι θα μεταβαίνουμε στην επόμενη διεργασία:
...
ISR_systimer:
;*****************************************************************************;
; System Timer Interrupt Service Routine (IRQ0 mapped to INT 0x20) ;
;*****************************************************************************;
push rax
mov al, PIC_EOI ; Send EOI (End of Interrupt) command
out PIC1_COMMAND, al
pop rax
inc qword [systimer_ticks]
inc qword [tasktimer_ticks]
cmp qword [tasktimer_ticks], 1 ; Every how many ticks we want to switch tasks.
jg .switch_task
iretq
.switch_task:
mov qword [tasktimer_ticks], 0
; In long mode, when an interrupt occurs, the processor pushes in the stack
; the interrupted program's stack pointer (SS:RSP), the RFLAGS, and the
; return pointer (CS:RIP). In order to switch task, we have to replace them.
; Therefore, we remove (pop) them from the stack.
pop qword [return_address] ; RIP
pop qword [code_segment] ; CS
pop qword [rflags] ; RFLAGS
pop qword [stack_pointer] ; RSP
pop qword [stack_segment] ; SS
; We save the current task state in the active task slot.
call Save_task_state
; We activate the next task slot
inc qword [active_task_slot]
; We check if the current task was the last task.
push rax
mov rax, [num_tasks]
cmp [active_task_slot], rax
pop rax
jnz .load
; If we reach the last task, switch to the first task
mov qword [active_task_slot], 0
.load:
; Load the next task state from the active task slot.
call Load_task_state
; We now push back to the stack the values we have loaded for the next task.
push qword [stack_segment]
push qword [stack_pointer]
push qword [rflags]
push qword [code_segment]
push qword [return_address]
; The instruction IRETQ will load these values to the proper registers
; and we will switch to the next task.
iretq
...kernel/kernel.asm
Here, we create three distinct tasks in order to see the Preemptive Multitasking in action:
Εδώ, δημιουργούμε τρεις ξεχωριστές διεργασίες ώστε να δούμε την Προεκτοπιστική Πολυδιεργασία στην πράξη:
BITS 64 ; We have entered the long mode! :)
;---Define----------------------------------------------------------------------
%define DATA_SEG 0x0010
;---Initialized data------------------------------------------------------------
hello_world_message dw 12
db 'Hello World!'
ticks_message dw 20
db 'System timer ticks: '
scancode_message dw 20
db 'Keyboard scan code: '
task1_message dw 6
db "Task 1"
task2_message dw 6
db "Task 2"
task3_message dw 6
db "Task 3"
;---Include---------------------------------------------------------------------
%include "kernel/video.asm"
%include "kernel/idt.asm"
%include "kernel/isr.asm"
%include "kernel/tasking.asm"
;---Code------------------------------------------------------------------------
Kernel:
lidt [IDTR] ; Load our IDTR
mov al, 0x80 ; OCW1: Unmask all interrupts at master PIC.
out PIC1_DATA, al
mov al, 0x80 ; OCW1: Unmask all interrupts at master PIC.
out PIC2_DATA, al
; Set all segments registers to DATA_SEG.
mov ax, DATA_SEG
mov ds, ax
mov es, ax
mov fs, ax
mov gs, ax
mov ss, ax
; Clear the screen.
mov rax, 0x0020002000200020 ; Set background color to black (0) and
; character to blank space (20).
call Fill_screen
; Print "Hello World!" at the upper right corner.
mov ah, 0x1E
mov r8, 69
mov r9, 1
mov rsi, hello_world_message
call Print
; Initialize general stack allocation to the current rsp value.
mov [stack_allocation], rsp
; Create three tasks
mov rsi, Task1
call Create_task
mov rsi, Task2
call Create_task
mov rsi, Task3
call Create_task
; Set active the first task slot.
mov qword [active_task_slot], 0
; Task 1: We print system timer ticks and keyboard scan code.
Task1:
mov ah, (VGA_COLOR_DARK_GREY << 4) | VGA_COLOR_WHITE
mov r8, 1
mov r9, 2
mov rsi, task1_message
Call Print
mov r8, 1
mov r9, 3
mov rsi, ticks_message
Call Print
mov r8, 1
mov r9, 4
mov rsi, scancode_message
Call Print
.loop:
; Print system timer ticks.
mov r8, 21
mov r9, 3
mov r10, [systimer_ticks]
call Print_hex
; Print keyboard scan code.
mov r8, 21
mov r9, 4
mov r10, [keyboard_scancode]
call Print_hex
jmp Task1.loop
; Task 2: We set r10 to 0 and we increase it by one in a loop.
Task2:
mov ah, (VGA_COLOR_GREEN << 4) | VGA_COLOR_WHITE
mov r8, 1
mov r9, 6
mov rsi, task2_message
Call Print
mov r8, 1
mov r9, 7
mov r10, 0
.loop:
inc r10
; Print number of ticks
Call Print_hex
jmp Task2.loop
; Task 3: We set r10 to 0xFFFFFFFFFFFFFFFF and we decrease it by one in a loop.
Task3:
mov ah, (VGA_COLOR_MAGENTA << 4) | VGA_COLOR_WHITE
mov r8, 1
mov r9, 9
mov rsi, task3_message
Call Print
mov r8, 1
mov r9, 10
mov r10, 0xFFFFFFFFFFFFFFFF
.loop:
dec r10
; Print number of ticks
Call Print_hex
jmp Task3.loopRunning our codeΕκτέλεση του κώδικά μας
We can test our code very easily using an emulator like QEMU:
Μπορούμε να δοκιμάσουμε τον κώδικά μας πολύ εύκολα, χρησιμοποιώντας έναν εξομοιωτή όπως ο QEMU:
$ make
$ qemu-system-x86_64 -drive format=raw,file=os.bin
Notice that, even though all the tasks use the same registers (e.g. the r10), nevertheless each task does its job normally and it's not affected by the constant task/context switching.
Παρατηρήστε ότι, αν και όλες οι διεργασίες χρησιμοποιούν τους ίδιους καταχωρητές (λ.χ. τον r10), παρόλα αυτά η καθεμία επιτελεί το έργο της κανονικά και δεν επηρεάζεται από τη συνεχή εναλλαγή διεργασιών/πλαισίου.
Full codeΠλήρης κώδικας
You can download the full code from here: code
Μπορείτε να κατεβάσετε τον πλήρη κώδικα απο εδώ: κώδικας