# 程式設計師的自我修養(筆記、內容簡述)

## Ch1
簡介:本書涉及windows、linux兩系統上，應用程式在編譯、連結和執行時發生各種事項。
複習:
**1.2 SMP vs. Multi-core processor**

:pencil2: SMP:每個processor的工作能力相同、且每個processor都有對等的權力來存取資源。
優點:可靠度高、效能較好 缺點:OS的開發較為複雜
:pencil2:Multiprocessor System: 一個機器裡有很多個processor(CPU)
優點:throughput增加、可靠度增加、運算能力之擴充符合經濟效益(n顆CPU比n個機器相比成本較為便宜，因為communication time更少)
:pencil2:Multicore CPU: 一個CPU裡面有多chips
:pencil2:硬體間的差異:
Multicore CPU傳輸速度較快而且比較省電

**1.4 提高效能從三個方面下手1.CPU、2.I/O device、3.Memory**

1.Multiprogramming vs. Time-sharing
:pencil2:Multiprogramming sys: 允許多個Job(processes)同時執行，以提高CPU utilization。
作法:透過CPU scheduling技術達成(Ex:當執行中的process在waiting for I/O-completed時，把CPU 切換給另一個process執行，避免CPU idle，只要系統中有Job，CPU就不會idle。
:pencil2:Time-sharing sys: It’s a logical extension of multiprogramming system. 與Multiprogramming sys最大的區別在CPU切換頻率極高，會利用CPU排程來讓最需要的CPU的process先做，以達到縮短response time，這也叫做multitasking
2.OS怎麼管理硬體(GDI/DirectX/FileSystem)演變成後來的I/O Device 的Driver

**1.5 Memory分配所遇到的問題、怎麼解決**

電腦上的記憶體有限，如要分配給多個程式使用，容易遇到1位址空間不隔離、2記憶體使用效率低、3.程式執行的位置不正確，這些問題可由虛擬位址(virtual address)來達成。
:pencil2:Segmentation: 將一段程式所需要的記憶體空間大小的虛擬空間對應到某個位址空間，可以解決上述1.3的問題，但還是會發生2的狀況(external fragmentation)。
配置原則: (1) segment與segment之間可以是非連續性配置、(2)對每一個segment而言，必須占用連續的space
作法:OS會替每Process建立segment table紀錄每segment的limit、base
:pencil2:Page:把記憶體空間分成固定大小的frame，每一個frame的大小皆相同，可將程式視為一組page的集合(page size=frame size)。有可能會發生page fault
配置方式:採取非連續性配置，如果process大小等於n個pages則OS會在physical memory找出n個free frame (不一定要連續)，配置給process。
作法:OS會體每一個process建立一個page table紀錄每個page至於哪個frame的frame number

**1.6 Thread定義、存取權、排序、preemption vs. non-preemption、一些指令(fork()、clone()、volatile() )、synchronization(lock、semaphore、mutex、critical section、read-write lock)、thread model(one-one、one-multithread、 multithread-multithread)**

:pencil2:Thread: 又叫 lightweight process，建立一個thread會包含private部分(pc、register、steak、thread id state etc.) ，此外同一個process內不同的thread彼此共享此process的code section、data section、OS resource

:pencil2:Thread schedule:排程時最少會分成3種狀態(running、ready、wait)而現在比較主流的排程都帶有priority schedule、round robin的痕跡，在linux、windows還會把scheduler利用I/O bound thread、CPU bound thread作區別，long-term scheduler、short-term scheduler、middle-term scheduler

Round robin:在time sharing的系統下，會規定一個CPU time Quantum，當process取得CPU執行後，若未能在此Quantum內完成，timer會發出time out interrupt，通知os，回到ready queue裡找下一個process。

I/O bound thread:此類型的thread需要比較多的I/O資源，但用到比較少的CPU資源

CPU bound thread:此類型的thread需要比較多的CPU資源，但用到比較少的I/O資源

:pencil2:程序安全

※多個thread要存取同一個變數，很有可能每次做的結果都不同，造成錯誤，為避免此狀況發生，作業系統會提供一些API給使用者，讓使用者可以進行一些不可分割的操作，但仍無法解決一些比較複雜的情況，所以為了避免錯誤產生，而衍生了synchronization的機制。

:pencil2:Lock:在存取資源前先將資源鎖住，等到用完資源再將資源釋放。

:pencil2:Binary Semaphore:是一種最簡單的lock，thread要存取資源的時候，先取得semaphore，要執行時，semaphore--，如果semaphore>0表示還有資源可以使用，而要結束將semaphore+1，釋放資源。

:pencil2:Mutex: 跟Binary Semaphore很像，只是Mutex的初值有互斥控制用的性質，可以決定那些thread不要同時用到這份資源。

:pencil2:Critical Section: 是比以上方法更嚴格的手段，以上方法中，lock是可被其他thread存取的，而critical section的作用範圍只限於該thread內，其他的thread是無法存取他的lock，除此之外，critical section也具有和mutex相同的性質。

:pencil2:Read-Write Lock: 可以同時讀取，但不能同時讀寫或是同時寫入，在寫入的部分要互斥。
:pencil2:過度最佳化:(1)lock並不能確保multi-thread不會發生錯誤、(2)CPU的動態排程可能會使multi-thread執行的狀況下發生錯誤，但因CPU的亂序執行，還是有可能造成錯誤，而目前並沒有可移植的阻止換序的方法，所以CPU提供一個指令，通常叫barrier，用在CPU換序的過程中，攔截CPU將要保護的指令交換到barrier之後。

## Ch2

編譯的過程:有四個步驟1.前置處理、2.compile、3.assmebly、4.linking

**2.11前編譯(processing)主要做了什麼**

將hello.c和相關的header file，用前編譯器(cpp)，編譯成一個.i檔

前編譯的主要過程在於將.c檔中，以#為開頭的前編譯指令(ex:#include、#define)等，在compiler前先執行。

主要處理的將#define刪除，展開巨集、處理所有前編譯指令#if、#ifdef、#elif、#else、#endif、處理include，將相應的檔案插入該前編譯指令的位址、刪除所有註解、添加行號與名稱標示、保留所有#pragma編譯器指令。

$gcc –E hello.c –o hello.i
$cpp hello.c > hello.i

**2.12編譯的過程會做甚麼**

把前置處理完成檔案進行一系列的詞法分析、語法分析、語意分析、最佳化後產相應的組合語言程式碼檔(.s)。

$gcc –S hello.i –o hello.s
$ccl hello.c (Gcc提供ccl:將前編譯跟編譯合併成一個過程)cclplus 給c++用、jcl 給java用
$gcc –S hello.c –o hello.s

**2.13組譯做甚麼事**

組譯器是將組合語言程式碼轉變成機器可以執行的指令，根據組語指令和機器指令的對照表一一翻譯就可以了，每一個組語語句幾乎都對應一條機器指令。

$as hello.s –o hello.o
$gcc –c hello.s –o hello.o
$gcc –c hello.c –o hello.o

**2.2編譯器做了甚麼**

編譯的過程分成六個步驟:1.scan、2.語法分析、3.語意分析、4.原始碼最佳化、5.程式碼產生、6.目的碼最佳化

例:array\[index\]=(index+4)*(2+6)

**2.21詞法分析**

**2.22語法分析**

**2.23語意分析**

:pencil2:Complier可以分析的語意是靜態語意，靜態語意是指在編譯階段可以確定的語意，通常包含(宣告、type)，而動態語意只有在執行階段才能確定的語意。

**2.24中間碼檔**
以上是經過(source code optimizer)最佳化的語法樹，但在語法樹上直接做最佳化比較困難，所以會將整個語法樹轉換成中間碼(他是語法樹的順序表示)，經過轉換後，會變成x = y op z的格式(通常是三位址碼)

**2.25目的碼檔跟最佳化**

編譯器的後端主要包括code generator和target code optimizer。