Rain Hu's Workspace
Go back

[計算機作業系統] 進程管理

Rain Hu

進程管理

進程與執行緒

1. 進程(process)

2. 執行緒(thread)

3. 區別

  1. 擁有資源
    • 進程是資源分配的基本單位，但是執行緒不擁有資源，而是訪問隸屬進程的資源。
  2. 調度
    • 執行緒是獨立調度的基本單位，在同一進程中，執行緒的切換不會引起進程切換，從一個進程中的執行緒切換到另一個進程中的執行緒時，才會進行進程的切換。
  3. 系統開銷
    • 由於創建或撤銷進程時，系統都要為之分配或回收資源，如硬碟中的記憶體、I/O 設備等，所付出的開銷遠大於創建或撤銷執行緒時的開銷。
    • 同樣的，在進行進程切換時，涉及當前執行進程 CPU 環境的保存及新調度進程 CPU 環境的設置，而執行緒切換只需保存和設置少量暫存器的內容，開銷較小。
  4. 通訊
    • 執行緒可以通過直接讀寫同一個進程中的數據進行通訊，但是進程的通訊需要借助 IPC(inter-process communication)。

進程狀態的切換

process state

進程調度演算法

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)

2.2 優先級調度(priority scheduling)

2.3 多級反饋佇列(Multilevel Feedback-Queue Scheduling, MLFQ)

3. 實時系統(real time system)

進程同步

1. 臨界區

// entry section
// crtical section;
// exit section

2. 同步與互斥(synchronization and mutex)

3. 號誌(Semaphore)

typedef int semaphore;
semaphore mutex = 1;
void P1(){
    down(&mutex);
    // critical section
    up(&mutex);
}

void P2(){
    down(&mutex);
    // critical section
    up(&mutex);
}

使用號誌實現生產者-消費者問題 producer-consumer-problem

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);
        up(&mutex);                 // entry section
        insert_item(item);          // critical section
        up(&mutex);                 // exit section
        up(&full);
    }
}

void consumer() {
    while(TRUE) {
        down(&full);
        down(&mutex);               // entry section
        int item = remove_item();   // critical section
        consume_item(item);         // exit section
        up(&mutex);
        up(&empty);
    }
}

4. 管程

monitor ProducerConsumer
    integer i
    condition c;

    procedure insert();
    begin
        // ...
    end

    procedure remove();
    begin
        // ...
    end
end monitor;
monitor ProducerConsumer
    condition full, empty;
    integer count = 0;
    conditon c;

    procedure insert(item: integer);
    begin
        if count = N then wait(full);
        insert_item(item);
        count := count + 1;
        if count = 1 then signal(empty);
    end;

    function remove: integer;
    begin
        if count = 0 then wait(empty);
        remove = remove_item;
        count := count - 1;
        if count = N - 1 then signal(full);
    end;
end monitor;

precedure producer
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end;
end;

Procedure consumer
begin
    while true do
    begin
        item = ProducerConsumer.remove;
        consume_item(item);
    end;
end;

經典同步問題

1. 哲學家進餐問題

philosopher

#define N 5
#define LEFT (i + N - 1) % N
#define RIGHT (i + 1) % N
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];           // philosopher's state
semaphore mutex = 1;    // mutex for critical section
semaphore s[N];         // semaphore of philosopher

void philosopher(int i){
    while(TRUE){
        think(i);
        take_two(i);
        eat(i);
        put_two(i);
    }
}

void take_two(int i){
    down(&mutex);
    state[i] = HUNGRY;
    check(i);
    up(&mutex);
    down(&s[i]);        // eat only if receive notification, or wait
}

void put_two(int i){
    down(&mutex);
    state[i] = THINKING;
    check(LEFT);        // notify left and right
    check(RIGHT);
    up(&mutex);
}

void eat(int i){
    down(&mutex);
    state[i] = EATING;
    up(&mutex);
}

void check(int i ){
    if (state[i] == HUNGRY && state[LEFT] != EATING && state[EIGHT] != EATING){
        state[i] = EATING;
        up(&s[i]);
    }
}

2. 讀寫問題

typedef int semaphore
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;

