5 1 PPT in Operating system

在學習並行程式設計之前，我們需要先了解 Program 、 Process 、 Thread 的定義，這邊筆者舉一個簡單的例子:

當我們開啟 APP 時，APP 會被載入到 Memory 中，而執行中的 APP 在一般情況下僅有一個執行緒 (Thread)。

在上面的例子中，尚未執行的 APP 就是 Program，執行中的 APP 則是 Process。

Program

Program 在 Operating System 這門學科中並沒有太多的介紹，讀者可以把 Program 當成是可執行檔 (*.out, *.elf, *.exe...) 即可。

Process

考慮上圖，Process 在執行時，狀態會不斷的改變，Process 的狀態共有：

• new： Process 被初始化。
• running： 正在被處理。
• waiting： 等待某些條件成立，及 Blocked (待會兒就會提到)。
• ready： 等待作業系統處理，此時作業系統可能將運算資源交給 I/O 或是其他 Process 了。
• terminated： Process 完成執行。

記憶體配置

以 32 位元的電腦為例，每個暫存器有 32 個位元可以利用，這也代表它做多可以定址 4GB 的記憶體位置。

下圖反映了當作業系統運行時，RAM 是如何被分配的:

• Stack 存放函數的參數、區域變數等。

• Heap 記憶體擴充區，程式設計者可以運用 Heap 的空間讓程式在記憶體使用上有更多的彈性。以 C 語言為例，使用 malloc 時，便會從 Heap 分配出一段空間:

  #include <stdlib.h>
  // ...
  int* p = (int*)malloc(sizeof(int));
  

• Data

  • UBSS 又稱 bss segment (block started by symbol, bss)，包含未明確初始的 global 和 static 變數，當執行程式時會將其這區段的記憶體初始為零。那之所以把未初始化的在分隔到一區段的原因是因為，當程式存放在硬碟中的時候，沒有那個必要留空間存放這些未初始化的資料，只需要執行時去紀錄位置和所需大小，在 run time 的時候利用 program loader 分配。
  • IBSS 存放已正確初始化的 global 和 static 變數，當程式被讀進記憶體中時，這些值就會從執行檔被讀入。

• Text Text segment 存放最重要的東西: 可執行的機器碼 (也就是編譯組語後的結果，內容是一堆 0 和 1 )。

Process ID

為了方便追蹤每個 Process，作業系統會分配給每個 Process 一個獨立的 ID (又稱 Process ID)。此外 Process 也會有一個紀錄 Parent PID 的 PPID。

#include <unistd.h>
pid_t get_pid(void);
pid_t get_ppid(void);

Process Tree

Parent process 會建立 Children processes，而 Children processes 又可以建立自己的 Children processes 形成樹狀結構:

PID in PThread

再以 POSIX Thread 為例，可以用 pthread_self() 查詢 PID :

#include <pthread.h>
#include <stdio.h>
 
void* thread_func(void *arg)
{
    printf("thread id=%lu\n", pthread_self());
    return arg;
}
 
int main(void)
{
    pid_t pid;
    pthread_t tid;
    pid = getpid();
    printf("process id=%d\n", pid);
    pthread_create(&tid, NULL, thread_func, NULL);
    pthread_join(tid,NULL);
    return 0;
}

補充 1 : 你可能會問 get_pid() 與 pthread_self() 都會返回 PID 阿，那差別在哪? 答: POSIX Thread 是 User-level 的 Thread 而 get_pid() 可以查詢 Kernel-level 的 Process ID。 補充 2 : pthread_self() 的定義也可以在 Linux Programmer's Manual 中查到:

More details...

不只如此， Processes 還包含:

• Running State 前面已經提到:

  

• File Descriptors 該 Process 使用到的 File。

  注意!這裡的 File 是指檔案，而非文件。 在 UNIX 的設計中，所有東西都是檔案!

• Arguments - 一個存放參數的文字列表，不同的程式語言都有不同的參數代入方法，以 C 語言為例:

  #include <stdio.h>
  int main(int argc, char *argv[]) {
    printf("We have %d arguments:\n", argc);
    for (int i = 0; i < argc; ++i) {
      printf("[%d] %s\n", i, argv[i]);
    }
    return 0;
  }
  

  將上面的程式編譯過後並執行:

  gcc source.c
  ./a.out 1 2 3
  

  可以得到:

  We have 4 arguments:
  [0] ./a.out
  [1] 1
  [2] 2
  [3] 3
  

• Environment List 紀錄環境變數，如下圖:

  

Thread

Thread 是可被作業系統排程的最小單位，它被包含在 Process 中，一個 Process 可以擁有多個 Thread。

像是前面提到的 POSIX Thread 便可以讓我們撰寫具有多個執行緒的程式。

Thread 包含了以下內容:

• Thread ID
• Thread State
• Program counter
• Register set
• Stack

而在同一個 Process 中的 Thread 共享以下資源:

• Code section
• Data section
• OS Resources

圖片取自該連結。

User-level v.s. Kernel-level

常見的 User-level thread 有這些實作方法:

• Pthread
• Win32 Threads
• JAVA Threads

常見的 Kernel-level thread:

• Windows XP/2000
• Solaris
• Linux
• Tru64 UNIX

而兩者有以下差異:

• 前者由程式編寫者分配，後者由作業系統分配。
• 作業系統察覺不到 User-level thread 的存在。

舉一個例子，假設有兩個 Process 存在，前者有 3 條 Thread，後者有 2 條 Thread。 如果作業系統採取均勻分配處理器資源的話，在不同的 Case 下會形成巨大的效能差異:

• User-level thread 因為作業系統無法察覺 User-level thread 的存在，縱使兩個 Process 有不同數量的執行緒，仍只能分配到同樣的處理器資源。
• Kernel-level thread 2 個 Process 共有 5 條執行緒，在作業系統能察覺的情況下，Process 1 能獲得 3 x 20% 的處理器資源，Process 2 則獲得剩餘的 40% 處理器資源。

Thread 的優勢

無論是建立成本或是 Context switch 的成本，Thread 都比 Process 有更顯著的效能。 不過也因為在同個 Process 底下的 Thread 享有 Code section 以及 Data，若設計不良可能會造成 Race condition 以及 Critical section 的原因。對於這個部分，會在之後的議題做更詳細的介紹。

執行緒一定是越多越好嗎?

設計優良的多執行緒程式的確能榨出更多的處理器資源，但多執行緒程式在設計上需要特別小心，錯誤的設計可能會導致整個 Process 被 Block。此外，建立執行緒以及內文交換都是需要成本的，如果程式的功能非常單一、簡單，將其改寫成多執行緒程式有時候反而會造成性能下降!

Reference

• mropengate.blogspot.com
• SystemProgramming
• 並行和多執行緒程式設計