운영체제 4주차 과제

병행성(동시성)에대해 설명해주세요.

동시성은 여러개의 작업들이 동시에 실행되는 것 처럼 보이는 것을 말합니다. context switching을 통해서 번갈아 가며 처리를 해줍니다.

문제점으로는 두개 이상의 작업들이 실행될 때, 공유 자원에 동시에 접근할 수 있습니다. 이 때 데드락이 발생하고, 또 다른 문제점으로는 계속해서 context switching이 일어나기 때문에 그로 인한 오버헤드가 많이 발생할 수 있습니다.

병렬성에 대해 설명해주세요.

여러 작업을 실제로 동시에 처리하는 것을 말합니다. 멀티 코어 환경에서 멀티 스레드와 추가적으로 멀티 스레드를 통해서 구현할 수 있습니다. 

동시성과 병렬성을 비교해서 설명해주세요

 

동시성은 티비를 보면서 공부를 하는 것이고,
병렬성은 노래를 들으면서 공부를 하는 것이다.

티비를 보면서 공부를 하는 경우에는 티비를 보다가 -> 공부를 하다가 -> 다시 티비를 보다가 -> 다시 공부를 하다가
와 같은 순서로 진행되고,노래를 들으면서 공부를 하는 경우에는 동시성 예시처럼 번갈아가면서 수행되는게 아니라 두 작업을 동시에 수행한다. (블로그 펌)

프로세스 동기화에 대해 설명해 주세요.

공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있습니다. 이 때 일관성 유지를 위해선, 협력 프로세스 간의 수행 시기를 맞추는 것을 의미합니다. 이는 크게 두가지로 분류할 수 있는데, 실행 순서를 제어함으로써 프로그램을 올바른 순서로 실행하고 상호배제를 통해서 동시에 두 개이상의 프로세스가 하나의 자원에 접근하지 못하도록 막아줍니다.

Race Condition이 무엇인가요?

여러 프로세스들이 동시에 공유 데이터에 접근하는 상황을 말합니다. 이 때, 데이터의 일관성이 깨지는 문제가 발생합니다.

 

Race Condition을 어떻게 해결할 수 있나요?

Mutual Exclusion (상호배제)

접근해서는 안되는 자원에 동시에 접근하지 못하게 하는 동기화 기법입니다.

Progress (진행)

임계 구역에 어떤 프로세스도 진입하지 않았다면, 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 합니다.

Bounded Waiting(유한 대기)

임계 구역에 들어오기 위해 프로세스가 무한정 대기해서는 안되고, 언젠간 임계 구역에 들어올 수 있어야 합니다. 

Critical Section에 대해 설명해주세요.

여러 프로세스들이 공유 자원에 접근할 때 문제가 발생하는 코드 영역을 임계 영역 (critical section)이라고 합니다. 

Mutual Exclusion에 대해 설명해주세요.

동시에 접근해서는 안되는 자원(critical section)에 접근하지 못하게 하는 것이 상호 배제 입니다.

 

예를 들어서, 계좌에 잔액이 10만원이 있고 프로세스 A는 읽어들인 잔액에 2만원을 더하고, B는 5만원을 더한다고 가정합시다. 우리는 총 결과값이 17만원임을 예상할 수 있지만, 결과값이 15만원인 예외 경우가 생길 수 있습니다.

A의 작업이 끝나기도 전에, B 프로세스가 실행된다면 초기 금액인 10만원을 읽고 5만원을 더한 15만원이 결과값으로 나옵니다. 이를 방지하기 위해, 한 프로세스가 잔액에 접근했을 때는 다른 프로세스는 대기해야 합니다.

Mutual Exclusion을 할 수 있는 방법은?

뮤텍스, 세마포어, 모니터를 통해서 상호 배제 (Mutual Exclusion)을 할 수 있습니다.

뮤텍스(Mutex)에 대해 설명해주세요.

공유된 자원의 데이터 혹은 임계 영역에 하나의 프로세스 혹은 쓰레드가 접근하는 것을 막아줍니다.

세마포어에 대해 설명해주세요.

공유된 자원의 데이터 혹은 임계 영역에 여러 프로세스 혹은 쓰레드가 접근하는 것을 막아줍니다.

세마포어에는 P연산과, S연산이 존재하는데, 각자 하는 역할이 다릅니다.

Wait(P연산)과 Signal(S연산)에 대해 설명해주세요

• P연산은 자원을 획득하는 것이고, S연산은 자원을 다 사용하고 나서 반납하는 것 입니다.
• 즉, P연산은 락을 거는 과정이고 S연산은 락을 푸는 과정이라고 이해하면 됩니다.
• atomic 연산에 의해서만 접근 가능합니다.

