OSの講義の8.xの問題を解く

これが正解だぜ(どや)みたいなノリでは書いてないです、ただの平均的な技術力を持っているB2が解いているだけ

課題の取り組みをブログで書いてもいいという許可をもらった上で記事を書いてます

最新の課題内容であることや、答えが正しいかどうかは保証しません

このブログの情報で読者に何らかの不都合が生じても著者は責任は取らないです

8.1 fragmentationを実際に見てみる

このページの問題を解く

malloc(メモリのアロケーション)したときのfragmentation(メモリ内でデータが断片化される現象)を測る課題

コードが2つ用意されている。

malloc_test.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


long MEMORY   = 16000*1000*100;  // test memory limit
long ALLOCATED   = 0;
long COUNT   = 8000;   // repeat count
long ACTIVE  = 1000;   // number of memroy segment
long MAXSIZE = 400000;  // 
long MINSIZE = 400;
long MIN_UNIT = 16 ;

typedef
struct mem_list {
    void *address;
    long size;
    struct mem_list *next;
} MEM_LIST, *MEM_LIST_PTR;


void
print_mem_list(MEM_LIST_PTR m)
{
    MEM_LIST_PTR n;
    if (!m) return;
    n = m->next;
    for(;n&&n!=m;n=n->next) {
       // some malloc returns very large value. remove it to keep output clear
      //     if (n->address && ! (((long)n->address) & 0x700000000000))
         printf("%p 0x%08lx\n",n->address,n->size);
    }
}

void
die(char *msg)
{
    fprintf(stderr,"%s\n",msg);
    exit(0);
}

void
option(long ac, char *av[])
{
    long i = 1;
    while(ac>1) {
    if (av[i][0] == '-') {
        switch (av[i][1]) {
        case 'c': COUNT = atol(av[++i]); break;
        case 'a': ACTIVE = atol(av[++i]); break;
        case 'u': MIN_UNIT = atol(av[++i]); break;
        case 'm': MAXSIZE = atol(av[++i]); break;
        case 'l': MINSIZE = atol(av[++i]); break;
        case 'M': MEMORY = atol(av[++i]); break;
        }
            ac--;
    }
    ac--; i++;
    }
}

int
main(int ac, char *av[])
{
    MEM_LIST mlist;
    MEM_LIST_PTR last = &mlist;
    MEM_LIST_PTR new;
    long i,size;

    option(ac,av);

    mlist.address = NULL;
    mlist.size = 0;
    for(i=0;i<ACTIVE;i++) {
    new = (MEM_LIST_PTR)malloc(sizeof(MEM_LIST)); 
    if (!new) die("malloc error");
    new->address = NULL;
    new->next = NULL;
    last->next = new;
    last = new;
    }
    last->next = &mlist;

    for(i=0;i++<COUNT;last=last->next) {
    size = ((random()%(MAXSIZE-MINSIZE))+MINSIZE)*MIN_UNIT;
    if (last->address) {
            ALLOCATED -= last->size;
            last->size = 0;
        free(last->address);
        last->address = 0;
    }
        if ( ALLOCATED + size > MEMORY) {
             // printf("%ld %ld size error\n",ALLOCATED , size);
             // continue;
        }
    last->size = size;
    last->address = (void *)malloc(size);
    if (!last->address) die("malloc error");
        memset(last->address, random(), size);
        ALLOCATED += size;
    }
    print_mem_list(&mlist);
    return 0;
}

display_js.pl

#!/usr/bin/perl

use strict;

my $width = 1200;
my $step = $width;
my $m_height = 3;
my $base = 0;


# my $malloc_test = "./malloc_test -m 100000 -l 10";
# my $malloc_test = "./malloc_test -m 10000000 -l 10";
my $malloc_test = "ssh amane ./malloc_test -m 10000000 -l 10";
# my $malloc_test = "ssh amane ./malloc_test -m 10000000 -l 10 -u 16";
# my $malloc_test = "ssh amane ./malloc_test -m 1000000 -l 10 -u 16";

open(TEST,"$malloc_test | sort|") or die("Cannot run $malloc_test $!\n");
my ($min,$max);
my @adr;
my @size;

while(<TEST>) {
    chop;
    my ($adr,$size) = split;
    $adr = eval($adr);
    $size = eval($size);
    $min = $adr if ($min==0||$adr<$min);
    $max = $adr if ($adr>$max);
    push(@adr,$adr);
    push(@size,$size);
}

