운영체제를 공부해보아요

atomic

Atomic operation, 즉 원자적 연산은 더 이상 분할할 수 없는 단위를 의미한다. 이러한 명령어는 수행되거나 또는 되지 않거나 둘 중 하나고, 부분적으로 수행되지 않는다.

동기화 (Synchronization)

동기화는 프로세스들이 서로 동작을 맞추고 정보를 공유하는 것이다. 다중프로그래밍 시스템에서 여러 프로세스가 공유 자원에 접근할 수 있기 때문에 이에 대해 동기화가 필요하다.

Lock

두 개 이상의 thread가 동시에 공유 자원에 접근할 경우 race condition이 발생해서 결과를 예측하기 어렵기 때문에 Lock이 필요하다

Race Condition: 실행 순서에 따라 결과 값이 달라지는 현상.

임계구역

임계구역, 즉 critical section은 공유 자원을 접근하는 프로세스 내부의 코드 영역을 의미한다.

여러 프로세스가 동시에 공유 자원에 접근하면 시간 차이 등으로 인해 잘못된 결과를 만들 수 있기 때문에 두 개 이상의 프로세스가 임계영역에 접근하면 안된다.

상호배제

Mutual Exclusion: 임계구역을 어느 시점에서 단 한개의 프로세스만 사용할 수 있도록 하고, 다른 프로세스의 접근을 막는 것

피터슨 알고리즘

피터슨 알고리즘: flag와 turn 변수로 임계영역에 들어갈 프로세스/스레드를 결정하는 방식

• 데커 알고리즘과 유사하지만, 상대방에게 진입기회를 양보한다는 차이가 존재한다
• boolean flag[2]와 int turn의 공유 변수를 가진다
• 구조
  • 임계영역에 진입하려면 먼저 flag[i] = true로 임계영역에 들어가고 싶다는 의사를 표시한다
  • turn = j로 설정한 후에, 프로세스 j가 임계영역에 들어갈 의사가 없다면(flag[j] = false) 임계영역에 들어갈 수 있다
  • 두 개의 프로세스가 동시에 임계영역에 진입하려고 하면 turn변수가 늦게 수행된 프로세스가 기회를 양보한다
  • 임계영역에서 나오는 프로세스는 flag[i]를 false로 하여 다른 프로세스가 임계영역에 들어가도록 허용한다

데커 알고리즘

데커 알고리즘: 두 개의 프로세스를 위한 상호배제의 최초의 소프트웨어 해결법

• boolean flag[2]와 int turn의 공유 변수를 가진다
  • 초기값:
    • flag[0] = flag[1] = false
    • turn = 0 or turn = 1
• 과정
  • 임계영역에 들어가려면 flag[i] = true 설정 후 Pj가 임계영역에 들어가려 하거나 이미 임계영역에 있는지 확인한다
  • Pj가 임계 구역에 있지 않고 들어가려 하지도 않으면 flag[j] = false, Pj가 임계영역으로 진입한다
  • 임계영역에서 나오는 Pi 프로세스는 빠져 나옴(flag[i] = false)을 알리고, turn은 기회를 양보하기 위해 j로 함

test_and_set

진입조건을 확인한 후에 그리고 진입여부를 반영하기 전에 인터럽트가 발생해 스레드가 진입했다는 것이 반영되지 않아 다른 스레드가 이를 확인하지 못해 동시 진입하게 되는 현상을 막기 위하여...

한 줄에 조건 확인하고 여부 반영한다

while (TestAndSet(lock));

1. lock 변수의 값을 먼저 테스트한다: 0인지 1인지
2. lock 변수 값을 1로 설정한다

장점: 소프트웨어적 코딩이 아니라 하드웨어 명령어로 두 줄을 한 줄로 합쳐서 시스템의 효율이 높아지고 인터럽트를 방지할 수 있다

하지만, 이 방식은 mutual exclusion을 만족시키지만 임계구역의 해결조건 중 bounded-waiting requirement을 만족시키지 않는다

모니터

모니터: 세마포어를 실제로 구현한 프로그램