P(S): while(S <= 0) do no-op:
         S--; 

 

V(S):
         S++;

busy-wait, block/wake-up에 대해서 설명해주세요

busy-wait을 구현한 방식은 스핀 락 이라고 말합니다.

자원이 없는 경우에, P연산을 하게되면 while문을 계속 돌며 대기하다가 CPU 대기 시간이 종료되면 반납하는 문제가 있습니다.

 

block & wake-up을 구현한 방식은 슬립 락 이라고 말합니다.

세마포를 획득할 수 없는 경우에, 프로세스를 block 처리하고 대기 큐에 넣어두고, 쓰고 나서 반납을 하게 되는 경우에 block된 프로세스를 wakeup 하여 반납하고 대기 큐에서 제거합니다.

P(S):  S.value--;
          if (S.value < 0) {
               block();
          }

 

V(S): S.value++;
          if (S.value <= 0) {
               wakeup(P);
          }

 

busy-wait과 block/wakeup의 장단점을 비교해주세요

• 일반적으로 block/wakeup을 쓰는 방식이 효율적 입니다.
  • 자원이 없는 경우를 생각해봅시다. 
• 임계 영역이 긴 경우, block/wakeup이 효율적이지만, 매우 짧은 경우 block/wakeup의 오버헤드가 busy-wait보다 더 커질 수 있기 때문에 유의해야 합니다.

counting semaphore와 binary semaphore에 대해 설명해주세요

• binary semaphore는 0또는 1만 가질 수 있습니다. 주로 mutual exclusion(상호 배제) 용도로 사용합니다.
• 변수값이 0이나 1이 아닐 때, counting semaphore라고 하는데 자원의 갯수가 여러개일 때 사용되고, 여분의 자원 갯수를 세는데 사용됩니다.

세마포어의 문제점이 무엇일까요?

• 한번의 실수가 모든 시스템에 치명적 영향을 줍니다.

락을 획득한 후에, 또 락을 획득하면 데드락이 발생할 수 있고, 락의 순서가 바뀐다면 상호 배제가 깨집니다.

뮤텍스(Mutex)와 이진 세마포어의 차이에 대해 설명해주세요.

• 뮤텍스는 락을 획득한 프로세스만이 해제를 가능하지만, 세마포어 같은 경우 소유권이 없기 때문에 다른 프로세스도 세마포어를 해지할 수 있습니다.
• 뮤텍스는 하나의 프로세스 혹은 쓰레드가 접근하는 것을 막아준다면, 이진 세마포어는 두개 이상의 쓰레드나 프로세스가 접근하는 것을 막아줍니다. 

둘다 상호 배제를 위해서 쓰입니다. 

모니터에 대해 설명해주세요.

세마포어에는 한번의 실수가 발생했을 떄 시스템에 치명적인 영향을 주는 단점이 있었는데, 이를 보완하기 위해 모니터가 등장했습니다. 

프로그래머가 직접 락을 걸 필요가 없이, 모니터 내부의 인터페이스를 통해서 공유 자원에 접근하면 자동으로 처리되고, 또 이를 통해서 임계 구역을 보호할 수 있습니다.

 

모니터에서는 조건 변수 (condition variable)을 사용하는데 이를 통해서 특정 조건이 완료될 때까지 block 상태를 유지시킵니다.

• wait(): 모니터 큐에서 자신의 차례가 올 때 까지 대기합니다. 
• signal(): 다음 프로세스에 순서를 넘겨줍니다.

데드락이 무엇인가요?

데드락은 교착상태라고 표현하기도 하며, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 기다리며 무한 대기에 빠지는 상태를 말합니다.

 

데드락 발생 조건 4가지를 설명해 주세요.

상호배제

매 순간 하나의 프로세스만이 자원을 사용할 수 있는것을 말합니다.

ex) 프린터를 사용하는 동안 다른 프로세스가 프린터를 사용할 수 없습니다.

 

점유와 대기

자원을 가진 프로세스가 다른 자원을 기다릴 때 보유한 자원을 놓지 않고 계속 가지고 있는 상태를 말합니다. 

ex) 프로세스 A가 프린터를 사용중이며 스캐너 사용을 요청하며 대기하고, 프로세스 B는 스캐너를 사용하며 프린터 사용을 요청하며 대기하는 상황을 말합니다.

비선점

이미 할당된 프로세스의 자원을 다른 프로세스가 강제로 뺴앗지 못하는 상황을 말합니다.

 

원형 대기