void reader(){
    while(TRUE) {
        down(&count_mutex);
        count++;
        if(count == 1) down(&data_mutex);
        up(&count_mutex);
        read();
        down(&count_mutex);
        count--;
        if(count == 0) up(&data_mutex);
        up(&count_mutex);
    }
}

void writer(){
    while(TRUE) {
        down(&data_mutex);
        write();
        up(&data_mutex);
    }
}
int readcount, writecount;                      // initial value = 0
semaphore, rmutex, wmutex, readLock, resource;  // initial value = 1

void reader() {
    // Entry section
    down(&readLock);                // reader is trying to enter
    down(&mutex);                   // lock to increase readcount
    readcount++;
    if (readcount == 1)
        down(&resource);            // if you are the first reader then lock the source
    up(&rmutex);                    // release for other readers
    up(&readLock);                  // done with trying to access the resource

    // critical section
    // <reading is performed>

    // Exit section
    down(&mutex);                   // reserve exit section - avoid race condition with readers
    readcount--;                    // indicate you're leaving
    if (readcount == 0)             // checks if you are last reader leaving
        up(&resource);              // if last, you must release the locked resource
    up(&rmutex);                    // release exit section for other readers
}

void writer() {
    // Entry section
    down(&wmutex);                  // reserve entry section for writers - avoids race conditions
    writecount++;                   // report yourself as a writing entering
    if (writecount == 1)            // checks if you're the first writer
        down(&readLock);            // if you're first, then you must lock the readers out. Prevent them from trying to enter CS
    up(&wmutex);                    // release entry section

    // critical section
    down(&resource)                 // reserve the resource for yourself - prevents other writers from simultaneously editing the shared resource
    // <writing is performed>
    up(&resource)                   // release file

    // Exit section
    down(&wmutex);                  // release exit section
    writecount--;                   // indicate you're leaving
    if (writecount == 0)            // check if you're the last writer
        up(&readLock);              // if you're last writer, you must unlock the readers. Allows them to try enter CS for reading
    up(&wmutex);                    // release exit section
}
int readCount                       // init to 0; number of readers currently accessing resource

// all semaphore initialized to 1
Semaphore resourceAccess;           // controls access (read/write) to the resource
Semaphore readCountAccess;          // for syncing changes to shared variable readCount
Semaphore serviceQueue;             // FAIRNESS: preserves ordering of requests (signaling must be FIFO)

void writer(){
    down(&servcieQueue);            // wait in line to be services
    // <enter>
    down(&resourceAccess);          // request exclusive access to resource
    // </enter>
    up(&serviceQueue);              // let next in line be serviced

    // <write>
    writeResource();                // writing is performed
    // </write>

    // <exit>
    up(&resourceAccess);            // release resource access for next reader/writer
    // </exit>
}

void reader(){
    down(&serviceQueue);            // wait in line to be serviced
    down(&readCountAccess);         // request exclusive access to readCount
    // <enter>
    if (readCount == 0)             // if there are no readers already reading
        down(&resourceAccess);      // request resource access for reader (writer blocked)
    readCount++;                    // update count of active readers
    // </enter>
    up(&serviceQueue);              // let next in line be serviced
    up(&readCountAccess);           // release access to readCount

    // <read>
    readResource()                  // reading is performed
    // </read>

    down(&readCountAccess);         // request exclusive access to readCount
    // <exit> 
    readCount--;                    // update count of active readers
    if (readCount == 0)             // if there are no readers left
        up(&resourceAccess);        // release resource access for all
    // </exit>
    up(&readCountAccess)            // release access to readCount
}

進程通訊

1. 管道

#include <unistd.h>
int pipe(int fd[2]);

它具有以下的限制：

2. FIFO

#include <sys/stat.h>
int mkfifo(const char *path, mode_t mode);
int mkfifoat(int fd, const char *path, mode_t mode);

3. 訊息佇列

4. 訊號量

5. 記憶體共享

6. word 套接

Share this post on:
Share this post via WhatsApp Share this post on Facebook Share this post on X Share this post via Telegram Share this post on Pinterest Share this post via email
Previous
[計算機作業系統] 記憶體管理
Next
[ML] introduction