[운영체제] Concurrency

Mutual exclusion, synchronization

컨쿼런시

프로세스 충돌? 왜 발생? 방지 방법

프로세스 충돌(컨쿼런시 충돌)

다수의 프로세스, 다수의 쓰레드, 다수의 이벤트가, 동시다발적(컨쿼런드 하게)으로 발생

컴퓨터 자원을 대상으로 발생, 메모리, 파일, 입출력 장치…

이를 예방, 방지 해주는 기술이 필요함..

그래서 프로세스들이 뭘 하고 있고, 사용하려는 자원이 무엇인지 관리를 해야 함.

따라서, critical secion이 mutual exclusion하게 실행되지 않으면, race condition이 발생할 수 있다.

공유 자원 접근은 누가 신경써야함 ?

운영체제에 의해 발생하는 것은 맞음, 다만 응용 프로그램에서 나타날 가능성이 높음, 공유 자원에서 문제 발생

ipc 관련 개념으로, shared memory.. 여기서 문제 발생

해결책: 커널 제공 동기화 도구 사용

세마포어( System V / POSIX ): 프로세스 간에 카운팅 세마포어를 이용해 접근 가능 횟수를 제어

뮤텍스(Mutex)／조건 변수(Condition Variable): 스레드뿐 아니라 프로세스 간에도 공유 가능한 POSIX 뮤텍스 사용

파일 잠금( flock / fcntl ): 파일 단위로 배타적(exclusive) 또는 공유(shared) 락을 설정

원자적 시스템콜: 가능하면 rename, link 같이 원자적 행동을 보장하는 호출을 활용

용어 정리

interrupt

하드웨어가 os에게 어떤 event가 발생했음을 알림.

인터럽트 라인에 신호가 발생했는지 수시로 확인하고, 신호가 없다면, 다음 instruction을 수행..

발생했으면 인터럽트 처리 함수를 수행.

0.001초, 1ms

100번째 클럭 인터럽트가 다되서 타임 슬라이스가 종료되 context switch 발생 <- 개념 정리

이거 개념 정리 해야할듯.

kernel mode change.. 몇번 interupt가 걸렷는지 count.. 100이 되지 않앗으면 사용자 코드 실행..

disable하면 처리가 미뤄지는 것임.

Mutual exclusion

공유 자원은 같은 시간대에 한 프로세스만 할당되게끔 하는 성질이다.

Critical section

공유 자원을 접근하는 역할을 하는 코드를 지칭한다.

만약 읽는 작업만 수행하더라도, 접근하는 작업만 수행해도 critical section ???

Race condition

프로세스가 어떤 공유 data item을 가지고 경쟁..

race condtion을 설명하는 Producer/Consumer Problem이 존재한다..

Producer가 생산한 정보를 IPC를 이용해 Consumer에 전달하려고 해보자..

만약 shared memory를 사용하지 않으면 race condition 발생 x?

버퍼를 이용해 Consumer가 정보를 이용함. 이때 접근할 때 mutual exclusion이 보장되어야 한다는 것이다.

버퍼는 c-style array를 이용해 circular queue를 구현하여 작동된다.

while문을 이용해 busy wait를 구현해보자.

그것으로 producer는 생산을 하지 못해,, time 퀀텀이 끝나면 process switching 이 발생해

언젠간 consumer process에게 스케줄링이 넘어가는 식으로 문제를 해결한다.

while (counter == BUFFER_SIZE); // null statement

각 critical에 해당하는 코드들이 mutual exclusion하게 atomically하게 수행되어야함.

사실 결국 어셈블리어로 변환을 해야하는데

이 counter++ 결국 어셈블리어로 변환하면 load, increment, store라는 3개의 instruction으로 변환됨.. 따라서 이 어셈블리어 들 사이에 다른 instruction이 수행되지 않게 수행되어야함.

race conditon 예방하기

크게 2가지 방법이 존재한다.

1. 크리티컬 section을 atomic operation으로 만들어버린다. 하나의 instruction처럼 간주

좋은 방법은 아님, 왜? 많은 수의 instruction이 critical section이면. 시스템 운영 문제..

