livaの雑記帳

OSDI 2010〜2018の中で個人的に面白かった論文を雑に一言づつ紹介

システム系のトップ学会の一つである、OSDI (USENIX Symposium on Operating Systems Design and Implementation)の論文を2010年まで一通り眺めてみたので、その中で個人的に面白かった物をまとめてみる。

 

一通り眺めたといっても、全て読んだわけではないので、見逃してる論文もたぶんある。あと、英語力低くて趣旨を取り違えてる論文もあると思うけど、寛大な心で見逃してもらえると有り難いです。

(こういう系の話、少し間違えると「おめーここ間違ってるじゃねーか!」ってマサカリが飛んでくる印象があって、あんまり書きたくないんですよね)

 

2018

LegoOS: A Disseminated, Distributed OS for Hardware Resource Disaggregation

https://www.usenix.org/conference/osdi18/presentation/shan

一つのマシンに全てのI/Oを積むのは辛い(PCIeレーン足りなかったり)、データセンター内の隣のマシンのI/Oを透過的に参照できると嬉しい。

それを実現するためのOSの抽象化モデルを提案、実装した論文。抽象化の際は、GPU、ストレージ、メモリ、CPUといった各リソースをコンポーネント単位に分割して(メモリとCPUも分割してる!)、コンポーネント間がネットワーク越しに通信する事で、リソースの柔軟な運用を可能にした。


Arachne: Core-Aware Thread Management

https://www.usenix.org/conference/osdi18/presentation/qin

アプリケーションにはスループット指向の物、レイテンシ指向の物等様々な物が存在するが、大前提としてOSはアプリの事が分からないので、例えばアプリがどれだけのCPUコアリソースを必要とするか分からない。
そこで、CPUコアリソースの調停者を作り、調停者と協調するアプリケーションは調停者管理下のコアで専有的に1コア1カーネルスレッドで動作できるようにした。管理外のコアでは既存のアプリケーションが従来の仕組みで動作する他、管理対象のコアは動的に増減可能。
調停者はユーザーランドで動くので、Linuxに変更を加える必要もなし。


wPerf: Generic Off-CPU Analysis to Identify Bottleneck Waiting Events

https://www.usenix.org/conference/osdi18/presentation/zhou

マルチスレッドアプリケーションでは、CPUの使用率が低いにも関わらずスループットが出ない、という事例が存在する。分かりやすく書くと、ボトルネックとなるスレッドがI/O待ち等でブロックしてサボってる(最適化すればより多くの処理をできるはずなのに、やってない)みたいなケースが該当する。既存の性能解析ツールでは「一番ヒマしている」スレッドを見つける事はできるが、必ずしもそれが実際のボトルネックのスレッドとは限らないので、こういう事例の解析は難しい。
これを解決するため、スレッド間の依存関係のグラフ解析等をする、新しい性能解析ツールを作った。

※1. 問題設定が面白いと思ったが、解決手法までは興味が無かったので、その辺は割愛

※2. SOSP2017でこれの前段の研究が出てる。見逃してた。これから読む。

 

 

2016

Machine-Aware Atomic Broadcast Trees for Multicores

 

https://www.usenix.org/conference/osdi14/technical-sessions/presentation/zellweger

コア間の通信コストはコア間インターコネクトやメモリの構成によって大きくばらつく。(コアAとコアBの通信コストと、コアAとコアCの通信コストが異なる事は良くある。分かりやすい例だと、AとBが同じNUMAノード内に属していて、AとCが異なるNUMAノードに属している場合とか)なので、データをブロードキャストする場合、NUMA越しの通信は極力少なくするなどといった最適化が必要になる。しかし、このような最適化はアーキテクチャ固有であるため、これまでの全てのCPUへの対応に加え、新しい世代のCPUが出る度に再度チューニングする必要があり、最適化コストが非現実的なレベルで高い。
そこで、CPUのスペックシート情報、スペックシートには乗ってない細かいデータを取るためのマイクロベンチマーク、そしてヒューリスティックな最適化を行う事で、自動的に最適なブロードキャスト順序を生成するアルゴリズムを開発した。


2014

Arrakis: The Operating System is the Control Plane

https://www.usenix.org/conference/osdi14/technical-sessions/presentation/peter

OSによるI/Oの仲介は、ネットワーク通信を始めとした広帯域、低遅延I/Oに追いつけなくなりつつあるので、もうカーネルがI/Oデータ処理のルーティングをするのを諦め(?)て、ハードウェアに任せちゃいましょうよ、という話。

このOSでは、アプリケーションが広帯域I/Oデバイスを直に触れるようにした。デバイスはI/O仮想化によって隔離されているので、アプリケーションが直にデバイスを触ってもシステムに影響を及ぼす事は無い。デバイスドライバや、プロトコルスタック層は、アプリケーションにリンクされるライブラリ(ライブラリOS)によって提供される。これによってOSはI/Oデータ処理から解放(遅いI/Oについては引き続きOSが仲裁するものの)され、デバイスのアクセス権やリソース制限といった管理業務のみを行うようになる、というのが提案されているモデルである。

 

