HackMD
2020_OS_Fall_HW1: Benchmark Your Computer Black Box
繳交期限：09/21-10/06 00:00
作業目標
- 請撰寫一支數值排序的程式，其功能是能夠將數值由小排序到大，且排序的資料量會遠大於電腦記憶體的容量。
- 請觀察及分析程式執行期間，包括但不限於CPU、Memory、Disk I/O的使用情況，探討作業系統是如何服務我們的程式。
測試資料
請撰寫一支程式，自行產生出符合以下條件的測試資料，做為此次作業的輸入資料。
- 請在單一檔案產生N個亂數數值，並以換行字元（LF）分隔，做為待排序的資料。
- 數值範圍: -2147483648 ~ 2147483647 即 -231 ~ 231-1 (4 bytes int)
- 請注意，換行字元的前後不要包含空白字符。
- 測試資料的檔案大小，至少要大於你電腦的實體記憶體大小。
- 這代表產生的資料量將會非常龐大，你所撰寫的排序程式必須要能夠妥善處理它。
- 請以 UTF-8 的字元編碼儲存，並將此測資檔案命名為「input.txt」。
你所產生的測試資料（input.txt），應該會長得像這樣：
如何開始
- 請依照前項的說明，產生出撰寫此作業需要使用的輸入資料「input.txt」。
- 請撰寫一支數值排序的程式，並將排序後的結果儲存為「output.txt」。
- 請注意，你所撰寫的排序程式必須要能夠處理龐大的資料量。
- 請使用任意工具或方法分析、觀察你所撰寫的程式，並優化你的程式（例如：降低執行時間）。
- 試著用盡電腦的計算能力，讓它集中在處理你的程式上，以電腦閒置資源最小化為目標。
- 將你所觀察到的現象，試著思考作業系統背後的行為，撰寫出一份完整的效能分析報告。
- 此部分的內容將會是作業評分的重點，盡你所能說明的越詳盡越好。
- 請嘗試往觀察CPU、Memory、Disk I/O的使用情形著手，對上述系統資源的觀察，並試著去結論作業系統應該要如何服務該些程式，使每隻程式能得到最好的服務。
- 請嘗試執行自己撰寫的排序程式若干支，就是讓系統同時有多支相同的程式執行（假設你所撰寫的是Single-thread程式），這時作業系統會負責切換這些程式的執行，你可以測量這一批程式執行的時間，觀察及討論作業系統在背後做了什麼有利於這麼多支程式的"事"。
- 將你撰寫的程式碼及說明文件，依照作業繳交的規定，於期限內上傳到Moodle平台。
說明文件
說明文件的格式不拘，你也可以使用Markdown來完成。
你在撰寫此份說明文件時，必須要包含下列基本內容。
學號：
姓名：
系級：
開發環境：
- OS: Ubuntu 20.04.1
- CPU: Intel® Core™ i7-10700 CPU @ 2.90GHz × 16
- Ｍemory: 32GB
- Programming Language(version): Java 1.8.0_261
程式執行時間：
- 請在你的程式中加入量測執行時間的程式碼，以精準的獲取此數值。
程式開發與使用說明：
- 你是如何開發這支排序程式，以達成支援大資料排序的行為？
- 你的程式該如何使用，請詳細說明執行的步驟。
效能分析報告：
請注意，分析報告的內容必須包含下列兩個部分。
- 你開發的排序程式對硬體效能優化程度的說明與驗證。
- 在同時運行多支你所開發的排序程式下，你對系統效能的觀察，並結論OS的設計要提供哪些優化服務。
- 你可以搭配圖片、圖表或外部資料來說明。
- 這部分將會是此作業評分的重點，請同學盡量發揮。
作業繳交
- 繳交期限：09/21-10/06 00:00
- 逾期繳交將按下規則採連續扣分。
- 逾期一日：得分扣10分。
- 逾期二日：再扣20分。
- 逾期三日：再扣30分。
- 逾期四日以上：得分以0分計算。
- 逾期繳交將按下規則採連續扣分。
- 請將你的「程式原始碼」、「說明文件」打包成ZIP壓縮檔（請以HW1_你的學號.zip命名）。
- 說明文件 -> 請繳交Markdown（.md），或是PDF檔案。
- 若你使用HackMD寫文件，可以接受以匯出的HTML檔案繳交。
- 若你用其他形式撰寫文件，請轉換成PDF格式繳交。
- 不需要繳交測試所使用的輸入檔（input.txt）及排序後的輸出檔（output.txt）。
- 說明文件 -> 請繳交Markdown（.md），或是PDF檔案。
- 請再次確認你的程式能夠正常執行，且說明文件中有包含指定的內容。
- 請將打包好的壓縮檔，上傳到Moodle的作業中，即可完成此次作業的繳交。
評分項目
作業會以下列原則評分，滿分為100分。
- 排序程式
- 排序程式是否能夠處理龐大的資料量。
- 助教會使用數種不同大小的測試資料（如：8G、16G、32G、64G、128G等）來驗證程式能否正確執行。
- 排序程式的執行效率（速度）。
- 對排序程式的優化程度。
- 排序程式是否能夠處理龐大的資料量。
- 說明文件：效能分析報告的內容是本項評分的重點。
- 文件是否有包含指定的內容。
- 報告內容的完整度及正確性。
- 對系統資源觀察的程度以及呈現的說明內容。
- 如何優化這支排序程式，驗證與說明的完整度。
注意事項
- 你可以使用任意程式語言撰寫作業，但助教只會用Ubuntu環境執行你的程式，因此建議使用Linux OS來撰寫此份作業。
- 你可以用任何OS(Windows、Windows Subsystem for Linux、Virtual Machine…)開發，但是就像上一點說的，助教只會在Ubuntu中執行你的程式。
- 你可以在 Virtual Machine 中開發，一樣是分析在 Virtual Machine 中的效能，並在開發環境的部份註記是使用 Virtual Machine。
- 請不要直接調用外部的函式庫來幫助你達成排序大檔案的行為。
- 嚴格禁止互相抄襲程式碼，助教會進行程式碼比對，違者此次作業以零分計算。