통신 인터페이스가 죽어버리는 등.. 패킷 깨짐 문제 등 발생. 키보드 마우스도 .. 감지 못함

그리고 선언 허용 문제도 필요해서.. 복잡

1. 일종의 fence를 설치한다.

fence 안에 critical section을 설치.. fence안의 mutual exclusion은 보장되지만, fence안의 critical section은 atomic하지않음!

한 프로세스만 fence를 실행..

atomic operation

instruction실행당 cpu는 interrupt line을 체크하는데. 그냥 이 체크를 atomic operation동안 씹어버린다(실행, 조사 안함, 발생은 함). 물론 수신은 계속 받지만, enable됬을때만 .. 처리..

instruction 실행당 cpu는 interrupt line을 체크하는게 원칙이라는데 이것도 조사

interrupt disable - interrupt enable

critical section problem

각각 critical section을 가진 프로세스

한 프로세스가 실행하고 있으면 동시에 접근하지 못하도록 하기

위문제를 해결하기 위해 요구사항을 3개 만족해야한다.

1. Mutual Exclusion
2. Progress (내 프로세스를 진행할 수 있어야 함.)
3. Bounding waiting (이러한 담장에서 프로세스가 존재한다면 기다려야 함. 단, 기다리는 시간이 제한되어있음.)

bounding waiting을 간략히 설명하자면, 프로세스에 cpu가 배정되어야 하는데, 이 때 소외되면 안된다는 것임. 이런 상황이 발생할 수 있는 가능성이 없어야 함.

software solution

critical section의 앞/뒤로 entry section, exit section을 추가하는 식으로 구현하는 것임.

나 들어갔어요~ 나 나왔어요~를 어떠한 공통 표시같은 거로.. 하는 거..

그렇게 entry section, exit section을 구현하면, critical section이 atomic하지 않더라도, mutual exclusion을 만족 할 수 있음..

entry section은 busy wait로 구현하능하고, 다른 방법에 대해서 찾아보기!!

프로그레스 성질은 만족하지 못하는데, 이는 busy wait로 인해서 그런 것임. 이를 해결해보자

Peterson’s algorithm, 위를 개량한 버전으로, 프로세스가 2개 있는 상황에서 3 조건을 만족

do {
  flag[i] = true;
  turn = j;
  while (flag[j] and turn == j);
  // critical section
  flag[i] = false;
  // remainder section
} while (1);

쉽게 설명하면, 이전에서 차례에 대해 검사를 수행하는 것 이외에도 지금 내가 프로세스를 진행 중임을 나타내는 flag를 이용해 나타내는 것..

n개의 프로세스에 허용되는 것이 Bakery Algorithm이다.

수행시간이 너무 길다는 단점이 존재한다.

do {
  choosing[i] = true;
  number[i] = max(number[0], ..., number[n-1]) + 1;
  choosing[i] = false;
  for (j = 0; j < n; j++) {
    while (choosing[j]);
    while ((number[j] != 0) && (number[j], j), (number[i], i));
  }
} while (1);

hardware solution

critical section을 atomic operation으로 만드는 것이 아니라, entry section을 atomic operation으로 만들어보는건 어떨까요 ?

이런 함수는 OS에 존재하며 test and set instruction이라는 것입니다.

testset

정말 심플하다. atomical 하게 작동된다.

boolean testset (i) {
  if (i == 0) {
    i = 1;
    return true; // 들어갈 수 있다.
  } else {
    return false; // 들어갈 수 없다.
  }
}

사용 예제:

const int n;
int bolt;
void P(int i) {
  while (1) {
    while (!testset(bolt)) // busy waiting
    // critical section
    bolt = 0;
    // remainder
  }
}

void main() {
  bolt = 0;
  parbegin (P(1), P(2), ..., P(n));
}

의문점 정리. bolt = 0은 몇개의 instruction ? parbegin()?

성능차이 비교

소프트웨어 처리방식 ex.. bakery 등과 비교했을때 하드웨어 처리방식이 단순하게 목적 성취 가능

but, 단점 존재.. 1. busy-waiting을 써야 됨. 꼭 써야되는지 조사(안 쓰는 방법 존재.)

testset은 무저건 busy-waiting을써야하는지 조사

