운영체제 정리 - 5장

1. 병행성 원리

멀티 프로세스

• 프로세스 / 쓰레드 관리를 위한 현대 운영체제의 설계 핵심 주제

  • 멀티 프로그래밍

  • 멀티 프로세서

  • 분산 프로세싱

  • 인터리빙(쓰레드 교행 수행), 오버래핑 (CPU 여러개로 쓰레드 동시에 돌아가는 것)

    • 동일한 문제 야기

• 병행성(Concurrency) Issue

  • 병행성은 프로세스 간 통신, 자원에 대한 공유와 경쟁, 프로세스 활동들의 동기화, 프로세스에 대한 처리기 시간 할당 등 다양한 이슈를 포함
  
  

• 병행성이 발생하는 3가지 문맥

  • 다수의 응용

    • 다수의 활동 중인 응용들 간에 처리시간의 동적 공유를 위해 멀티 프로그래밍이 발전

  • 구조화된 응용

    • 모듈화된 설계 원칙과 구조적인 프로그래밍이 발전되면서 일부 응용이 병행 프로세스의 집합

  • 운영체제 구조

    • 운영체제도 다수의 프로세스와 쓰레드의 집합으로 구현

  
  
  

병행처리의 문제점

• 전역 자원의 공유가 어렵다

  • 어떤 순서로 읽기, 쓰기가 지행되는지에 따라 결과가 달라진다.

• 운영체제가 자원을 최적으로 할당하기 어렵다

• 프로그래밍 오류를 찾아내는 것이 어렵다.

  • 간헐적으로 재현되는 오류는 실행 순서에 따라 달라질 수 있기 때문

인터리빙, 오버래핑으로 인해 발생하는 문제점

단일 처리기나 다중 처리기 시스템에서 동일

• 단일 처리기

  : 프로세스 수행의 상대적인 속도 예측이 어려움

  • 다른 프로세스의 행동에 종속

  • OS의 스케줄링 정책에 의존

    • 누가 먼저 참조하는가 알 수 없다

  • OS의 인터럽트 처리 방법에 따라 달리진다.

    • 실행 모드가 빠져나갈 때 스케줄러가 등장하기에 몇 번 뜨는지는 달라진다.

    → 공유 자원 참조 중 시간 만료로 끊겼는데, 다음 작업도 공유 자원을 사용한다면 동기화 문제 발생

병행성 원리

• 병행성의 다른 예들

  • 공유 함수(shared functions)

    

  • 연관된 공유 데이터 집합 ( a = b라는 일관성 유지 필요)

    

경쟁 상태 (Race condition)

• 다중 프로세스 / 쓰레드가 공유 데이터를 읽거나 쓸 때 발생

• 최종 결과는 수행의 순서에 의해 결정 됨

  • 경쟁(race)의 패자(loser) - 마지막 코드가 가장 마지막으로 데이터를 수정하여, 결국 최종 결과를 결정함

운영체제 고려사항

• 다양한 프로세스의 행위를 추적할 수 있어야 한다.

• 각 프로세스에게 자원을 할당하거나 반납받을 수 있어야 한다.

  자원: 처리기 시간, 메모리, 파일, I/O 장치

• 한 프로세스가 소유한 자원이나 데이터를 다른 프로세스의 간섭으로부터 보호할 수 있어야 한다.

• 수행 결과가 프로세스들의 수행 순서와 독립적일 수 있도록 보장해야 한다.

  • 똑같은 결과가 나와야 한다. (같은 데이터)

  ⭐ 수행 결과가 프로세스들의 수행 속도와 순서에 영향을 받지 않아야 한다.

💨 프로세스 상호작용: 경쟁, 공유, 통신

자원 경쟁

• 병렬 프로세스들이 같은 자원을 사용하려고 경쟁하면 충돌이 발생한다.

  • I/O 장치, 메모리, 처리기 시간, 클락 등

• 프로세스들이 경쟁하면 다음 3가지 제어 문제가 발생

  • 상호 배제 (지원해야 함)

  • 교착 상태 (deadlock)

    : 서로 상대방이 자원을 제공해 줄 때까지 기다릴 뿐, 자신이 이미 할당받은 자원을 반납하지 않는다. 따라서 두 프로세스는 대기만 할 뿐 더 이상 수행을 진행하지 못한다.

  • 기아 (starvation)

    : 교착 상태는 아닌데, 접근이 계속 거절되는 것

  임계 자원
  : 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원
  
  
  임계 영역
  : 자원을 접근하는 프로그램 코드의 일부분