# print "$width $max $min\n";
my $scale = $step/($max-$min);

# print "$scale $width $max $min\n";
# $m->update;
# exit;

my @data;

for(my $i =0; $i<$#adr;$i++) {
    my $adr = ($adr[$i]-$min)*$scale;
    my $size = $size[$i]*$scale;

    my $y = int($adr/$width) * $m_height + $base;
    my $x = int($adr)%$width;

# print STDERR "$adr $size $x $y\n";
    push(@data,  $x,$size );
}

my $xydata = "[" . join(",",@data) ."]";
my $count = int ($#data / 2);

my $js = << "EOFEOF";
<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>D3 World Map</title>
    <script src="https://d3js.org/d3.v4.min.js"></script>
    <style>
        #halfpage{
            background: "white";
            overflow-x: scroll;
        }
    </style>
  </head>
  <body>
  <button type="button" onclick="shrink()" >shrink </button>
  <button type="button" onclick="enlarge()" >enlarge</button>

  <script type="text/javascript">

  var elements = Array.from(Array($count).keys());
  var xydata = $xydata;
  var scale = 1;

  var shrink = function(){
      scale = scale * 0.7 ;
      svgContainer.remove();
      svgUpdate(scale,"green");
  }

  var enlarge = function(){
      scale = scale / 0.7 ;
      svgContainer.remove();
      svgUpdate(scale,"green");
  }

  var svgUpdate = function(scale,color){
     svgContainer = d3.select("body").append("svg")
    .attr("width", 1200 * scale)
    .attr("height", 300)
    .attr("id", "halfpage");

    svgContainer.selectAll("rects1").data(elements).enter().append("rect")
                .attr("width", function(d,i) { return xydata[i*2+1] * scale;} )
                .attr("height", 20)
                .attr("y", 175)
                .attr("x", function(d,i) { return xydata[i*2] * scale; })
                .style("fill", color)
                .style("stroke-width", 1)
                .style("stroke", "black");
  }

   svgUpdate(scale,"green");

    </script>
  </body>
</html>
EOFEOF

print "$js";


# end

さっきのmalloc_test.cのテストファイルを実行したときのfragmentationを可視化したときのhtmlを標準出力で出力するスクリプト

8.2 Page テーブルのGUI demo

このページの問題を解く