1. bounded waiting이 지원되지 않음. 스케줄링으로 인해서 그럼.. 운이 안좋으면 소외(새치기)당할수 있음 (이론적으로 가능성이 존재)

상용 프로그램에서는 거의 발생하지 않기 때문에 배제하고 구현하는 경우가 많음

1. deadlock이 가능함.

교착.. $P_L$ $P_H$ 스케줄링에 의해 프로세스가 뺏김..

ex) $P_L$이 critical section을 사용하고 있어 entry section에서 다른 프로세스들이 막히는데, 여기서 스케줄링으로 인해 우선 순위가 높은 프로세스에게 cpu가 계속 할당이 되면 교착 발생

누구는 critical section을 가지고 싶어하고, 누구는 cpu를 가지고 싶어함..

현대 os에서는 이거에 대한 해결책이 존재, 전부 해결함. (스케줄링 쪽에서 해결!)

질문? critical section을 뺏어가는건 어떰? deadlock이 발생할 수 없긴함, 근데 뺏기는 입장에서 너무 피해가 커서, 일종의 권한만 부여하는 식으로.. 자원을 뺏진 않음.

자세히 설명하면 좋을 듯.

정리하면, 큰 단점으로는 busy-waiting인데, 이것이 필요할 때도 존재함… 따라서 무조건 나쁜 방법인 것만은 아님.

Semaphores

다른 하드웨어 지원 방법 세마포어에 대해 알아보자! busy-waiting 회피

정의: 정수형 변수, 자기만의 큐가 존재. 추가적 정리 필요

semWait(s), semSignal(s) atomically하게 실행..

s라는 세마포어 이름을 선언하는 것(프로그래머)

interrupt가 발생해도 나중에 처리!

단순히 정리하자면, 진입 불가 상태를 판별하면, block(wait, sleep) 상태로 변환함! 이를 os가 함..

쉽게 설명하면 entry section에서는 잠을 자고.. 나가는 section에서는 다른 자는 프로세스를 깨워주는 그런 느낌..

이것이 wait, signal..!

wait은 감소, signal은 증가

구현 코드 예제.. ? Semaphore Primitives..

struct semaphore {
  int count;
  queueType queue;
}

void semWait(semaphore s) {
  s.count--;
  if (s.count < 0) {
    // place this process in s.queue;
    // block this process
  }
}

void semSignal(semaphore s) {
  s.count++;
  if (s.count <= 0) {
    // remove a process P from s.queue;
    // place process P on ready list;
  }
}

사실상 s.count가 음수면, queue의 원소 개수를 의미하는 것으로도 해석할 수 있을 것 같다.

원자적으로 실행되며, 이게 atomically 하게 실행 되지 않으면, race condition이 발생한다.

const int n;
semaphore s = 1; // 맨 처음 할당해줘야한다.

void P(int i) {
  while (true) {
    semWait(s);
    // critical section
    semSignal(s);
    // remainder
  }
}

void main() {
  parbegin (P(1), P(2), ..., P(n));
}

이런 패턴으로 작성된다.!!

semaphore값은 무조건 1이어야하나? 양수여도 되는거 아닌가.. 프로세스으 ㅣ문제인가..

질문, 그럼 testset과 semaphore의 장단점이 무엇이고 사용하는 시점 ?

Semaphore 활용

// semaphore상수로 0을 지정할 수도 있다. buffer안에 들어있는 원소의 개수를 의미한다.
semaphore count = 0;

semaphore empty = BUFFER_SIZE; // 버퍼의 할당된 공간을 의미한다.

semaphore mut_ex = 1; // mutual_exclusion, 초기값은 1이어야 한다.

void producer() {
  while (1) {
    produce();
    semWait(empty);
    semWait(mut_ex);
    append(); // 생산 아이템을 버퍼에 집어 넣는다.
    semSignal(mut_ex);
    semSignal(counter);
  }
}

void consumer() {
  while (1) {
    semWait(counter);
    semWait(mut_ex);
    take(); // 버퍼에서 생산된 아이템을 얻는다.
    semSignal(mut_ex);
    semSignal(empty);
    consume();
  }
}

void main() {
  parbegin(producer1, producer, ..., consumer);
}

