CS

準備中

進程管理 進程與執行緒 1. 進程(process) 進程是資源分配的基本單位。 進程控制塊(Process Control Block, PCB)描述進程的基本訊息和運行狀態，所謂的創建進程和撤銷進程，都是指對 PCB 的操作。 2. 執行緒(thread) 執行緒又稱線程，是獨立調度的基本單位。 一個進程可以有多個執行緒，它們共享進程資源。 以瀏覽器(browser)為例，瀏覽器進程有很多執行緒，如 HTTP 請求(request)、事件響應、渲染。執行緒的並行處理(concurrent)使得瀏覽器中點擊一個新的超連結從而發起 HTTP 請求時，瀏覽器還可以響應用戶的其它事件。 3. 區別 擁有資源 進程是資源分配的基本單位，但是執行緒不擁有資源，而是訪問隸屬進程的資源。 調度 執行緒是獨立調度的基本單位，在同一進程中，執行緒的切換不會引起進程切換，從一個進程中的執行緒切換到另一個進程中的執行緒時，才會進行進程的切換。 系統開銷 由於創建或撤銷進程時，系統都要為之分配或回收資源，如硬碟中的記憶體、I/O 設備等，所付出的開銷遠大於創建或撤銷執行緒時的開銷。 同樣的，在進行進程切換時，涉及當前執行進程 CPU 環境的保存及新調度進程 CPU 環境的設置，而執行緒切換只需保存和設置少量暫存器的內容，開銷較小。 通訊 執行緒可以通過直接讀寫同一個進程中的數據進行通訊，但是進程的通訊需要借助 IPC(inter-process communication)。 進程狀態的切換 就緒就態(ready)：等待被調度 執行狀態(running) 阻塞狀態(waiting)：等待資源 只有就緒狀態和執行狀態可以相互轉換，其它的都是單向轉換。就緒狀態的進程通過調度演算法從而獲得 CPU Time，轉為執行狀態；而執行狀態的進程，在分配給它的 CPU Time 片段用完之後就會轉為就緒狀態，等待下一次調度。 阻塞狀態是缺少需要的資源從而由執行狀態轉換而來，但是該資源不包括 CPU Time, 缺少 CPU Time 會從執行狀態轉換為就緒狀態。 進程調度演算法 不同環境的調度演算法目標不同，因此需要針對不同環境來討論調度演算法。 1. 批次處理系統(batch system) 批次處理系統沒有太多的用戶操作，在該系統中，調度演算法目標是保証吞吐量和周轉時間(從提交到終止的時間)。 1.1 先來先服務(first-come first-served, FCFS) 非搶占式的調度，按照請求的順序進行調度。 有利於長作業，不利於短作業，因為短作業必須一直等待前面的長作業執行完畢才能執行，而長作業又需要執行很長時間，造成短作業等待時間過長 1.2 短作業優先(shortest job first, SJF) 非搶占式的調度算法，按估計運行時間最短的順序進行調度。 長作業有可能會永遠做不完，處於一直等待短作業執行完畢的狀態。因為如果一直有短作業到來，那麼長作業永遠得不到調度。 1.3 最短剩餘時間優先(shortest remaining time next, SRTN) 最短作業優先的搶占式版本，按剩餘運行時間的順序進行調度。當一個新的作業到達時，其整個運行時間與當前進程的剩餘時間作比較。如果新的進程需要的時間更少，則夠停當下進程，運行新的進程；否則則讓新的進程進入等待。 2. 交互式系統(time-sharing system) 交互式系統有大量的用戶交互操作，在該系統中調度演算法的目標是快速地進行響應。 2.1 時間片段輪轉(robin round scheduling, RR) 將所有就緒進程按 FCFS 的原則排成一個佇列，每次調度時，把 CPU 時間分配給佇首進程，該進程可以執行一個時間片段，當時間片段用完時，由計時器發出時鐘中斷，調度程序便停止該進程的執行，並將它送往就緒佇尾，同時繼續把 CPU 時間分配給佇首的進程。 時間片段輪轉演算法的效率和時間片段的大小很有關係： 因為進程切換都要保存進程的訊息並且載入新進程的訊息，如果時間片段太小，會導致頻繁地切換進程，導致時間浪費。 而如果時間片段過長，那麼實時性就不能得到保証。 2.2 優先級調度(priority scheduling) 為每個進程分配一個優先級，按優先級進行調度。 為了防止低優先級的進程永遠等不到調度，可以隨著時間的推移增加等待進程的優先級。 2.3 多級反饋佇列(Multilevel Feedback-Queue Scheduling, MLFQ) 一個進程需要執行 100 個時間片段，如果採用時間片段輪轉調度演算法，那麼需要交換 100 次。 多級佇列是為這種需要連續執行多個時間片段的進程考慮，它設置了多個佇列，每個佇列時間片段大小都不同，例如 1, 2, 4, 8,…。進程在第一個佇列沒執行完，就會被移到下一個佇列。這種方式下，之前的進程只需要交換 7 次。 每個佇列優先權也不同，最上面的優先權最高。因此只有上一個佇列沒有進程在排隊，才能調度當前佇列上的進程。可以將這種調度算法看成是時間片段輪轉調度算法和優先級調度算法的結合。 3. 實時系統(real time system) 實時系統要求一個請求在一個確定時間內得到響應。 分為硬實時和軟實時，前者必須滿足絕對的截止時間，後者可以容忍一定的超時。 進程同步 1. 臨界區 對臨界資源進行訪問的那段代碼稱為臨界區。 為了互斥訪問臨界資源，每個進程在進入臨界區之前，需要先進行檢查。 // entry section // crtical section; // exit section 2. 同步與互斥(synchronization and mutex) 同步(synchronization)：多個進程因為合作產生的直接制約關係，使得進程有一定的先後執行關係。 互斥(mutual exclusion, mutex)：多個進程在同一時刻只有一個進程能進入臨界區。 3. 號誌(Semaphore) 號誌，或稱信號量，是一個整數變數，可以對其執行 down 和 up 操作，也就是常見的 P 和 V 操作。 down：如果號誌量大於 0，執行 -1 操作；如果號誌等於 0，進程睡眠，等待號誌大於 0。 up：對號誌執行 +1 操作，喚醒睡眠的進程讓其完成 down 操作。 down 和 up 操作需要被設計成原語，不可分割，通常的做法是在執行這些操作的時候屏蔽中斷。 如果號誌的取值只能為 0 或者 1，那麼就成為了互斥(mutex)，0 表示臨界區已經加鎖，1 表示臨界區解鎖。 typedef int semaphore; semaphore mutex = 1; void P1(){ down(&mutex); // critical section up(&mutex); } void P2(){ down(&mutex); // critical section up(&mutex); } 使用號誌實現生產者-消費者問題 ...