[JavaScriptで書いた Page テーブルのGUI demo](https://ie.u-ryukyu.ac.jp/~kono/lecture/os/os08/vm/vm.html) を、もう少し見栄えのするように改良したい。

    わかりやすい表示 (線ぐらいでて欲しいよね?)
    白黒かよ!
    ページテーブルの中身の書き換え(当然...)
    アニメーション
    多段の場合
    仮想記憶が入る場合
    inverted page table

などの改良が考えられる。なんらかの改良をして見よう。

GUIの改善点を見つける

JavaScriptで書いた Page テーブルのGUI demoを見てみよう
改良できそうなことを列挙する
- 矢印を表示していない
- 白黒だけ
- ページテーブルの中身の書き換えしていない
- アニメーションがない
- 多段の場合の表示がない
- 仮想記憶が入る場合がない
矢印を表示していないところを改善することにした

コードを編集して矢印を表示させる

GUIのhtmlファイルをダウンロードする
scriptタグ内にjavascriptのコードが記述されているので実装を見てみる

<script type="application/x-javascript">

var width = 30;
var scale = 2;
var address = 0;
var vmsize = 6;
var psize = 4096;
var pagetableString = "";
var pagetable = new Array(7);

var llow;
var lhigh;
var plow;
var phigh;

for(var i=0;i<vmsize;i++) {
    var v = Math.floor(Math.random()*vmsize);
    pagetable[i] = v;
    pagetableString += v.toString(16) +"\n";
}

function draw() {
    var canvas = document.getElementById("canvas");
    var ctx = canvas.getContext("2d");
    canvas.ontouchmove = TouchXY;

    memory(ctx,10,10);
    memory(ctx,250,10);
    pointer(ctx,80,50);
    pointer(ctx,170,50);
    page(ctx, 130,120);

}

function text(name,text,x,y)
{
    // ctx.fillText(text,x*scale,y*scale);
    var X=document.body.scrollLeft+x*scale;
    var Y=document.body.scrollTop+y*scale;
    document.all[name].style.left=X+20;
    document.all[name].style.top=Y-5;
    document.all[name].innerText=text;
}


function MouseXY()
{
    var x = event.x/scale;
    var y = event.y/1;
    XY(x,y);
}

function TouchXY()
{
    var canvas = document.getElementById("canvas");
    var x =  event.pageX - canvas.offsetLeft;
    var y =  event.pageY - canvas.offsetTop
    XY(x,y);
}

function XY(x,y)
{
    if (10<=x&&x<=110&&10<=y&&y<=310) {
    var canvas = document.getElementById("canvas");
    var ctx = canvas.getContext("2d");
    ctx.clearRect(10,10,10+60,410);
    memory(ctx,10,10);
    ctx.clearRect(250*scale,10,250*scale+60,410);
    memory(ctx,250,10);

    strokeRect(ctx,10,y,10+width,y+2);
        address = (y-10)*100;
        physical = translate(address);
    y = physical/100+10;
    strokeRect(ctx,250,y,250+width,y+2);
    update1();
    }
}

function update1() 
{
    text("Logical","logical address = 0x"+address.toString(16),10,150);
    text("Physical","physical address = 0x"+physical.toString(16),250,150);
    text("Pagetable",pagetableString,130,70);
    text("lhigh",lhigh.toString(16),90,32);
    text("llow",llow.toString(16),120,32);
    text("phigh",phigh.toString(16),90+90,32);
    text("plow",plow.toString(16),120+90,32);
}

function translate(adr)
{
    lhigh = Math.floor(adr/psize);
    llow = adr%psize;
    phigh = pagetable[lhigh];
    plow = llow;
    return phigh*psize+plow;
}

function strokeRect(ctx,x,y,x1,y1)
{
    return ctx.strokeRect(x*scale,y,(x1-x)*scale,(y1-y)*scale);
}

function pointer(ctx,x,y) {
    var dy = 10;
    strokeRect(ctx,x,y,x+width,y+dy);
    x += width;
    strokeRect(ctx,x,y,x+width,y+dy);
}

function memory(ctx,x,y) {
    var dy = 40;
    var dx = 40;

    for(var i=0;i<vmsize-1;i++) {
    strokeRect(ctx,x,y,x+width,y+dy);
    y += dy;
    }
}

function page(ctx,x,y) {
    var dy = 20;
    var dx = 40;

    for(var i=0;i<vmsize-1;i++) {
    strokeRect(ctx,x,y,x+width,y+dy);
    y += dy;
    }
    return box;
}


  </script>

実装を見ると基本的にはXY()関数を編集すればいいことがわかる
矢印を表示させるスクリプトを書けば終了なのだが、味気ないのでChapGPTにコードを生成させてみることにした
以下のような命令をChatGPTに投げる
- javascriptで(fromX, fromY)から(toX, toY)までの矢印をctx上に描画するスクリプトを生成してください
ChatGPTは以下の関数を生成する
- ちなみにまじで生成した関数に対して1ミリも調整や編集することなく課題を解くのに使うことができた

function drawArrow(ctx, fromX, fromY, toX, toY) {
  // 矢印を描画するために必要な変数を計算する
  var headLength = 10;
  var angle = Math.atan2(toY - fromY, toX - fromX);
  // 矢印を描画するために必要な座標を計算する
  var x1 = toX - headLength * Math.cos(angle - Math.PI / 6);
  var y1 = toY - headLength * Math.sin(angle - Math.PI / 6);
  var x2 = toX - headLength * Math.cos(angle + Math.PI / 6);
  var y2 = toY - headLength * Math.sin(angle + Math.PI / 6);
  // 矢印を描画する
  ctx.beginPath();
  ctx.moveTo(fromX, fromY);
  ctx.lineTo(toX, toY);
  ctx.lineTo(x1, y1);
  ctx.moveTo(toX, toY);
  ctx.lineTo(x2, y2);
  ctx.stroke();
}

関数をコピペする
XY()関数を以下のように編集した

function XY(x,y)
{
    if (10<=x&&x<=110&&10<=y&&y<=310) {
        var canvas = document.getElementById("canvas");
        var ctx = canvas.getContext("2d");
        ctx.clearRect(0,0,159,canvas.height);
        ctx.clearRect(0,71,259,canvas.height);
        ctx.clearRect(321,71,canvas.width,canvas.height);
        ctx.clearRect(461,0,canvas.width,canvas.height);
        memory(ctx,10,10);
        memory(ctx,250,10);
        strokeRect(ctx,10,y,10+width,y+2);
        address = (y-10)*100;
        physical = translate(address);
        drawArrow(ctx,85,y+1,150,60);
        drawArrow(ctx,195,75,250,130+(lhigh*20));
        y = physical/100+10;
        drawArrow(ctx,330,130+(lhigh*20),375,75);
        drawArrow(ctx,465,60,495,y+1);
        strokeRect(ctx,250,y,250+width,y+2);
        update1();
    }
}

以上でコードの編集終了、ChatGPT怖すぎる
amaneのホームディレクトリにpublic_htmlというディレクトリを作って(すでにあるなら無視)、その中に8-2というディレクトリを作り、index.htmlというファイルとしてhtmlファイルを置けば
このような感じで改善したGUIを配信できる
- URLはこんなかんじ→https://ie.u-ryukyu.ac.jp/~e205723/8-2/

8.3 Perfomance of Demand Paging

このページの問題を解く

(1) TLB miss してpage が実メモリにあった場合の平均page-falut処理時間が1μ sec, memory access 1.0n sec の時に、page fault rate が、1% の時の effective access time を求めよ。

(2) TLB miss してpage が仮想メモリにあった場合の平均page-falut処理時間が1m sec, memory access 1.0n sec の時に、page fault rate が、0.001% の時の effective access time を求めよ。

(3) 実メモリ上のpage fault rate が、0.001% の時の effective access time を求めよ。性能低下を 20%以下にするためには、page fault rate はいくらでなければならないか。

    effective access time = (1-p) x (memory access time) + p x (page fault time)

この結果を200文字程度に簡潔にまとめよ。

(1)

effective access time = (1-p) x (memory access time) + p x (page fault time)

この式に当てはめる変数の中身は(1)の場合

p=0.01、memory access time=1.0n sec、page fault time=1μ sec = 1000.0n secである

式に代入すると

effective access time = (1 - 0.01) x (1.0n sec) + 0.01 x (1000.0n sec) = 10.99n sec

答えは10.99n sec

(2)

(1)では、TLB miss したときにpage が実メモリにあったが、(2)ではpage が実メモリにある。

そのため、平均page-falut処理時間が(1)では1μ secだったのに対し、(2)では1m sec(1μ secの1000倍)である。

effective access timeを求める式に、p=0.00001、memory access time=1.0n sec、page fault time= 1m sec = 1000000.0n sec`を代入すると

effective access time = (1 - 0.00001) x (1.0n sec) + 0.00001 x (1000000.0n sec) = 10.99999n sec

答えは10.99999n sec

(3)

「実メモリ上のpage fault rate が、0.001% の時」と書かれているので、「TLB miss してpage が実メモリにある」と考える。

effective access timeを求める式に、p=0.00001 、memory access time=1.0n sec、page fault time=1μ sec = 1000.0n secを代入すると

effective access time = (1 - 0.00001) x (1.0n sec) + 0.00001 x (1000.0n sec) = 1.00999n sec

effective access timeは1.00999n secになる。

memory access time=1.0n sec、page fault time=1μ sec = 1000.0n secを固定して、性能低下(率)とpage fault rateの関係を考える。

性能低下率を1 - (effective access time/page fault rate=0のeffective access time)と定義する。

性能低下率が20%(=0.2)以下であることを数式で表現すると、

0.2 >= 1 - {(1-p) x (memory access time) + p x (page fault time)}/memory access timeである

値を代入すると

0.2 >= 1 - {(1-p) x (1.0n sec) + p x (1000.0n sec)}/1.0n sec = -999 x p

となる。

0.2 >= -999 x pという不等式をこねくり回してp <= 2/9990 = 0.0002002002 = 0.02002002%に変形する。

結果、性能低下を20%以下に抑えるには、page fault rateは 0.02002002%以下でなければならないという結論になる。

有効数字とか全然意識せずに端数エグいことになっている計算ですが…ヨシザウルスの愛嬌に免じてということで…

8.4 mlock

このページの問題を解く

8.5 mmap によるコピー

このページの問題を解く

Yoshisaurのメモ

OSの8.xの課題

OSの講義の8.xの問題を解く

8.1 fragmentationを実際に見てみる

8.2 Page テーブルのGUI demo

GUIの改善点を見つける

コードを編集して矢印を表示させる

8.3 Perfomance of Demand Paging

(1)

(2)

(3)

8.4 mlock

8.5 mmap によるコピー