/*
 * virtual_address_translation.c
 *
 * 仮想アドレスを VPN とオフセットに分解し、
 * 簡易ページテーブルを用いて物理アドレスに変換するシミュレーション。
 *
 * コンパイル: gcc -Wall -o vat virtual_address_translation.c
 * 実行: ./vat
 */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
 
#define PAGE_SIZE       4096        /* 4KB = 2^12 */
#define PAGE_SHIFT      12          /* log2(PAGE_SIZE) */
#define NUM_PAGES       (1 << 20)   /* 2^20 = 1M ページ (32bit) */
#define PT_SIZE         1024        /* シミュレーション用の小さなテーブル */
 
/* ページテーブルエントリの制御ビット */
#define PTE_PRESENT     (1 << 0)
#define PTE_WRITABLE    (1 << 1)
#define PTE_USER        (1 << 2)
#define PTE_ACCESSED    (1 << 3)
#define PTE_DIRTY       (1 << 4)
 
typedef struct {
    uint32_t entry;  /* PFN (上位20ビット) + フラグ (下位12ビット) */
} PageTableEntry;
 
typedef struct {
    PageTableEntry entries[PT_SIZE];
    int num_entries;
} PageTable;
 
/* PTE からフレーム番号を取得 */
static inline uint32_t pte_get_pfn(PageTableEntry pte) {
    return pte.entry >> PAGE_SHIFT;
}
 
/* PTE にフレーム番号とフラグを設定 */
static inline PageTableEntry pte_make(uint32_t pfn, uint32_t flags) {
    PageTableEntry pte;
    pte.entry = (pfn << PAGE_SHIFT) | (flags & 0xFFF);
    return pte;
}
 
/* PTE のフラグを確認 */
static inline int pte_is_present(PageTableEntry pte) {
    return pte.entry & PTE_PRESENT;
}
 
/* ページテーブルの初期化 */
void page_table_init(PageTable *pt) {
    memset(pt->entries, 0, sizeof(pt->entries));
    pt->num_entries = PT_SIZE;
}
 
/* マッピングの追加 */
void page_table_map(PageTable *pt, uint32_t vpn, uint32_t pfn, uint32_t flags) {
    if (vpn >= (uint32_t)pt->num_entries) {
        fprintf(stderr, "Error: VPN %u exceeds page table size\n", vpn);
        return;
    }
    pt->entries[vpn] = pte_make(pfn, flags | PTE_PRESENT);
    printf("  Mapped: VPN 0x%05X -> PFN 0x%05X (flags: ", vpn, pfn);
    if (flags & PTE_WRITABLE) printf("W ");
    if (flags & PTE_USER)     printf("U ");
    printf(")\n");
}
 
/* 仮想アドレスの変換 */
int translate_address(PageTable *pt, uint32_t virtual_addr,
                      uint32_t *physical_addr) {
    uint32_t vpn    = virtual_addr >> PAGE_SHIFT;
    uint32_t offset = virtual_addr & (PAGE_SIZE - 1);
 
    printf("\n--- Address Translation ---\n");
    printf("Virtual Address : 0x%08X\n", virtual_addr);
    printf("  VPN           : 0x%05X (page %u)\n", vpn, vpn);
    printf("  Offset        : 0x%03X (%u bytes)\n", offset, offset);
 
    if (vpn >= (uint32_t)pt->num_entries) {
        printf("  Result        : FAULT (VPN out of range)\n");
        return -1;
    }
 
    PageTableEntry pte = pt->entries[vpn];
    if (!pte_is_present(pte)) {
        printf("  Result        : PAGE FAULT (page not present)\n");
        return -1;
    }
 
    uint32_t pfn = pte_get_pfn(pte);
    *physical_addr = (pfn << PAGE_SHIFT) | offset;
 
    /* Accessed ビットをセット（ハードウェアが行う処理を模倣） */
    pt->entries[vpn].entry |= PTE_ACCESSED;
 
    printf("  PFN           : 0x%05X (frame %u)\n", pfn, pfn);
    printf("  Physical Addr : 0x%08X\n", *physical_addr);
    printf("  Result        : SUCCESS\n");
    return 0;
}
 
int main(void) {
    PageTable pt;
    page_table_init(&pt);
 
    printf("=== Page Table Setup ===\n");
    page_table_map(&pt, 0x00000, 0x00005, PTE_WRITABLE | PTE_USER);
    page_table_map(&pt, 0x00001, 0x00003, PTE_WRITABLE | PTE_USER);
    page_table_map(&pt, 0x00002, 0x0000B, PTE_USER);  /* 読み取り専用 */
    page_table_map(&pt, 0x00010, 0x0007B, PTE_WRITABLE | PTE_USER);
 
    uint32_t pa;
 
    /* 正常な変換 */
    translate_address(&pt, 0x00000A7C, &pa);  /* VPN=0, offset=0xA7C */
    translate_address(&pt, 0x00001500, &pa);  /* VPN=1, offset=0x500 */
    translate_address(&pt, 0x00010FF0, &pa);  /* VPN=0x10, offset=0xFF0 */
 
    /* ページフォルト: マッピングされていないページ */
    translate_address(&pt, 0x00003000, &pa);  /* VPN=3, マッピングなし */
 
    /* ページフォルト: 範囲外 */
    translate_address(&pt, 0xFFFFF000, &pa);
 
    return 0;
}