2. 상호배제

상호배제 (mutual exclusion) 요구 조건

• 어느 한 순간에는 오직 하나의 프로세스 만이 임계영역에 진입할 수 있다.

• 임계영역이 아닌 곳에서 수행이 멈춘 프로세스는 다른 프로세스의 수행을 간섭해서는 안 된다.

• 교착 상태, 기아가 일어나지 않아야 한다.

• 프로세서의 개수나 상대적인 수행 속도에 대한 가정은 없어야 한다. (편애 x)

• 프로세스는 유한 시간 동안만 임계 영역에 존재할 수 있다.

상호배제 해결방법

• 어느 한 순간에는 오직 하나의 프로세스 만이 임계 영역에 진입

  • 각 함수는 공유하려는 자원 이름을 인자로 사용한다.

  • 이미 다른 프로세스가 임계 영역에 존재하고 있을 때, entercritical 함수를 호출한 프로세스는 대기한다.

  
  

entercritical(), exitcritical() 구현 방법

락코드: atomic operation

• 소프트웨어적 접근 방법

  • 모든 책임을 병행 수행하려는 프로세스들이 담당하는 것

  • 프로그래밍 언어 또는 운영체제의 특별한 자원 없이, 프로세스 간 협력을 통해 직접 상호배제를 보장하는 것

    • 수행 부하가 높고, 놀리적 오류의 위험이 크다 (atomic이 아닐 수 있다)

• 하드웨어 지원

  • 인터럽트 금지(오버헤드가 크다)

    • 클럭도 없어짐, 멀티 프로세서 시스템에서는 보장 x

  • 특별한 기계 명령어

    : Test and Set, Exchange(=Compare & Swap)

    • 기계 명령어가 수행되는 동안, 같은 메모리 위치를 접근하려는 다른 명령어들은 블록된다.

• 사용하기 쉬운 동기화 기법들

  • 세마포어

  • 모니터

  • 메세지 전달

3. 하드웨어 지원

인터럽트 금지

• 멀티 프로세서의 경우: 클록 인터럽트 없으면 힘듦

특별한 기계 명령어

1) compare: 메모리에 저장된 값과 테스트하려는 값을 비교

2) swap: 변경

• word: 저장된 값

  testval: 테스트 하려는 값

  newval: 새로운 값

• 원래 있던 값과 test 값을 비교해서, 같으면 새로운 값으로 갱신한 후 옛날 값을 리턴

• 동일하지 않으면 기존 값을 그대로 유지

특별한 기계 명령어 사용 예

1) compare & swap

• bolt: 공유 변수로 0으로 초기화 된다.

  • 임계 영역에 진입할 수 있는 유일한 프로세스는 이 변수가 0일 때 compare & swap을 호출한 프로세스

  • bolt = 0: 임계 영역에 프로세스 x

    bolt = 1: 임계 영역에 프로세스 o

2) exchange

• bolt = 1이면, 다지 하나의 프로세스, 즉 key = 0 인 프로세스 만이 임계 영역에 들어가 있다.

  • Lock Code: keyi가 0이 아닐 때까지 돌아라 (bolt가 1일때까지)

  • 임계 영역에 들어가면 keyi는 0 bolt는 1

특별한 기계 명령어 장점

• 임의 개수의 프로세스에 적용 가능

• 단일 프로세서와 공유 메모리 기반 다중 프로세서에 모두 적용 가능

• 간단하고, 검증하기 쉬움

• 서로 다른 변수를 사용하면 다중 임계영역 지원

특별한 기계 명령어 단점

• 바쁜 대기(Busy-waiting)

  • 프로세스가 임계영역에 들어가기 위한 허가가 나올 때까지 변수를 테스트하는 명령을 반복 실행하는 것

    • 대기하는 쓰레드는 Lock 코드를 계속 검사함

• 기아 상태 발생가능

• 교착 상태 발생 가능

  • 우선순위가 낮은 프로세스가 임계 영역에 진입한 상태이고, 우선 순위가 높은 프로세스가 그 임계 영역에 진입하기 위해 바쁜 대기를 하고 있다면 교착 상태 발생

4. 병행성 기법

5. 세마포어

세마포어의(Semaphore) 정의

