Teorija
Prekid i prioritet
Interrupt (prekid) je signal kojim uređaj traži pažnju procesora. Procesor dovrši trenutnu instrukciju, spremi kontekst prekinutog programa i skoči u interrupt service routine (ISR, prekidna rutina) tog uređaja. Svaka linija ima prioritet, a dok se ISR izvodi, procesor radi na njezinoj razini, interrupt priority level (IPL, razina prioriteta prekida). Zahtjev jednakog ili nižeg prioriteta tada čeka, jer ga trenutni IPL maskira: to je masking (maskiranje). Zahtjev višeg prioriteta prekida rutinu, pa nastaje nested interrupt (ugniježđeni prekid). Bez gniježđenja ISR radi do kraja uz sve prekide maskirane (IPL max), pa na stogu leži najviše jedan okvir prekida. Prekidima uređaji javljaju kraj prijenosa, vidi Tehnike U/I i Upravljački programi; timer interrupt (prekid timera) pokreće preemption (preempciju), vidi Raspoređivanje.
Interrupt and priority
An interrupt is a signal by which a device asks for the processor's attention. The processor finishes the current instruction, saves the context of the interrupted program and jumps to the device's interrupt service routine (ISR). Each line has a priority, and while an ISR runs, the processor runs at its level, the interrupt priority level (IPL). A request of equal or lower priority then waits, because the current IPL masks it: this is masking. A request of higher priority interrupts the routine, and a nested interrupt occurs. Without nesting, an ISR runs to completion with all interrupts masked (IPL max), so at most one interrupt frame lies on the stack. Devices use interrupts to signal the end of a transfer, see I/O techniques and Device drivers; the timer interrupt drives preemption, see Scheduling.
Stog jezgre i kontekst
Pri svakom prihvatu procesor na kernel stack (stog jezgre) stavlja jedan frame (okvir) s context (kontekst) prekinute rutine: povratnu adresu PC, program status word (PSW, riječ stanja programa) s razinom IPL i registre. Stack pointer (SP, pokazivač stoga) pritom se pomiče prema nižim adresama, a instrukcija IRET na kraju rutine skida okvir i nastavlja prekinutu rutinu točno gdje je stala. Stvarni stog jezgre ima fiksnu veličinu (na x86-64 Linuxu 16 KB, na mikrokontrolerima često samo stotine bajtova). Kad se napuni, novi okvir završi ispod granice, preko susjednih podataka jezgre: to je stack overflow (preljev stoga). Sustav se ne sruši odmah, ali su podaci oštećeni. Obrane su zaštitna stranica ispod stoga, zaseban stog za prekide, ograničena dubina gniježđenja ili odgađanje prekida (opcija „Odgodi prekid”). Neograničen stog je idealizacija koja pokazuje koliko bi memorije trebalo.
Kernel stack and context
On every accepted interrupt the processor pushes one frame onto the kernel stack with the context of the interrupted routine: the return address PC, the program status word (PSW) with the IPL, and the registers. The stack pointer (SP) moves toward lower addresses, and the IRET instruction at the end of the routine pops the frame and resumes the interrupted routine exactly where it stopped. A real kernel stack has a fixed size (16 KB on x86-64 Linux, often only a few hundred bytes on microcontrollers). When it is full, a new frame lands below the limit, over neighboring kernel data: this is a stack overflow. The system does not crash at once, but the data is corrupted. The defenses are a guard page below the stack, a separate interrupt stack, a limited nesting depth, or deferring interrupts (the option “Defer the interrupt”). An unlimited stack is an idealization that shows how much memory would be needed.
Re-entrant rutina
Ako prekidnu rutinu smije prekinuti samo strogo viši prioritet, prekidi zajedno zauzimaju najviše onoliko okvira koliko ima razina prioriteta, ovdje pet. Rutina iznimke ili sistemskog poziva radi na IPL 0, pa ispod tog lanca može ležati još jedan okvir (najviše šest; bez gniježđenja najviše dva). Re-entrant rutinu smije prekinuti i novi zahtjev iste linije dok još radi, pa ista rutina može biti na stogu više puta i dubina više nije ograničena prioritetima (scenarij „Rafal IRQ4 × 10”). To je sigurno samo ako rutina sve svoje podatke drži na stogu, a ne u zajedničkim varijablama, i ako je stog dovoljno velik. Zato jezgre to obično ne dopuštaju: linija ostaje maskirana dok njezina rutina ne završi, a novi zahtjev dok je stari još na čekanju se gubi.
Re-entrant routine
If an ISR may be interrupted only by a strictly higher priority, the interrupts together take at most as many frames as there are priority levels, here five. An exception or system call routine runs at IPL 0, so one more frame can lie below that chain (at most six; without nesting at most two). A re-entrant routine may also be interrupted by a new request on the same line while it is still running, so the same routine can be on the stack several times and the depth is no longer bounded by the priorities (scenario “Burst IRQ4 × 10”). This is safe only if the routine keeps all its data on the stack, not in shared variables, and if the stack is large enough. That is why kernels usually do not allow it: the line stays masked until its routine finishes, and a new request while the old one is still pending is lost.
Sekvencijalna i ugniježđena obrada
Stallings uspoređuje dva pristupa na primjeru s pisačem (prioritet 2), komunikacijskom linijom (5) i diskom (4), čiji zahtjevi stižu redom u t = 10, 15 i 20, a svaka rutina traje 10 jedinica. Kod sequential interrupt processing (sekvencijalna obrada) procesor tijekom obrade onemogući prekide, pa se zahtjevi obrađuju redom: komunikacije čekaju 5, a disk 10 jedinica. Kod nested interrupt processing (ugniježđena obrada) komunikacije odmah prekidaju pisač, disk čeka 5 jedinica, a pisač završava zadnji, u t = 40. Prikaz „Sekvencijalno ↔ ugniježđeno” na vremenskoj crti pokazuje oba tijeka jedan ispod drugoga.
Sequential and nested processing
Stallings compares the two approaches with an example of a printer (priority 2), a communications line (5) and a disk (4), whose requests arrive at t = 10, 15 and 20 respectively, and each routine takes 10 time units. With sequential interrupt processing the processor disables interrupts while it processes one, so the requests are handled in order: communications wait 5 and the disk 10 units. With nested interrupt processing the communications ISR immediately interrupts the printer ISR, the disk waits 5 units, and the printer finishes last, at t = 40. The view “Sequential ↔ nested” on the timeline shows both runs, one below the other.
Prekid, iznimka i softverski prekid
Osim vanjskih prekida postoje sinkroni događaji koje izaziva sama instrukcija programa. Exception (iznimka; Stallings za nju koristi naziv trap, također iznimka) nastaje kad instrukcija ne može završiti, npr. zbog page fault (promašaj stranice); nakon obrade ista se instrukcija ponavlja (vidi Prevođenje adresa). Supervisor call (sistemski poziv; češće system call) namjeran je zahtjev programa jezgri. Na x86 ga pokreće software interrupt (softverski prekid), instrukcija int 0x80, pa program nakon obrade nastavlja iza te instrukcije (vidi Sistemski pozivi). Sva tri ulaze u jezgru istim mehanizmom: okvir na stogu, vektor, IRET.
Usporedba triju načina ulaska u jezgru
| Prekid | Iznimka | Softverski prekid |
|---|
| Izvor | uređaj (vanjski signal) | instrukcija koja ne može završiti | instrukcija int u programu |
|---|
| Sinkron? | ne, stiže bilo kad | da | da |
|---|
| Može se maskirati? | da (IPL) | ne | ne |
|---|
| Primjer | timer, disk, tipkovnica | promašaj stranice, dijeljenje nulom | sistemski poziv int 0x80 |
|---|
| Točka povratka | sljedeća instrukcija | ista instrukcija (ponavlja se) | instrukcija iza int |
|---|
Interrupt, exception and software interrupt
Besides external interrupts there are synchronous events, caused by an instruction of the program itself. An exception (Stallings also calls it a trap) occurs when an instruction cannot complete, for example because of a page fault; after handling, the same instruction is repeated (see Address translation). A supervisor call (more often: system call) is a deliberate request from a program to the kernel. On x86 it is triggered by a software interrupt, the instruction int 0x80, so after handling the program continues after that instruction (see System calls). All three enter the kernel by the same mechanism: a frame on the stack, a vector, IRET.
Three ways into the kernel compared
| Interrupt | Exception | Software interrupt |
|---|
| Source | device (external signal) | an instruction that cannot complete | the int instruction in the program |
|---|
| Synchronous? | no, arrives at any time | yes | yes |
|---|
| Can it be masked? | yes (IPL) | no | no |
|---|
| Example | timer, disk, keyboard | page fault, division by zero | system call int 0x80 |
|---|
| Return point | the next instruction | the same instruction (repeated) | the instruction after int |
|---|
Ciklus instrukcije s provjerom prekida
Instruction cycle (ciklus instrukcije) sastoji se od koraka fetch (dohvat) i execute (izvršavanje), a između dviju instrukcija procesor radi interrupt check (provjera prekida). Ako postoji zahtjev koji smije prekinuti trenutnu rutinu, procesor u interrupt vector table (IVT, tablica vektora prekida) pronađe interrupt vector (vektor prekida) tog zahtjeva, odnosno adresu njegove rutine, i skoči na nju. U simulatoru IRQ n ima vektor 0x20 + n (kao nakon preslikavanja PIC-a u Linuxu), promašaj stranice vektor 0x0E, a sistemski poziv 0x80. Traka „Ciklus instrukcije” u kartici procesora u svakom taktu pokazuje rezultat provjere, dohvaćeni PC i rutinu koja se izvršava.
Instruction cycle with an interrupt check
The instruction cycle consists of the fetch and execute stages, and between two instructions the processor performs an interrupt check. If there is a request that may interrupt the current routine, the processor looks up that request's interrupt vector, that is, the address of its routine, in the interrupt vector table (IVT) and jumps to it. In the simulator IRQ n has vector 0x20 + n (as after the PIC remapping in Linux), the page fault vector 0x0E, and the system call 0x80. The “Instruction cycle” strip in the processor card shows in every tick the result of the check, the fetched PC and the routine being executed.
Literatura: Stallings, Operating Systems: Internals and Design Principles, 9. izd., pogl. 1, odjeljak 1.4 Interrupts (ciklus instrukcije s prekidima, višestruki prekidi); alternativno Tanenbaum & Bos, Modern Operating Systems, odjeljci 1.3.5 (U/I uređaji i prekidi) i 5.1.5 (ponovno o prekidima).Reading: Stallings, Operating Systems: Internals and Design Principles, 9th ed., ch. 1, sec. 1.4 Interrupts (instruction cycle with interrupts, multiple interrupts); alternatively Tanenbaum & Bos, Modern Operating Systems, sec. 1.3.5 (I/O devices and interrupts) and 5.1.5 (interrupts revisited).