"""
lru_page_replacement.py
 
LRU (Least Recently Used) ページ置換アルゴリズムのシミュレーション。
ページ参照列に対するページフォルト回数を計算し、
各ステップのフレーム状態を可視化する。
 
実行: python3 lru_page_replacement.py
"""
 
from collections import OrderedDict
from typing import List, Tuple
 
 
class LRUPageReplacer:
    """LRU ページ置換アルゴリズムの実装。
 
    OrderedDict を使用して、アクセス順序を効率的に管理する。
    最も最近アクセスされたページが末尾、最も古いページが先頭に位置する。
    """
 
    def __init__(self, num_frames: int):
        """
        Args:
            num_frames: 利用可能な物理フレーム数
        """
        if num_frames <= 0:
            raise ValueError("フレーム数は正の整数でなければならない")
        self.num_frames = num_frames
        self.frames: OrderedDict[int, bool] = OrderedDict()
        self.page_faults = 0
        self.history: List[Tuple[int, list, bool]] = []
 
    def access_page(self, page: int) -> bool:
        """ページにアクセスする。
 
        Args:
            page: アクセスするページ番号
 
        Returns:
            True: ページフォルトが発生した場合
            False: ページが既にフレーム内にあった場合 (ヒット)
        """
        fault = False
 
        if page in self.frames:
            # ヒット: ページを末尾（最新）に移動
            self.frames.move_to_end(page)
        else:
            # ミス: ページフォルト
            fault = True
            self.page_faults += 1
 
            if len(self.frames) >= self.num_frames:
                # フレームが満杯 → LRU ページ（先頭）を追い出す
                evicted_page, _ = self.frames.popitem(last=False)
 
            # 新しいページを末尾に追加
            self.frames[page] = True
 
        # 状態を履歴に記録
        self.history.append((page, list(self.frames.keys()), fault))
        return fault
 
    def simulate(self, reference_string: List[int]) -> int:
        """ページ参照列全体をシミュレーションする。
 
        Args:
            reference_string: ページ参照列
 
        Returns:
            総ページフォルト回数
        """
        for page in reference_string:
            self.access_page(page)
        return self.page_faults
 
    def print_trace(self) -> None:
        """シミュレーションのトレースを表示する。"""
        print(f"\n{'='*60}")
        print(f"LRU Page Replacement Simulation (Frames: {self.num_frames})")
        print(f"{'='*60}")
        print(f"{'Step':>4} | {'Page':>4} | {'Frames':<25} | {'Result'}")
        print(f"{'-'*4:>4}-+-{'-'*4:>4}-+-{'-'*25:<25}-+-{'-'*10}")
 
        for i, (page, frames, fault) in enumerate(self.history):
            frames_str = str(frames)
            result = "FAULT" if fault else "HIT"
            print(f"{i+1:>4} | {page:>4} | {frames_str:<25} | {result}")
 
        print(f"\nTotal page faults: {self.page_faults}")
        hit_count = len(self.history) - self.page_faults
        hit_rate = hit_count / len(self.history) * 100 if self.history else 0
        print(f"Hit rate: {hit_rate:.1f}%")
 
 
def compare_algorithms(reference_string: List[int],
                       num_frames: int) -> None:
    """FIFO と LRU を比較する。"""
 
    # --- FIFO ---
    from collections import deque
    fifo_frames: deque = deque()
    fifo_set: set = set()
    fifo_faults = 0
    for page in reference_string:
        if page not in fifo_set:
            fifo_faults += 1
            if len(fifo_frames) >= num_frames:
                old = fifo_frames.popleft()
                fifo_set.discard(old)
            fifo_frames.append(page)
            fifo_set.add(page)
 
    # --- LRU ---
    lru = LRUPageReplacer(num_frames)
    lru_faults = lru.simulate(reference_string)
 
    # --- OPT ---
    opt_faults = 0
    opt_frames: list = []
    for i, page in enumerate(reference_string):
        if page not in opt_frames:
            opt_faults += 1
            if len(opt_frames) >= num_frames:
                # 将来最も遅く参照されるページを探す
                farthest = -1
                victim = -1
                for f in opt_frames:
                    try:
                        next_use = reference_string[i+1:].index(f)
                    except ValueError:
                        next_use = float('inf')
                    if next_use > farthest:
                        farthest = next_use
                        victim = f
                opt_frames.remove(victim)
            opt_frames.append(page)
 
    print(f"\n{'='*50}")
    print(f"Algorithm Comparison (Frames: {num_frames})")
    print(f"Reference String: {reference_string}")
    print(f"{'='*50}")
    print(f"{'Algorithm':<12} | {'Page Faults':>12} | {'Hit Rate':>10}")
    print(f"{'-'*12}-+-{'-'*12:>12}-+-{'-'*10}")
    total = len(reference_string)
    print(f"{'OPT':<12} | {opt_faults:>12} | "
          f"{(total-opt_faults)/total*100:>9.1f}%")
    print(f"{'LRU':<12} | {lru_faults:>12} | "
          f"{(total-lru_faults)/total*100:>9.1f}%")
    print(f"{'FIFO':<12} | {fifo_faults:>12} | "
          f"{(total-fifo_faults)/total*100:>9.1f}%")
 
 
if __name__ == "__main__":
    # 教科書的な参照列
    ref_string = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
 
    lru = LRUPageReplacer(num_frames=3)
    lru.simulate(ref_string)
    lru.print_trace()
 
    compare_algorithms(ref_string, num_frames=3)
    compare_algorithms(ref_string, num_frames=4)