作業系統 簡介 電腦系統主要可分成四個部分，或分成硬體(hardware)、軟體(software)、數據(data) 硬體(hardware)：為系統提供基本的計算資源。 中央處理器(central processing unit, CPU) 記憶體(memory) I/O 裝置 應用程式(Application programs)：定義資源如何用來解決使用者的計算問題。 使用者(users) 作業系統(Operating system, OS)： 作業系統(Operating system, OS) 是管理電腦硬體與軟體資源的電腦程式，同時也是電腦系統的核心與基石。 OS 最主要的兩個功能是： 資源分配：根據需求調配資源分配率(resource utilization)與效能(performance) 監控使用者程式的執行，避免不正常的運作造成對系統的危害。 一個標準的 PC 作業系統應該提供以下的功能： 行程管理(Processing management) 記憶體管理(Memory management) 檔案系統(File system) 網路通訊(Networking) 安全機制(Security) 使用者介面(User interface) 驅動程式(Device drivers) PC 基本特徵 1. 並行計算(Concurrent computing) Concurrent computing 是指宏觀上在一段時間內能同時運行多個進程，微觀上是交替發生的；而平行計算(parallel computing) 則指同一個時間內能運行多個指令。 平行計算需要硬體支持，如多線程(multi-thread)、多核處理器(multi-core processor)或者分散式計算機系統(distributed OS)。 作業系統通過引入進程(process)與線程(thread)，使程式能夠並行運作。 2. 分享(Sharing) 共享是指系統中的資源可以被多個並行進程共同使用。 有兩種共享方式：互斥共享(mutual exclusion)與同時訪問(time sharing)。 互斥共享的資源稱為臨界資源(critical resources)，例如印表機等，在同一時間內只允許一個進程訪問，需要用同步機制來實現互斥訪問。 3. 虛擬(Virtual) 虛擬技術把一個物理實體轉換為多個邏輯實體。 主要有兩種虛擬技術：分時技術(time sharing)、空間分享技術。 多個進程能在同一個處理器上並行處理使用了分時技術，讓每個進程輪流占用處理器，每次只執行一小個時間片段並快速切換。 虛擬記憶體使用了空間分享技術，它將物理記憶體抽象化為地址空間，每個進程都有各自的地址空間。地址空間的頁被映射到物理記憶體中，地址空間的頁並不需要全部在物理記憶體中，當使用到一個沒有物理記憶體的頁時，執行頁面置換演算法，將該頁置換到記憶體中。 4. 異步(Asynchronous) 異步指進程不是一次性執行完畢，而是走走停停，以不可知的速度向前推進。 基本功能 1. 進程管理(Process management) 進程管理、進程同步、進程通信、死鎖處理、處理調度等。 2. 記憶體管理(Memory management) 記憶體分配、地址映射、記憶體保護與共享、虛擬記憶體等。 3. 文件管理(File management) 文件儲存空間的管理、目錄管理、文件讀寫管理和保護等。 4. 設備管理(Equipment management) 完成用戶的 I/O 請求，方便用戶使用各種設備，並提高設備的利用率。 主要包含緩衝管理、設備分配、設備處理、虛擬設備等。 系統調用 如果一個進程在用戶模式(user mode)需要使用內核模式(kernel mode)的功能，就進行系統調用從而陷入內核，由作業系統代為完成。 Linux 的系統調用主要有以下這些： Task Commands 進程控制 fork(); exit(); wait(); 進程通信 pipe(); shmget(); mmap(); 文件操作 open(); read(); write(); 設備操作 ioctl(); read(); write(); 訊息維護 getpid(); alarm(); sleep(); 安全 chmod(); umask(); chown(); 內核與微內核 ...