• 상호배제를 운영체제와 프로그래밍 언어 수준에서 지원하는 매커니즘

  • 블록(수면)과 깨움을 지원

    • 스핀락하지 않고 블록

  • 세마포어는 정수 값을 갖는 변수

    • 3가지 인터페이스를 통해 접근

      1. 초기화 연산 (initialize operation)

         : 세마포어 값을 음이 아닌 값으로 초기화 한다.

         • semwait을 호출한 후 대기 없이 계속 수행할 수 있는 프로세스의 개수 (동시에 진입 가능한 쓰레드의 수)

      2. 대기 연산 (wait operation) → 진입할 때

         : 세마포어의 값을 감소시킨다.

         • 값이 음수이면 호출한 프로세스는 블록된다.

         • 음수가 아니면 프로세스는 계속 수행될 수 있다.

      3. 시그널 연산 (signal operation) → 빠져나올 때

         : 세마포어 값을 증가시킨다.

         • 값이 양수가 아니면 블록된 프로세스를 깨운다.

카운팅 (Counting) 세마포어

• 여러 개의 공유 자원에 대한 엑세스를 제어할 목적 (일반 세마포어에 해당)

💨 binary semaphore는 count = 1;로 두면 된다.

• P, V operation

  • Proberen: to try (semWait 연산)

  • Verhogen: to increase (semSignal 연산)

  • 연산: P(s) → 공유자원 접근 → V(s)

이진(binary) 세마포어

• mutex 역할

  mutex: 객체를 얻거나 반납할 때 사용하는 프로그래밍 플래그

• mutex는 락을 설정한 프로세스만 락을 해제할 수 있다. (이진은 다를 수 있음)

• semWaitB(binary_semaphore s)

  • 세마포어가 0이면 semWaitB 호출 프로세스 블록,
    1이면 0으로 변경시키고 프로세스 계속 수행

• semSignalB(binary_semaphore s)

  • 블록되어 있는 프로세스가 존재하는지 확인,
    블록되어 있다면 깨우고, 없으면 세마포어를 1로 설정

세마포어를 이용한 상호배제

💨 각 프로세스는 임계영역을 사용하기 전에 semWait(s)를 호출

💨 동일한 자원을 접근하려는 n개의 프로세스가 존재, i는 p(i)를 수행

• 세마포어를 이용한 상호배제 동작 예①

  • 가정: 3개의 프로세스 존재

    • A, B, C라는 3개의 프로세스는 lock이라는 이름의 세마포어 변수에 의해 보호되는 공유 자원을 접근하고 있다.

💨 임계영역이 아닌 정상적인 실행에서는 프로세스들이 병렬처리되지만, 임계영역에서는 직렬화(serialized) 된다.

⭐세마포어 변수의 값과 프로세스 개수와의 관계는?

• 음수의 세마포어 락의 값에 절대값을 붙이면 대기하고 있는 프로세스(쓰레드)의 개수

  • s.count ≥ 0 : 임계 영역에 진입할 수 있는 프로세스의 수

  • s.count ≤ 0 : s.count의 절대 값은 s.queue에 블록되어 있는 프로세스의 수

• 세마포어를 이용한 상호배제 동작 예②

  • 가정: 3개의 프로세스 존재

    • A, B, C라는 3개의 프로세스는 프로세스 D가 생산한 데이터를 소비

• 큐에서 제거되는 순서

  • Strong 세마포어

    : 큐에서 들어온 순서대로 실행 (선입선출)

  • Weak 세마포어

    : 순서가 정해지지 않은 것

세마포어의 특징

• 프로세스가 블록될지 여부를 세마포어를 감소시키기 전까지 알 수 없다.

• 프로세스가 세마포어를 증가시키고, 블록되어 있던 프로세스를 깨우면, 이 두 프로세스 모두 수행가능 상태가 된다.

  • 단일 처리기 시스템에서 이 두 프로세스 중에 누가 먼저 수행될 지 알 수 없다. (스케줄러 마음)

• 세마포어에 시그널을 보낼 때 (V연산), 다른 프로세스가 대기 중인지 알 필요가 없다.

  • 즉, 깨어나는 프로세스는 없거나 하나이다.

6. 생산자 / 소비자 문제

데이터를 만들어내는 쓰레드와 사용하는 쓰레드가 동시에 돌아가는 상황

