Abstract

This thesis describes the design of large scale management systems, which is based on abstraction that allows optimization for underlying architecture. The importance of the design was demonstrated by two implementations of different kinds of management system: a parallel scheduling and OS migration.

Recently, management systems cannot deal with overall configurations and conditions because size and complexity of hardware and rapid development of software. The underlying architecture which includes software architecture (e.g., file system, network protocol) is difficult to see from the management systems. It causes inefficient execution, implicit security problems, and frequent administration.

The goal of this thesis is to offer efficient and trustworthy management systems, which balance user requests and current computing resources. The design of management systems must be abstracted so as to balance the simplicity and performance, which take account of the underlying system architecture. Following the design approach, two management systems with different requirement and usage, were developed. One management systems is a process scheduling on massive parallel computers, which achieves quick response of each task and high processor utilization. The other management system deals with migration of operating systems through the Internet, which copes with the problem of software version management. For the former approach, I developed a scheduling which combined space sharing and time sharing. For the latter approach, I developed a framework to distribute bootable disk images through the Internet.

The scheduling which combines space sharing and time sharing offers abstracted parallel computers called slices. Tasks are allocated on a slice with a partitioning algorithm for each architecture. The slices are dispatched to real parallel computers and tasks are processed. The feature of the scheduling is co-existing of tasks among slices. When the area of a task on a slice is free on other slices, the task can sit on these slices in order to attain better processor utilization. Multiple tasks reduce the number of slices and make quick responses. The scheduling was simulated on mesh-connected parallel computers (32×32) with two partitioning algorithms: Adaptive Scan and 2D Buddy. The simulation showed the increase of processor utilization was 38% and 19% on Adaptive Scan and 2D Buddy respectively. The scheduling was implemented on AP/Linux: a parallel operating system for Fujitsu AP1000+. The implementation utilized the Linux local schedulers which were loosely synchronized by hardware clock, and communication library which switched from busy wait to signal wait. It offered moderate co-scheduling and achieved good performance for fine- and coarse-grain processes. It differs from rigid gang scheduling in that it does not promise strict synchronization of a parallel process on all processors. Therefore, the scheduling was supposed to have processor thrashing for fine-grain parallel processes, but it avoided the thrashing problem by controlling all parallel processes with the organized hardware clocks. Conversely, it offered effective processing of coarse-grain parallel processes by overlapping with the communication library which switched from busy wait to signal wait. The co-scheduling skew of the implementation was 2% in a range of co-scheduling period 200ms, which was compensated by the high processor utilization of the scheduling.

The migration of operating system allows us to boot any operating systems without installation on any machine. It is used for bringing back an old OS image or trying a new OS function without side effect. The OS migration is called OS Circular and operating systems are transferred by the network transparent virtual disk called LBCAS (LoopBack Content Addressable Storage). LBCAS reconstructs a virtual disk from abstracted block files which are made from split and compressed block device. The file abstraction make easy to treat. The block file is named by the SHA-1 value of its contents, and the access to the virtual disk is a redirect addressing based on the SHA-1 block files. The same contents blocks are shared by the same SHA1 value and reduce the total volume. The update of application on the LBCAS creates new block files with new SHA-1 file name. The old block files are reserved and make possible to bringing back an old OS image. The new block files are creased for the updated data only, and the saver save the total volume of LBCAS. The integrity of block files is verified with the SHA-1 on a client. The feature makes possible to distribute the block files by un-trusted servers. The downloaded block files are cached on a local storage in order to eliminate redundant download.

The performance of LBCAS was affected by underlying software architectures: the data, access pattern, and the size of block file. The feature was made cleared by the experiment and the optimizations for quick boot were applied. The target operating systems were Windows and Linux, and the LBCAS is optimized by reallocation tool of files system (DiskKeeper and PerfectDisk for Windows and ext2optimizer for Linux). The latency issues in the Internet were optimized by DLAHEAD and DNS-Balance. DLAHEAD downloads necessary block files in advance at boot time. DNS-Balance is the name resolver which uses routing information database and suggests the nearest server for each client. The techniques hid network latency and made possible to distribute the disk image worldwide.

The implementation of two management systems showed that the design compensated the abstraction overhead by allowing optimization for each architecture. The design balances portability and performance on management systems and offers the sophisticated computing environment.

論文要旨

本論文は下位のアーキテクチャの最適化を考慮する抽象化を基とした大規模管理システムについて述べる.この設計の重要性は異なる二種類の管理ステムである並列スケジューリングとOSマイグレーションの実装を通して明らかにする.

近年,管理システムはハードウェアの規模や複雑さ,およびソフトウェアの頻繁な開発のために全体を見渡すことが難しくなっている.下位のアーキテクチャはソフトウェアアーキテクチャ(例えばファイルシステムやネットワークプロトコル)であっても,管理システムから見えにくくなっている.このことは実行の非効率化,セキュリティ問題の潜在化,管理業務の増大化を招いている.