• 용도: 순차적으로만 사용할 수 있는 공유 자원 또는 공유 자원 그룹을 할당한다
• 병행성 구조: 공유 자원을 하나의 프로세스가 독접하지 않고 병행해서 처리한다
• 구조
  • 모니터 내 자원을 원하는 프로세스는 반드시 해당 모니터의 entry를 호출해야 한다 (공유 자원 접근 함수)
  • 모니터 외부의 프로세스는 모니터 내부의 데이터를 직접 접근할 수는 없다
  • 스위치 개념 기반, 한 번에 하나의 프로세스만이 모니터에 진입할 수 있다
  • 2개의 큐를 가진다: mutual exclusion queue, conditional synchronization queue
• 연산: Wait, Signal

Java는 모니터를 제공하고, 자바의 모든 개체가 모니터가 될 수 있다.

class C {
  private int value, ...;     // 공유 변수
  synchronized void Foo() {   // 배타동기
    // ...
  }
  synchronized void Goo() {
    // ...
  }
  void H() {
    // ...
  }
}

• synchronized 키워드: 상호배타 함수로 선언한다
  • 이 키워드를 갖는 두 함수가 같은 임계구역을 갖는다는 뜻
  • 한 함수에서 한 쓰레드가 수행 중이면 이 함수와 다른 함수에도 다른 쓰레드는 접근할 수 없다.
• 메서드 호출
  • wait(): 호출한 스레드를 조건동기 큐에 삽입한다
  • notify(): 조건동기 큐에 있는 하나의 스레드를 깨운다
  • notifyAll(): 조건동기 큐에 있는 모든 스레드를 깨운다

배리어

메모리 배리어 명령어가 수행되면, 시스템은 현재까지의 load and store 명령어들이 barrier 이후의 load and store 이전에 완료되도록 보장한다

test_and_set()과 compare_and_swap() 명령어가 프로세서에서 특정값에 대한 load and store 과정의 atomic한 실행을 보장한다

compare_and_swap

• 현대 CPU에서는 원자적 연산으로 제공된다

public static class MyLock {
    private AtomicBoolean locked = new AtomicBoolean(false);

    public boolean lock() {
        return locked.compareAndSet(false, true);
    }
}

뮤텍스와 세마포어

뮤텍스와 세마포어는 임계구역에 여러 프로세스 또는 스레드가 함부로 접근할 수 없도록 관리하는 방식이다.

동시성과 병렬성

동시성 (Concurrency):

• 동시에 실행되는 것 같이 보이는 것
• 싱글 코어에서 멀티쓰레드를 동작 시키는 방식
• 논리적인 개념

병렬성 (Parallelism):

• 실제로 동시에 여러 작업이 처리되는 것
• 멀티 코어에서 멀티 쓰레드를 동작시키는 방식
• 물리적인 개념

뮤텍스

뮤텍스: 동시프로그래밍 환경에서 공유 불가능한 자원의 동시사용을 피하기 위한 알고리즘

• 임계구역을 접근하는 스레드들의 실행시간이 겹치지 않고 각각 단독으로 실행되도록 한다
  • 상호배제 (Mutual Exclusion) 구현
• 한 프로세스에 의해 소유될 수 있는 key를 기반응로 한 상호배제
  • key에 해당하는 객체가 주로 존재하며, 이 객체를 소유한 스레드/프로세스만이 공유자원에 접근할 수 있다.
• 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 동기화/락을 사용한다
• 뮤텍스 객체를 두 스레드가 동시에 사용할 수는 없다

세마포어

세마포어: 멀티프로그래밍 환경에서 공유된 자원에 대한 접근을 제한하는 방법

• 공유자원의 상태로 나타낼 수 있는 카운터와 유사하다
  • 사용하고 있는 스레드/프로세스의 수를 공통으로 관리하는 하나의 값을 이용해 상호배제를 구현한다
    • 주로 운영체제/커널의 한 지정된 저장장치 내의 값이다
  • 일반적으로 비교적 긴 시간을 확보하는 리소스에 대한 이용에 사용한다
• 공유 자원에 접근할 수 있는 프로세스의 최대 허용치만큼만 동시에 사용자가 접근 가능하다
• 각 프로세스는 세마포어의 값을 확인하고 변경할 수 있다
  • 세마포어를 사용하는 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에는 그 값을 변경해서 다른 세마포어 사용자들이 확인하고 대기/사용하도록 해야 한다
• 프로세스가 자원에 접근할 때, 최대 허용치가 차지 않았으면 즉시 자원을 사용하고, 최대 허용치가 찼으면 재시도 전 일정시간을 대기한다
• 세마포어는 이진수를 사용하거나 추가적인 값을 사용할 수 있다.