자원을 기다리는 프로세스간에 사이클이 형성되어야 하는 것을 말합니다.

ex) 프로세스 A가 자원 1을 점유하고 자원 2를 대기하고, 프로세스 B가 자원 2를 점유한 채 자원 1을 기다리는 경우 입니다.

데드락을 막는 방법에 대해 설명해주세요.

데드락 방지

• 상호 배제: 모든 자원이 공유 가능해야 합니다. 
• 점유 대기: 프로세스가 자원을 요청할 떄 어떤 자원도 가지고 있지 않아야 한다.
  • 프로세스 시작 시 모든 필요한 자원을 미리 할당받는 방법
  • 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청
• 비선점: 이미 할당된 프로세스의 자원을 빼앗아 올 수 있는 경우 데드락이 발생하지 않습니다. 
• 원형 대기: 자원에 대해서 순서를 정하고 오름차순 순서로 자원을 할당받게 한다면 데드락이 발생하지 않습니다. 

전체적인 성능 저하 및 starvation 문제가 발생하기 떄문에 비효율적인 방법입니다.

데드락 회피

데드락의 가능성이 있는 요청에 대해선, 자원을 할당하지 않습니다. 프로세스가 시작 될 때 자원 별 최대 사용량을 통해서 현재 남아있는 자원과 요청으로 들어오는 자원을 비교할 수 있습니다.

 

자원의 instance가 하나라면 자원 할당 그래프를 사용할 수 있고, 여러개라면 banker's 알고리즘을 통해서 회피할 수 있습니다. 

 

데드락 검출 및 회복

데드락 검출은 크게 두가지로 분류할 수 있는데, 타임아웃을 위한 검출과 자원 할당 그래프를 이용한 검출 두가지가 있습니다.

 

• 타임아웃을 이용하는 방법

가벼운 교착 상태 검출이라고도 불리며, 일정 시간 동안 작업이 진행되지 않은 프로세스를 데드락이 발생했다고 간주하고 처리합니다. 이 방법은 데드락 외의 이유로 작업이 진행되지 않은 프로세스까지 종료시킨다는 단점이 있으나, 대부분의 OS나 운영체제에서 사용됩니다.

 

• 자원 할당 그래프를 이용하는 방법

작업이 너무 많아 구현하기가 힘들기 때문에 무거운 교착 상태 검출이라고 불립니다,

 

교착 상태 회복에도 두가지 방법이 있는데,

• 선점을 통한 회복

교착상태가 해결될 때 까지 다른 프로세스로부터 자원을 강제로 빼앗아 한 프로세스에 할당합니다. 

• 프로세스 강제 종료를 통한 회복

교착 상태에 놓인 프로세스들을 모두 동시에 종료하는 방법은 확실하지만 종료된 프로세스들이 다시 실행하면 다시 교착 상태를 일으킬 수 있습니다.

 

교착 상태가 없어질 때 까지 프로세스들을 하나씩 종료하는 방법은 어떤 프로세스들을 먼저 종료시킬지에 대한 기준이 필요합니다. 예를 들면 우선 순위가 낮은 프로세스, 혹은 작업 시간이 짧은 프로세스들을 우선적으로 종료합니다. 이 방식은 교착 상태가 없어졌는지 여부를 판단하는 과정에서 오버헤드가 발생하고, 시스템에 상당한 부하를 줄 수 있습니다. 

 

데드락 무시

• 현대의 OS가 대부분 사용
• 사용자가 직접 인터럽트를 걸어서 처리합니다
• 효율성과 복잡성을 고려했을 떄, 교착상태를 다루는 것이 오히려 추가적인 비용과 성능 저하를 일으킬 수 있기 때문입니다.

https://velog.io/@chappi/OS%EB%8A%94-%ED%95%A0%EA%BB%80%EB%8D%B0-%ED%95%B5%EC%8B%AC%EB%A7%8C-%ED%95%A9%EB%8B%88%EB%8B%A4.-8%ED%8E%B8-Critical-section-%EC%9E%84%EA%B3%84-%EA%B5%AC%EC%97%AD2-mutex-semaphore-monitor-condition-variable

OS는 할껀데 핵심만 합니다. 9편 Critical section (임계 구역2) , mutex, semaphore, monitor, condition variable

 

https://work2type.tistory.com/entry/%EB%8F%99%EC%8B%9C%EC%84%B1%EA%B3%BC-%EB%B3%91%EB%A0%AC%EC%84%B1%EC%9D%98-%EC%B0%A8%EC%9D%B4

[CS] 동시성과 병렬성의 차이

 

https://www.baeldung.com/cs/concurrency-vs-parallelism