병행성의 개념

운영체제 설계의 핵심 주제 -> 프로세스와 스레드의 관리

• 멀티프로그래밍(Multiprogramming)
  - 단일처리기(프로세서) 시스템 상에서 다수의 프로세스 관리
• 멀티프로세싱(Multiprocessing)
  - 멀티프로세서(다수의 프로세서) 시스템 상에서 다수의 프로세스 관리
• 분산처리(Distributed processing)
  - 다수의 분산된 컴퓨터들 상에서 수행되는 다수의 프로세스 관리
  => 병행성(concurrency)
• 프로세스 간 통신
• 자원에 대한 공유와 경쟁(메모리, 파일, I/O 등 모든 자원)
• 프로세스 활동들의 동기화
• 프로세스에 대한 처리기 시간 할당

멀티프로세싱과 분산 시스템과 같이 다수의 처리기가 있는 시스템뿐만 아니라 단일처리기 멀티프로그래밍 시스템에서도 발생되는 이슈

병행성의 발생 이유

• 다수의 응용(application)
  - 다수의 활동 중인 응용들 간에 처리 시간의 동적 공유를 위해 멀티프로그래밍 개발
  - Context Switching 자체의 오버헤드 + 프로그램 수행의 점프로 인한 Hit ratio 하락으로 인한 부담
• 구조화된 응용
  - 모듈화된 설계 원칙과 구조적 프로그래밍의 발전으로 일부 응용들은 병행 프로세스들의 집합으로 구현
• 운영체제 구조
  - 운영체제는 다수의 프로세스와 스레드의 집합으로 구현

병행성과 관련 있는 주요 용어

용어	설명
원자적 연산(atomic operation)	하나 or 여러 개의 명령어들로 구성되어 함수/액션으로 더 이상 분할할 수 없는 단위
임계영역(critical section)	공유 자원을 접근하는 프로세스의 내부 코드 영역으로 다른 프로세스가 이 영역에 있을 때, 이 프로세스 또한 이 영역을 실행할 수 없음 독점이 보장되는 영역(어느 한 순간에 하나만 실행)
교창상태(deadlock)	두 개 이상의 프로세스들이 더 이상 진행할 수 없는 상태
라이브락(livelock)	두 개 이상의 프로세스들이 다른 프로세스의 상태 변화에 따라 자신의 상태를 변화시키는 작업만 수행 중인 상태
상호배제(mutual exclusion)	한 프로세스가 임계영역 코드를 수행하고 있으면 다른 프로세스들은 해당 임계영역 코드 수행 불가
경쟁상태(race condition)	두 개 이상의 프로세스가 공유 자원을 동시에 접근 상대적 수행 순서에 따라 최종 수행 결과가 달라질 수 있음
기아(starvation)	특정 프로세스가 매우 오랜 기간 스케줄링 되지 못하는 경우

deadlock 추가 설명

• 서로가 서로의 임계 영역이 풀리길 기다리고 있는 상태이기 때문에 각 프로세스를 깨워 줄 조건이 없는 상태.

병행성의 원리

단일처리기 시스템 상에서의 프로세스

• 시스템에서 프로세스들은 인터리빙(interleaving), 여러 프로세스들이 서로 번갈아 수행
  - 번갈아 수행하는게 빨라서 병렬처리되는 것처럼 보이지만 실제로 병렬처리되는 것은 아님
  - 시스템 처리 효율과 구조적인 프로그래밍에 장점 제공
  - 멀티프로세서 시스템에서는 프로세스들의 인터리빙뿐만 아니라 오버래핑(overlapping)도 지원

복습

오버래핑(overlapping)
두 개 이상의 프로세스들이 시간이 중첩되어 실제로 병행 수행

인터리빙(interleaving)
두 개 이상의 프로세스들이 서로 번갈아 수행

인터리빙과 오버래핑의 문제점

• 단일 처리기 환경에서 프로세스들의 수행의 상대 속도를 예측할 수 없음
  - 프로세스들이 수행되는 상대 속도는 운영체제의 스케줄링 정책과 다른 프로세스 활동, 운영체제가 인터럽트를 처리하는 방법 등에 따라 동적으로 바뀌기 때문

문제에 대한 어려움

• 전역 자원의 공유의 어려움
  - 순서 따라 결과가 바뀔 수도 있기 때문에 전역 자원의 공유가 어려움
• OS가 자원을 최적으로 할당하기 어려워짐
  - 한 프로세스가 IO 특정 입출력 자원을 요청하여 운영체제에 할당받아놓고 일시중지되면 다른 프로세스들이 사용할 수 없음
  - 가용한 자원이 프로세스의 실행 순서에 따라 사용될 수 없는 상황
  => 시스템의 교착 상태 발생
• 프로그래밍 오류를 찾아내는 것이 어려워짐
  - 특정 실행 순서에서 프로그래밍 오류가 나타나는데 순서가 바뀌고 오류가 안 뜨면 이후에도 디버깅이 어려움

상호 배제의 필요성

• 함수 이미지가 하나만 존재할 경우, 같은 함수를 사용하는 과정에서 전역 변수에 접근하는 코드와 같은 부분에서 순서가 바뀔 수 있음
• 한 함수에 한 프로세스만 진입이 가능하다면 다른 프로세스가 실행되던 이전 함수에서 똑같이 진입한다고 해도 막히기 때문에 공유 자원에 대한 접근을 제어

단일 CPU와 멀티프로세스에서