뮤텍스 vs. 세마포어

• 동기화 대상
  • 뮤텍스) 동기화 대상은 딱 1개
  • 세마포어) 동기화 대상이 1개 이상
• 자원 소유
  • 뮤텍스) 자원 소유 가능
  • 세마포어) 자원 소유 불가
• 해제 권한
  • 뮤텍스) 뮤텍스를 소유하고 있는 스레드만이 뮤텍스 해제 가능
  • 세마포어) 세마포어를 소유하지 않는 스레드가 세마포어 해제 가능
• 범위
  • 뮤텍스) 프로세스의 범위로 프로세스가 종료될 때 자동으로 clean up된다
  • 세마포어) 시스템 범위에 걸쳐 있고, 파일 시스템 상의 파일로 존재한다

교착상태 (Deadlock)

프로세스A와 프로세스B가 존재할 때, 각 프로세스가 서로가 사용하고 있는 자원을 필요로 하여 두 프로세스 모두 상대방의 작업이 끝나기만을 기다려 결과적으로 아무것도 완료되지 못하는 상태를 뜻한다.

데드락이 발생하기 위해서는 4가지 조건이 필요하다.

교착 상태 조건

• 상호배제 (Mutual Exclusion): 자원은 한 번에 한 프로세스만 사용할 수 있다
  • race condition 문제를 해결하기 위해 두 개 이상의 프로세스/스레드가 동시에 한 공유 자원에 접근할 수 없도록한다
  • 자원에 대한 배타적 통제권을 부여해 해당 자원을 오직 하나의 프로세스/스레드만 쓰겠다는 말
  • 하나의 프로세스/스레드가 자원을 독점적으로 사용하면, 다른 스레드가 자원에 접근하려고 락을 획득하기 위해 무한 대기하는 상황이 발생할 수 있다
• 점유상태로 대기 (Hold and Wait): 프로세스가 최소 하나의 자원을 점유하고 다른 프로세스가 사용하는 자원을 할당받기 위해 대기한다
  • 여러 개의 자원을 동시에 써야 하는 경우, 락을 획득한 자원에 대한 처리는 끝났는데, 남은 자원의 락을 다른 스레드가 가지고 있어 무한정으로 대기한다
  • 자신이 점유하고 있는 락도 해제해줘야 그 락을 획득하기 위해 기다리고 있는 다른 스레드들이 자원에 접근하여 처리를 할 수 있을텐데 어느 스레드도 락을 해제하지 않아 서로 무한정 대기하는 상태가 발생할 수 있다
• 선점 불가 (No preemption): 다른 프로세스가 사용중인 자원을 강제로 뺏을 수 없다
  • 다른 프로세스/스레드가 자원을 선점하고 있어서 자원을 뺏어올 방법이 없다
  • 만일 하나의 스레드가 공유자원의 락을 획득해 선점하고 있으면, 그 공유자원에 접근해야 하는 다른 스레드들은 아무리 잠깐 처리하면 끝나는 상황이라도 락을 빼앗을 방법이 없어서 무한정 대기해야 한다
• 순환성 대기 (Circular Wait): 프로세스A가 프로세스B가 사용 중인 자원을 할당받기 위해 대기하고 프로세스B는 프로세스A의 자원을 할당받으려 대기하는 상태
  • 프로세스가 어느 자원을 점유하고 있고 다른 자원을 요청하여 대기하는데, 순환적인 구조가 형성되는 것
  • 락을 해제하고 락을 획득하는 과정이 순차적으로 잘 일어나면 좋겠지만, 어느 순간 모드 프로세스가 락을 획득하려고 대기하여 모든 프로세스가 무한대기에 놓인 상황이 발생할 수 있다

데드락 해결 방법

