Operating System Lecture 6/6

先週の復習 -- Synchronization

さまざまな同期機構
Transaction
Lock
Dead lock

Unix Operating System では、同期機構としては以下のようなものが用意されている。

lockf
ファイルをロックする標準的な機構
flock, fcntl
歴史的な理由で存在するロック、fcntl は /dev/tty* をlockするのに使う
symbolic link
これらのsystem callが使えない時には、ln を使ってsymbolic linkが作成されたかどうかをチェックすることによってlockを実現することができる
select
複数のstreamからただ一つを選び出す。daemon / server が monitor として機能することをこれにより実現できる
listen, accept
TCP socket 上のselect。複数のTCP socket connection の要求からただ一つを選び出す。 Unix daemon は、これを使う方が普通である。
recv
UDP socket 上のselect。複数のUDP socket connection の要求からただ一つを選び出す。信頼性が保証されてないのが欠点
fork, wait
同期機構としてはかなり限られたものであるが、仕事の待ち合わせには便利
semop
System V の機能。ipcs というprogramで外から制御することができる。あまり使っている人はいない。
msgop
System V の機能。ipcs というprogramで外から制御することができる。あまり使っている人はいない。
thread library
情報実験では新城先生が作った thread library を用いる。これらは、 thread 上での同期機構を提供する。

宿題

情報工学実験Iの6 プロセス間の同期・通信をおこなうこと。この実験は Sun で行います。desgin1 または、 fish1 に rlogin して実験して下さい。レポートはメールで

    Subject: Operating System Lecture 6/6

というように、課題を出した日付をサブジェクトに入れたメールで提出して下さい。しめきりは、2週間後(6/19)とします。既にレポートで提出した人は、そのむね同じサブジェクトのメールで連絡して下さい。

Memory Management

コンピュータにはメモりが付き物である。このメモリは、どのように使われているのだろうか? メモリは、

malloc()
free()

によって要求されたり返されたりする。これは最終的には、sbrk(), brk() という system callを呼び出す。メモリを要求したり返したりしていると、fragmentation (細分化)という問題が起きる。

この状況は最悪、メモリの有効利用度(Memory Utilization)を50%程度にまでさげてしまうことが知られている。

さらにメモリは、OS下の複数のプロセス、ユーザから要求されている。この時に、個々のプロセスでは、あたかも自分一人がCPUとmemoryを専用している下のように見えた方が良い。これは仮想プロセッサと呼ばれるものであった。仮想プロセッサのメモリと実際のメモリを結びつけるには、アドレス変換(Address Translation) という技術を用いる。

この時に、flagmentation を防ぐために、実際のメモリ(Physical memory) は、前もって細分化されて、それの不連続(non-contiguous)な集合が、プロセスのメモリ(Virtual Memory)上での連続なメモリに対応するようになっている。

アドレス変換は、基本的には表引きで行われる。

p は page offset, d はdisplacement, f は frames と呼ばれる。ただし、この表も、64bit/32bit のメモリ空間に対しては、かなり大きくなってしまう。

問1

frame size を2kbyte とした時に、32bit memory spaceで必要なpage table の大きさを求めよ。64bit ではどうか? 一つのpage table entry の大きさは8byteとする。

Multi level page-table scheme

そこで、この変換を2重3重にしておこなう。

問2

32bit address に対して、 3重の変換を行った時に、frame size 2kbyte, p1 のbit幅8とする時に、 p2 のbit 幅はいくつか? この時に必要な page table entry の大きさはいくつか?

この変換は結構 hard ware にとっても重いので、このpage entry を cache するという技術が使われる。これを、TLB (Traslation lookup buffer) という。