CS:APP 電腦系統:程式設計師的角度 第一章筆記

這是來自卡內基梅隆大學的優質課程，對底層系統的理解越深，對程式設計師來說只有百利而無一害。雖然一時半刻看不到有什麼成效，但未來的某些日子一定會覺得當初學了這些真是太好了

電腦名詞譯名

首先從hello world開始

以C語言來說，讓寫好的以下程式碼執行，需要經過如下步驟

#include <stdio.h>

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

The compilation system

多方合作最終產生可執行的program

為什麼要懂編譯的運作過程?

  • 優化程式效能: 尤其是C語言這種的古老語言，需要懂得編譯的過程是怎麼運作的才能使我們做更好的選擇。如今Java以及Python等新的語言都有一群高手在底層做各種優化，讓寫程式的我們可以免除很多麻煩與顧慮
  • 理解link-time errors: 當程式可以使用之前，需要把各個需要的library link起來
  • 避免安全漏洞

以上這些都會在未來的章節詳細介紹

系統常見的硬體佈局

Hardware organization of a typical system

先來大致看過就好，未來的章節會詳細說

Buses (匯流排)

  • 為部件傳遞bytes訊息
  • 通常傳遞固定大小，稱為words
  • 不同系統的words可能有不同的大小
  • 通常32位系統使用4 bytes，64位使用8 bytes words

I/O Devices

  • 系統連接外部世界的方式，例如滑鼠鍵盤
  • 通過controller或是adapter連接至I/O bus(controller是晶片組在主板上或是設備本身；而adapter是可插入主板插槽的card。他們的目的都是為了能夠在bus與device之間傳遞訊息)

Main memory (主記憶體)

  • 當處理器執行該程式時，存放程式執行時的臨時資料，包含程式以及其操控的數據
  • 通常包含一坨Dynamic random access memory (DRAM)晶片
  • 邏輯上，記憶體是一串Bytes陣列，每個陣列都有獨一無二的位址

處理器

  • CPU
  • interprets or executes在主記憶體中的指令
  • 核心是word-size storage device(或稱register)，名為program counter (PC)
  • 任何時候，PC都指向在主記憶體中的machine-language instructions
  • 只要系統運作中，處理器永遠都在執行PC所指向的指令，完成後更新PC指向下一個指令(指令不一定是記憶體中的連續下一個指令)
  • register file是一個小的儲存裝置，裡面包含一坨word-size registers
  • ALU (Arithmetic/logic unit)計算新的數據和位址
  • 以下是幾個常見的CPU operation
    • Load: 從主記憶體複製byte或是word到一個register，覆蓋該register先前值
    • Store: 從register複製byte或是word到主記憶體的某個位置，覆蓋該位置的值
    • Operate: 複製兩個registers的內容到ALU，對兩個words執行arithmetic operation，然後儲存結果到一個register，覆蓋register的先前值
    • Jump: 提取出指令本身，然後複製該word到Program counter，覆蓋PC先前值
  • 雖然架構簡單，但是現代的處理器使用複雜許多的機制來加速程式執行時間，詳細在之後章節會討論

執行hello程式

當我們在shell輸入./hello的時候，這幾個字會通過controller->I/O bridge->Bus interface->register->最後再到main memory，像下圖所示

Reading the hello command from the keyboard

當按下enter鍵的時候，shell就知道我們已經輸入完畢，接著就會自動執行hello這個程式，然後把其指令以及數據從硬碟複製到主記憶體，數據包含hello, world\n就會最終被印出來

期間，數據從硬碟到主記憶體是使用direct memory access (DMA)技術，不用經過處理器，像Figure 1.6所示

Loading the executable from disk into main memory

最終印出時，指令會從記憶體複製hello, world\n的bytes到register file最後再到display device，如Figure 1.7

Writing the output string from memory to the display

Cache (快取)大有用處

綜上所述，可以發現系統花很多時間在移動資訊，例如為了加載程式，需要把程式複製到主記憶體；為了處理器可以執行程式，指令需要從主記憶體被複製到處理器等等。以程式設計師的角度來看，這些無疑都是為”real work”增加負擔。因此，系統設計師的主要目標就是要讓這些複製的操作盡可能的變快

物理定律造成越大容量的設備讀寫速度越慢，但越快的設備同樣的容量價格越高昂，例如:

  • disk drive容量比主記憶體容量大一千倍，但處理器可能需要一千萬倍的時間去讀取disk drive，相對於主記憶體

隨著半導體的進步，處理器與記憶體之間的速度差異逐年上升，簡單來說就是讓處理器變快比讓記憶體變快更加簡單

為了應對這個巨大的processor-memory gap，系統設計師引入了cache memory，又小又快，存放著處理器短期內可能會需要的資料，如Figure 1.9，越上層的儲存設備存取速度越快

An example of a memory hierarchy

容量大小: L1 > L2 > L3

  • 他們都是static random access memory (SRAM)技術的產物
  • L3基本上存在於高性能電腦
  • locality是提升性能的關鍵，如何讓最常用的資料儲存在cache中是核心
  • Figure 1.9，每一層都是下一層的cache

作業系統掌管硬體

  • 回到hello程式，從頭到尾，其實程式都沒有直接存取滑鼠、鍵盤、主記憶體和螢幕等等的設備，全都是通過作業系統來達成溝通，如Figure 1.10所示，OS介於程式與硬體之間

Layered view of a computer system