Decoupling Cores, Kernels, and Operating Systems

https://www.usenix.org/conference/osdi14/technical-sessions/presentation/zellweger

今後ヘテロジニアスメニーコアアーキテクチャの普及が予想されるが、そのようなアーキテクチャでは電源効率のため、一部のコアを「頻繁に」動的にon/offする事になると考えられる。しかし、既存のアーキテクチャは、コアの動的なon/offを高速に行う事を想定していない。

そこで、コア単位のOSのステート、及びアプリケーションのステートをカーネルから分離したOSモデルを提案した。これによりコアの動的なon/offを高速に行えるようになった他、その応用として、カーネルのライブアップデートや、それまで動いてたカーネルをより低消費電力なコア上でマイグレーションする事を可能にした。

 

2012

Dune: Safe User-level Access to Privileged CPU Features

https://www.usenix.org/conference/osdi12/technical-sessions/presentation/belay

今のアプリケーションはRing3で動くが、Ring0上で動けるようになるとハードウェアを直接制御できるので嬉しい。具体的には、ガーベージコレクションの際にページのdirty bitを直接参照できるのでどのメモリを回収すべきか(回収しないべきか)を高速に判断できるとか、web browserやモバイルアプリケーションといった、untrustedなコードをsandbox上で走らせたい場合にring3上で走らせれば良いだけなので低オーバーヘッドになる、等である。

そこでVt-xを用いてプロセスをアイソレーションするLinuxカーネルモジュールを開発した。プロセスはRing0で動き、システムコール呼び出し時はsyscallでは無く、vmcallを用いてRing -1のLinuxを呼び出す。Linuxカーネルへの変更は不要で、かつアプリケーションもライブラリをリンクしてdune_init()を呼び出すコードを追加するだけなので、ほぼ無変更で適用可能。(標準libcだとシステムコールを呼び出す際にsyscallを経由した後vmcallを呼ぶ事になるので、syscallを省略したければ改造版libcを再コンパイルする必要あり)


2010

An Analysis of Linux Scalability to Many Cores

https://www.usenix.org/conference/osdi10/analysis-linux-scalability-many-cores

2008年、2009年と「メニーコアでOSをスケールさせるためにはカーネルの設計を大きく変えるべきだ!」的な論文が盛り上がっていたが、「いや、別にLinuxもちゃんと同期周りをきちんと改善すればスケールするでしょ、はい解散」と言った論文。

メニーコアだとスピンロックのコストが高すぎるので、できるだけコア毎の構造に分割し、ロックを取らないようにするとか、リファレンスカウンタの厳密性を緩和して同期コストを下げるとか、ボトルネックとなっている細かい同期コストを修正していきましたよ、という話

FlexSC: Flexible System Call Scheduling with Exception-Less System Calls

https://www.usenix.org/conference/osdi10/flexsc-flexible-system-call-scheduling-exception-less-system-calls

システムコールを頻繁に呼び出すのはアプリケーションの性能低下の原因になるため、システムコールの呼び出し回数を減らしたい。システムコールのコストが高いのに加え、キャッシュを汚染してしまうためにアプリケーションコードそれ自体のIPCも低下するからである。

そこで、システムコール処理をバッチする(システムコールが呼び出された瞬間はsyscall()を発行せず、バッファに呼び出し情報を記載しておく)事を提案した。これは同期的なシステムコールを、インターフェースを変える事無く非同期的(aio的な)に扱う事を意味する。また、pthread互換なM:Nスレッドモデルのスレッドライブラリを実装した。このスレッドライブラリのユーザースレッドのスケジューリングは、ユーザースレッドがシステムコールを発行したら次のスレッドに切り替える事を繰り返し、実行できるユーザースレッドがなくなった時点でカーネル空間に遷移、まとめてシステムコールを実行する、という物である。

更に、システムコールバッチ処理する事により、システムコールを処理するコアとシステムコールを呼び出すコアを分離する事ができる。(システムコールは割り込みでは無く、コア間の通信となる)これにより、システムコール処理専用コア、アプリケーションロジック処理専用コアという分離が可能になり、キャッシュのヒット率も向上する上にカーネル空間とユーザー空間の遷移コストも削減できる。

おまけ:satさんイチオシ(かどうかは知らない)

 

 

宣伝

ここに書かれている内容に興味がある方、「もっと良いアイディアで問題解決をしたい!」と思う方は、東京大学大学院情報理工学系研究科コンピュータ科学専攻加藤研究室東京大学情報基盤センター品川研究室(情報理工システム情報学専攻と兼担)がオススメです。
これはあまり一般には知られてない情報なんですが、大学院からだと比較的入りやすいらしいですよ?