本研究の目標は,ユーザの要求と利用可能な計算資源を考慮した効率的,且つ信頼できる管理システムを提供することである.管理システムの設計は下位のアーキテクチャの最適化を考慮して単純さと効率を両立するように抽象化しなければならない.この設計方針の下,それぞれ異なる利用形態および制約条件を持つ2つの管理システムの開発を行う.一つは大規模並列計算機においてユーザが投入する個々をタスクの応答性を良く,且つ全体の計算機利用率を高く実行するプロセススケジューリングである.もう一つは,ソフトウェアのバージョン管理のためのインターネット経由のOSマイグレーションを扱う.前者ために,空間分割と時間分割を効率的に融合したスケジューリングを開発した.後者のために,起動可能なディスクイメージをインターネット経由で配信するフレームワークを開発した.

空間分割と時間分割を融合したスケジューリングでは,任意の並列計算機を抽象化するsliceを用意し,その上に並列計算機のアーキテクチャを考慮したパーティショニングアルゴリズムでタスクを割り当てる.sliceは実並列計算機に割り当てられてタスクの処理を進める.このスケジューリングではスライス間に共存するタスク管理を特徴とする.あるsliceでタスクが占有している領域を別のsliceで未使用の場合,そのタスクを複数のsliceに配置することによりプロセッサ利用率の向上を計る.多重タスクはslice数の削減を行い,素早い応答性を可能にする.このスケジューリングは2つのパーティショニングアルゴリズムAdaptive Scanと2D Buddyを対象に,メッシュ結合並列計算機(32×32)でシミュレーションを行った.シミュレーションはプロセッサ利用率の向上がAdaptive Scan と2D Buddyでそれぞれ38%および19%であることを示した.

提案したスケジューリングは実計算機 AP1000+ のオペレーティングシステムであるAP/Linuxに組込まれた.実装においては各プロセッシングエレメント上の物理時計に緩やかに同期する Linux のローカルスケジューラとbusy wait から signal waitに切り替わる通信ライブラリを活用した.この方式はfine及びcoarse-grainの並列プロセスを効率的に実行する緩やかな co-schedulingを提供した.本方式は厳格なプロセス同期を要求するギャングスケジューリングと異なり,並列プロセスが同時に実行されていることを保証しない.このため頻繁な通信を行なう fine-grain 並列プロセスの場合,プロセッサスラッシングが予想されるが,一元管理された物理時計による全並列プロセスを管理することで解決できた.また, coarse grain 並列プロセスも一定時間で busy wait を signal waitに切り替える通信ライブラリを併用することで並列プロセスをオーバーラップさせ,効率的に処理できた.co-schedulingの周期を200msとした場合,co-scheduling skew が2%程度であったが,これはスケジューリングのプロセッサ利用率の向上により十分に打消される範囲であった.

OSマイグレーションは任意のマシン上でインターネットからインストールなしでOSを利用可能する.この機能により,古いOSイメージへのロールバックや新しいOSの新機能を副作用なしで確認することを可能にする.このOSマイグレーションをOS Circularと呼び,OSはLBCAS (LoopBack Content Addressable Storage)と呼ぶネットワーク透過な仮想ディスクにより転送される.LBCASはブロックデバイスを分割圧縮して作られた抽象化ブロックファイルから仮想ディスクを再構築する.ファイルによる抽象化は取扱いを簡単にする.ブロックファイルはその内容のSHA-1値をファイル名とし,仮想ディスクへのアクセスはSHA-1ブロックファイルによる間接アドレスシングとなる.同一内容のブロックファイルは同一SHA-1値で共有され,総容量を削減する.LBCASでのソフトウェア更新では新しいSHA-1値のブロックファイルを追加することになる.古いブロックファイルはそのまま保存され,古いOSイメージへロールバックを可能とする.また,新しいブロックファイルは変更のあったデータのみに対して作られるため,サーバの総容量を減らすことができる.クライアントではSHA-1によるコンテンツの完全性を検証する.この性質は信頼できないサーバからの配信も可能にする.ダウンロードしたブロックファイルは不用なダウンロードを抑制するため手元の二次記憶にキャッシュされる.

LBCAS性能は,収録するデータ,アクセスパターン,および分割サイズなどの下位のソフトウェアーキテクチャによって影響される.この特徴は実験により明らかにし,高速な起動のための最適化を行った.起動するOSはWindowsとLinuxとし,ファイルシステムのブロック再配置ツール(WindowsではDiskKeeperとPerfectDisk,Linuxではext2optimizer)を利用してLBCASを最適化した.インターネットのレイテンシはDLAHEADとDNS-Balanceにより最適化された.DLAHEADは必要なブロックファイルを先行ダウンロードする.DNS-Balanceはルーティング情報データベースに基づくネームサーバであり,各クライアントに対して近接のサーバを導く.これらの技術はネットワークの遅延を隠蔽し,世界規模のディスクイメージ配信を可能とした.

