Exokernel
An operating system architecture for
application level resource management
B4. グェン トアン ドゥク
1
全体の内容
1. Abstractions in traditional operating
systems
2. Exokernel overview
3. Exokernel architecture
4. Exokernel design
5. Summary
2
全体の内容
1. Abstractions in traditional operating
systems
2. Exokernel overview
3. Exokernel design
4. Exokernel implementation
5. Summary
3
Abstractions in traditional OS
General purpose abstractions
固定したインタフェースと実装
どのアプリケーションがその上で動いているか
は考慮しない
問題点:
Resourceの管理の仕方はほとんど決められ、
(applicationは)勝手に変えられない
Hardware abstractionはほとんど変わらない
より良いやり方があっても適用しない
4
Abstraction in traditional OS
Applicationはそれらの問題点に影響され
る
アプリケーションのperformanceを減らす
Applicationに(ハードウェアの)情報を隠す
Application特定の性質を利用できない
HW exceptions, page faults, raw device I/O….
Applicationの機能を限定する
Applicationとhardwareとのインタフェースは唯一に決められ
る
5
全体の内容
1. Abstractions in traditional operating
systems
2. Exokernel overview
3. Exokernel design
4. Exokernel implementation
5. Summary
6
Exokernel overview(1)
どのアプリケーションでもresourceを自分で管理
できる
Resourceの管理と保護を分離する
Kernel は安全にresourceを保護する
Applicationは効率的にresourceを管理する
Kernel は resourceをapplicationにexportする
Virtual memory, file systemなどはapplication
libraryにある
それらのライブラリはlibrary operating
system(LibOS)と呼ぶ
Hardware は異なるLibOS間で共有している
7
Exokernel overview(2)
保護と管理の分離の理由
LibOSがprivileged OSと同等な能力を持ち、し
かも(applicationの)performanceに影響しな
い
各OSが“同居”できるようにする
OSのabstractionの仕方を容易に変化できる
ようにする
8
全体の内容
1. Abstractions in traditional operating
systems
2. Exokernel overview
3. Exokernel design
4. Exokernel implementation
5. Summary
9
Exokernel design
3.1. Design principles
3.2. Exokernel architecture
3.3. Resource multiplexing
10
3.1. Design principles
保護機能と管理機能を分離する
何でもExposeする(見せる)
11
保護機能と管理機能を分離する
保護機能に必要な管理機能だけを実現する
保護機能とは?
Timer, TLBはkernelが管理する
Resourceの所有権を監視する
Resourceが使用される度に所有権をチェックする
必要なときには、resourceのaccess権利をapplication
から取り戻す
Resourceの使い方はLibOSに任せる
12
何でもexposeする(1)
Expose hardware
Applicationは全てのhardware resourceにaccessで
きる(CPU, TLB, physical memory, disk, exception,
interrupt…)
保護機能を実現できる限り、resourceを低レベルで見
せる
Disk block, physical pages…を見せる、高度抽象化したファ
イルなどとして見せない.
Expose allocation
Application allocates resource explicitly、つまり、
applicationはresource allocation過程に参加する
Applicationは色々な情報を持っているので、参加す
ると最適化できる
13
何でもexposeする(2)
Expose nameとsystem infomation
Physical nameを使う(physical disk block…)
System全体の情報を見せる(kernel data structure,
system statistic…)
Expose revocation
Visible resource revocation(resourceを取り戻すとき
に、applicationに知らせる)
例えばmemoryを回収するときに、applicationがどのpageを
返すかを決める
Applicationは所有しているresourceを制御できる
14
3.2. Exokernel architecture
Exokernel はハードウェアの上の薄いlayerであ
る。
そのlayerがhardwareをmultiplexするし、exportする
(low-level primitivesとして、exportする)
例): CPU: yeild(), TLB: TLBwrite(), TLBvadelete(),
…
Exokernel上のlibrary operating systemが高度
な抽象化を実現する
Virtual memory, file system…などを実装する
この抽象化は簡単に拡張、変化できる
色々なLibOSが同じkernel上で共存できる
15
Exokernel architecture
16
Secure binding(1)
Resourceを安全にmultiplexする(複数があるように見せ
る)ために、resourceを監視する必要がある
Resourceの監視を効率的に実現するために、kernel は
LibOSをresourceにsecure bindingさせる
Secure bindingとは、application(LibOS) がresourceの
所有権をもらうことである
Kernelが提供されたプリミティブ群を用いて所有権を宣言する
(例: TLBwrite()). 宣言するときはbind timeと呼び、使用すると
きはaccess timeと呼ぶ.
Bind timeでkernelは権限をチェックする、access timeはチェック
しなくて済む.
17
Secure binding(2)
18
Secure binding(3)
Secure bindingを実現するために、３つの方法が
ある
ハードウェアサポートを利用する
Software caching
TLB faultのとき、application(LibOS)がTLBWrite() を 呼ぶ
(bind time)、その後、自由に使える(access time)
Software TLBを実現する
Downloading application code
Application codeをkernel にdownloadする
権限チェックなどの時にこのコードをkernelで実行
Applicationがscheduleされなくてもこのコードが実行できる
19
3.3. Resource multiplexing
Multiplexing
Multiplexing
Multiplexing
Multiplexing
CPU
Physical memory
Network
Disk
20
Multiplexing CPU(1)
CPUをtime slices vectorとして見る
ProcessはCPUのtime slicesをallocateできる(メ
モリのように)
Time sliceはtimer interruptでマークされる
Kernel schedulerはそのtime slices vector上の
processesをround robin的にCPUを割り当てる
走っているprocessにtimer interrupt毎に、
kernelが通知する(processが自分のtimer
interrupt handlerを持つ)
21
Multiplexing CPU(2)
走っているprocessが自分のtime slice数がなく
なってもCPUを返さなければ、超えたtime slice数
だけを次のroundでもらえなくなる
超えたtime slice数には上限がある。その限界を超え
たらkernelはcontext switchingをする(processがtime
slice数の規則を守ったらkernelはcontext switchしな
くても良い)
ProcessがCPUを返すときに、必要なregisterだけを保
存する(例: FPU stateを保存必要のないprocessは
FPU stateを保存しなくても良い)
ProcessがCPUを要らないときには、yeild(other pid);
system callで自分の残っているtime slices分を譲るこ
とができる
22
Multiplexing CPU(3)
もしprocessが無理なtime slices数を要求したら、
allocate失敗
CPUがたくさん使いたいprocessは大きなtime slices
数を要求する(switching overheadが小さくなる),
interactiveなprocessは小さなtime slices数を何回も
allocateする(応答性が良くなる)
それでもinteractive processの応答性が良いとは限ら
ない!!
どうするか???
23
Multiplexing Physical memory
Allocation:
Protection
ProcessはTLBWrite(); でphysical pageをもらう
Kernelはpage毎にどのapplicationがアクセス権限や
deallocate権限を持つかを記憶
Pageがアクセスされる度に、kernelは権限検査をする
権限がなければ、accessさせない
Deallocation:
Kernelがその権限を変える。Bindingを開放する。
24
Multiplexing Network(1)
Application networking:
Application library は全てのnetworking機能
(TCP, UDP…)を実現する
Protection:
どのapplicationがこのnetwork messageを所
有するか
Exokernel は分からない
そのmessageの意味が分からないからである。
解決法: Dynamic package filtering(DPF)
25
Multiplexing Network(2)
Application networking
26
Dynamic Package Filter(DPF)
LibOS(application)からの小さなfunctionをkernelに
downloadする(code downloading)
そのfunctionは誰がmessageを所有するかを決める
Protection: DPFは特別な言語で書かれ、runtime時に
compileされる。
PDF言語ではmessageの所有権衝突を容易に検出できる
PDF言語は任意のpriviledged instructionを実行させない
27
Multiplexing Disks
LibOS(application) がLibFS(file
system)を作る
1つのLibOSが複数LibFSを持っても良
い
LibFSがfile systemを作る
LibFSがキャッシュ、disk layout,
write order(scheduling)…を制御
する
異なるLibFSが安全に1つのdisk
blockを共有できるようにする
28
Disk protection
Exokernel vs. Microkernel
Microkernel: privileged, 共有できない
Exokernel: non-privileged, 共有できる
29
Disk protection
Block level protection
複数のfile system(FS)にdiskをmultiplexする必要が
あるからである
異なるFSが1つのblockを共有できる
難しい問題:
誰がこのdisk blockを使用できる?
FSが所有しているdisk blockを記憶しているはずので、
kernelも記憶すると無駄
FSのmetadata(file systemの情報)を再利用したい.
しかし、kernelはそのmetadataのformatや意味が分からな
い
解決法: Untrusted Deterministic Functions(UDF)
30
Untrusted Deterministic Functions(UDF)
LibFSはmetadata type毎にinterpreter function “owns”を提供
Correctness:
Ownsは決定的でなければならない(つまり、Ownsは同じ入力で常に同じ出力を出す)
Own 集合が変わる度にInductive testingをする
UDFの使い方:
Owns(metadata) = set of blocks controled by metadata
Proc Initialize(medatada)
If( owns(metadata) != {} ) then error();
Proc Allocate(metadata, b){
old_set = owns(metadata);
<let LibFS changes metadata>
new_set = owns(metadata);
if( new_set != old_set U {b}) then error();
}
DeallocateはAllocateと同様
Kernelはmetadataが分からなくても、信頼することができる
31
全体の内容
1. Abstractions in traditional operating
systems
2. Exokernel overview
3. Exokernel design
4. Exokernel implementation
5. Summary
32
Exokernel implementation
実際にExokernelを実装したシステムがあ
る:
Xok(x86のExokernel), ExOS(LibOS: Unixlike)
Aegis(Exokernel runs on MIPS)
Xok(Exokernel), ExOS:
OpenBSDのlibcを使う
ほとんどのapplicationをOpenBSDからもらう
33
Xok/ExOSの性能
FreeBSDのbinaryの実行時間(秒)
Xok,
OpenBSD,
FreeBSDの
pax, cp, diff,
gcc, gunzip,
rm 各々に同
じデータを入
力する
34
Global performance: Xok/ExOS vs. BSD
Xok, BSDで同じConcurrent applications setを実行
Total time to complete a concurrent tasks: system throughput
35
5. Summary
Exokernel のdesign principlesと
architectureを調べた.
Exokernelでresourceの保護機能と管理機
能を分離することにより、virtual memory,
file system, …はapplication levelで作れ
る
そのため、performanceが良くなる
36
© Copyright 2024 ExpyDoc