이 semaphore의 초깃값을 정하는 게 코드를 짜는 것보다 어렵다!!

semWait()와 semSignal()의 순서는 상관 없지만, 불리는 총 횟수는 서로 같아야함. 모든 프로세스를 점검해봤을때 개수가 같아야 한다는 의미인듯.

semaphore를 다른 방식으로 이용할 수도 있는데, 프로세스 A 다음에 프로세스 B가 실행되게 끔 하는 방식으로 구현할 수도 있음. (ShellLab…), flag 방식을 이용한다.

ex) 쓰기 작업 이후 읽기 작업 수행

readers/writers problem

critical section problem의 확장, 공유 데이터 액세스 할때 읽기만 하면…

여러 명이 같이 읽어도 되잖음 ? 수정 안하니깐.

writer는 한명만 하고, reader는 여러 명이 들어가도 괜찮음.. (정리해야할듯)

세마포어 사용 패턴 정리

1. Mutual Exclusion을 위한.. 일종의 쉴드
2. 프로세스 간 순서 제어
3. readers/writers problem.. 등 특정 프로세스에 대해 예외 처리

semaphore wsem = 1, rsem = 1;

void writer() {
  while (1) {
    semWait(wsem);
    WRITEUNIT(); // 쓰기 작업 수행
    semSignal(wsem);
  }
}

void reader() {
  while (1) {
    semWait(rsem);
    readcount++;
    if (readcount == 1) semWait(wsem);
    semSignal(rsem);

    READUNIT(); // 읽기 작업 수행

    semWait(rsem);
    readcount--;
    if (readcount == 0) semSignal(wsem);
    semSignal(rsem);
  }
}
// 쉽게 설명하면, read 일 때는 read 프로세스가 허용됨
// write 프로세스는 허용되지 않음.

binary semaphore

세마포어 값이 1/0밖에 없음.. mutual exclusion .. mut_ex라고도 함.

자고있는 프로세스를 동시에 다 깨움.(?) 스케줄링에 따른 경쟁 발생.

이거에 따라 os는 구현이 조금 다름.

개념 정리!!

이름만 Lock이지 binary semaphore를 구현한것..

pthread_mutex_unlock(): 앞에 ㅇㅆ는거 하나만 깨움

pthread_mutex_lock()

모니터

고수준 동기화 레벨..

software module

프로시져들을 정의..

하나씩 실행 가능.. race condition 발생 금지..!

특징: 프로시져를 실행하다가 조건이 맞지 않으면 옆의 공간(큐)로 잠시 나가서 다른 프로시져 실행하는 방식

모니터 코드 알아보면 좋을듯

Monitors

모니터는 소프트웨어 모듈로, – 추상 데이터 타입을 동시 실행 중인 여러 프로세스 간에 안전하게 공유할 수 있도록 해 주는 고수준 동기화 구조입니다.

주요 특징

모니터의 지역 데이터 변수는 오직 모니터 내부에서만 접근할 수 있습니다.

프로세스는 모니터의 절차(메서드) 중 하나를 호출해야 비로소 모니터 안으로 진입합니다.

한 번에 오직 하나의 프로세스만 모니터 안에서 실행될 수 있습니다.

Deadlock

Starvation

보통 상황보다 많이 기다릴때 발생조건: 두 개 이상의 프로세스가 발생할 수 없는 이벤트를 무한정 기다리는 상황

Starvation이 영원히 지속되서, 끝나지 않는 상태.

그냥 구조적인 문제라서, 프로세스들끼리는 해결을 못함, 관리자가 이를 해결해야함..

효율적인 해결책이 업슴

따라서, deadlock이 발생하는 프로세스중 하나를 골라서 수정해주면 됨..

컴퓨터 자원의 종류

Reusable Resources: 대부분의 자원들(입출력 장치, 메모리) 데드락 발생 가능성 존재

Comsuable Resources: 사용되면 사라지고, 데드락이 발생 가능함. ex) 메세지

Resource Allocation Graphs

데드락을 시각적으로 표현하는 방법이다.

컴퓨터 자원은 사각형으로 표현되며, 안에 점이 있는데 개수가 몇 개 있는지 표현