• 교착 상태 예방: 교착상태 발생조건 중 하나 이상을 제거해 데드락 발생 가능성을 차단한다
  • 상호배제 조건 방지: 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다
    • 근본적으로 공유가 불가능한 자원도 존재한다
    • 추후 동기화 관련 문제가 발생할 수 있다
  • 점유대기 조건 방지: 자원을 요청할 때 다른 자원들을 점유하고 있지 않다는 것을 보장한다
    • 프로세스가 실행되기 전 필요한 모든 자원을 할당받고 시작한다
    • 프로세스가 자원을 점유하지 않은 상태에서만 자원을 요청할 수 있도록 한다
    • 단점:
      • 나중에 사용할 자원도 실행 전에 할당받아야 하기 때문에 자원 이용률이 감소한다
      • 기아 상태 가능성이 존재한다
  • 비선점 조건 방지: 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정한다
    • 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 요청 자원을 사용할 수 검사한다
    • 사용이 가능하면 점유하고 있는 자원을 반납한다
  • 순환대기 조건 방지: 자원을 사용하기 위해 순환형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 한다
    • 자원에 고유 번호를 할당하여 번호 순서대로 자원을 요구하도록 하게 할 수 있다
    • 각 프로세스는 현재 점유 중인 자원의 고유번호를 기준으로 앞/뒤 중 한 방향으로만 자원을 요구할 수 있게 할 수 있다
  • 단점:
    • 시스템의 처리량이나 효율성을 떨어트리기 쉽다
    • 자원 효율성이 떨어진다
    • 비용이 많이 든다
• 교착상태 회피: 교착상태가 발생하기 전, 교착상태를 예측하고 회피한다
  • Safe sequence/state (안정 상태): 시스틈의 프로세스들이 요청하는 모든 자원을 데드락 가능성 없이 차례로 모두에게 할당해줄 수 있는 상태
  • 불안정 상태: 안정상태가 아닌 상황으로, 데드락 발생 가능성이 존재한다
    • 교착 상태가 불안정 상태의 부분집합
  • 사전검사를 통해 자원 할당 후에도 시스템이 안정상태면 자원을 할당하고, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기한다
• 교착상태 탐지 복구
  • 탐지: allocation, request, available 등으로 시스템에 데드락이 발생했는지 탐색한다
  • 복구: 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제해서 회복한다
    • 프로세스 종료
      • 교착상태에 빠진 모든 프로세스를 중단시키거나,
        - 계속 연산 중이던 프로세스들이 모두 일시 중단되어 부분 결과가 폐기될 수 있는 부작용 존재
      • 교착상태가 제거될 때까지 한 프로세스씩 중지시킨다
        • 매번 탐지 알고리즘을 호출 및 수행해야 해서 작업이 부담될 수 있다
    • 자원 선점하기
      • 교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스는 일시정지한다
      • 우선순위가 낮은 프로세스, 수행된 횟수가 적은 프로세스 위주로 프로세스의 자원을 선점한다
      • 희생자 선택: 어느 자원/프로세스들이 먼저 선점될 것인가?
        • 비용 최소화를 위해 각 프로세스가 점유하고 있는 자원의 수와 프로세스가 지금까지 실행하는데 소요한 시간과 같은 매개변수를 고려한다
      • 후퇴: 프로세스로부터 자원을 선점하려면 그 프로세스를 어떻게 해야하는가
        • 안정 상태 여부를 결정하기 어렵기 때문에 프로세스를 그냥 중지시키고 재시작한다
      • 기아상태: 기아상태를 발생하지 않도록 어떻게 보장할 것인가?
        - 희생자를 선택할 때 주로 비용에 근거하기 때문에 동일한 프로세스가 항상 희생자로 선택될 수 있다
        • 이 프로세스는 일을 수행하지 못하고 기아상태가 되기 쉽다
        • 희생자를 선택할 때 한정된 시간 동안만 희생될 것을 보장해야 한다
  • 단점: 어느 시점에서 교착상태를 탐지해야 하는지 알 수 없기 때문에 주기적으로 알고리즘을 실행해야 된다. 비용이 크고 실용적이지 않다
• 교착상태 무시: 교착상태를 무시하고 특별한 조치를 취하지 않는다
  • 교착상태의 발생확률이 낮으면 효율적인 방법이다
    • 많은 시스템에서 교착 상태는 드물기 때문에 처리에 대한 부가적인 비용이 그만한 가치를 안한다
  • 교착상태가 발생하면 프로세스 종료 또는 자원 선점으로 회복한다
  • 대부분의 운영체제가 사용하는 방법이다

라이브락

한 프로세스가 이미 자원을 점유한 상태에서 다른 프로세스가 그 자원을 사용하기 위해 무한정 대기상태에 빠지는 것

지극히 정상적이지만 동시에 문제가 있다.

producer_consumer_problem

생산자: 데이터를 생산하는 자
소비자: 데이터를 소비하는 자

