摘要 比較並評估四種分頁替換演算法(page replacement algorithm)，以三種不同的資料型態進行比較，演算法各為 FIFO、ARB、ESC、DESC，資料型態各為Random、Locality、Most Random (MR.)。整體的排名為 (優) DESC > FIFO > ESC > ARB (差)，本實驗提出了「先生生成」與 DESC 兩個概念，分別是特殊的資料生成方式和獨特的演算法，如上述 DESC 在表現上比現有的幾個演算法好，但仍有許多進步的空間。 簡介 分頁(paging) 是作業系統裡記憶體管理的一種技術，可以使電腦的主記憶體可以使用儲存在輔助記憶體中的資料。作業系統會將輔助記憶體中的資料分割成固定大小的區塊，稱為分頁（page），而分頁表 (page table) 為儲存了虛擬位址到實體位址間之對映的表。當軟體試圖訪問目前未被載入在實體記憶體中的一個分頁時，會由中央處理器的記憶體管理單元發出中斷，這個狀況稱之為分頁錯誤(page fault) ，此時就需要替這個分頁尋找一個頁框(frame) 來使用。這個在發生分頁錯誤後，尋找頁框並使用的動作就稱為分頁替換(page replacement) 。當實體記憶體還沒滿的時候，分頁會被寫回實體記憶體，並更新分頁表；反之，當實體記憶體已滿時，找出一個將被替代掉的犧牲者(victim) ，儲存犧牲者的資訊，並將新分頁替換上來，更新分頁表，分頁的調入調出之相關操作方法，即分頁替換演算法。 本次實驗會實作四種分頁替換演算法，分別為First-in-first-out algorithm (FIFO) 、Additional reference bits algorithm (ARB) 、Enhanced second-chance algorithm (ESC) 、Decent enhanced second-chance algorithm (DESC) 。DESC 是我設計的分頁替換演算法，主體以ESC 進行改編，並融入本人發想的獨特設計-—Store Bits。本次實驗的資料有三種型態，分別為Random、Locality、Most Random (MR.)，MR. 亦是本人親自發想設計的，中文命名為「先生生成」，主要概念為模擬長期使用之電腦的實際狀況。 分頁替換演算法 (page replacement algorithm) First-in-first-out algorithm (FIFO) FIFO 的核心理念是先來者先出去，故犧牲者為先來者，也就是存在記憶體中最久的分頁。FIFO 可以使用佇列 (queue)來實現，是易實作且不差的演算法。FIFO 的特性使得佇列中的分頁得以經常被更新，而且所有分頁都有機會被替換。

紅黑樹實作: 研究紅黑樹 https://hackmd.io/@sysprog/rJbMiW3S3 紀錄問題並重現實驗 + extra 講解影片 介紹紅黑樹 簡述紅黑樹 紅黑樹是 2-3-4 樹的變形，1978 年 Leonidas J. Guibas 和 Robert Sedgewick 發明最初的紅黑樹。2008 年 Sedgewick 做了改進，並將此命名為 LLRBT (Left-leaning red–black tree，即 左傾紅黑樹)，後者相比 1978 年的紅黑樹要簡單，程式碼量更精簡，可參見 Left-leaning Red-Black Trees。 image 底下為一個符合規則的紅黑樹

