1. 解説 (40 分)
2. グループワーク (30 分)
3. CTF (10 分)
4. グループワーク (10 分)
5. リフレクションシート記入 (10 分)2024-04-12 のものと同じ。
https://lsnl.jp/~ohsaki/lecture/os/2024/#15-1
- C 言語で書かれたプログラムのポインタの値と仮想記憶 (ページング) における仮想アドレスの関係を理解し、他人に説明できるようになる。
- ページ置き換えアルゴリズム FIFO を理解し、その動作をトレースできるようになる。
- ページ置き換えアルゴリズム LRU を理解し、その動作をトレースできるようになる。
- 最適なページ置き換えアルゴリズムがどのようなものかを理解するとともに、その実現がなぜ困難であるかを理解する。
以下のプログラム ex1-1.c および ex1-2.c をコンパイルし、 実行ファイル ex1-1 および ex1-2 を得た。 その後、 64 ビットの OS 上で ex1-1 および ex1-2 を同時に実行したところ以下のような出力が得られた。 ex1-1 の変数 x と ex1-2 の変数 y が同じアドレスに格納されているのはなぜか。
ex1-1.c:
#include <stdio.h>
#include <unistd.h>
int x = 123;
int
main (void)
{
printf ("&x = %p\n", &x);
sleep (60);
}
ex1-2.c:
#include <stdio.h>
#include <unistd.h>
double y = 456.789;
int
main (void)
{
printf ("&y = %p\n", &y);
sleep (60);
}
プログラムの実行
$ ./ex1-1 & ← バックグラウンドで実行
&x = 0x555555558038
$ ./ex1-2 & ← バックグラウンドで実行
&y = 0x555555558038以下のページが順番に参照された時のページフォールト数と、 最終的に主記憶装置に格納されているページの番号をすべて答えよ。 ただし、 ページ置き換えアルゴリズムは FIFO とする。 また、 主記憶に格納できるページ数を 4 とし、 初期状態ではどのページも格納されていない (空の状態である) とする。
0, 2, 1, 3, 5, 4, 6, 3, 7, 4, 7, 3, 3, 5課題 2 において、 ページ置き換えアルゴリズムを LRU とした時の、 ページフォールト数と最終的に主記憶装置に格納されているページの番号をすべて答えよ。
課題 2 において、 最適なページ置き換えアルゴリズムを用いた時のページフォールト数を答えよ。 なお、 ページの参照系列があらかじめ分かっていると仮定してよい。
変数 x や変数 y のアドレスがページングによって実現されている仮想アドレスだから。 プロセスのデータ領域は独立しているため、 変数 x と変数 y は異なるデータ領域に格納されている。 OS によって各プロセスには 64 ビットの仮想空間が提供されている。 変数 x と変数 y は同じ仮想アドレスに格納されているが、 実際には主記憶上の異なる物理アドレスに格納されている。
ページフォールト数 10、 最終的に格納されているページ 7、 6、 5、 3 (順番は入れ替わっても構わない)。
FIFO (First In First Out)
ページフォールト数 9、 最終的に格納されているページ 3、 5、 4、 7 (順番は入れ替わっても構わない)。
LRU
次に参照される予定が最も先であるページを優先してページアウトすればよい。 ページフォールト数 8。
Memory paging
https://en.wikipedia.org/wiki/Memory_paging
In computer operating systems, memory paging (or swapping on some
Unix-like systems) is a memory management scheme by which a
computer stores and retrieves data from secondary storage[a] for
use in main memory.[citation needed] In this scheme, the
operating system retrieves data from secondary storage in
same-size blocks called pages. Paging is an important part of
virtual memory implementations in modern operating systems, using
secondary storage to let programs exceed the size of available
physical memory.
For simplicity, main memory is called "RAM" (an acronym of
random-access memory) and secondary storage is called "disk" (a
shorthand for hard disk drive, drum memory or solid-state drive,
etc.), but as with many aspects of computing, the concepts are
independent of the technology used.
Depending on the memory model, paged memory functionality is
usually hardwired into a CPU/MCU by using a Memory Management
Unit (MMU) or Memory Protection Unit (MPU) and separately enabled
by privileged system code in the operating system's kernel. In
CPUs implementing the x86 instruction set architecture (ISA) for
instance, the memory paging is enabled via the CR0 control
register.
ページング方式
https://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%BC%E3%82%B8%E3%83%B3%E3%82%B0%E6%96%B9%E5%BC%8F
ページング方式 (Paging) とは、コンピュータのオペレーティングシス
テムにおいて記憶装置をページと呼ばれる小さな単位に分割して割り当
てを行うアルゴリズム群である。仮想記憶のベースとなる設計の一つ。
== 「方式」とは「群」である??
===== 「ベース」の意味が不明
=== 「方式」=「群」=「設計の一つ」??
物理メモリ空間および論理メモリ空間を、基本的に一定サイズのページ
と呼ばれる単位に分割して管理を行う。論理メモリから物理メモリ空間
への対応づけはページテーブルと呼ばれる構造体で実現され、この構造
===== 「データ構造」の誤り?
体はオペレーティングシステム (OS) によって管理される。物理メモリ
空間に対応づけられていない論理メモリを参照した時にはページフォル
トという例外によってOS側の例外処理ルーチンに制御が移行し、OS側の
管理によって適宜対応したページを二次記憶等から読み込み、テーブル
== なぜ「等」?? 他に何があるのか??
======= 「管理」によって「読み込む」??
======= なぜ「ページテーブル」ではなく「テーブル」??
を更新してその参照した命令の実行に戻る。
============== 日本語がおかしい。
これを実現するハードウエアであるメモリ管理ユニット (MMU) の中には
=== 「これ」が何を差すか不明。「ページング」であれば実現するのは OS。
トランスレーション・ルックアサイド・バッファ (Translation
Lookaside Buffer:TLB) と呼ばれる一種のキャッシュがあり、ユニット
======== 何を差している?? MMU??
内部ではこの対応表に基づいてメモリアドレスの対応づけを行っている。
== 上では「キャッシュ」、ここでは「表」??
============ 何と何の対応か書かれていない。
このテーブルから参照出来なかったときをTLBミスと呼ぶ。このときの処
================== 意味不明
理はMMUの設計によって異なり、MMU内にはTLBのみを持ちTLBミスが即例
外を起こし、OSがページテーブルを引いてTLBに追加することによって
===== 意味不明
TLBミスを解決するアーキテクチャや、ページテーブル自体のフォーマッ
============ 何のアーキテクチャ?? この日本語だと「処理」の「アーキテクチャ」となって意味不明。
トがOSが使えるビットを含めた形でMMUによって定義されていて、TLBミ
==================================================== 意味不明。書いている人が理解していないと思われる。
ス時にMMU自身が与えられた物理アドレスにあるページテーブルを参照す
るアーキテクチャもある。
================== そもそも「ページング」の本質と関係ない話。他にもっと重要なことがたくさんある。「レポート課題 2024-04-12」と同じ。
https://lsnl.jp/~ohsaki/lecture/os/2024/#10-10
- CTFで出題内容もしくは模範解答に誤りがあった場合、後日修正されたかどうかがCTF内に表示されると嬉しいです。なぜなら貴重な問題なので解けるようになりたいという思いがあったのですが、今回の自習中に正しい答えがわからない状態だったからです。
そうですね。授業後に回答を修正した場合は、CTF のページに掲載するようにします。- 講義ありがとうございました。CTFで自主学習の時に授業内で確認していても後から振り返ったときにCTFの答えが分からなくなるので、自分たちが回答した答えは見えるようにしていただきたいです。
今の CTF は個々のユーザ認証を行っていないので (今の実装だと) 困難です (正解
した人の回答を誰でも見られるような実装だからです)。 技術的にはユーザ認証を追
加するのは困難ではありませんが、今の CTF のほうが単純で美しいと思ってます。
……と思いましたが、「回答済みであっても再度回答できる」ようにすればニーズに
は答えられるような気がしました。- 講義ありがとうございました。
[<17. 8. メモリ管理 (1)] [>19. 10. 入出力 (外部 I/O)]