• 병행 수행되는 생산자와 소비자, 생산된 item을 버퍼에 저장

• 한 순간에 하나의 생산자 또는 소비자만 버퍼에 접근 가능

• 생산자는 가득 찬 버퍼에 저장하면 안 됨

• 소비자는 빈 버퍼에서 꺼내면 안 됨

버전①: 무한 공유 버퍼

💨 in이 out을 따라간다.

<생산자 의사 코드>

<소비자 의사 코드>

이진 세마포어를 이용한 방법: 부정확한 방법

• if (n == 1) semSignalB(delay);

  :delay를 signal 시켜준다. 즉 생산자가 소비자에게 데이터가 채워졌음을 알려준다.

• semWaitB(delay);

  : 비어 있는 데 consumer가 사용하면 블록으로

• if ( n == 0 ) semWaitB(delay);

  : 버퍼 데이터 없으면 소비자는 대기 (delay)

💨 0으로 떨어질 때, CPU를 빼앗기면 producer는 n을 막 증가시키고, 그럼 원래 delay가 1번 되어야 하는 것이 못하게 된다. 즉 싱크가 안맞게 되고, 소비자는 버퍼에서 존재하지 않는 데이터를 소비했다.

이진 세마포어를 이용한 방법: 정확한 방법

무한 버퍼에서 범용 세마포어를 이용한 해결 방법

버전②: 유한 공유 버퍼

병행 수행되는 생산자와 소비자, 유한 공유 버퍼

<생산자 의사 코드>

<소비자 의사 코드>

유한 버퍼에서 범용 세마포어를 이용한 해결 방법

7. 세마포어 구현

• semWait와 semSignal은 원자적으로 구현되어야 함

• 하드웨어 또는 펌웨어로 구현 가능

• Dekker’s 또는 Peterson’s 알고리즘 같은 소프트웨어적인 기법으로도 구현 가능

• 상호 배제를 위해 하드웨어 지원 기법 중에 하나를 사용

8. 모니터

모니터의 정의

상호배제를 위한 소프트웨어 모듈(프로그래밍 언어 수준에서 제공)

• 세마포어처럼 상호배제 기능 제공

  • but, 사용이 훨씬 쉽다.

• 특징

  • 지역변수는 모니터 내부에서만 접근 가능

  • 프로세스는 모니터 프로시저 중 하나를 호출함으로 모니터 내부로 진입

    • 모니터 프로시저: 클래스 안의 멤버함수 정도?

  • 한 시점에 단 하나의 프로세스만 모니터 내부에서 수행 가능

9. 신호 기반 모니터

• 구조

  • 하나 또는 그 이상의 프로시저

    • 임계영역

  • 지역변수

  • 조건 변수

동기화를 위한 조건 변수 사용

• 모니터 내부에서 사용

• 두 함수로 접근

  • cwait(c)

    : 호출한 프로세스를 조건 c에서 일시중지 시킨다.

    • 진입하려면 조건 변수 (cwait)을 잡아야만 프로시저에 들어간다.

    • 다른애가 잡고 있으면 sleep으로 들어감

  • csignal(c)

    : cwait에 의해서 중지되었던 프로세스를 재개시킨다.

    • 여러개 중 한 개를 선택해 프로세스의 수행을 재개

모니터를 이용한 생산자 / 소비자 문제 해결 방법

💨 count == N과 cwait(notfull)이 동시에 일어나지 않을 수 있음, 즉 count != N일 수 있음

• 모니터와 세마포어의 차이

  • 모니터는 자체에서 상호배제 보장

    • 동기화 부분만 고려

  • 세마포어는 상호배제와 동기화를 모두 프로그래머가 책임져야 함

10. Mesa 모니터

모니터의 문제점을 개선한 것

• 모니터의 문제점

  • csignal을 호출한 프로세스가 호출 이후 여전히 해야할 작업이 남아 있다면, 두 번의 프로세스 문맥 교환이 필요하다.

  • csignal(notempty)이 호출되면 새로운 소비자가 모니터에 들어오기 전에 notempty 큐에서 깨어난 프로세스가 먼저 수행되어야 한다.

    만일 새로운 소비자가 먼저 수행되어 데이터를 소비해버리면, 깨어난 프로세스는 빈 버퍼에서 데이터를 꺼내오게 된다.

• 변경 사항

  • csignal() -> cnotify()

  • if -> while

  

11. 메시지 전달