contributed by < marsh-fish > 自我檢查清單 [x] 研讀前述 Linux 效能分析 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作，從中也該理解為何不希望在虛擬機器中進行實驗; [ ] 閱讀〈Linux 核心模組運作原理〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 insmod 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 strace 追蹤 Linux 核心的掛載，涉及哪些些系統呼叫和子系統？ [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 lib/sort.c 在排序過程中的平均比較次數，並提供對應的數學證明; [ ] 解釋 xoroshiro128+ 的原理 (對照〈Scrambled Linear Pseudorandom Number Generators〉論文)，並利用 ksort 提供的 xoro 核心模組，比較 Linux 核心內建的 /dev/random 及 /dev/urandom 的速度，說明 xoroshiro128+ 是否有速度的優勢？其弱點又是什麼？ Linux 效能分析的重點 作業主題一: 並行的混合排序

contributed by < marsh-fish > 閱讀〈因為自動飲料機而延畢的那一年〉的啟發 我非常喜歡作者引用了《鋼之鍊金術師》的金句，許多老一輩的人都認為看動漫是件幼稚的行為，但動漫裡頭能讓人學習到的東西非常的多(當然會因作品而異)，不應該因自身的「刻板印象」對他人的喜好亂下評斷，但人又何嘗不是如此呢?回到文章，作者在專案前期預期著完美的理想成品，但由許多的理想都難以實現，光是自動掉冰塊機就花了相當多的時間才有成品，我一看到作者初期對自動掉冰塊機的想像，就有相當大的疑問，當下一直在思考「如果是我做的話會怎麼做?」，看到作者想用彈簧實現，就讓我想到當初檳榔去鬚機的出代版本也是用彈簧，後來才改成現在常見的形式，不過後來作者是直接購買冰塊分配器就是了。「三折肱為良醫」究竟是折肱三次方能成為良醫，還是幫助過三個「折肱」人即成為良醫呢?當然，字典會告訴你答案是前者，但若折肱這件事能為你帶來啟發，何必是「自己」來折肱呢?《因為自動飲料機而延畢的那一年》最後的結局雖不是最完美，但就如《灌籃高手》、《棋靈王》這樣的故事，往往能帶給人來更多的感觸，我也不禁感動落淚。 想投入的專案 kHTTPd 改進 Linux 核心的 lib/{list_}sort.c int mul_10(int x) {

決戰!食物 遊戲目的: 選出大家心目中最想要的那個食物吧!!!!!!!! 遊戲規則: 所有玩家先選出自己想要的3家店家 由主持人倒數一起出牌 最高票的店家獲得勝利，出現多數同票情形，則以同票店家再次進行一輪遊戲，此時每位玩家限定只能出一張牌 出牌規則:

contributed by < marsh-fish > Reviewed by marvin0102 q_ascend 和 q_descend 的實作中，我原本的作法是透過 list_for_each_entry_safe 逐一排查，當檢查到不符合 ascned 或 descend 的節點時，將期刪除後還須回過頭檢查之前的佇列，review 時，發現 marsh-fish 同學的作法更有效率。 需要解釋 marsh-fish 的方案為何更有效率，這樣才有同儕程式碼審查的效果。 :notes: jserv Reviewed by mesohandsome 可以貼出修改或新增的程式碼，或是貼出 commit 紀錄，以便日後修改或參考時較為便利。

contributed by < marsh-fish > 第三週測驗題 測驗 1 測驗 2 用 bitwise 來實作除法運算，根據 Hacker's Delight 使用 bitwise 來實現除法會比用除法運算更有效率。 若我們欲除以 10 ，但除以 10 無法單純的改成 bitwise 的形式，因為 10 並不是 2 的冪或接近 2 的冪的數值，於是我們打算找到一個接近 10 的數值以取代除以 10 的除法運算操作。以本題為例， $2^N = 128, a = 13, \cfrac{128}{13} \approx 9.84$ 因此 $\cfrac{128}{13}$ 便是一個可用來代替除以 10 的數值，乘 13 的運算以 bitwise 改寫會成((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2)，其中的 d0 d1 d2 為向右位移 3 時所遺失的所以須再運算完後將其補回。餘數為被除數減去商數乘以除數的結果(餘數定理)，又10＝(4+1)*2，因此 r = tmp - 10 * q; 以 bitwise 寫成 r = tmp - (((q << 2) + q) << 1);

from pptx import Presentation def read_first_slide(pptx_file): prs = Presentation(pptx_file) text = [] # Process only the first slide first_slide = prs.slides[0] for shape in first_slide.shapes: if hasattr(shape, "text"):

contributed by < marsh-fish > 第一週測驗題 測驗 1 利用左右指標(左指標從頭部開始，右指標從尾部)紀錄所有大於和小於 pivot 的數之量，藉此得出 pivot 應插入之位置。 測驗 2 原理和 merge sort 類似，藉由分成數個 runs 來合併，由於在分成 runs 的過程中會轉成遞增的序列，所以能夠有效的減少合併的次數。