作業系統這樣做有兩個目的:

  1. 保護硬體
  2. 提供應用程式一個簡單且統一的方式去操控各式各樣的硬體設備

為此兩個目的，OS用抽象化來達成，就像Figure 1.11

Abstractions provided by an operating system

  • Files是I/O devices的抽象
  • virtual memory -> main memory
  • processes -> processor

Processes

當我們在執行hello這個程式的時候彷彿沒有被打斷，整個系統都在為了執行它而工作，這個就是process的厲害之處，因為實際上是有多個processes同時執行。而通常processes會比CPU還多，所以沒辦法一個CPU執行一個process

  • 單CPU可以通過context switching的方式來切換process以達到多工處理的功能
  • context swtiching會儲存當前process的context然後restore the context of the new process，像Figure 1.12
  • 接下來的幾段章節會著重討論只有單CPU的uniprocessor system

Process context switching

當我們在shell process輸入完指令按下enter，shell會呼叫系統，讓OS儲存shell的context，建立hello process還有其context，讓hello process獲得控制權，結束後再restore shell context

Kernel是OS的一部分，常駐在記憶體中，當一個程式需要OS的協助的時候，例如讀取和寫入檔案，會執行system call指令把控制權交還給kernel，執行完操作後再交還給原本的程式。Kernel本身不是一個process，他是一坨code和資料結構被系統用來管理所有的processes

Threads (執行緒)

  • 現代系統中一個process常常包含很多thread
  • 越發重要，因為網路伺服器需要併發效能
  • 在threads之間傳遞訊息比processes之間簡單得多
  • 通常比processes更有效率

Virtual Memory (虛擬記憶體)

  • 讓process以為自己有main memory的專屬使用權
  • 對每個process來說，memory都長一樣，名為virtual address space，如Figure 1.13所示

Linux process virtual address space (The regions are not drawn to scale)

  • 最上層是給OS對每個process的通用data和code的空間
  • 往下層的都是process所定義的code和data
  • 地址由下往上遞增

Files

  • 一大串bytes，就這樣
  • 每個I/O設備包含硬碟、鍵盤、螢幕和網路等等都被模擬成file，系統中的input和output都是以寫入和讀取檔案來執行

用網路來和其他系統溝通

  • 網路可以被視為另一個I/O設備

A network is another I/O device

Using telnet to run `hello` remotely over a network

本章結語和重點概念

Amdahl’s Law

  • Gene Amdahl
  • 代表處理器並行運算之後效率提升的能力
  • 要顯著提升系統的效率，就一定要提升整個系統絕大部分的執行速度
  • $T_{old}和T_{new}$代表舊與新的時間
  • $\alpha$是占總時間的比例
  • $k$是提升多少係數

$T_{new} = (1 - \alpha)T_{old} + (\alpha T_{old}) / k = T_{old}[(1 - \alpha) + \alpha / k]$

可以得到加速$S = T_{old} / T_{new}$

Ex.

假設一個任務佔了某系統60%的時間($\alpha = 0.6$)，加快了係數3($k = 3$)，那套用公式就可以得到$S = 1 / {(1 - 0.6) + 0.6 / 3}$，$S = 1.67$，速度約提升1.67倍

即便提升60%系統部分的時間，加快的效果也不顯著，所以為了顯著提升，越大部分能提升越好，最好是整個系統都能提升係數k。上述例子如果改成整個系統提升k係數的話那可以直接提升5倍速度

Concurrency and Parallelism (並行性與平行性)

  • Concurrency: 一個系統有多個同時執行的活動
  • Parallelism: 用Concurrency來讓系統執行更快

Parallelism可以用不同程度的abstraction來包裝

Thread-Level Concurrency

  • uniprocessor system通過快速切換任務來達成concurrency
  • multiprocessor system同時使用多個處理器來並行，通常使用multi-core processors和hyperthreading

Categorizing different processor configurations

Multi-core processor organization

  • 多核之間共享高階cache以及main memory
  • Hyperthreading(超執行緒)有時稱作simultaneous multi-threading，允許單個CPU執行多個控制流，簡單來說就是一個核心多個thread，例如Intel Core i7每個核心都有兩個threads，所以四核心就會有八個threads

Instruction-Level Parallelism

  • 在更底層的abstraction
  • 現代處理器可以一次執行多個命令，一個clock cycle可以執行2~4個指令，雖然需要比較多的cycles(20)，但可以執行更多命令；以前(1978)一次只能執行一條命令，且需要多個clock cycles(3~10)
  • pipelining把指令切開成多個步驟，以達到並行的目的
  • superscalar(超純量)CPU架構可以讓一顆核心執行指令級並行的運算

Single-Instruction, Multiple-Data (SIMD) Parallelism

  • 在最底層，現代處理器有特殊的硬體讓單一個指令可以變成多個動作，藉此並行運算，這種模式就稱為SIMD parallelism

Abstraction是CS最重要的概念之一

  • 有了abstraction可以讓程式統一，進而讓不同硬體也能執行同一個程式，也能讓程式設計師在寫程式的時候不用把每個層級實際要做的事情都寫下來

Some abstractions provided by a computer system

電腦科學 > Computer Systems - A Programmer's Perspective
#Computer System
CS:APP 電腦系統:程式設計師的角度 第一章筆記
https://f88083.github.io/2024/02/14/CS-APP-電腦系統-程式設計師的角度-第一章筆記/
作者
Simon Lai
發布於
2024年2月14日
許可協議