/*
 * clock_algorithm.c
 *
 * Clock (Second-Chance) ページ置換アルゴリズムの実装。
 * 円形バッファとリファレンスビットを使用して LRU を近似する。
 *
 * コンパイル: gcc -Wall -o clock clock_algorithm.c
 * 実行: ./clock
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MAX_FRAMES 64
 
typedef struct {
    int page_number;    /* ページ番号 (-1 = 空) */
    int reference_bit;  /* 参照ビット (Accessed ビットに相当) */
    int dirty_bit;      /* 変更ビット */
} Frame;
 
typedef struct {
    Frame frames[MAX_FRAMES];
    int num_frames;
    int hand;           /* 時計の針 (次に検査するフレームのインデックス) */
    int used_frames;    /* 現在使用中のフレーム数 */
    int page_faults;
    int writes_back;    /* ディスクへの書き戻し回数 */
} ClockReplacer;
 
void clock_init(ClockReplacer *cr, int num_frames) {
    if (num_frames > MAX_FRAMES) {
        fprintf(stderr, "Error: num_frames exceeds MAX_FRAMES\n");
        exit(1);
    }
    cr->num_frames = num_frames;
    cr->hand = 0;
    cr->used_frames = 0;
    cr->page_faults = 0;
    cr->writes_back = 0;
    for (int i = 0; i < num_frames; i++) {
        cr->frames[i].page_number = -1;
        cr->frames[i].reference_bit = 0;
        cr->frames[i].dirty_bit = 0;
    }
}
 
/* フレーム内にページが存在するか検索 */
int clock_find_page(ClockReplacer *cr, int page) {
    for (int i = 0; i < cr->num_frames; i++) {
        if (cr->frames[i].page_number == page) {
            return i;
        }
    }
    return -1;
}
 
/* ページアクセス処理 */
int clock_access(ClockReplacer *cr, int page, int is_write) {
    int idx = clock_find_page(cr, page);
 
    if (idx >= 0) {
        /* ヒット: 参照ビットを 1 にセット */
        cr->frames[idx].reference_bit = 1;
        if (is_write) {
            cr->frames[idx].dirty_bit = 1;
        }
        return 0; /* ページフォルトなし */
    }
 
    /* ページフォルト */
    cr->page_faults++;
 
    if (cr->used_frames < cr->num_frames) {
        /* 空きフレームがある場合 */
        for (int i = 0; i < cr->num_frames; i++) {
            if (cr->frames[i].page_number == -1) {
                cr->frames[i].page_number = page;
                cr->frames[i].reference_bit = 1;
                cr->frames[i].dirty_bit = is_write ? 1 : 0;
                cr->used_frames++;
                return 1;
            }
        }
    }
 
    /* Clock アルゴリズムで置換対象を選択 */
    while (1) {
        if (cr->frames[cr->hand].reference_bit == 0) {
            /* 置換対象が見つかった */
            int evicted = cr->frames[cr->hand].page_number;
            if (cr->frames[cr->hand].dirty_bit) {
                cr->writes_back++;
                printf("    [Write-back] Page %d written to disk\n", evicted);
            }
 
            cr->frames[cr->hand].page_number = page;
            cr->frames[cr->hand].reference_bit = 1;
            cr->frames[cr->hand].dirty_bit = is_write ? 1 : 0;
 
            printf("    [Evict] Page %d replaced by Page %d at Frame %d\n",
                   evicted, page, cr->hand);
 
            cr->hand = (cr->hand + 1) % cr->num_frames;
            return 1;
        }
        /* Second Chance: 参照ビットをクリアして次へ */
        cr->frames[cr->hand].reference_bit = 0;
        cr->hand = (cr->hand + 1) % cr->num_frames;
    }
}
 
/* フレームの状態を表示 */
void clock_print_state(ClockReplacer *cr) {
    printf("  Frames: [");
    for (int i = 0; i < cr->num_frames; i++) {
        if (i > 0) printf(", ");
        if (cr->frames[i].page_number == -1) {
            printf("  -  ");
        } else {
            printf("P%d(%c%c)", cr->frames[i].page_number,
                   cr->frames[i].reference_bit ? 'R' : '-',
                   cr->frames[i].dirty_bit ? 'D' : '-');
        }
    }
    printf("]  Hand→%d\n", cr->hand);
}
 