• 단일 처리의 경우 이러한 문제가 발생하는 경우는 위와 같이 같은 함수에 진입할 시에 전역변수가 공유되면서도 순서가 바뀌어 문제가 발생할 가능성이 있음
• 멀티프로세서 또한 이러한 프로세서들이 함수에 서로 진입하는 과정에서 결과가 바뀌는 잠재적 문제가 생길 가능성이 있음

=> 단일 처리기/멀티프로세서 시스템 모두 같은 전역변수 접근 제어, 인터럽트의 비동기적인 발생으로 문제가 생길 가능성이 높음

경쟁 상태

예시 1

P1, P2가 전역변수 a를 공유한다는 가정 하에
P1은 a를 1로 수정, P2는 a를 2로 수정

=> 서로 전역변수 a에 접근하기 위해 경쟁하고 있는 상태

예시2

P3, P4가 있고, b=1, c=2로 초기화
P3은 b = b+c 수행
P4는 c = b+c 수행

수행 결과는 각 프로세스의 수행 순서에 따라 달라질 가능성이 있음
P3 -> P4의 순서대로 했을 때 : b = 3, c = 5
P4 -> P3의 순서대로 했을 때: b = 4, c = 3

운영체제의 고려 사항들

• 모든 프로세스들의 상태와 수행 위치 추적
  - 프로세스 제어블록(PCB: Process Control Block)으로 가능
• 자원 할당, 해제
  - 처리기 시간
  - 메모리
  - 파일
  - I/O 장치
• 다른 프로세스의 간섭으로부터 자원 및 데이터 보호
• 프로세스의 기능과 수행 결과는 프로세스의 수행속도 및 동시에 수행되는 다른 프로세스들의 상대적인 수행 속도와 독립적이어야 함

프로세스 간 상호작용

프로세스 간 서로에 대해 인식의 정도와 이에 따른 상호 영향

프로세스가 병렬적으로 수행될 때 병렬로 수행되는 다수의 프로세스가 서로에 대해 인식하는 정도와 이러한 프로세스들이 공유자원에 접근하여 발생할 수 있는 잠재적인 제어 문제가 상이함.

인식 정도	관계	한 프로세스가 다른 프로세스에게 미치는 영향	잠재적인 제어 문제
서로를 인식하지 못함	경쟁	한 프로세스의 수행 결과는 다른 프로세스들의 행위와는 독립 프로세스의 타이밍에 영향	상호 배제 교착 상태 기아 상태
서로를 간접적으로 인식	공유를 통한 협력	한 프로세스의 수행 결과는 다른 프로세스들로부터 얻은 정보에 의해 영향 프로세스의 타이밍에 영향	상호 배제 교착 상태 기아 상태 데이터 일관성
서로를 직접적으로 인식	통신을 통한 협력	한 프로세스의 수행 결과는 다른 프로세스들로부터 얻은 정보에 의해 영향 프로세스의 타이밍에 영향	교착 상태 기아 상태 소모성 자원

자원에 대한 프로세스 간 경쟁

• 두 개 이상의 프로세스들이 수행 중에 특정 자원을 사용하려 할 때, 각 프로세스는 다른 프로세스의 존재를 모름
• 각 프로세스는 다른 프로세스의 수행 결과에 영향을 받지 않아야 함
• 각 프로세스는 사용한 자원의 상태를 변화시켜서는 안됨
• 경쟁 관계의 프로세스 간 정보 교환 없음

• Ra - 임계자원
  - 공유하는 자원
• entercritical(RA) - 임계영역 진입
  - 공유하고 있는 자원에 접근 할 때 사용하는 코드가 있는 영역에 진입
• 상호배제
  - 임계 영역에 대해 한 순간에 하나의 프로세스만 진입하게 하는 명령어
• exitcritical(Ra)
  - 임계영역에 해당하는 코드를 사용하지 않는다고 운영체제에 알림

공유를 이용한 프로세스 간 협력

a = b라는 조건이 지켜지도록

P1: a = a + 1; b = b + 1; P2: b = 2 b; a = 2 a;

인터리빙될 경우
a = a + 1; => P1
b = 2 * b; => P2
b = b + 1; => P1
a = 2 * a; => P2

• 서로를 알지 못 함
  - 공유 변수, 공유 파일, 공유 데이터베이스에 대해서 서로가 데이터를 공유하고 이를 통해 협력
• 데이터의 무결성(integrity)
  - 조건이 만족되지 못하는 것 => 무결성이 떨어짐
• 상호배제가 지켜져도 일관성을 상실할 수밖에 없음

=> 읽기모드와 쓰기모드를 구별하지 않아 상호 배제에서 쓰기 모드를 구분하지 않음
=> 데이터의 무결성이 깨어지게 됨

상호 배제 요구조건

1. 강제되어야 함
   • 동일한 자원이나 공유 객체에 대한 임계영역을 가진 모든 프로세스들 중에서 반드시 단 하나의 프로세스만이 임계영역에 진입 가능
2. 임계 영역이 아닌 곳에서 수행이 멈춘 프로세스는 다른 프로세스의 수행을 간섭하면 안됨
3. 임계 영역에 접근하고자 하는 프로세스의 수행이 무한히 미루어져서는 안됨
   • 교착상태나 기아상태가 일어날 확률이 없어야 함
4. 임계영역이 비어 있을 때 진입하고자 하는 프로세스는 즉시 들어갈 수 있음
5. 프로세서의 개수나 상대적인 프로세스 수행 속도에 대한 가정이 없어야 함
6. 일단 임계영역에 들어간 프로세스는 일정한 시간 내에 임계영역에서 나와야만 한다.