화살표는 요청 방향.. Requests, Hold by

cycle과, 직사각형의 개수로 데드락을 판정할 수 있다.. 조사!

아마 수학적으로 잘 정의되어있을듯 ?!

데드락의 조건

아래 4가지가 동시에 만족해야 발생하는 것을 알아냄

1. Mutual exclusion (혼자 사용하면 발생할 일이 없음)
2. Hold-and-wait (어떤 자원을 가진 상태에서 다른 자원을 요구하는 것)
3. No preemption (프로세스가 자신이 원하는 자원이 다른 프로세스에게 할당되어잇으면 뺏어오는 것을 못함.)
4. Circular wait (프로세스 체인이 cycle을 가짐, hold-and-wait가 맞물린 것..)

데드락 해결방법(handling)

크게 3가지 방법이 존재한다.

1. 아예 걸리지 않도록 OS가 예방
2. 발생할 때 OS가 감지하고 이를 해결(recover)
3. 아무것도 하지 않음 (사람에게 떠넘김)

1, 2번이 좋아보이지만 성능 문제로 인해 3번.

1, 2번 방법에 대해 알아보자.

1번 방법(예방)

앞서 있었던 데드락의 조건 4가지 중 하나를 없애보는 것이다.

1. 자원을 같이 쓰게 해보자 (Break Mutual Exclusion property)
2. 프로세스 수행 시 자원을 모두 받고 해결한다. (Break Hold-and-wait)
3. 자원을 뺏어올 수 있게 해보자. (Break No Preemption)
4. 프로세스 체인의 cycle을 깨보자. 일부 프로세스에게만 Hold-and-wait를 적용하지 않는다던지.. (Break Circular Wait)

그나마 4번 방법을 시도해볼만 한데, 결국 특정 프로세스에 대해 1, 2, 3번 방법을 수행하는 것이라 현실적으로 불가능하다.

2번 방법(recover)

감지하고, 해결해보자. 방법은 2가지가 있다.

1. 데드락 프로세스를 전부 Abort한다.
2. 데드락 걸린 프로세스 중 하나만 Abort해본다.

그럼 무엇을 Abort해볼까? 우선순위가 가장 낮다던지, 자원 사용량이 낮다던지 등 다양한 조건으로 선정할 수 있다.

Dining Philosophers Problem

Deadlock과 Starvation을 표현하는 문제이다.

위 문제를 푸는 자명한 해답은 동시에 식사할 수 있는 사람(내 포크를 들 수 있는 사람)의 수를 $n - 1$명으로 제한하는 것임.

따라서 이것에 대한 코드를 구현해주면 된다.

banker’s algorithm

프로세스가 자원을 할당해달라고 OS에게 요청하면, 운영체제가 할당하는 것이 아니라 할당했다고 가정해

safe상태인지, 데드락이 걸릴 수 있는 상태인지 판단해 예방하는 알고리즘이다.

실행해보고, 안전한 상태면, 자원을 줌, 안전한 상태가 아니면 블록 걸어서, 안전한 상태가 되면 할당

이는 은행의 운영방식과 비슷하다 해서 banker’s algorithm

자원할당하기전 algorithm을 수행하고, 이를 수행하면 safe sequence가 나올 수 있는데, 나오면 안전하니 자원을 할당해도 되는 방식.

프로세스가 자원이 얼마나 필요한지 OS가 전부 알고있다는 가정이 필요함. 알기 위해서는 OS에게 신고(등록)를 해야함. -> 거의 불가능에 가까움..

위 정보를 Claim Matrix라는 테이블에 운영체제가 이를 저장.

Available vector.. // 메모리의 총량

Allocation Matrix, Need Matrix

할당되있는거, 더 필요한거.. 행렬

줬다고 가정하고 사용 가능한 메모리량 계산.. 일종의 블록 상태 돌입 하면서.. 예방!

60 줘도 됨? yes.. ! 그렇게 판단하면 safe sequence를 줌

1. 결국 실행해나가면서 데드록을 판별해야하는데, 결국 일종의 온라인 알고리즘..
2. 자원을 요청할 때마다 이 알고리즘이 수행되어야 하는데, 그러면 부담이 너무 심함.