作業系統討論區整理

第一章 === 中斷向量表（Interrupt Vector Table） --- 儲存中斷向量的資料結構，存放各種中斷的編號及其服務程式的起始位置。當中斷發生時，處理器會查詢中斷向量表，找出對應的程式位置，並跳到指定位置處理中斷。 Trap和Interrupt --- * **Interrupt：** 當程式或事件需要立即關注時，由軟體或硬體發出的信號，分為非同步的Hardware Interrupt和同步的Software Interrupt。 * **Trap：** 屬於Software Interrupt，當發生除零計算、無效的記憶體存取或使用者程式向作業系統發出明確的服務請求時，就可能產生Trap。作業系統的主要目的有哪些？ --- * **使用者的角度：** 協助使用者分配軟硬體的資源、使使用者執行的指令效果最大化、降低操作難度。 * **系統的角度：** 掌控並有效且公平的分配各項資源（CPU時間、記憶體空間、儲存空間、I/O控制⋯）。以購置成本而言，相較於閉源軟體，開源軟體應該佔優 --- * **安全性比較：** 開源軟體因為它的原始碼是公開的，bug和安全問題更容易被發現，也因為允許任何人修改，通常能更快修復問題。 * **測試和實踐比較：** 開源軟體能讓任何人使用，所以泛用性更高，被使用實踐的次數通常也更多。 Multiprogramming和Multitasking的定義及差異 --- * **Multiprogramming（多工程式）：** 最初始的CPU分配方式，根據要求順序，當前一個程式不需要使用CPU資源時，監控程式才會把資源分配給下一個需要的程式。 * **Multitasking（多工系統）：** 使用Preemptive的CPU分配方式，具體上不給予要求CPU的terminal先後順序（不重視隊伍，只重視服務當前），而是給予每個任務獨立的空間，並且由作業系統接手監控的作用。會依照優先級分配資源，若單一任務佔用太多時間會強制停止，並且分配給每個terminal的時間不多，會讓CPU快速切換，使得看起來很像同時進行多個任務。 | | Multiprogramming | Multitasking | | -------- | -------- | -------- | | 排程 | 先後順序 | 每個時間點到即中斷 | | 複雜度 | 簡單 | 困難 | | 作用時間 | 第一排程結束時 | 規定時間結束時 | | 目的性 | 最大化CPU使用率 | 最小化CPU反應時間 | Hardware interrupt/Software interrupt運作流程的差異 --- | | Hardware interrupt | Software interrupt | | -------- | -------- | -------- | | 觸發方式 | 由外部硬體設備所引發的事件觸發的（如：鍵盤輸入） | 由CPU執行指令觸發的，通常是執行中的程式主動要求的 | | 觸發時機 | 可以發生在任何時間，不可預期，所以是非同步。 | 由程式明確觸發的，可以預期到它的發生，所以是同步。 | | 處理程序 | 通常會引導到特定的ISR，這些ISR是事先寫好用於處理特定硬體設備的中斷事件，負責處理並讀取外部設備的數據 | 處理程序也被稱為系統調用，它是由操作系統提供的服務，用於執行特權操作、訪問共享資源。 | CPU在收到Interrupt Request後，經歷了哪些流程才回去執行原來的程序？ --- 1. 中斷被觸發 2. 停止目前執行的指令 3. 儲存當前程式狀態到特定的記憶體位置 4. 從PIC接收Interrupt ID（number） 5. 透過Interrupt ID去IDT找特定的ISR（Interrupt handler） 6. 保存ISR可能要用到的暫存空間 7. 執行ISR 8. 發送EOI command給PIC，表示中斷處理完畢 9. 恢復暫存器 10. IRET指令中斷返回，利用先前儲存在特定記憶體位址的程式狀態返回原先未處理完的程式解釋並由慢到快排序儲存裝置 --- **1. Magnetic taps（磁帶）：** 按順序儲存資料，主要用於長期存檔 **2. Optical disk（CD/DVD）：** disk上的小孔可以透過激光讀取資料，儲存空間靜態且可讀性的資料 **3. HDD：** 一個內部或外部的儲存資料（應用程式or使用者資料夾）的電腦元件，使用旋轉磁盤讀寫資料 **4. Nonvolatile memory：** 通常以快閃記憶體的形式存在（SSD、USB驅動器），在速度和儲存空間之間提供良好的平衡 **5. Cache：** 小型的高速存儲區，用於暫時儲存經常訪問的資料，作為速度較慢的大型記憶體的buffer，由SRAM組成（Static random access memory） **6. Main memory：** 提供快速的資料訪問，是運行應用程式的關鍵部件，由DRAM組成（Dynamic random access memory） **7. Registers：** CPU內部最快的存儲元素，用於非常高速的數據訪問和操作 ``` SRAM：揮發性記憶體，只要提供電源就能保存資料，不需要定期刷新，較貴較小 DRAM：揮發性記憶體，將數據存儲在電路中微小電容器的電荷必須定期刷新（通常每幾毫秒一次）防止數據丟失，用於儲存大量數據 ``` Asynchronization和Synchronization的差異以及作用 --- | | Asynchronous（非同步） | Synchronous（同步） | | -------- | -------- | -------- | | 主要差異 | 接收到需求，不需等到需求完成再執行其他需求，有助於提高系統的響應性和性能。 | 必須等待對方完成動作，才能執行其他事情。通常作用於確保多個線程之間不會同時訪問共享資源，防止數據損壞和不一致性。 | | 單核心 | 用於處理I/O操作（文件讀寫、網路通信），可以在等待操作完成的時間執行其他計算任務，充分利用CPU時間。 | 用於處理多個線程之間的併發，以便交替運行實現多任務，操作系統會使用時間片輪轉來切換線程的執行。 | | 多核心 | 用於並行執行獨立的計算任務，從而充分利用多個核心的處理能力。 | 用於確保多個核心之間的協作和數據一致性，例如多個線程可能需要協同工作以完成某個任務，同步機制可以確保它們按照正確的順序執行，避免數據競爭和錯誤結果。 | Interrupt的分類樹 --- ![photo-output.PNG](https://hackmd.io/_uploads/HJX96MzQT.png) 說明以下名詞，能否放在同一張圖？ --- * **Disk drive：** 磁碟，一種資料存放的裝置， * **Disk driver：** 磁碟驅動程式，讓電腦控制磁碟或是與之溝通的軟體。 * **Disk controller：** 磁碟控制器，讓CPU能與磁碟溝通的控制電路。 * **User application：** 使用者的應用程式，為了使用者需求所安裝的軟體。 * **System call：** 系統呼叫，指運行在user mode的程式項作業系統核心請求需要更高權限運行的服務。 **（圖待補）** 列出所有帶有interrupt單字的專有名詞，判斷其為硬體/韌體/軟體，並簡要說明其意義，可否將上述專有名詞整合在一張圖之中？ --- > 軟體 * **interrupt：** CPU內部或外部有緊急事件發生時，會發送給CPU的訊息。 * **interrupt vector：** 為中斷的ID及其服務程式的起始位置。 * **interrupt-handler routine（中斷處理程序/ISR）：** 軟體，是一段特定的程式碼，用於處理特定類型的中斷事件。當中斷發生時，處理器會跳到對應的中斷處理程序例程，以執行與中斷相關的任務，然後返回原來的程式。 * **nonmaskable interrupt（不可屏蔽中斷）：** 是一種特殊類型的中斷，通常用於處理緊急情況，如系統崩潰或硬體故障。這種中斷不能被系統屏蔽或停用，以確保及時處理。 * **interrupt chainning（中斷連結）：** 是一種處理多個中斷的方法，其中一個中斷處理程序可以呼叫或連結到另一個中斷處理程序。這允許按照優先順序處理中斷，確保高優先順序的中斷能夠及時回應。 > 硬體 * **interrupt-request line（中斷請求線）：** 硬體，是電腦硬體中的一種實體電纜或訊號線，用於傳遞裝置或外部事件觸發的中斷請求。當一個設備需要處理時，會透過中斷請求線發送訊號，通知處理器需要中斷處理。 * **interrupt-controller hardware（中斷控制器硬體）：** 硬體，用於管理和分派系統中各種中斷要求。有助於確保中斷的優先順序和順序得到正確處理，以避免衝突和混亂。 * **maskable interrupt（可屏蔽中斷）：** 是一種可以被系統屏蔽或停用的中斷。系統可以根據需要選擇性的啟用或停用這些中斷，以控制中斷的處理優先權和時機。 * **interrupt priority levels（中斷優先權等級）：** 是用來決定中斷處理優先權的系統機制。不同中斷可以分配不同的優先級，以確保高優先級的中斷得到更快的回應和處理。 **（圖待補）** 第二章 === 請說明何為privilege escalation，以及有什麼privilege escalation的例子 --- 指利用作業系統或應用軟體中的程式錯誤、設計缺陷來取得對應用程式或使用者來說進階的存取權限，也就是說使用者和應用程式會獲得原本不該有的權限。其中又分為兩種： * **Vertical privilege escalation(垂直權限提升)：** 低特權的使用者可以使用高特權使用者的功能或內容 * **Horizontal privilege escalation(水平權限提升)：** 一般使用者訪問原本不可訪問的其他一般使用者的內容 **privilege escalation的例子：** 1. 網上銀行用戶訪問到網站管理功能，或者繞過密碼認證措施 2. 一種特權提升攻擊，其中網站擊破了網頁瀏覽器的安全模型，從而可以在客戶端的計算機上運行惡意代碼 3. 以一企業為例，在A部門的普通員工可以存取B部門一般職員擁有的訊息或系統動作安裝軟體時都是有作業系統在的情況下安裝的，那麼作業系統要如何安裝? --- 軟體大致有以下兩種安裝方式 * **applet：** 安裝程式本體、registry和設定檔到選擇位置，通常不會動到系統配置，又稱為可攜式軟體。 * **application：** 包含了程式本體、動態連結程式庫、設定檔、註冊檔、環境變數的設定，通常會將檔案安裝至「C:\Program Files」資料夾裡面。不論是哪種類型的軟體，OS 皆需做到 File management 建立設定檔、 Protection 操作系統會驗證用戶應用程式的請求，以確保不會對系統的安全性和穩定性造成威脅。請列出 system call 的五種類型，且舉例並說明這些類型包含哪些 system call --- 系統呼叫（system call）是操作系統提供給應用程式使用的一組函數，它們允許應用程式與操作系統核心進行互動，執行各種操作，以下是五種常見的系統呼叫類型。 **檔案系統系統呼叫：** * **open()：** 用於開啟檔案或建立新檔案。 * **read()：** 用於從檔案讀取資料。 **進程控制系統呼叫：** * **fork()：** 用於創建新的子進程。 * **exec()：** 用於執行新的程序。 **記憶體管理系統呼叫：** * **malloc()：** 用於分配動態記憶體。 * **free()：** 用於釋放已分配的記憶體。 **網路通信系統呼叫：** * **socket()：** 用於建立網路套接字。 * **bind()：** 用於將套接字綁定到特定的位址和埠號。 **使用者資訊與許可權管理系統呼叫：** * **getuid()：** 用於取得當前使用者的使用者識別碼（UID）。 * **getgid()：** 用於取得當前使用者的群組識別碼（GID）。 Dual Mode可分為哪兩種模式？這兩種模式分別使用在什麼地方？以及它們的權限分別為何？在x86 Protection Rings中，依權限的高低可分為幾個層級？每個層級的應用有哪些？ --- 1. 使用者(user)模式、核心(kernel)模式 2. 3. | | Kernel mode | User mode | | -------- | -------- | -------- | | 使用在什麼地方 | 可以直接存取和控制計算機的硬體資源，包括中央處理器、記憶體，還可以處理硬體中斷，如硬碟I/O操作、計時器中斷、網絡數據包接收等。 | 讀取自己的內存、處理自己的錯誤、可以為用戶提供各種服務，如文字處理、媒體播放、網路通信等、處理用戶輸入。 | | 權限為何 | 擁有最高的權限，能夠使所有的硬體操作和其他系統停止指令，可以直接訪問硬體資源、執行特權指令、檔案、關機、分配記憶體，以及處理硬體中斷。 | 基本上是「受限」的模式。除了一些基本的操作之外什麼都不能做。它們無法執行特權指令、直接訪問硬體資源或操作系統核心的內存。需要操作系統和系統調用所提供的服務來執行需要更高權限的任務。 | 4. 在x86 Protection Rings中，權限由高到低共有4個層級，**分別是Ring 0、1、2跟Ring 3**，其中Ring 0擁有最高的權限可以直接和所有硬體互動，如存取記憶體或執行與I/O相關的指令；而Ring 0則有最低的權限，為一般應用程式的運行模式，這兩個Ring也就是Dual mode裡面的kernel mode以及user mode。至於Ring 1還有Ring2，每一張說明Protection Rings的圖片上都顯示這兩個Rings是for Device Drivers的，不過實際能找到例子並不多 **Ring 1：** 虛擬機VirtualBox曾將guest kernel code放在Ring 1下執行 **Ring 2：** 作業系統OS/2廣泛地將Ring 2使用於需要特權的I/O code 當一個system call無法正常結束，CPU會如何處理這個問題，又是哪個單元負責分析crash的原因？對應2.3.3和2.10 --- 當一個system call無法正常結束，CPU會再呼叫多一個 system call，之後是由 debugger 負責分析crash的原因請說明「Dual Mode」是什麼，包括它的模式區別、應用、及優缺點 --- Dual mode是指作業系統將系統使用權限分為user mode與kernel mode此兩種模式。user mode僅可執行一般的指令與存取user-memory，kernel mode則可額外執行特權指令（privileged instruction）與存取kernel-memory。作業系統利用Dual mode把一些可能會造成危害的機器指令設為特權指令，可以防止使用者程式（user program）直接使用這些指令，對系統或其他user造成危害，如此一來可以保護硬體之類的重要資源不受到使用者的破壞。優點如上述所說，可以增加系統的安全性。還有可以提升系統的穩定性，因為Dual mode讓使用者程式所執行的指令不會干涉到系統階級的操作。缺點則是可能會降低系統效能，因為每次在user mode與kernel mode之間切換時需要context switch。且使用Dual mode會讓系統變得更加複雜，使其難以設計與維護。系統呼叫和函式呼叫之間有什麼區別？ --- 系統呼叫指運行在使用者空間的程式向作業系統核心（OS kernel）請求需要更高權限運行的服務，是一種應用程式與作業系統之間進行交互的機制，用於訪問系統提供的服務和資源，例如文件操作、網絡通信等，常常需要通過特定的系統呼叫編程接口（API）來調用，也會通過軟體中斷（Software Interrupt）或硬體中斷（Hardware Interrupt）來執行。而函式呼叫通常發生在應用程式的內部，通過調用函式或方法進行呼叫並執行。總結來說系統呼叫用於與操作系統，訪問底層資源和服務，而函式呼叫用於組織和執行應用程式。兩者在目的、用途和實現方式上都有不同，但在軟體開發中都有重要的功能。課本2.7.3 Implementation最後三段的重點 --- 低階的kernel可能會用組合語言或C語言撰寫，高階的可能用C和C++ 撰寫，大多數Android系統函式庫都是用C和C++ 編寫的。使用高階語言來實現作業系統的優點：可以編寫得更快、更緊湊，並且更容易理解、更容易移植到其他硬體，例如小型嵌入式設備、Intel x86系統等等。使用高階語言來實現作業系統的缺點：速度降低、儲存要求增加，但現代的編譯器可以執行複雜的分細、具有深度管線還有多個功能單元，這不是很大的缺點。作業系統主要效能改進是更好的資料結構和演算法的結果，而不是更好的組合語言程式碼。利用分層方式(layered approach)設計的分層作業系統，簡單描述這種設計方式以及說明這種結構的優缺點。 --- 定義 1.採取Top-down切割系統功能/元件 2.上層能呼叫下層功能，反之則不行 3.使用Bottom-up測試、除錯(防止下層能構呼叫上層) 4.將OS切成N層，最底層layer 0是硬體，最頂層layer N是使用者介面，第n層的執行能力來自的n-1層提供的服務，也只關心第n-1層所發生的錯誤，沒有複雜牽扯的干擾優點 1.降低設計複雜度(分解成多個子系統將原系統的複雜度縮小) 2.有助於分工(每個子系統都有特定功能) 3.debug和維護容易(能修復單個元件而不須更動其他地方) 缺點 1.層次沒有明確的規範(難以排序，沒有一定的相依性) 2.層次太多會造成效能較差，user program需透過多層才能達到OS服務 OS帶有三種protection, CPU, memory, 以及I/O, 1.說明它們的任務為何? 2.它們是在以下的哪一個階段導入OS? multi-programming, simple batch, time-sharing --- OS帶有三種protection, CPU, memory, 以及I/O, 1.說明它們的任務為何? ANS: CPU PROTECTION: cpu protection確保每個process不會無限期的持續占用cpu,進而導致其他process分配不到cpu時間。每個process應該都要有一段時間執行他們的指令,而不會只有一個process從頭到尾獨佔資源; 為了解決這個問題我們會使用計時器來限制每個process使用cpu的時間，當定時器時間一到,便會向process傳送一個訊號告訴他釋放cpu,將cpu交給下一個process。 MEMORY PROTECTION: 記憶體保護是當記憶體中有兩個或多個process,並且有一個process可能存取另一個process記憶體的情況發生的時候, 這時候我們會使用兩個暫存器分別是:Base register和Limit register Base register用來儲存程式的起始位址, Limit register則用來儲存process的大小。這樣做是為了確保每當process想要存取記憶體時，os都可以檢查該process想要存取的記憶體區域是否有權被該process存取。 I/O PROTECTION: 透過 I/O 保護，作業系統可確保process永遠不會執行以下操作： 1.終止其他process的 I/O:一個process不應該能夠終止其他process的 I/O 操作。 2.查看其他process的 I/O: 一個process不應該能夠存取其他process從磁碟讀取/寫入的資料。 3.防止User Program在執行時，直接使用I/O Device。User Program必須透過OS提出I/O Request，再由OS控制I/O運作,並將I/O Result告知User Program。執行流程：發出 I/O Request，即System Call，會伴隨一些Trap，以轉換Modes執行相對應的I/O服務 I/O回傳結果給OS,OS再將結果回傳給User Program 2.它們是在以下的哪一個階段導入OS? multi-programming, simple batch, time-sharing ANS: multi-programming時期說明課本66頁，Unix 的三個system calls : fork( ), exit( ), wait( )的用途 --- l fork(): 產生一個新的行程，為當前行程的複製，稱為子行程。Unix系統需要產生新的行程時，先依靠fork()產生新行程，再用exec()使子行程被新的程式所覆蓋。 l 可使用fork()的回傳值來判別當下為父行程(正值)或子行程(0)以及fork是否成功(失敗為負值)。 l exit(): 當一個行程結束，或是遇到不正常的訊號、例外時，子行程就會呼叫exit()，並向父行程發送SIGCHLD的訊號。 l wait(): 有時候父行程需要等待子行程結束執行，這時父行程呼叫wait()；等到收到SIGCHLD後再繼續執行。雙擊桌面的簡報檔, 帶出了powerpoint程式. 請問這樣的過程引發了那些系統呼叫? 請舉出三個 --- createProcess(), open(), read() 呼叫createProcess來啟用新的process。(想要在程式中啟動另一個執行檔時，使用createProcess來進行執行檔的路徑和其他行程參數的設定。) 呼叫open來開啟檔案。(讀取檔案中的資訊，決定如何開啟檔案。) 呼叫read來讀取檔案內容。(通常與open同時使用，先使用open開啟文件，然後使用read從文件中讀取資料。) 請說明課本2.7.3 Implementation, 81頁最後三段的重點 --- 低階的kernel可能會用組合語言或是C語言編寫，高階的可能用C和C++編寫，大多數Android系統函式庫都是用C和C++編寫的。使用高階語言來實現作業系統的優點:程式碼可以邊寫得更快、更緊湊，並且更容易理解、更容易移植到其他硬體，例如小型嵌入式設備，Intel x86系統等等... 使用高階語言來實現作業系統的缺點:速度降低、儲存要求增加，但這並不是很嚴重的缺點。現代編譯器可以執行複雜的分析、具有深度管線還有多個功能單元，優點遠大於缺點。作業系統主要效能改進是更好的資料結構和演算法的結果，而不是更好的組合語言程式碼。第三章 === 介紹Linux的task_struct, 挑選兩個有興趣的fields說明之. 這個結構佔據了多少bytes?(先選定kernel 版本,找到source code) --- Q1: 介紹 Linux 的 task_struct，挑選兩個有興趣的 fields 說明之。 A1: 我們選擇的是 v6.5.7 的版本，source code 在此：https://elixir.bootlin.com/linux/v6.5.7/source/include/linux/sched.h 我們想要介紹的兩個 fields 分別是： * 1. (long) state: state 就是它字面上的意思，是用 2 的次方在存（即 2^x），這樣存的優點是可以使用 OR('|') 來組成新的 state，又或是可以使用 AND('&') 來進行測試（？）。 ``` 可以參考以下例子： #define TASK_RUNNING 0 #define TASK_INTERRUPTIBLE 1 #define TASK_UNINTERRUPTIBLE 2 #define __TASK_STOPPED 4 #define __TASK_TRACED 8 /* in tsk->exit_state */ #define EXIT_DEAD 16 #define EXIT_ZOMBIE 32 #define EXIT_TRACE (EXIT_ZOMBIE | EXIT_DEAD) /* in tsk->state again */ #define TASK_DEAD 64 #define TASK_WAKEKILL 128 #define TASK_KILLABLE (TASK_WAKEKILL | TASK_UNINTERRUPTIBLE) #define task_is_stopped(task) ((task->state & __TASK_STOPPED) != 0) ``` * 2. (struct task_struct) *real_parent: real_parent 這個指標會指向其 parent_process 若創建它的 parent_process 已不再存在（即 terminated），則此指標指向 PID 為 1 的 init process。 Q2: 這個結構佔據了多少 bytes？ A2: Around 1.7 kilobytes on a 32-bit machine. There may be some discrepancies based on version differences. 課本習題3.1, 說明Figure 3.30, LINE A的輸出結果? --- 右下圖為圖3.30 設全域變數value=5,使用fork()系統呼叫產生,產生新的行程,新行程(子行程)的fork傳回碼為0,非零的行程傳回原父行程(為兩個相同程式碼的併行行程) 所以程序當pid==0先運轉子程序,使value加成為20;後因pid非零(整數值),子程序執行exec(),或是父程序藉由wait()系統呼叫等待子程序完成並當完成時結束子程序exit()系統呼叫,把控制權轉回父程序,後列印出 PARENT value = 20 結束程序 (圖代補) 行程狀態圖, 由running 到 ready的事件標示著"interrupt" (process.pptx, page 6), 這個事件與InterruptBasic.pptx 討論的 interrupt 有何關係? (完全一樣, 完全不一樣, ...) --- 不太一樣，即便英文相同，但從觸發條件到中斷處理的過程都不一樣。前者透過計時器來定期中斷目前正在運行的process。然後中斷處理程序(interrupt handler)呼叫作業系統調度process來確定是調度另一個process還是繼續運行。如果調度程序決定運行另一個process，則當前的process就從running state轉換到ready state。後者透過其他硬體或外部事件觸發中斷，如：硬碟讀寫、I/O操作、鍵盤輸入。 CPU執行完當前指令後檢查到interrupt發生，儲存當前process的狀態，從PIC接收Interrupt Number。再去IDT找對應的ISR，保留暫存器空間並執行ISR。結束後傳送EOI command給PIC並恢復暫存器空間。再透過IRET回到中斷點。說明什麼是context switch？ --- * CPU在執行時，只能運用一個process，如果切換給另一個process時，須將舊process的相關資訊用PCB 儲存起來，並載入新process在PCB的相關資訊，此過程稱context switch。哪些事件會引發context switch? --- * 中斷處理：在接受到中斷（Interrupt）的時候，CPU必須要進行context switch。 * 多工：在先佔式多工(Preemptive multitasking)中，每一個process都將輪流執行不定長度的時間段落。如果process並非自願讓出CPU(例如執行I/O操作時，process就需放棄CPU使用權)，當時限到時，系統將產生一個定時中斷，作業系統將排定由其它的process來執行。此機制用以確保CPU不致被較依賴處理器運算的process壟斷。說明context switch 所花費的時間，由哪些因素決定？ --- * 通常因CPU內部的記憶體速度、有多少內容必須被複製、有多少特殊指令等，即硬件影響context switch所需時間。說明”context switch time is pure overhead”這句話的含意 --- * Context switch對於時間是純粹的開銷 * 此句話在表達會造成額外的效能浪費，在切換process時，對於CPU來說是沒有效用的，當多次的切換疊加時，將導致系統效能下降。 * 總結:Context switch是對系統資源的浪費，它額外消耗了時間、算力，降低了系統的效能。更導出對於Context switch優化的重要性。 CPU scheduler 和 process schedler的使用目的與時機 --- * CPU scheduler 的目的是在多程式系統中，讓 CPU 能夠有效地利用，避免任何一個 process 佔用 CPU 的時間太長。CPU scheduler 會根據不同的因素，例如 process 的優先權、CPU 使用時間、I/O 需求等，來決定哪個 process 可以使用 CPU。 * Process scheduler 的目的是在多程式系統中，讓所有 process 都能有機會使用 CPU。Process scheduler 會根據不同的因素，例如 process 的到達時間、資源需求等，來決定哪個 process 可以被加入到就緒狀態的佇列中。使用時機 * CPU scheduler 會在每一個 CPU 週期結束時，或是在 process 需要放棄 CPU 時，進行一次調度。 * Process scheduler 會在 process 被創建時、process 完成 I/O 操作時、或是 process 發生異常時，進行一次調度。 program, process與thread的差異 --- * 程式 (Program)：程式是指由一系列指令組成的文件或軟體。它是靜態的，通常以可執行檔的形式存在，並被存儲在硬碟或其他儲存裝置上。舉例來說，一個應用程式的執行檔就是一個程式。 * 進程 (Process)：進程是指正在運行的程式的實例。它是作業系統分配資源的基本單位，包括記憶體、處理器時間和檔案和裝置的存取權。每個進程都有自己的位址空間、資源和狀態。不同的進程之間是獨立運行的，彼此不會互相干擾。 * 執行緒 (Thread)：執行緒是進程中的執行單元，它是一個輕量級的執行序列。一個進程可以包含多個執行緒，這些執行緒共享該進程的資源，如記憶體和檔案處理。執行緒之間共享記憶體空間，能夠更有效地進行通訊和資源共享。比較： 1.程式是靜態的指令集，而進程是程序的執行實例。 2.進程是作業系統資源分配的基本單位，而執行緒是進程中的執行單元，能夠更有效地利用資源並提高效率。不同的進程之間是獨立運行的，而 3.同一進程中的執行緒是共享資源的，因此需要注意同步和互斥問題。 Process的結束方式分為兩種，結束小孩還是結束父母，說明結束父母時所需要的指令即結束方式。 --- * A: 結束父母可以分為以下兩種情況： 1. 被動終止：在這個情況下，這個 process 是被 kill() system call 或是 kill 指令來殺死的，而這需要該 process 的 PID。而默認的終止訊號通常是 SIGTERM(15)，但若 process 不理會此訊號的話可以使用更強的強制終止訊號 SIGKILL(9)。 2. 主動終止：在這個情況下，process 是執行完所有它該做的事並使用 exit() system call 來結束自己。而當 process 使用 exit() system call 時，operating system 會 deallocate 這個 process 所使用的 resource。做context switch的情況裡面(除了interrupt)其中兩個，並說明一下嗎? --- 分別為多工(Multitasking)以及使用者模式和核心模式交換(User and kernel mode switching): * 多工(Multitasking):最常見的是，在某些排程大綱(scheduling scheme)中，必須將一個程序切換出 CPU，以便另一個程序可以運行。當程序自己無法運行時，上下文切換(context switch)將被觸發，例如透過等待 I/O 或同步操作完成。在先佔式多工作業系統(pre-emptive multitasking system)上，排程可以切換至仍可運行的進程。為了防止其他行程缺乏 CPU 時間，先佔式排程通常會配置計時器中斷，以便在程序超過其時間片時觸發。此中斷確保排程將獲得執行上下文切換的控制權。 * 使用者模式和核心模式交換(User and kernel mode switching):當系統在用戶模式和核心模式之間轉換時，不需要上下文切換；模式轉換本身並不是上下文切換。然而，根據作業系統的不同，此時也可能發生上下文切換。舉例並說明Process State的每個state在做什麼，以及什麼情況下會切換state？ --- New：當process被創建時，將code讀到記憶體中，並將前述記憶體狀態初始化 Ready： Process 競爭的資源是 CPU 的核心，管理的方式為佇列 (Queue)，在等待被執行的階段，會被放在佇列當中，此狀態稱為 Ready Running：被CPU排程選到，執行instructions。OS為了確保主控權，一段時間就會將CPU switch給scheduler 而打斷(interrupt)程序 Waiting：有些指令不會直接使用CPU (如 I/O)，因為不需要CPU，又需等待某些指令完成，所以進入Waiting狀態，待完成後重新放回Ready Terminated: Process完成執行，釋放資源給OS。 Admitted: 當該process準備好被執行，OS會分配資源給該process，就會轉跳到Ready階段。 Scheduler dipatch: 當CPU可以執行下一個process時，OS會根據scheduling algorithms，在Ready queue裡抓取要進行的process。 Interrupt: 當CPU位置被OS搶占，例如有個更高權限的process在Ready queue中，OS會打斷現在的process，讓正在執行的process回到Ready queue。 I/O event wait/completion: process可能在等待使用者輸入，process會到Waiting State，等待輸入結束後，會回到Ready queue中。 Exit: 當process被完成或被OS中止，會到Terminated State。如果兩個行程要互相聯繫，它們之間會存在一個通訊鏈（Communication link）。請比較三個通訊鏈操作方法的差異並且說明他們的定義。 --- 直接或間接溝通(Direct or Indirect Communication)：直接溝通(Direct Communication)： · 直接通信，無需任何中介或中央樞紐。 · 通常用於需要低延遲、高效率通訊的場景。間接溝通(Indirect Communication)： · 通訊需要使用中介或中心樞紐 · 通常用於需要集中協調或路由的場景。同步或異步通信(Synchronous or Asynchronous Communication)：同步通訊(Synchronous Communication)： · 發送者和接收者時間(real-time)同步的通訊方式。 · 通常用於即時或即時互動。異步通信(Asynchronous Communication)： · 不需要雙方及時同步。 · 流程將會有所延遲。自動或明確緩衝(Automatic or Explicit Buffering)：自動緩衝(Automatic Buffering)： · 系統在傳遞或接收之前自動儲存資料或訊息。 · 可以處理發送者和接收者之間不同速度的通訊。顯式緩衝(Explicit Buffering)： · 系統需要手動執行緩衝區管理。 · 發送方和接收方需要管理緩衝區中的儲存和資料。為什麼作業系統中需要使用 cooperating process，他又是怎麼在不同 process 之間進行資料共用的？ --- cooperating process是任何與能影響其他行程，或是會受到其他行程影響的行程以下是作業系統中需要需要使用 cooperating process的原因 •資訊共享(Information Sharing): 數個使用者可能對相同的一項資訊(例如，複製和貼上)有興趣，因為不同user會透過不同的process來存取資料，所以需要process之間需要溝通和合作。 •加速運算(Computation Speedup): 可以透過平行程式，讓很多process來解決同一個問題，因為解決的是同一個問題，當中難免會需要溝通。但是需要電腦擁有多個處理核心才能達到加速的效果。 •模組化(Modularity): 把系統分成一塊塊的模組，再讓模組之間溝通，以達成目的。ex: microkernel OS(把所有的component都丟到User space，透過IPC做溝通) •方便性(convenience):若是提供一個環境，使process可以互相合作溝通，可以讓使用者在同時進行多項工作時，這些工作可以同時順利進行，並且不會產生衝突。請問shared memory與message passing的定義和比較? --- **shared memory共享記憶體：** * process之間共享一部分的記憶體(共享變數)，透過存取記憶體達到彼此溝通、交換資訊的目的。利用write資料(producer把資料放進buffer內)和read資料(consumer去同一個buffer把資料取出來)來完成資訊交換。 **message passing訊息傳遞：** * process間會建立連接通道來溝通，過程為：建立連接通道→互傳訊息→傳輸完畢，中斷連接通道。而通訊方式也分成兩種：直接傳遞、間接傳遞直接傳遞：指定溝通的對象，所以必須知道資料要送給誰以及接收了誰的資料，因此系統可以很明確地知道誰跟誰之間必須要有連接通道。由此可知直接傳遞的連接通道是自動建立，具有One-to-One的特性，且通常為單向通道。間接傳遞：資料在mailbox中，傳送方只負責將資料傳送到mailbox，而需要資料的接收方自己要去mailbox拿，因此傳送方不知道接收方是誰，接收方也不知道傳送方是誰。由此可知間接傳遞必須先建立mailbox，才能建立連接通道，具有Many-to-Many的特性，而可能是單向也可能是雙向通道。 * 比較shared memory和message passing：溝通方式：shared memory透過共享變數存取資料；messagepassing則是在process之間建立連接通道。共享性：在shared memory，所有的process皆可存取共享變數；在messagepassing，process間有專屬的連接通道，不會隨意被其他process共用。第四章 === 請簡單敘述multi-threading可以帶來哪些好處? --- 1.提升效率:在同一個程序(Process)中，建立多個線程同時執行任務，不同的線程可以同時執行不同的任務，藉此來提升效率。 2.資料傳遞:資料彼此傳遞相較multi-processing簡單，因為不同線程的 memory 之間是共用的 3.簡化複雜性：將程式拆分成多個線程可以使代碼更容易理解和維護，因為不同的任務可以分開處理請說明multiprocessing、multithreading兩者的差異，並各舉一個例子 --- multithreading為多執行緒平行運算是透過 context-switch 的方式實現 multithreading為多執行緒平行運算是透過 context-switch 的方式實現各執行緒彼此共用相同的資料空間有機會讓相同的工作在比較短的時間內完成較適合處理資訊共用的任務 multiprocessing為多核心平行運算每個核心都有各自的資料空間如果要互通資源比multithreading耗時由於每個 Process 都需要一些資源來工作所以會比 multithreading 更消耗資源可以在相同的時間內完成較多的工作較適合處理資訊獨立的任務應用實際例子: 程式運行效率與CPU密切相關(瓶頸在計算)multiprocessing 程式需大量資料交互(ex爬蟲)(瓶頸在I/O)multithreading 在 multithreading 中，如果process 內的 thread 呼叫 fork() system call，則新的 process 是要重複所有 parent process 的 threads，還是只有一個 thread？ --- 一般來說，fork()做出來的新process的parent不會是一個thread，而是一個process。所以當process裡的其中一個thread在呼叫fork()後會複製parent process裡面的所有threads。但除了呼叫fork()的那個thread以外的threads都不會做事。 Multithreaded programming帶來的好處之一是responsiveness, 請說明responsiveness的含意請設計一個場景來展現Multithreaded programming帶來的好處(responsiveness) 此場景之下，請逐步說明Multithreaded programming的運作情況沒有Multithreaded programming的時候，又會如何運作 --- 1.請說明responsiveness 的含意 Responsiveness 在中文課本裡翻譯為「應答」，但比較多人稱他為「響應」，也就是程式對使用者互動所做出的回應。Multithreaded programming帶來的好處為增加對使用者的響應。一個應用程式（行程）可以產生多個執行緒來執行任務，即使其中某個執行緒暫停運作，或是在處理需要花費長時間的操作時，其他執行緒還可以繼續執行，進而提高響應速度，不會使整個行程陷入等待、無法回應使用者操作的問題。 2.請設計一個場景來展現Multithreaded programming帶來的好處(responsiveness), 場景如:Multithreaded file download，假設有兩個threads，第一個thread負責下載文件的前一部分，第二個thread負責同時下載文件的後一部分，用戶可以在文件下載過程中立即開始使用部分已經下載的文件，而不需要等待整個文件完全下載。 3.此場景之下，請逐步說明Multithreaded programming的運作情況, step1.用戶啟動下載 step2.創建兩個或多個threads：應用程式創建兩個或多個threads，每個thread有其特定的工作。 step3.分割文件：在多線程下載的情況下，文件通常會被分為幾個部分，每個部分由不同的下載線程處理。 step4.合併部分文件：當每個下載線程完成其工作並將部分文件保存後，應用程式將這些部分合併成一個完整的文件。 step5.即時反應和使用：一旦有足夠的文件數據下載完成，用戶可以開始使用文件的一部分，而無需等待整個文件下載完畢。這提供了即時反應和更好的用戶體驗。 step6.下載完成：當所有下載線程完成其工作並且文件合併完成後，用戶可以繼續使用整個文件。 4.沒有Multithreaded programming 的時候，又會如何運作若無Multithreaded programming，在下載文件時，文件的前一部分若檔案超級大，則需要花費大量時間等待下載，而在下載期間使用者無法進行任何操作，必須等待下載完成後才可進行下載第二部分文件的操作。說明process affinity 什麼樣的環境需要考慮process affinity --- 1. Process affinity 是一種允許進程或執行緒綁定到特定 CPU或CPU範圍的技術。這可確保進程或執行緒僅在指定的CPU上執行，而不是在任何CPU上執行。它也稱為CPU pinning 或 cache affinity。該技術可用於透過減少快取未命中等降級事件來提高中斷很少的 CPU 密集型流程的效能。但是，它可能會減慢普通程式的速度，因為它們需要等待 CPU 再次可用。 2. 假設情況下，作業系統在任何可用的 CPU 上調度進程和線程，當多個應用程式競爭 CPU 時間時，這可能會導致效能問題。處理器親和性(process affinity)可以減少資源競爭的可能性並提高應用程式效能。另外，其允許將 CPU 資源專用於即時處理等任務，同時在單獨的 CPU 上執行其他任務。 CPU密集型應用程序：當應用程序需要大量的 CPU資源來執行計算密集型任務時，使用處理器親和力可以確保這些任務能夠在特定的CPU上執行，從而提高性能。即時應用程序：即時應用程序需要確保在特定時間內完成任務，並且需要預測性能。處理器親和力可用於確保這些應用程序能夠在特定的CPU上運行。多核系統：當使用多核CPU的系統時，處理器親和力可以協助優化多線程應用程序的性能，使它們能夠更有效地利用不同核心。口頭說明thread的基本概念(還是要在討論區回答, 但是報告時請別參考)。對於資工系的學生而言，該具備哪些"thread的應用"的知識？ --- 什麼是Thread？ Thread（線程，執行緒）它是操作系統進程（Process）的基本執行單元，用於實現多任務處理、並行處理和多核處理器的利用。 Thread的優勢：並行處理：多個Thread可以同時執行不同的任務，從而實現並行處理，提高系統性能。效率：比起建立新的進程（Process）,建立新的Thread的速度更快，因此能夠更有效地利用資源。共享資源：Thread可以輕鬆共享進程（Process）的資源，例如記憶體和文件。而且一個Thread可以處於不同的狀態，如（Ready）、（Running）、（Waiting）等狀態。操作系統根據狀態來調度Thread的執行。既使只有一個CPU，一個core，採取multi-process的方式仍然會比採用single process的方式有效率。請舉出一個實例說明，你認為最關鍵的因素(請給一個名詞)是什麼? --- 1.以圖像處理程序舉例: 前提:你的圖像需要一些複雜的處理，且有多張要處理 multi-process: 雖然一次只能執行一process，當一個process在等待I/O時，可以切換到另一個準備進行的process。這樣就會比起只能順序執行的single-process更有效率的使 2.並行(concurrency): 並行的主要概念是同一時間可以執行多個任務，但這些任務不必同時進行。在單個CPU或核心的系統中，並行通常通過快速的任務切換（context switching）來實現，這使得每個任務都有機會執行一段時間，然後切換到另一個任務，以便實現同時性和更好的資源利用率。說明並比較signal與interrupt的差異 --- Interrupt可以由CPU、硬體裝置或CPU指令發起。它們最終由CPU管理，CPU中斷當前任務，並呼叫kernel提供的ISR處理程序。 Signal可以由kernel或process發起。它們最終由kernel管理，kernel將它們傳遞到目標thread/process，呼叫通用操作（ignore, terminate）或process提供的signal處理程序。兩者的差異就在於溝通的對象不同，Interrupt可以被視為CPU和kernel之間的一種通訊方式，Signal則是被視為kernel和process之間的通訊方式。 thread被創建時會使用到哪些資源？它們與建立process時用到的資源的差異是什麼？ --- 創建執行緒(thread)時會使用到程式計數器、一組暫存器、及一個堆疊空間，並與和它同一個行程的其它執行緒共用程式碼區域、資料區域和作業系統資源(例如開啟的檔案)。建立行程(process)時則需指派一個行程控制表(process control block, PCB) 的大型資料結構，其中包含行程狀態、程式計數器、暫存器、記憶體映射、開啟檔案列表和環境變數等。 thread是CPU使用時的一個基本單位，是process的一部分，會共用process的部分資源，因此建立thread比建立process使用更少資源。請描述kernel是如何在kernel-level threads之間進行context-switch操作 --- 每個kernel thread都有其TCB(thread control block)來保存thread的狀態，包含stack,pc,以及其對應的process等等，TCB一般都儲存在OS kernel中執行流程: 當要進行thread context-switch時，執行流程與process context-switch類似 1. OS保存當前thread的狀態到其對應的TCB 2. OS根據演算法決定下個要執行的thread 3. OS將欲執行的thread所對應到的TCB內容載入到系統中 4. CPU開始執行該thread的指令其中，與process context-switch的差異為，thread須保存的資訊相對process來說較少，因此thread context swtich的速度會比process context switch來的快。請說明User threads 跟 Kernel threads 分別是什麼以及他們之間的比較 --- User threads: User threads是由 user 透過 threads library 進行控制，kernel不知道user threads之存在，他只把它們視為single-thread process 。 user-thread的管理不需要kernel介入干預。由於不由 kernel 控制，通常在創建及管理上會比較快，且在執行緒切換不需要kernel mode的特權。在User thread裡的每個thread都擁有自己的stack，但它們共用相同的地址空間。優點: thread之creation、context switching快速，成本較低缺點: (1) 若process內某條執行中的user-thread被block，則會導致整個process也被block，即使process內還有其他可用的threads。 (2) 由於User threads大部分是由單一核心執行，因此它們無法在多核系統上實現真正的並行執行。 Kernel threads: Kernel threads是直接由kernel支援，由 kernel 進行創建及管理，每個Kernel thread都代表一個可以獨立排程和管理的執行單元，kernel可以單獨處理每個執行緒，而不會受到其他thread的影響。在Kernel threads中，每個執行緒都有自己的stack和獨立的地址空間。優點: (1) process內某條執行中的kernel-thread被block，其他thread不會受到影響。 (2) Kernel threads可以在多核系統上實現真正的並行執行，所以可以更有效地利用可用的硬體資源。缺點: Thread的creation跟context switching比較慢，且開發成本較高。 User threads 跟 Kernel threads的比較: User threads Kernel threads It is implemented by the users It is implemented by the OS Kernel can’t recognize Kernel can recognize 實現User threads比較容易實現Kernel threads比較複雜 create and manage 比較快 create and manage 比較慢 Context switch花費時間少 Context switch花費時間多 share the same address space have their own address space 在Linux系統中提供clone()與fork()系統呼叫，請問兩者有何相異之處? --- fork()在修改記憶體空間資料時，父子行程為了避免因為資料干擾所造成的不穩定，行程會建立一份記憶體空間的副本 clone()則是在建立該呼叫時可以增加旗標來控制需要共享的資源，並且在修改共用資料的時候父子行程的資料會同步修改。