Transcript Original Presentation

Toward Self-Stabilizing
Operating Systems
Shlomi Dolev, BGU
Reuven Yagel, BGU-Rafael
Talk Outline
• Motivation for self-stabilizing operating systems
• OS do not stabilize! NMI example, must shut down
the computer!
• Blackbox
– Periodic reset re-install and execute
– Periodic re-install and execute
– Continues re-install monitor and establish consistency
• Write a self-stabilizing tiny OS
Goal: Autonomic Computer
• Following any sequence of transient faults, softerrors (98% of RAM errors are soft errors), wrong crc during
communication etc. the system converges.
• Self Stabilization
– System can be started in arbitrary state
– Traditionally used in distributed systems (where
transient faults are frequent)
– Cannot run self-stabilizing algorithms unless
hardware+OS are stabilizing (Fair composition
[Dolev2K,DH03])
Operating Systems
• Main OS (black-box):
– UNIX (Berkeley), LINUX (freeware)
– DOS, WINDOWS (Microsoft)
• Three main parts of a kernel (tailored):
– Process scheduler
– Memory manager
– Device drivers
Hardware Platform
• IA-32 Architecture
– CPU modes – (real, protected, virtual 8086, system)
– Boot process – BIOS, MBR, 2nd Loader.
– Memory: RAM + ROM, 20-bit segment addressing,
Interrupt Vector Table, IDTR
– Interrupts (INT + NMI pins, software interrupts)
• Watchdog device
– Machine restart
– Recovery Monitor in ROM [Castro & Liskov 2k]
– OS Re-install
• Harvard Model (data - program separated)
Unix-Linux-Windows-Dos do not
Stabilize
• Processor - NMI
– During NMI handler, further NMI are
discarded, until the IRET instruction is
executed [Intel 2003
• IDTR
– LIDT instruction can change table location
Periodic reset re-install and
execute
• Watchdog Timer – Self Stabilizing
• Processor reset
• OS code copy from ROM to RAM during
bootstrap (check that it is self-stabilizing)
• Slow & Bother continuous work
Periodic re-install and execute
• Watchdog
• Re-install only
• Require hardware changes
– NMI countdown register
• Decremented toward 0 in each cycle
• Enables NMIs when equal to 0
• Set to a value that enables full execution of the
stabilizer code
– NMI vector hardwired
• Still bothers continuous work
OS Stabilizer Code
OS_SEGMENT
STABILIZER_ROM_SEGMENT
OS_ROM_SEGMENT
equ 0x1000
equ 0x2000
equ 0x3000
;enter real mode
mov cr0, 0
;copy OS image
mov
mov
mov
mov
mov
mov
mov
cld
rep
ax, OS_ROM_SEGMENT
ds, ax
ax, OS_SEGMENT
es, ax
si, 0x00
di, 0x00
cx, 0x100
Processor
cr0 0
0
ax
1000
3000
cx
100
99
ds
3000
si
10
es
1000
movsb
di
PC
2000
0
Address Space
01
PSW
2000
10000
OS CODE
20000
Stabilizer
30000
OS Image
OS Stabilizer Code cont.
; prepare for journey back
mov ax, WATCHDOG_ROM_SEGMENT
mov ss, ax
mov sp, 0xFFFF
pushf
push word OS_SEGENT
push word 0x0
; enable NMI & jump to OS code
iret
Or better just:
mov
mov
jmp
ax, OS_SEGMENT
es, ax
[es:0]
Assumptions
• Initial Configuration
• RAM contains OS code and initialized
variables, processor is configured to run the OS
(real-mode), PC register points to the first
instruction of the OS code.
• Stabilizing processor & watchdog.
• Processor will react to watchdog interrupt.
• Stabilizer code can not be corrupted
Proof Sketch
• Every execution of the OS stabilizer is finite and
does not depend on previous state
• OS stabilizer will be executed infinitely often.
• The OS stabilizer code enters the system into the
initial configuration.
• Thus: In every infinite execution the system will
infinitely often will reach the initial configuration.
Continues re-install monitor and
establish consistency
• Warm boot
• Consistency check & Establishment
• …
Minimal OS
• Various Small OSs
• Tiny OS – Specialized
• SONIX (Temporary Name)
Demonstration
Demo – SONIX Code
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
[SEGMENT .text]
jmp
StartOS
msgWelcome
reversedCol
;holds the raw that will be reversed
fontColor
;originally blue
delayCounter
dw
StartOS:
mov ax, cs
;location where loader2 is loaded
mov ds, ax
db
db
"SONIX is NOT Linux!", 0x00
9
db
1
0
;make it work slower
OsLoop:
mov
mov
; screen col 10
mov
; screen row 13
mov
si, msgWelcome
cl, 10
; welcome message
ch, 13
dh, byte [fontColor]
; all this mess is to determine which character will be reserved
mov
al, [reversedCol]
inc
al
cmp
al, 29
; end of message
jb
GoAhead
; put reverse video back to first column and also switch color
mov
al, 9
inc
byte [fontColor]
cmp
byte [fontColor], 8
jb
GoAhead
mov
byte [fontColor], 1
; normal attribute