# CS:APP 第一章重點整理 - Introduction
contributed by < `JimmyLiu0530` >

###### tags: `CSAPP`

{%hackmd BJrTq20hE %}

- [課程錄影 (Fall 2015)](https://scs.hosted.panopto.com/Panopto/Pages/Sessions/List.aspx#maxResults=250&folderID=%22b96d90ae-9871-4fae-91e2-b1627b43e25e%22)
- [課程錄影(中英字幕)](https://www.youtube.com/watch?v=ScMxnXq6fbI&list=PLcQU3vbfgCc9sVAiHf5761UUApjZ3ZD3x)
- [課程介紹 (Spring 2021)](http://www.cs.cmu.edu/~213/schedule.html)

## 概述
CS:APP 在一開始利用所有新手程式員學的第一支程式，即在螢幕上輸出 `hello world`，來展示程式從被產出、執行、結束的過程，也幾乎都有點到了各章節的重點，因此接下來內容的範例幾乎都是以 `hello.c` 為主。

#include <stdio.h>

int main()
{
    printf("Hello, world\n");
    return 0;
}

我認為這樣的編排再好不過了，如此一來，能先讓讀者對於每個章節都有一個粗略的了解，而且章節間的連結性也藉由這支 hello world 的程式慢慢地浮現。

## 從 source program 到 executable program
### 編譯系統 (compilation system)
包括前置處理器、編譯器、組譯器、連結器等程式。

### 流程

**1. 前置處理 (preprocess)**
把 `#` 開頭的程式碼展開。像是 **#include <stdio.h>** 或是 **#define MAX 100** (macro)。

通常前置處理完後的副檔名為 `.i`。

**2. 編譯 (compile)**
將 `hello.i` 翻譯成 **assembly language** 程式, `hello.s`。

之所以翻譯成 assembly language 是因為這種語言不管在任何的高階程式語言、任何的編譯器都是通用的。

**3.組譯 (assemble)**
將 `hello.s` 更進一步翻譯成 machine language 指令並組裝，形成所謂的 **relocatable object program**, `hello.o`。

**4. 連結 (link)**
最後，因為 `hello` 會呼叫 `printf` 的緣故，所以需要將 `hello.o` 和 `printf.o` 連結起來，形成可執行檔 `hello`。

### 為什麼我們需要了解編譯系統的運作?

1. 優化程式效能
我們必須了解基本的內部系統運作原理，才能提升程式的效能。比如說
- `switch` 總是比 `if-else` 來的有效率嗎?
- `while` 總是比 `for` 來的有效率嗎?
- 利用`指標`存取陣列會比利用 `[]` 來的有效率嗎?
- 如果將值加總到區域變數，而不是加到 passed by reference 的引數，為什麼能夠減少迴圈執行的時間?

> 這些問題分別在第 3、5 以及 6 章一一的解答。

2. 了解連結時期的錯誤
這點尤其在建立大型程式時容易發生的錯誤。舉例來說，
- 靜態函式庫與動態函式庫的差異
- 為什麼一些連結相關的錯誤直到執行時期才出現?

> 這些問題分別在第 7 章一一的解答。

3. 避免安全性的漏洞
很多安全性上的漏洞其實都是因為程式人員缺乏基本知識，抑或是未謹慎地限制資料的量以及格式而造成的。為了避免這些漏洞，在第 3 章會提到 stack discipline 和 buffer ovewrflow 等議題

## 處理器讀取、執行儲存於記憶體的指令
通過編譯、組譯以及連結，最後形成可執行檔後，此檔案會被放在磁碟中。如果要讓程式執行，必須先把它讀取至記憶體中。在說明資料是如何從磁碟被讀取到記憶體之前，需先了解硬體架構。

### 硬體架構

**輸入/輸出匯流排 (I/O bus)**
元件間傳輸資料的通道，通常以一個 `word` 為單位傳輸。至於一個 `word` 的大小是多少，則取決於系統。在 32-bit 系統，一個 `word` 等於 4 bytes。

**輸入/輸出裝置 (I/O devices)**
系統與外部連接的方式，如上圖，有 4 個 I/O 裝置，滑鼠、鍵盤、螢幕以及磁碟(硬碟)。

每個 I/O 裝置都是透過 **controller** 或 **adapter** 與匯流排相連。兩者最大的不同在於組裝方式，前者直接在主機板上；後者則是吃主機板插槽的卡。不過兩者都是為了在匯流排與裝置間傳輸。

> 在第 6 、 10 章分別有磁碟和 UNIX I/O 的介紹

**主記憶體 (main memory)**
主要用來暫時儲存處理器執行期間的程式以及資料。實際上，主記憶體是由數個 DRAM 晶片所構成。不過我們也能把記憶體想像成一個 byte array。

> 在第 6 章有更詳細的介紹

**處理器 (processor/CPU)**
執行指令的核心。在 CPU 中，有一個暫存器叫 **program counter**，負責保存下一個指令的記憶體位址。

> 第 3、4、5 章都有與處理器相關的內容

### 執行 `hello` 程式


上圖顯示從 shell 輸入 `./hello` 的資料流。當輸入 **./hello** 時，shell 程式讀取這個字串進暫存器，並寫入記憶體中。


接著，當我們按下 enter 後，shell 知道我們輸入完成，因此會根據我們所輸入的命令去做相對應的事。在此，他會把可執行檔 `hello` 跟字串 `"hello world\n"` 從磁碟讀取到記憶體中。這邊我們利用 direct memory access (DMA) 直接把資料從磁碟讀取到記憶體，不經過處理器。
> 第 6 章有 DMA 的介紹


`hello` 機械碼又會從記憶體載入到暫存器，並從 `hello` 的 `main()` 開始執行。期間會先把欲輸出的字串載入到暫存器，再由暫存器傳送到輸出裝置顯示。

## 快取 (cache)
從上面的例子可以發現，程式執行需要大量的資料搬移，而這個搬移對於執行效率來說是有負面影響的，因此我們想辦法盡可能把資料搬移的時間縮短。又因為記憶體容量愈大，讀取速率愈慢，因此朝向**小容量**記憶體發展，於是有了快取。

快取說穿了就是一個小而快的記憶體，儲存一些處理器在不久的將來有可能使用到的資料。根據容量大小又可細分成 L1, L2, L3，彼此間的層級關係如下所示:


之所以可以預測哪些資料很快還會被用到，都是有賴於程式存取資料的特性，叫 **locality**。Locality 又可以分成:
1. spatial locality
- 若在這個記憶體位址的資料被存取，則與它相鄰的資料在將來很有可能也會被存取
- 像是陣列、程式碼
2. temporal locality
- 若這個資料現在被存取，則在將來很有可能會再次被存取
- 像是迴圈

> 詳細的介紹請見第 6 章。

## 作業系統 (operating system)
把作業系統想像成硬體跟使用者程式之間的一層軟體。它不僅保護硬體不被使用者程式破壞，還能為使用者提供一個簡單且統一的機制來操作硬體設備。

作業系統利用一些基本的抽象化 (abstraction)，像是行程 (process)、虛擬記憶體 (virtual memory) 跟檔案 (files) 分別針對處理器、主記憶體跟 I/O 裝置來實現上述的目標。

> In computer science, **abstraction** is a simplified version of something technical, such as a function or an object in a program.
> The goal of "abstracting" data is to reduce complexity by removing unnecessary information.
>
> [TechTerms - Abstraction](https://techterms.com/definition/abstraction)


### 行程 (process)
當在執行我們的程式時，對於其他也正在執行的程式是沒有感覺的，就好像目前只有我們的程式在執行的錯覺，之所以有這樣的錯覺都是有賴於行程這個抽象化的功勞。

行程就是執行中的程式的抽象概念。

當一個處理器要並行地 (concurrently) 處理多個程式時，也就是不同程式的指令會交織在一起執行，因此必須確保當輪到某程式執行時，它的一些內容 (PC、暫存器、記憶體) 要與上一次執行結束時相同，而確保這件事的機制叫做 **context switch**。


以 `hello.c` 的執行來說，會有兩個行程，`shell` 以及 `hello`。一開始當使用者在 shell 上輸入 `./hello` 時，只有 `shell` 行程在執行。當 `shell` 行程執行我們所輸入的命令，並得知我們想要執行 hello 程式後，觸發系統呼叫，將處理器還給作業系統。

接著，作業系統就會保存 `shell` 行程的內容，建立一個新的行程叫 `hello`，並把處理器給它。因為它需要將機械碼從磁碟複製到記憶體，會讀取磁碟，因此會觸發中斷 (interrupt)。

`hello` 行程終止後，作業系統恢復 `shell` 行程的內容，並將處理器交還給它，繼續等待下一個命令的輸入。

> 詳細介紹請見第 8 章

### 執行緒 (thread)
在現代的系統，一個行程實際上包含多個執行單元，稱作**執行緒**。
它是作業系統中進行==運算排程==的最小單位。同一個行程底下的執行緒彼此共用全部系統資源，像是記憶體、變數..等等，比行程間的資源共用簡單。執行緒也能有自己的空間 (stack、register)。

以聊天室 Process 為例，可以同時接受對方傳來的訊息以及發送自己的訊息給對方，就是同個 Process 中不同 Thread 的功勞。Thread 就像是工廠 (process) 內的工人，確保工廠的每項功能，並且共享工廠內的每一項資源。

> 有關並行以及如何寫出利用執行緒的程式，請見第 12 章

### 虛擬記憶體 (virtual memory)
與行程類似，當我們執行程式時，也是感受不到其他程式在使用記憶體，這是因為有虛擬記憶體的幫助。我們可以把實際的記憶體想像成下圖，稱為虛擬位址空間 (virtual address space)。
> 以 Linux 作業系統為例


這整個空間可以依照儲存資料類型的不同分成以下幾類:
- program code and data
- 存放程式碼以及全域變數的空間
- 這個區塊直接由可執行檔 (e.g. `hello`) 來初始化
> 第 7 章有更詳細的介紹
- heap
- 存放動態配置變數的空間
> 第 9 章有更詳細的介紹
- shared libraries
- 存放共享函式庫，像是 C 函式庫的空間
> 第 7 章有更詳細的介紹
- stack
- 編譯器用來實作含是呼叫的記憶體空間
> 第 3 章有更詳細的介紹
- kernel virtual memory
- 留給核心 (kernel) 的空間

### 檔案 (files)
檔案說穿了就是一連串的位元組 (byte)。每個 IO 裝置，包括磁碟、鍵盤、顯示器、甚至網路都可以算是一種檔案。對於所有不同的 IO 裝置，它提供了一個統一的看法。舉例來說，程式人員可以在不了解磁碟的硬體架構下，對它操作。

> 第 10 章有更詳細的介紹

## 透過網路與其他機器傳輸
如同我們在上面所說，網路其實也可以視為一種"檔案"。只是資料流不像我們習慣的從記憶體經過匯流排抵達磁碟控制器，再寫入磁碟；而是經過網路卡 (network adapter) 與外部網路 (e.g. Internet) 連接，抵達另一台機器。

一樣以 `hello.c` 為例，想利用 telnet 在遠端的機器上執行 `hello` 程式。

與 sever 建好連線後，登錄遠端機器並執行 shell，等待輸入命令。接下來的步驟如下圖:

> 第 11 章有更詳細的介紹

## 其他相關的重點
### Amdahl's Law
用來計算如果提升一些部份 ($\alpha$) 的效能至 $k$ 倍，則對整體系統而言會提升多少的公式。公式如下:

$S = \dfrac{1}{(1-\alpha)+\alpha/k}$

:::warning
若要有效地提升系統效能，提升的方法一定要是對**大部分**的系統有效才行，否則成效不彰。
:::

### 並行 (concurrent) 以及平行 (parallel)
#### Thread-level concurrency
在 1960 年代早期，出現了分時 (time-sharing) 的概念，藉由快速地在行程間切換，來達到並行。

直到今日，即使處理器需要在行程間快速切換，大部分的計算仍是由單個處理器完成，因此稱這樣的系統為單處理器系統 (uniprocessor system)。

自從 1980 年代，慢慢出現多處理器的系統 (multiprocessor system) 以完成大規模的計算。然而近年來，多核 (multi-core) 處理器以及超執行緒 (hyperthreading) 的來臨，也使多處理器的系統變得常見。

所謂**多核處理器**，就是一個 CPU 中有許多獨立的處理單元 (cores)。如下圖，這是一顆擁有 4 個獨立處理單元的 CPU，其中每個處理單元都有自己的暫存器、L1 以及 L2 快取，L3 快取則是共用。


至於**超執行緒** ( Hyper Threading / Simultaneous Multithreading ) 則指的是在 CPU 內部僅複製必要的資源 (如暫存器)，讓多個執行緒可在同個 cpu 上同時執行，其餘的硬體資源 (如 FPU、ALU、cache ) 皆為共享。簡單來說就是利用單核來模擬出多核的技術。
其目的是為了降低 cpu 閒置的時間，提升使用率。例如 Intel Corei7 處理器每個核都有 2 個執行緒。

Reference
- [Hyper-threading (wiki)](https://en.wikipedia.org/wiki/Hyper-threading)
- [What Is Hyper-Threading? (Intel)](https://www.intel.com/content/www/us/en/gaming/resources/hyper-threading.html)

::: warning
**多核處理器 (Multicores) vs 多處理器 (Multiprocessors)**

在釐清這兩個名詞之前，必須先了解什麼是 CPU?

CPU (a.k.a processor)，中文翻譯為處理器，包含許多元件，像是快取、指令解碼器、各種處理單元 (ALU、FPU 等等)。

- **多核處理器**
如上面所述，就是**只有一個** CPU 但裡面有許多獨立的處理單元 (cores)，允許處理器可以同時在不同的核上讀取且執行指令，像是計算、跳躍、讀寫指令。
> 至於處理單元包含哪些元件，這取決於實際的架構。

- **多處理器**
擁有**多顆**處理器 (CPUs)，每個處理器能各自執行自己的程式，因此允許**平行**執行，而且單一處理器壞掉不會影響其他處理器，因此也比較可靠。
另外，處理器間可以共享記憶體或是不共享。若採用共享記憶體，這些處理器使用相同的匯流排來存取記憶體，而且也只有單一的記憶體空間 (因為共享，所以處理器看到的記憶體應相同)。
若採不共享，則每個處理器都有自己的記憶體，如果需要用到其他處理器的資料時，則必須與處理器溝通。

| Multicores | Multiprocessors |
|:----------:|:---------------:|
| 執行單個程式較快 | 執行多個程式較快 |
| 可靠性較低 | 可靠性較高 |
| 整體佔的空間小 | 整體佔的空間大 |

這張圖能明顯的看出三種的差異:


Reference
- [What is the difference between MultiCore and MultiProcessor](https://superuser.com/questions/214331/what-is-the-difference-between-multicore-and-multiprocessor)
- [Difference between MultiCore and MultiProcessor System](https://www.geeksforgeeks.org/difference-between-multicore-and-multiprocessor-system/)

:::

#### Instruction-level parallelism
相較以往的處理器需要多個(通常 3-10 ) cycles 來執行一個指令，現代處理器能夠同時執行多個指令，即 Instruction-level parallelism。儘管單一個指令可能變成需要 20 個 cycles 才能完成，但是同一時間卻能容納 100 個指令在執行。

第 4 章會介紹 **pipeline**，它就是利用這種技術。
第 5 章也會介紹類似 pipeline，但是能得到大於 1 的執行速率 ( instruction per cycle ) 的 **superscalar**。

#### Single-instruction, multiple-data (SIMD) parallelism
在最底層，很多現代的處理器有一些特殊的硬體能讓單一指令變成可平行執行的數個操作。像是 Intel 和 AMD 的處理器提供能夠平行加總 8 對單精度浮點數的指令。通常這些指令都是用來加速圖片、聲音以及影像的處理。

> 第 5 章有更詳細的介紹