2つの管理システムの実装を通して,設計が各アーキテクチャに対する最適を考慮することで抽象化のオーバーヘッドを打ち消すことを示した.この設計が管理システムの汎用化と効率のバランスを取り,洗練された計算環境を提供することができた.

OSなどの管理システムは、ハードウェアの大規模化やソフトウェアの頻繁な開発のため、その全体を見渡すことが難しくなっている。これは、下位レベルのアーキテクチャと管理システムが想定する抽象化の不一致に起因することが多く、実行の非効率化、管理業務の増大化などを招いていると考えられる。本学位請求論文は、下位レベルのアーキテクチャにおける最適化を考慮した抽象化に基づき、筆者が設計・開発したi) プロセススケジューリングおよびii) OSマイグレーション(インターネットから起動可能なOS)という二つの管理システムの機構を説明し、それらの新規性と有用性を示すものである。

本論文の第1章では研究の動機と背景、目標、既存の研究との違い、および博士論文による貢献が概説されている。

第2章では、メッシュ結合型の並列計算機を想定し、空間分割と時間分割を効率的に融合したスケジューリング方式の開発が述べられ、この開発が下位のアーキテクチャの最適化を考慮した適切な抽象化に基づき、効率的で汎用的なスケジューリングを実現したことを示している。ここでの適切な抽象化とはsliceと呼ばれる時間分割のための並列計算機の抽象化を意味し、slice上に実行すべきタスク群が空間分割アルゴリズムにより並列計算機アーキテクチャを考慮して割り当てられる。必要に応じてsliceは複数生成され、ラウンドロビンで実計算機に割り当てて処理することで、タスクの割り当て待ちを回避し、応答性を向上させる。タスク群は空間分割アルゴリズムによりスライス内に効率的に割り当て場所が決められ、一定のプロセッサ利用率が達成される。本方式ではさらに複数のスライスを用いてプロセッサの有効利用を図っている。タスクが占有するプロセッサ群の配置はタスク終了するまで変わることがないが、その配置場所が他のスライスで使われていなければ、そのタスクを複数のスライス上で存在させ、処理を進めることを許す。この機能によりタスクの応答性が向上するばかりでなく、全スライスを考慮したとき、より高いプロセッサ利用率を達成できる。

本スケジューリング方式の性能評価はシミュレータを用いて行われ、それにより応答性の良さとプロセッサ利用率の高さを両立することが示された。さらに、実際の並列計算機(富士通製AP1000+)にこの方式を適用しその実用性を示した。

第3章では、OSのバージョン管理の手間の問題を解決するために、各ユーザがInternetからインストールなしに直接OSが起動できるOS Circularを提案し、その実現としてネットワーク透過なブロックデバイスLBCAS(LoopBack Content Addressable Storage)方式を開発して、どのようなOSでも仮想計算機上に起動可能であることを示した。LBCASは、ブロックをファイルとして抽象化し管理するLoopBackと、ブロックの内容のSHA-1値よる間接アドレスシングを行うCAS (Content Addressable Storage)を組み合わせたものである。これにより、ファイルという抽象化による管理の容易さおよび、同一内容のブロックは同一SHA-1値で共有されため容量削減の効果が得られる。

OS Circularの設計・開発では、転送されるOSイメージは、ファイルレベルの抽象化ではなく、それより下位のブロックレベルの抽象化により扱われ、任意のOSを扱うとことができた。また、ブロックレベルの抽象化により、任意のファイルシステムでの最適化も可能となった。論文ではLBCASシステムの基本性能を測定し、キャシュの有効性やネットワークレイテンシを考慮した最適なブロックサイズなども確定している。

開発されたOS Circular は世界で広く公開されている。2つのLinuxディストリビューション(Ubuntu とDebian)を毎週更新しており、ネットワーク起動で最新のものが利用できるようになっている。アクセスも大変多く、実証実験では北米の3サイト、欧米に3サイト、国内に7サイトを用意し、近隣のサーバを見つけるDNS-Balanceによりレイテンシを隠蔽した世界規模の配信も可能であることを確認している。

第4章でおいて全体のまとめと将来の研究方向を示されている。

以上をまとめると、下位レベルのアーキテクチャにおける最適化を考慮した適切な抽象化が管理システムの設計・実現方針として重要であるのと認識のもとに、空間分割と時間分割を効率的に融合したスケジューリング、および起動可能なディスクイメージをInternet経由で配信する新規性と有用性の高い技術を開発した。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。