int main(void) {
    ClockReplacer cr;
    clock_init(&cr, 4);
 
    /* ページ参照列: (ページ番号, 書き込みかどうか) */
    int refs[] =    {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
    int writes[] =  {0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0};
    int n = sizeof(refs) / sizeof(refs[0]);
 
    printf("=== Clock (Second-Chance) Algorithm ===\n");
    printf("Frames: 4, Reference String Length: %d\n\n", n);
 
    for (int i = 0; i < n; i++) {
        int fault = clock_access(&cr, refs[i], writes[i]);
        printf("Step %2d: Access Page %d (%s) -> %s\n",
               i + 1, refs[i],
               writes[i] ? "WRITE" : "READ",
               fault ? "FAULT" : "HIT");
        clock_print_state(&cr);
        printf("\n");
    }
 
    printf("=== Summary ===\n");
    printf("Total page faults : %d\n", cr.page_faults);
    printf("Total write-backs : %d\n", cr.writes_back);
    printf("Hit rate          : %.1f%%\n",
           (double)(n - cr.page_faults) / n * 100.0);
 
    return 0;
}

/*
 * mmap_demo.c
 *
 * mmap() を使ってファイルをメモリにマッピングし、
 * 通常のメモリアクセスでファイルを読み書きするデモ。
 * デマンドページングの恩恵を直接観察できる。
 *
 * コンパイル: gcc -Wall -o mmap_demo mmap_demo.c
 * 実行: ./mmap_demo
 *
 * 動作環境: Linux / macOS (POSIX 準拠)
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <errno.h>
 
#define FILE_PATH "/tmp/mmap_demo.dat"
#define FILE_SIZE (4096 * 4)  /* 16KB = 4 ページ分 */
 
/* デモ用のデータファイルを作成する */
int create_demo_file(const char *path, size_t size) {
    int fd = open(path, O_RDWR | O_CREAT | O_TRUNC, 0644);
    if (fd < 0) {
        perror("open");
        return -1;
    }
 
    /* ファイルサイズを設定。ftruncate がファイルを指定サイズに拡張する。
       なぜ必要か: mmap はファイルサイズを超える領域にはマッピングできない */
    if (ftruncate(fd, size) < 0) {
        perror("ftruncate");
        close(fd);
        return -1;
    }
 
    return fd;
}
 
int main(void) {
    printf("=== mmap Demo: Memory-Mapped File I/O ===\n\n");
 
    /* Step 1: ファイルを作成 */
    printf("[1] Creating demo file: %s (%d bytes = %d pages)\n",
           FILE_PATH, FILE_SIZE, FILE_SIZE / 4096);
    int fd = create_demo_file(FILE_PATH, FILE_SIZE);
    if (fd < 0) return 1;
 
    /* Step 2: ファイルをメモリにマッピング
       MAP_SHARED: 変更がファイルに反映される（他プロセスからも見える）
       MAP_PRIVATE にすると COW でプライベートコピーが作成される */
    printf("[2] Mapping file to memory with mmap()\n");
    char *mapped = mmap(NULL, FILE_SIZE, PROT_READ | PROT_WRITE,
                        MAP_SHARED, fd, 0);
    if (mapped == MAP_FAILED) {
        perror("mmap");
        close(fd);
        return 1;
    }
 
    /* mmap 後は fd を閉じても、マッピングは有効
       なぜなら: カーネルがファイルの参照カウントを管理しているため */
    close(fd);
    printf("    File descriptor closed (mapping still valid)\n");
 
    /* Step 3: メモリ書き込み = ファイル書き込み */
    printf("[3] Writing data through memory mapping\n");
    const char *messages[] = {
        "Page 0: Hello from mmap!",
        "Page 1: This is page-aligned data.",
        "Page 2: Memory-mapped I/O is efficient.",
        "Page 3: No read()/write() syscalls needed."
    };
 
    for (int i = 0; i < 4; i++) {
        /* 各ページの先頭に書き込み。
           初回アクセス時にデマンドページングでページフォルトが発生し、
           物理フレームが割り当てられる */
        char *page_start = mapped + (i * 4096);
        snprintf(page_start, 4096, "%s", messages[i]);
        printf("    Wrote to page %d (offset %d): \"%s\"\n",
               i, i * 4096, messages[i]);
    }
 
    /* Step 4: メモリ読み出し = ファイル読み出し */
    printf("[4] Reading data through memory mapping\n");
    for (int i = 0; i < 4; i++) {
        char *page_start = mapped + (i * 4096);
        printf("    Page %d: \"%s\"\n", i, page_start);
    }
 
    /* Step 5: msync でディスクへの同期を強制
       なぜ必要か: カーネルはパフォーマンスのために書き込みをバッファリングする。
       msync を呼ぶことで、変更が確実にディスクに書き出される */
    printf("[5] Syncing changes to disk with msync()\n");
    if (msync(mapped, FILE_SIZE, MS_SYNC) < 0) {
        perror("msync");
    }
 
    /* Step 6: アンマップ */
    printf("[6] Unmapping memory\n");
    if (munmap(mapped, FILE_SIZE) < 0) {
        perror("munmap");
    }
 
    /* Step 7: 通常の read() で確認 */
    printf("[7] Verifying with normal read()\n");
    fd = open(FILE_PATH, O_RDONLY);
    if (fd >= 0) {
        char buf[64];
        ssize_t n = read(fd, buf, sizeof(buf) - 1);
        if (n > 0) {
            buf[n] = '\0';
            printf("    Read from file: \"%s\"\n", buf);
        }
        close(fd);
    }
 
    /* クリーンアップ */
    unlink(FILE_PATH);
    printf("\n=== Demo Complete ===\n");
 
    return 0;
}

"""
paging_stats.py
 
Linux の /proc ファイルシステムからページング関連の統計情報を
読み取り、わかりやすく表示するツール。
 
仮想メモリの使用状況、ページフォルト回数、スワップ使用量、
TLB フラッシュ回数などを確認できる。
 
実行: python3 paging_stats.py
動作環境: Linux のみ
"""
 
import os
import sys
from typing import Dict, Optional
 
 
def read_proc_file(path: str) -> Optional[str]:
    """procfs からファイルを読み取る。"""
    try:
        with open(path, 'r') as f:
            return f.read()
    except (FileNotFoundError, PermissionError) as e:
        print(f"  Warning: Cannot read {path}: {e}")
        return None
 
 
def parse_meminfo() -> Dict[str, int]:
    """
    /proc/meminfo を解析し、メモリ情報を辞書として返す。
    値は全て KB 単位。
    """
    content = read_proc_file('/proc/meminfo')
    if content is None:
        return {}
 
    info = {}
    for line in content.strip().split('\n'):
        parts = line.split(':')
        if len(parts) == 2:
            key = parts[0].strip()
            # 数値部分を取り出す。"1234 kB" → 1234
            value_str = parts[1].strip().split()[0]
            try:
                info[key] = int(value_str)
            except ValueError:
                pass
    return info
 
 
def parse_vmstat() -> Dict[str, int]:
    """
    /proc/vmstat を解析し、仮想メモリ統計を辞書として返す。
    """
    content = read_proc_file('/proc/vmstat')
    if content is None:
        return {}
 
    stats = {}
    for line in content.strip().split('\n'):
        parts = line.split()
        if len(parts) == 2:
            try:
                stats[parts[0]] = int(parts[1])
            except ValueError:
                pass
    return stats
 
 
def parse_process_status(pid: int) -> Dict[str, str]:
    """
    /proc/[pid]/status を解析し、プロセスのメモリ情報を返す。
    """
    content = read_proc_file(f'/proc/{pid}/status')
    if content is None:
        return {}
 
    status = {}
    for line in content.strip().split('\n'):
        parts = line.split(':', 1)
        if len(parts) == 2:
            status[parts[0].strip()] = parts[1].strip()
    return status
 
 
def format_kb(kb: int) -> str:
    """KB を人間が読みやすい形式に変換する。"""
    if kb >= 1048576:
        return f"{kb / 1048576:.1f} GB"
    elif kb >= 1024:
        return f"{kb / 1024:.1f} MB"
    else:
        return f"{kb} KB"
 
 
def print_memory_overview(meminfo: Dict[str, int]) -> None:
    """メモリの概要を表示する。"""
    print("=" * 60)
    print("MEMORY OVERVIEW")
    print("=" * 60)
 
    total = meminfo.get('MemTotal', 0)
    free = meminfo.get('MemFree', 0)
    available = meminfo.get('MemAvailable', 0)
    buffers = meminfo.get('Buffers', 0)
    cached = meminfo.get('Cached', 0)
 
    used = total - free - buffers - cached
    usage_pct = (used / total * 100) if total > 0 else 0
 
    print(f"  Total     : {format_kb(total)}")
    print(f"  Used      : {format_kb(used)} ({usage_pct:.1f}%)")
    print(f"  Free      : {format_kb(free)}")
    print(f"  Available : {format_kb(available)}")
    print(f"  Buffers   : {format_kb(buffers)}")
    print(f"  Cached    : {format_kb(cached)}")
 
    # ページサイズ情報
    page_size = os.sysconf('SC_PAGE_SIZE')
    print(f"\n  Page Size : {page_size} bytes ({page_size // 1024} KB)")
    print(f"  Total Pages: {total * 1024 // page_size:,}")
 
 
def print_swap_info(meminfo: Dict[str, int]) -> None:
    """スワップ情報を表示する。"""
    print(f"\n{'='*60}")
    print("SWAP INFORMATION")
    print("=" * 60)
 
    swap_total = meminfo.get('SwapTotal', 0)
    swap_free = meminfo.get('SwapFree', 0)
    swap_used = swap_total - swap_free
    swap_cached = meminfo.get('SwapCached', 0)
 
    if swap_total == 0:
        print("  Swap is not configured")
        return
 
    usage_pct = (swap_used / swap_total * 100) if swap_total > 0 else 0
    print(f"  Total  : {format_kb(swap_total)}")
    print(f"  Used   : {format_kb(swap_used)} ({usage_pct:.1f}%)")
    print(f"  Free   : {format_kb(swap_free)}")
    print(f"  Cached : {format_kb(swap_cached)}")
 
 
def print_paging_stats(vmstat: Dict[str, int]) -> None:
    """ページング関連の統計情報を表示する。"""
    print(f"\n{'='*60}")
    print("PAGING STATISTICS (since boot)")
    print("=" * 60)
 
    # ページフォルト
    pgfault = vmstat.get('pgfault', 0)
    pgmajfault = vmstat.get('pgmajfault', 0)
    pgminfault = pgfault - pgmajfault
 
    print(f"  Page Faults (total) : {pgfault:>15,}")
    print(f"    Minor faults      : {pgminfault:>15,}")
    print(f"    Major faults      : {pgmajfault:>15,}")
    if pgfault > 0:
        major_pct = pgmajfault / pgfault * 100
        print(f"    Major fault ratio : {major_pct:>14.4f}%")
 
    # ページイン/ページアウト
    pgpgin = vmstat.get('pgpgin', 0)
    pgpgout = vmstat.get('pgpgout', 0)
    print(f"\n  Pages In  (from disk) : {pgpgin:>12,} KB")
    print(f"  Pages Out (to disk)   : {pgpgout:>12,} KB")
 
    # スワップイン/スワップアウト
    pswpin = vmstat.get('pswpin', 0)
    pswpout = vmstat.get('pswpout', 0)
    print(f"\n  Swap In  : {pswpin:>12,} pages")
    print(f"  Swap Out : {pswpout:>12,} pages")
 
 
def print_process_memory(pid: int) -> None:
    """特定プロセスのメモリ情報を表示する。"""
    print(f"\n{'='*60}")
    print(f"PROCESS MEMORY (PID: {pid})")
    print("=" * 60)
 
    status = parse_process_status(pid)
    if not status:
        print(f"  Cannot read process {pid} info")
        return
 
    print(f"  Name     : {status.get('Name', 'Unknown')}")
    print(f"  VmSize   : {status.get('VmSize', 'N/A'):>12} (仮想メモリサイズ)")
    print(f"  VmRSS    : {status.get('VmRSS', 'N/A'):>12} (物理メモリ使用量)")
    print(f"  VmSwap   : {status.get('VmSwap', 'N/A'):>12} (スワップ使用量)")
    print(f"  VmPeak   : {status.get('VmPeak', 'N/A'):>12} (仮想メモリピーク)")
    print(f"  VmData   : {status.get('VmData', 'N/A'):>12} (データ領域)")
    print(f"  VmStk    : {status.get('VmStk', 'N/A'):>12} (スタック領域)")
    print(f"  VmLib    : {status.get('VmLib', 'N/A'):>12} (共有ライブラリ)")
 
    # ページフォルト情報は /proc/[pid]/stat から取得
    stat_content = read_proc_file(f'/proc/{pid}/stat')
    if stat_content:
        fields = stat_content.split()
        if len(fields) > 11:
            minflt = int(fields[9])
            majflt = int(fields[11])
            print(f"\n  Minor faults: {minflt:>12,}")
            print(f"  Major faults: {majflt:>12,}")
 
 
def main():
    if sys.platform != 'linux':
        print("This tool is designed for Linux systems.")
        print("Demonstrating with simulated data...\n")
 
        # Linux 以外でもデモ表示
        print("=" * 60)
        print("SIMULATED PAGING STATISTICS")
        print("=" * 60)
        print("  On a Linux system, this tool reads from:")
        print("    /proc/meminfo    - Memory usage overview")
        print("    /proc/vmstat     - Virtual memory statistics")
        print("    /proc/[pid]/stat - Per-process page fault counters")
        print("\n  Key metrics to monitor:")
        print("    - Major page faults: High values indicate thrashing")
        print("    - Swap usage: Non-zero means physical memory is insufficient")
        print("    - Minor/Major ratio: Should be >99% minor faults")
        return
 
    meminfo = parse_meminfo()
    vmstat = parse_vmstat()
 
    print_memory_overview(meminfo)
    print_swap_info(meminfo)
    print_paging_stats(vmstat)
    print_process_memory(os.getpid())
 
    print(f"\n{'='*60}")
    print("HUGE PAGES")
    print("=" * 60)
    hp_total = meminfo.get('HugePages_Total', 0)
    hp_free = meminfo.get('HugePages_Free', 0)
    hp_size = meminfo.get('Hugepagesize', 0)
    print(f"  Total     : {hp_total}")
    print(f"  Free      : {hp_free}")
    print(f"  Page Size : {format_kb(hp_size)}")
 
    thp = meminfo.get('AnonHugePages', 0)
    print(f"  Transparent Huge Pages (anon): {format_kb(thp)}")
 
 
if __name__ == '__main__':
    main()

"""
working_set_estimator.py
 
ページ参照列からワーキングセットサイズ (WSS) を推定する。
ワーキングセットとは、ある時間窓 Δ 内でアクセスされた
ページの集合であり、スラッシング防止の基礎概念である。
 
実行: python3 working_set_estimator.py
"""
 
from typing import List, Set, Tuple
import random
 
 
def compute_working_set(reference_string: List[int],
                        window_size: int) -> List[Tuple[int, Set[int], int]]:
    """各時刻のワーキングセットを計算する。
 
    Args:
        reference_string: ページ参照列
        window_size: ワーキングセットの時間窓 Δ
 
    Returns:
        各時刻の (時刻, ワーキングセット, WSSサイズ) のリスト
    """
    results = []
 
    for t in range(len(reference_string)):
        # 時刻 t から過去 window_size 回分のアクセスを見る
        start = max(0, t - window_size + 1)
        window = reference_string[start:t + 1]
        ws = set(window)
        results.append((t, ws, len(ws)))
 
    return results
 
 
def analyze_working_set(reference_string: List[int],
                        window_sizes: List[int]) -> None:
    """異なるウィンドウサイズでワーキングセットを分析する。"""
    print("=" * 70)
    print("Working Set Analysis")
    print(f"Reference String ({len(reference_string)} accesses):")
    print(f"  {reference_string}")
    print("=" * 70)
 
    for delta in window_sizes:
        results = compute_working_set(reference_string, delta)
 
        # 平均 WSS を計算
        avg_wss = sum(wss for _, _, wss in results) / len(results)
        max_wss = max(wss for _, _, wss in results)
        min_wss = min(wss for _, _, wss in results)
 
        print(f"\nWindow size (Δ) = {delta}")
        print(f"  Average WSS: {avg_wss:.2f} pages")
        print(f"  Max WSS    : {max_wss} pages")
        print(f"  Min WSS    : {min_wss} pages")
 
        # 各時刻の詳細（短い参照列の場合のみ表示）
        if len(reference_string) <= 20:
            print(f"\n  {'Time':>4} | {'Page':>4} | {'Working Set':<25} | {'WSS':>3}")
            print(f"  {'-'*4}-+-{'-'*4}-+-{'-'*25}-+-{'-'*3}")
            for t, ws, wss in results:
                ws_str = str(sorted(ws))
                print(f"  {t:>4} | {reference_string[t]:>4} | "
                      f"{ws_str:<25} | {wss:>3}")
 
 
def simulate_thrashing(total_frames: int, num_processes: int,
                       wss_per_process: int) -> None:
    """スラッシングのシミュレーション。
 
    全プロセスのワーキングセット合計が物理フレーム数を超えると
    スラッシングが発生する様子を示す。
    """
    total_wss = num_processes * wss_per_process
 
    print(f"\n{'='*60}")
    print("Thrashing Simulation")
    print(f"{'='*60}")
    print(f"  Physical frames     : {total_frames}")
    print(f"  Processes           : {num_processes}")
    print(f"  WSS per process     : {wss_per_process} pages")
    print(f"  Total WSS demand    : {total_wss} pages")
    print(f"  Overcommit ratio    : {total_wss / total_frames:.2f}x")
 
    if total_wss <= total_frames:
        print(f"\n  Status: STABLE")
        print(f"  All working sets fit in physical memory.")
        print(f"  Expected page fault rate: LOW (compulsory faults only)")
    elif total_wss <= total_frames * 1.5:
        print(f"\n  Status: WARNING - Moderate swapping expected")
        print(f"  Some processes may experience elevated page faults.")
        print(f"  Expected performance degradation: 20-50%")
    else:
        print(f"\n  Status: THRASHING - Severe performance degradation")
        print(f"  Working sets cannot fit in memory.")
        print(f"  CPU will spend most time on page fault handling.")
        print(f"  Recommendation: Reduce processes or add memory.")
 
        # どのプロセスを退避すべきか
        max_active = total_frames // wss_per_process
        print(f"\n  Maximum concurrent processes: {max_active}")
        print(f"  Processes to suspend: {num_processes - max_active}")
 
 
if __name__ == "__main__":
    # 局所性のあるページ参照列
    ref_string = [1, 2, 3, 2, 1, 3, 4, 5, 4, 5, 6, 5, 4, 3, 2, 1, 2, 3, 1, 2]
 
    analyze_working_set(ref_string, window_sizes=[3, 5, 8])
 
    # スラッシングシミュレーション
    simulate_thrashing(total_frames=1000, num_processes=5, wss_per_process=150)
    simulate_thrashing(total_frames=1000, num_processes=10, wss_per_process=150)
    simulate_thrashing(total_frames=1000, num_processes=20, wss_per_process=150)

"""
page_table_walk.py
 
x86-64 の 4 階層ページテーブルウォークをシミュレーションする。
仮想アドレスを各レベルのインデックスに分解し、
ページテーブルを辿って物理アドレスに変換する過程を表示する。
 
実行: python3 page_table_walk.py
"""
 
from typing import Optional, Dict, Tuple
 
 
class PageTableEntry:
    """ページテーブルエントリを表現するクラス。"""
 
    def __init__(self, pfn: int = 0, present: bool = False,
                 writable: bool = True, user: bool = True,
                 accessed: bool = False, dirty: bool = False,
                 huge: bool = False):
        self.pfn = pfn
        self.present = present
        self.writable = writable
        self.user = user
        self.accessed = accessed
        self.dirty = dirty
        self.huge = huge  # Huge Page (2MB / 1GB)
 
    def __repr__(self) -> str:
        flags = []
        if self.present:  flags.append("P")
        if self.writable: flags.append("W")
        if self.user:     flags.append("U")
        if self.accessed: flags.append("A")
        if self.dirty:    flags.append("D")
        if self.huge:     flags.append("H")
        return f"PTE(PFN=0x{self.pfn:05X}, flags={'|'.join(flags)})"
 
 
class FourLevelPageTable:
    """x86-64 の 4 階層ページテーブルをシミュレーションする。
 
    階層構造:
      PML4 (Page Map Level 4)       → 9ビット (bits 47-39)
      PDPT (Page Directory Pointer)  → 9ビット (bits 38-30)
      PD   (Page Directory)          → 9ビット (bits 29-21)
      PT   (Page Table)              → 9ビット (bits 20-12)
      Offset                         → 12ビット (bits 11-0)
    """
 
    PAGE_SHIFT = 12
    ENTRIES_PER_TABLE = 512  # 2^9
    INDEX_BITS = 9
 
    def __init__(self):
        # 各テーブルを辞書の辞書として表現
        # tables[level][table_pfn][index] = PageTableEntry
        self.tables: Dict[int, Dict[int, Dict[int, PageTableEntry]]] = {
            4: {},  # PML4
            3: {},  # PDPT
            2: {},  # PD
            1: {},  # PT
        }
        self.cr3 = 0x1000  # PML4 の物理アドレス (フレーム番号)
        self._init_pml4()
        self.walk_count = 0
 
    def _init_pml4(self):
        """PML4 テーブルを初期化する。"""
        self.tables[4][self.cr3] = {}
 
    def _ensure_table(self, level: int, table_pfn: int):
        """テーブルが存在しなければ作成する。"""
        if table_pfn not in self.tables[level]:
            self.tables[level][table_pfn] = {}
 
    def map_page(self, virtual_addr: int, physical_frame: int,
                 writable: bool = True, user: bool = True) -> None:
        """仮想ページを物理フレームにマッピングする。"""
        indices = self._extract_indices(virtual_addr)
 
        # Level 4 (PML4) → Level 3 (PDPT) のエントリ
        current_table_pfn = self.cr3
        next_pfn = physical_frame + 0x1000  # 中間テーブル用のフレーム
 
        for level in range(4, 1, -1):
            idx = indices[level]
            self._ensure_table(level, current_table_pfn)
 
            if idx not in self.tables[level][current_table_pfn]:
                # 新しい中間テーブルを割り当て
                new_table_pfn = next_pfn
                next_pfn += 1
                self.tables[level][current_table_pfn][idx] = PageTableEntry(
                    pfn=new_table_pfn, present=True,
                    writable=True, user=True
                )
                self._ensure_table(level - 1, new_table_pfn)
 
            entry = self.tables[level][current_table_pfn][idx]
            current_table_pfn = entry.pfn
 
        # Level 1 (PT) の最終エントリ
        idx = indices[1]
        self._ensure_table(1, current_table_pfn)
        self.tables[1][current_table_pfn][idx] = PageTableEntry(
            pfn=physical_frame, present=True,
            writable=writable, user=user
        )
 
    def _extract_indices(self, virtual_addr: int) -> Dict[int, int]:
        """仮想アドレスから各階層のインデックスを抽出する。"""
        offset = virtual_addr & 0xFFF
        pt_idx  = (virtual_addr >> 12) & 0x1FF
        pd_idx  = (virtual_addr >> 21) & 0x1FF
        pdpt_idx = (virtual_addr >> 30) & 0x1FF
        pml4_idx = (virtual_addr >> 39) & 0x1FF
 
        return {
            4: pml4_idx,
            3: pdpt_idx,
            2: pd_idx,
            1: pt_idx,
            0: offset
        }
 
    def walk(self, virtual_addr: int, verbose: bool = True
             ) -> Optional[int]:
        """4 階層ページテーブルウォークを実行する。"""
        self.walk_count += 1
        indices = self._extract_indices(virtual_addr)
 
        if verbose:
            print(f"\n{'='*60}")
            print(f"Page Table Walk #{self.walk_count}")
            print(f"Virtual Address: 0x{virtual_addr:016X}")
            print(f"{'='*60}")
            print(f"  PML4 index : {indices[4]:>3} (0x{indices[4]:03X})")
            print(f"  PDPT index : {indices[3]:>3} (0x{indices[3]:03X})")
            print(f"  PD   index : {indices[2]:>3} (0x{indices[2]:03X})")
            print(f"  PT   index : {indices[1]:>3} (0x{indices[1]:03X})")
            print(f"  Offset     : {indices[0]:>3} (0x{indices[0]:03X})")
            print()
 
        level_names = {4: "PML4", 3: "PDPT", 2: "PD  ", 1: "PT  "}
        current_table_pfn = self.cr3
        memory_accesses = 0
 
        for level in range(4, 0, -1):
            idx = indices[level]
            memory_accesses += 1
 
            if (current_table_pfn not in self.tables[level] or
                idx not in self.tables[level][current_table_pfn]):
                if verbose:
                    print(f"  [{level_names[level]}] Table@0x{current_table_pfn:05X}"
                          f"[{idx}] -> PAGE FAULT (not present)")
                return None
 
            entry = self.tables[level][current_table_pfn][idx]
 
            if not entry.present:
                if verbose:
                    print(f"  [{level_names[level]}] Table@0x{current_table_pfn:05X}"
                          f"[{idx}] -> PAGE FAULT (P=0)")
                return None
 
            if verbose:
                print(f"  [{level_names[level]}] Table@0x{current_table_pfn:05X}"
                      f"[{idx}] -> {entry}")
 
            # Accessed ビットをセット
            entry.accessed = True
 
            if level > 1:
                current_table_pfn = entry.pfn
            else:
                # 最終レベル: 物理アドレスを計算
                physical_addr = (entry.pfn << self.PAGE_SHIFT) | indices[0]
                memory_accesses += 1  # データアクセス
 
                if verbose:
                    print(f"\n  Physical Address: 0x{physical_addr:016X}")
                    print(f"  Memory accesses for translation: {memory_accesses}")
                return physical_addr
 
        return None
 
 
if __name__ == "__main__":
    pt = FourLevelPageTable()
 
    # いくつかのページをマッピング
    print("Setting up page mappings...")
    pt.map_page(0x0000_0040_0000, 0x00100)  # 仮想 0x400000 → 物理フレーム 0x100
    pt.map_page(0x0000_0040_1000, 0x00200)  # 仮想 0x401000 → 物理フレーム 0x200
    pt.map_page(0x0000_7FFF_F000, 0x00300)  # スタック領域の仮想アドレス
    pt.map_page(0x0000_0000_1000, 0x00050)  # 低アドレス
 
    # ページテーブルウォークを実行
    pt.walk(0x0000_0040_0A7C)  # VPN=0x400, offset=0xA7C
    pt.walk(0x0000_0040_1500)  # VPN=0x401, offset=0x500
    pt.walk(0x0000_7FFF_F100)  # スタック近辺
    pt.walk(0x0000_0000_1234)  # 低アドレス
 
    # マッピングされていないアドレス → ページフォルト
    pt.walk(0x0000_DEAD_BEEF)

/* アンチパターンの例 */
void *buf = malloc(HUGE_SIZE);
mlock(buf, HUGE_SIZE);  /* 全メモリをロック → 危険 */
 
/* 正しいアプローチ */
void *secret_key = malloc(KEY_SIZE);
mlock(secret_key, KEY_SIZE);  /* 必要最小限のみロック */
/* 使用後 */
memset(secret_key, 0, KEY_SIZE);  /* ゼロクリア */
munlock(secret_key, KEY_SIZE);
free(secret_key);