(예) 컴파일러가 내놓은 코드를 어셈블러에서 입력받는다. 컴파일러 (생산자), 어셈블러 (소비자)
(예) 서버에서 송신한 데이터를 클라이언트에서 수신받는다. 서버 (생산자), 클라이언트 (소비자)

생산자와 소비자의 작업 속도에 차이가 있기 때문에 생산자는 생산한 데이터를 소비자가 아니라 생산자와 소비자 사이에 놓인 버퍼에 저장한다. 이 버퍼는 메모리 상에 존재하기 때문에 크기가 유한하다. 버퍼가 차면 생산자는 더 이상 데이터를 저장할 수 없고, 버퍼가 비었으면 소비자는 버퍼에서 데이터를 가져갈 수 없다

주로 생산자가 속도과 더 빠르다.

생산자-소비자 문제: 생산자가 데이터를 생성하여 버퍼에 저장하고, 소비자가 버퍼에서 데이터를 가져와 소비하는 과정에서 발생할 수 있는 문제
(예) 공유 자원에 대한 임계구역 문제, busy waiting 문제 등
프로세스 동기화를 통해 해결한다

busy waiting: 프로세스 동기화 상황에서 프로세스가 자원에 대한 접근 권한을 얻기 위해 될 때까지 접근 조건을 반복적으로 확인하는 일

Readers_Writes_Problem

독자: 데이터를 읽기만 하는 프로세스
저자: 읽고 수정하는 프로세스

독자-저자 문제: 다수의 독자와 다수의 저자가 하나의 공통 데이터베이스를 사용할 때 발생할 수 있는 문제
프로세스 동기화로 해결 가능

공유되는 데이터베이스를 임계구역으로 지정할 수도 있지만 데이터 수정하지 않는 독자에게도 mutex 처리하는 것은 비효율적이다. 독자끼리는 임계구역에 들어가도 데이터 일관성이 보장된다는 장점을 활용하자.

Dining_Phiplosophers_Problem

1. 왼쪽 젓가락부터 집어든다. 다른 철학자가 이미 왼쪽 젓가락을 쓰고 있다면 그가 내려놓을 때까지 생각하며 대기한다.

2. 왼쪽을 들었으면 오른쪽 젓가락을 든다. 들 수 없다면 1번과 마찬가지로 들 수 있을 때까지 생각하며 대기한다.

3. 두 젓가락을 모두 들었다면 일정 시간동안 식사를 한다.

4. 식사를 마쳤으면 오른쪽 젓가락을 내려놓고, 그 다음 왼쪽 젓가락을 내려놓는다.

5. 다시 생각하다가 배고프면 1번으로 돌아간다.

교착상태 발생의 4가지 필요조건을 모두 만족한다

모든 철학자가 동시에 배고파서 왼쪽 젓가락을 집어들면, 오른쪽 젓가락은 이미 자신의 우측에 앉은 철학자가 가져가서 모두가 영원히 오른쪽을 들지못한다 > 교착상태
교착상태에 빠진 철학자는 기아현상으로 굶어죽는다

1. 상호배타: 젓가락은 한 번에 한 철학자만 사용
2. 보유 및 대기: 집어든 젓가락은 계속 들은채로 남이 사용중인 반대 젓가락을 기다린다
3. 비선점: 이미 가져간 젓가락을 뺏을 수 없다
4. 순환형 대기: 모든 철학자가 자신의 오른쪽에 앉은 철학자가 젓가락을 놓기를 기다린다.

---

https://hyeo-noo.tistory.com/105
https://seamless.tistory.com/42
https://m.blog.naver.com/hirit808/221785171412
https://kimcoder.tistory.com/306
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ecarooce&logNo=140050543483
https://overcome-the-limits.tistory.com/342
https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-11.-%EB%AA%A8%EB%8B%88%ED%84%B0
https://jhnyang.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-Atomic%EB%B0%A9%EB%B2%95testandset-CompareandSwap-Bounded-waiting
https://velog.io/@seokjun0915/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EB%B2%A0%EB%A6%AC%EC%96%B4
https://roxxy.tistory.com/entry/OS-%EA%B2%BD%EC%9F%81%EC%83%81%ED%83%9C-%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C-%EB%9D%BC%EC%9D%B4%EB%B8%8C%EB%9D%BD-Race-Condition-Deadlock-Livelock
https://m.blog.naver.com/hirit808/221786966867