Chapter 06. Process Syncronization and Mutual Exclusion (1of7) - Instruction

프로세스 동기화 & 상호배제

Process Syncronization (동기화)

• 다중 프로그래밍 시스템
  • 여러 프로세스들 존재
  • 프로세스들은 서로 독립적으로 동작 (동시에 동작)
  • 공유 자원 또는 데이터가 있을 때, 문제 발생 가능
    (둘이 대화로 풀어야한다) (대화하는 작업이 동기화)
• 동기화 (Syncronzation)
  • 프로세스들이 서로 동작을 맞추는 것
  • 프로세스들이 서로 정보를 공유하는 것

Asyncronous and Concurrent P's

• 비동기적 (Asyncronous)
  • 프로세스들이 서로에 대해 모름
• 병행적 (Concurrent)
  • 여러 개의 프로세스들이 동시에 시스템에 존재
• 병행 수행중인 비동기적 프로세스들이 공유 자원에 동시에 접근할때 문제가 발생할 수 있음

Terminologies

(용어정리)

• Shared data (공유 데이터) or Critical data
  • 여러 프로세스들이 공유하는 데이터
• Critical section (임계 영역) (cs)
  • 공유 데이터를 접근하는 코드 영역(code segment)
• ☆Mutual exclusion☆ (상호배제)
  • 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것

Critical Section (example)

memory에는 0이라는 값의 sdata 존재
process-Pi가 sdata++;
process-Pj가 sdata++;

memory에 있는 sdata의 값을 항상 2로 기대할 수 있을까?
꼭 그렇지는 않음

기계어 명령(machine instruction)의 특성

• Atomicity (원자성), Indivisible (분리불가능)
• 한 기계어 명령의 실행 도중에 인터럽트 받지 않음

기계어(assembly)로 번역하면

Pi

㉠ Load Ri , sdata : sdata값(0)을 Ri(레지스터)에 가져온다.
㉡ Add Ri, 1
㉢ Store Ri, sdata : sdata에 Ri값(1) 저장

Pj

ⓐ Load Rj , sdata
ⓑ Add Rj, 1
ⓒ Store Rj, sdata

㉠ 일어난 후 preemption 발생 (CPU 빼앗겨 running에서 ready로)
ⓐⓑ 진행 후 preemption 발생
㉡㉢ 진행 후 Pj dispatch ⓒ 진행
그 결과 sdata=1;

실행 순서에 따라 결과가 달라진다 : Race condition

그렇다면 우리가 원하는 결과를 얻기 위해서는 어떻게 해야할까?

Mutual Exclusion (상호배제)

Pi를 일하는 동안 sdata??? ㉠㉡㉢??? (critical section) 에 접근 못하도록 막아주는 것

Mutual Exclusion Methods

• Mutual exclusion primitives(가장 기본이 되는 연산)
  • enter CS() primitive
    • cs에 진입 전 검사 (노크 똑똑똑)
    • 다른 프로세스가 cs 안에 있는지 검사
  • exit CS() primitive
    • cs를 벗어날 때의 후처리 과정

Requirements for ME primitives

ME 기본연산을 만들기 위한 조건

1. Mutual exlusion (상호배제) : cs에 프로세스가 있으면, 다른 프로세스의 진입을 금지 (당연하고)
2. Progress (진행) : cs 안에 있는 프로세스 외에는, 다른 프로세스가 cs에 진입하는 것을 방해하면 안됨
   (CPU가 empty 상태여서 B라는 프로세스가 들어가려고 하는데, 프로세스 A가 진입을 막는 것)
3. Bounded wating (한정대기) : 프로세스의 cs진입은 유한시간 내에 허용되어야 함 (무한대기하면 안된다)

ME primitives ver. 1

turn이라는 boolean 값의 변수를 선언

turn이 0이면 P0가 들어가고 나오면서 turn=1;
turn이 1이면 P1이 들어가고 나오면서 turn=0;

완벽한가? No

• Progress 조건 위배
  • why?
    • P0이 cs에 진입하지 않는경우
      (P0가 cs에 도달하기전에 죽어버리면 empty인데도 P1이 들어갈 수 없게 됨)
    • 한 Process가 두 번 연속 cs에 진입 불가
      (P0가 한바퀴 돌아서 다시 들어왔는데 P1은 아직 도착도 안한 상황;;)

ME primitives ver. 2

flag라는 크기가 2인 boolean 배열 값의 변수를 선언

P1 깃발 올려져있으면(flag[1]이 true면) 기다린다.
P1 깃발 내려져 있으면(flag[1]이 false면) P0은 본인 깃발 올리고 (flag[0] = true) 들어간다.
나오면서 깃발 내린다 (flag[0] = false)

이러면 완벽한가? No

• Mutual exlusion 조건 위배
  • why?
    • (P1 깃발이 내려져있어서 P0이 들어가려고 한다. P0가 깃발올리기 전에 preemption 당한다.
      P1은 P0 깃발이 내려져있어서 본인 깃발 올리고 cs 들어감. 이때 P0가 CPU할당받아서 다시 일한다. 본인 깃발 올리고 cs들어감..)
    • 문제가 뭐냐
    • 상대방의 깃발을 확인하고 내깃발 올리는게 문제

ME primitives ver. 3

그러면 내깃발 먼저올린다는 의사를 밝히고 없으면 들어간다.

얘는 완벽한가 ? No

• Progress, Bounded wating 조건 위배
  • why?
    • (P0가 들어갈거야 하고 깃발을 들었다. 그런데 preemption 당함. P1이 나 들어갈거야하고 깃발 올림. 어 근데 P0깃발이 올라가있네? empty인데 무한 기다림)

그러면 어떻게 해결하지?

다음장으로