同期プロセス

共有リソースの一貫性を確保するために、コラボレーションプロセス間で実行順序ルールを設定します.

は、競合によって共有リソースが信頼性を失うことを防止するために、ルールを制定し、ルールに従うことによってプロセスを同期させる

1.用語

競合条件:複数のプロセス(またはスレッド)が共有リソースに同時にアクセスすると、共有リソースへのアクセス順序が実行結果に影響する可能性があります.

臨界領域:複数のプロセス(またはスレッド)がリソースを共有している場合、1つのプロセス(スレッド)のみがアクセスできるコード領域.

2.同期に関する古典的な問題

銀行口座問題

親送金、子供送金

送金と送金過程は別々に

を行う.

臨界区:口座残高変更

読者質問

読者読書、著者加文

人以上の読者は同時に文章を読むことができるが、同時に著者は

を書くことができない.

作者は書いていて、読者は読むことができなくて、他の作者も書くことができません

臨界区:本を書く

生産者消費者問題

生産者は貨物を倉庫に入れる、消費者は倉庫から貨物を取り出す

.

倉庫はいっぱいで物が置けず、空いていると物が取れません

臨界区:清倉出荷

食事の哲学者問題

の丸いテーブルに哲学者たちが座っていて、哲学者の両側にフォーク

が置いてあります.

食事にはフォークが2つ必要

哲学者が食事をしている場合、双方の哲学者は

食事をすることができません.

臨界領域:フォークが使用可能かどうかを確認した後、

を使用します.

3.臨界領域問題の解決条件

次の3つの条件を満たさなければ解決できない.

反発:1つのプロセスが臨界領域で実行されている場合、他のプロセスはアクセスできません.

≪実行|Go|emdw≫:臨界領域で作業中のプロセスがない場合は、適切なプロセスを選択して臨界領域に入ります.

有限待機:他のプロセスの飢餓を防止するために、臨界領域に近づくと、臨界領域に再進入する際に制限しなければならない.

4.臨界領域問題のソフトウェア解決方案

ピーターソンアルゴリズム:2つのプロセスの臨界領域故障診断アルゴリズム

データチェーンアルゴリズム:ピーターソンアルゴリズム、2つの類似過程の臨界領域問題に対するアルゴリズム

を解く

RAMポートのパン屋アルゴリズム:2つ以上のプロセスのための臨界領域トラブルシューティングアルゴリズム

// 피터슨 알고리즘
// Shared data
int turn;
bool flag[2];

// Process i
do {
    flag[i] = true;  // 입장 구역, 자원 사용 요청
    turn = j;
    while (flag[j] && turn == j); // busy wait
    /* 임계 구역 */
    flag[i] = false;  // 퇴장 구역
    /* 나머지 구역 */
} while (true);

// Process j
do {
    flag[j] = true;  // 입장 구역, 자원 사용 요청
    turn = i;
    while (flag[i] && turn == i);  // busy wait
    /* 임계 구역 */
    flag[j] = false; // 퇴장 구역
    /* 나머지 구역 */
} while (true);

/* flag[j] && turn == j 의 뜻 */
// flag[j]이 true라면, 프로세스 j가 사용 요청을 하고 대기 중이거나 임계 구역에서 작업하고 있다는 뜻
// turn == j이 true라면, 프로세스 j가 아직 실행되지 않았거나 또는 프로세스 i보다 먼저 실행됐다는 뜻 
// flag[j] && turn == j가 true라면, 프로세스 j가 프로세스 i보다 먼져 임계 구역 접근을 요청했거나 프로세스 j가 임계 구역에서 작업 중이라는 뜻

5.臨界領域の問題のハードウェア解決方案

rock(lock)の解決策を用いる:プロセスはrockを得てこそ臨界領域に入ることができ,臨界領域を離れた後にrockを返し,臨界領域問題を解決する.

臨界領域の問題を解決するためのハードウェア命令はtest and set()とcompare and swap()である.

// test and set
bool test_and_set(bool *target) {
    bool ret = *target;
    *target = true; 
    return ret;
}
do {
    while (test_and_set(lock));
    /* 임계 구역 */
    lock = false;  // 퇴장 구역
    /* 나머지 구역 */
} while (true)

// swap
void swap(bool *a, bool *b) {
    bool tmp = *a;
    *a = *b;
    *b = tmp;
}
do {
    key = true;
    while (key == true) swap(&lock, &key);
    /* 임계 구역 */
    lock = false;
    /* 나머지 구역 */
} while (true);