準備中

C 當我們要去評價程式碼的品質時，我們會考慮以下元素： 正確性(correctness): 程式碼是否有正確的解決我們的問題 設計(design): 程式碼的好壞決定於它的效率與可讀性 風格(style): 程式碼在視覺上是否有良好的format 我們的第一個 C 語言程式： #include <stdio.h> int main(void) { printf("hello, world\n"); } 整合開發環境、編譯器、介面 IDEs, compilers, interfaces 在執行程式前，我們必須將程式碼轉變成電腦可讀的 binary codes，也就是 0 與 1。 IDE(integrated development environments) 可以協助我們開發、編譯程式碼。如Visual Studio Code 我們撰寫的程式碼為開源碼(source code)，我們必須將他轉變成機器碼(machine code)，才能被電腦執行。 編譯器(compiler)是將一種語言轉變成另一種語言的程式，例如將開源碼編譯成機器碼。 在 IDE 中，我們可以在一個叫作 terminal 的視窗中輸入指令。 terminal 提供了 command-line interface(CLI) 當我們輸入 make hello，會產生一個叫作 hello 的檔案，我們可以透過輸入 ./hello 執行它。 . 代表當下的目錄，上面的指令代表我們要執行當下目錄中叫作 hello 的檔案。 hello 即是內含機器碼的檔案。 欲刪除檔案可以用 rm 指令。 輸入 ls 列出當下目錄所包含的檔案。 若源碼檔經過修過，則必須重新編譯，才能對執行檔進行修改。 函式、引數、傳回值、變數 Functions, Arguments, Return Values, Variables printf("Hello, world"); 此處，介紹一個叫作 printf 的函數 f 代表 formatted 的字串。字串是多個字元(characters)組成的字詞，在 C 中，我們需要用雙引號("")來包住它。 括號 () 使我們可以輸入引數，也就是 printf 函數的 input。 最後，我們需要分號 ;，來宣告述句的結束。 其中，函式的一種產物叫作 side effect，也就是我們可以觀察到的變化，如螢幕印出字樣，或是發出聲響。 相比與 **side effects，我們也可以將函式的回傳值用於程式中，回傳值通被儲存於變數中。 string answer = get_string("What's your name? "); 此處，示範 CS50 IDE 中的一個函數。 這裡的 get_string為函式，而What's your name? 為引數。 然後，我們可以將回傳值存入到變數中，以上例，我們可利用賦值運算子(=)將右值(r_value)傳給左值(l_value)的answer。 最後，我們宣告變數的變數型別(type)。 如果我們嘗試將上述的變數改為其他變數型別，編譯器會顯示錯誤。 printf("Hello, world\n"); 我們此處為了換行，而使用了 escape sequence \n。

什麼是 Computer Science(CS)? CS 意在解決問題，更精準地說，是將問題 (input) 轉換成答案 (output) 的過程。 在計算機的世界，為了表達 inputs 和 outputs，我們必須將資訊標準化來儲存與操作它們，因為計算機只讀得懂 0 與 1 (開路/通路)。 如何表達數字? 在人類的世界，人們使用十進制(Decimal)。 在計算機的世界，用的是二進制(Binary)，也就是 0 與 1。 \(1+1=10\) \((1,2,3,4,5,6,7,…)_{10}=(001,010,011,100,101,110,111,…)_2\) 每個二進制的位元(digit)稱為 bit。 在現代計算機結構中，是由數以億計的電晶體(transistors)所組成的。 電晶體是一種具有開關(switch)性質的邏輯元件。 大部分的計算機一次用 8 個 bits，或稱 1 bytes，來表達數字。 \(8 \text{bits}=1 \text{bytes}\) 如何表達文字? 要表達文字，只需將不同的字元定義到對應的數字即可。 ASCII，American Standard Code for Information Interchange，即是一種基於拉丁字母的編碼系統，可應用顯示現代英語。 A->65, B->66, …etc a->97, b->98, …etc H->72, I->73, !->33, so HI!=72, 73, 33 在不同語言，有不同的字符，就必須定義新的編碼系統，來容納更多的字符。 如 Unicode。 如 emojo 顏文字也是一種字符。 如何表達顏色? 同理，可以把不同的數字定義給不同的顏色，其中最常見的就是 RGB 系統。 由紅綠藍色塊所組成。 紅、綠、藍又個別以 8 bits 儲存的 256 種不同層度的顏色強度表示。 一共由 24 bits 來表達，超過1百萬種顏色。 那圖案、影片、音樂呢? 圖案是由數以萬計的色塊(dots)所組成，在螢幕顯示器上我們稱作畫素(pixels)。 影片則是由連續的圖案經由連續播放所建構而成的。 音樂同樣可以用 bits 來表達，其中 MIDI 是一種用數字來表達音符的形式。 All are composed by 0 and 1 in the computer world. ...