모니터와 유사, but 동기화 제공이 없을 때 임시로 제공하는 것

메시지 전달 인터페이스

• send (destination, message)
receive (source, message)

• 기본적으로 정보 교환을 위해 사용

• 또한 상호배제와 동기화를 위해 사용 가능

• mailbox(port): 누가 수신자 / 송신자인지는 port 번호로 구분

• blocking operation: 입출력 요청 후, 응답이 올 때까지 기다려야 함

• 메시지를 받는 쪽은 상대편 프로세스가 메시지를 보내기 전에는 받을 수 없다.

관련 용어

• Blocking, nonblocking

• Addressing

  • 직접 주소 지정

    : PID, 프로세스의 식별자를 지정하는 것

  • 간접 주소 지정

    : 송신자가 수신자에게 메시지를 바로 보내는 것이 아니라, 잠시 메시지는 보관하는 공유 큐로 보낸다.

    • 큐: 메일박스

    • 장점: 송신자와 수신자를 나눔으로써 메시지 사용이 유연해진다.

      

• Message format

• Queuing discipline

  • 기본: 선입선출

동기화

• 두 개의 프로세스간 통신에는 암묵적인 동기확 포함되어 있다.

  • 수신자는 다른 프로세스가 메시지를 보내기 전에 수신할 수 없음

• 프로세스가 receive()를 호출하면 다음 2가지 기능

  • 만일 메시지가 존재하지 않으면 블록이 되거나 또는 수신을 포기하고 다른 작업들을 함

  • 만일 메시지가 존재하면 수신하고 계속 수행

메시지 전달을 이용한 상호배제

• 임계 영역에 들어가고자 하는 프로세스는 우선 메일 부스에서 메세지를 수신해야 한다.

  • 메일 박스가 비어 있을 경우, 프로세스는 블록된다.

• 임계 영역을 빠져 나올 때, 메세지를 메일 박스에 송신한다.

메시지 전달을 이용한 생산자 / 소비자 문제 해결 방법

• 생산자가 데이터를 만들면 mayconsume으로 보낸다.

  • 메일 박스에 적어도 하나의 메세지가 존재한다면, 소비자는 계속하여 수행할 수 있다.

• mayconsume은 버퍼의 역할

• 버퍼의 크기는 전역변수 capacity에 의해 관리된다.

• mayproduce의 메시지 수는 메세지가 생성될 때 마다 감소하고, 소비하면 증가된다.

12. 판독자 / 기록자 문제

판독자 / 기록자 문제 정의

• 병행 수행되는 판독자와 기록자

• 공유 자원 (파일, 데이터베이스)

  • 특정 블록, 처리기 내부 레지스터일 수 있다.

요구 조건

• 여러 판독자들이 공유 데이터를 동시에 읽을 수 있다.

• 한 시점에 오직 하나의 기록자만 공유 데이터를 변경할 수 있다.

• 기록자가 데이터를 변경하고 있는 동안 판독자가 그 데이터를 읽을 수 없다.

• 생산자 / 소비자 문제와 차이점

  • 생산자 / 소비자 문제는 reader 이건 writer이건 임계 영역에는 하나만 들어갈 수 있다.

  • 판독자 / 기록자에서 판독자는 계속 들어갈 수 있다.

세마포어를 이용한 해결 방법: 판독자 우선

• 판독자가 기록자 보다 높은 우선순위

• 라이터가 리더보다 먼저 들어와도 wsem을 리더가 잡고 있는 한, 다른 리더들이 계속 들어가기 때문

💨 라이터가 먼저 들어오면, 첫번째 리더는 wsem에서 대기, 두번째 리더는 semWait(x)에서 대기

💨 라이터가 나가야 첫 리더 들어가고, 기다리던 리더는 다 들어감

세마포어를 이용한 해결 방법: 기록자 우선

• 기록자가 판독자보다 높은 우선순위

• 라이터가 먼저 왔으면 들여보내라!

• x: readcount 보호

• rsem: writer가 먼저 들어가 있을 때 첫 번째 reader가 기다리는 세마포어

• z: writer가 먼저 들어가 있을 때 두 번째 이후의 reader가 기다리는 세마포어

• y: writecount 보호

• wsem: reader건 writer건먼저 들어온 프로세스가 갖는 세마포어

  • critical section에 들어가려면 무조건 wsem을 잡아야 한다.