운영체제 스터디 - 2

최민수·2023년 8월 13일
cs전공지식스터디추가공부
0

CS 전공지식

목록 보기
34/36

0813 운영체제
https://github.com/VSFe/Tech-Interview
면접 대비 질문 정리 깃허브를 참고해서 CS를 대비해 보고 있다.

이번 주제는 운영체제. 범위는 질문 #1 ~ #15 까지이다
마지막 부분인 #09 ~ #15 까지 정리한 내용이다.

9. Deadlock 에 대해 설명해 주세요.

"데드락(Deadlock)"은 동시 컴퓨팅에서 두 개 이상의 프로세스가 서로 다른 프로세스가 홀딩하고 있는 리소스를 기다리며 진행할 수 없는 상황을 말합니다. , 프로세스들은 절대 해제되지 않을 리소스를 기다리는 루프에 갇혀 진행이 정체된 상태입니다.

데드락이 발생하기 위한 4가지 조건

이 네 가지 조건은 동시에 모두 참이어야 데드락이 발생합니다:

  1. 상호 배제(Mutual Exclusion)

    적어도 하나의 리소스는 여러 프로세스 사이에서 동시에 공유될 수 없는 성격을 가져야 합니다. 즉, 한 번에 하나의 프로세스만 사용할 수 있는 상태여야 합니다.

    예를 들어, 한 프로세스가 프린터에 독점적인 액세스를 가지고 있다면, 다른 프로세스는 프린터가 해제될 때까지 기다려야 합니다.

  2. 점유 대기(Hold and Wait)

    프로세스들은 적어도 하나의 리소스를 보유하고 있으며, 다른 프로세스가 보유한 추가 리소스를 얻기 위해 기다리고 있어야 합니다. 만약 다른 프로세스가 요청한 리소스를 보유하고 있다면 이는 순환 대기를 유발할 수 있습니다.

  3. 비선점 불가(No Preemption)

    리소스는 홀딩한 프로세스로부터 강제로 빼앗아갈 수 없습니다. 리소스는 오직 홀딩한 프로세스 자신만이 자발적으로 해제할 수 있습니다. 이는 프로세스는 새로운 리소스를 요청하기 전에 이미 가진 모든 리소스를 해제해야 함을 의미합니다.

  4. 순환 대기(Circular Wait)

    두 개 이상의 프로세스 간에 순환적인 의존 관계가 존재하며, 각 프로세스가 사슬에서 다음 프로세스가 홀딩한 리소스를 기다리고 있는 상황입니다. 이는 프로세스 간의 의존성 순환을 형성하여 교착 상태를 유발합니다.

이 중에서 한 가지만 부정하면 데드락을 피할 수 있는 이유

데드락을 방지하려면 이 중 하나 이상의 조건을 부정해야 합니다.

예를 들어, 리소스에 순서를 부여하여 순환 대기를 제거하면 데드락을 피할 수 있습니다.

또한 리소스를 공유 가능하게 만들어 버리면 상호 배제 조건을 부정하여 데드락을 피할 수 있습니다.

또 조건을 만족하지 못하면 대기하는 것이 아니라 해제시켜 보유 및 대기 조건을 부정하면 데드락을 피할 수 있습니다.

마지막으로 비선점 방식을 부정해서 리소스를 강제로 빼앗을 수 있게 한다면 데드락을 피할 수 있습니다.

예방법?

4가지 조건 중 한 가지만 부정하면 데드락을 피할 수 있기 때문에 마찬가지 전략으로 간다.

  1. 상호 배제 방지:
    • 리소스를 공유할 수 있도록 시스템을 설계하거나 여러 프로세스가 동시에 리소스에 액세스할 수 있도록 허용합니다.
    • 여러 프로세스가 동시에 리소스를 읽을 수 있지만 쓰기는 하나만 할 수 있는 읽기/쓰기 잠금과 같은 기술을 사용합니다.
  2. 보유 및 대기 방지:
    • 프로세스가 실행을 시작하기 전에 필요한 모든 리소스를 미리 요청해야 하는 정책을 구현합니다.
    • "리소스 할당 그래프" 기법을 사용하여 리소스 요청을 승인하기 전에 잠재적인 순환 대기를 확인합니다.
  3. 비선점 방지:
    • 필요한 경우 시스템이 프로세스로부터 리소스를 강제로 빼앗을 수 있는 리소스 선점 개념을 도입합니다.
    • 프로세스에 우선순위를 할당하고 필요한 경우 높은 우선순위 프로세스에게 리소스를 할당합니다.
  4. 순환 대기 방지:
    • 리소스에 전체적인 순서를 할당하여 순환 대기의 가능성을 없앱니다. 예를 들어 리소스에 고유 번호를 할당하여 미리 정해진 순서를 만들 수 있습니다.

왜 현대 os는 deadlock을 예방하지 않을까?

데드락 예방 전략은 자원의 미사용으로 이어질 수 있으며, 데드락이 절박하지 않은 경우에도 프로세스가 리소스 액세스를 거부받을 수 있습니다. 자원 활용과 데드락 예방 간에 균형을 맞추는 것은 트레이드오프입니다.

또한 포괄적인 데드락 예방 메커니즘을 구현하는 것은 운영 체제에 상당한 오버헤드와 복잡성을 도입할 수 있습니다. 이는 시스템 성능에 영향을 미치며 시스템 내 버그나 오류 가능성을 증가시킬 수 있습니다.

마지막으로 현대 OS는 동적이며 프로세스가 자주 들어가고 나오는 특징이 있습니다. 프로세스의 리소스 요구 사항과 패턴은 시간이 지남에 따라 변경될 수 있으므로 모든 가능한 데드락 시나리오를 예측하고 예방하는 것이 어려울 수 있습니다.

10. 프로그램이 컴파일 되어, 실행되는 과정을 간략하게 설명해 주세요.

   +-------------------+        +-----------------+        +------------------+
   |   Source Code    |        |  Object Files   |        |   Executable     |
   | (Programming)    |        | (Intermediate)  |        |   Program        |
   +-------------------+        +-----------------+        +------------------+
          |                           |                           |
          |                           |                           |
          |                           |                           |
     +----v-----------+          +----v-----------+          +----v-----------+
     |    Compiler    |          |    Compiler    |          |     Linker      |
     |  (Compilation) |          |  (Compilation) |          |    (Linking)    |
     +----+-----------+          +----+-----------+          +----+-----------+
          |                           |                           |
          |      Object Files         |                           |
          +---------------------------+                           |
                              |                                    |
                              v                                    |
                    +------------------+                          |
                    |     Linker       |                          |
                    |    (Linking)     |                          |
                    +------------------+                          |
                              |                                    |
                              v                                    |
                     +----------------------+                      |
                     |      Executable      |                      |
                     |       Program        |                      |
                     +----------------------+
  1. 소스 코드 (프로그래밍): 프로세스는 프로그래밍 언어(C, C++, Java 등)를 사용하여 프로그램의 소스 코드를 작성하는 것으로 시작합니다.
  2. 컴파일 (컴파일러): 소스 코드는 컴파일러에 입력됩니다. 컴파일러는 어휘 분석, 구문 분석, 의미 분석, 최적화 및 코드 생성과 같은 다양한 작업을 수행합니다. 이 단계의 출력은 일반적으로 머신에서 읽을 수 있는 코드를 포함하는 하나 이상의 오브젝트 파일입니다.
  3. 오브젝트 파일 (중간 파일): 컴파일러는 하나 이상의 오브젝트 파일을 생성합니다. 이 파일에는 프로그램의 개별 함수 또는 부분에 대한 컴파일된 코드가 포함됩니다. 이 파일들은 아직 컴퓨터에서 직접 실행할 수 있는 형식이 아닙니다.
  4. 링커: 프로그램이 여러 개의 소스 파일로 구성되거나 외부 라이브러리를 사용하는 경우, 링커는 오브젝트 파일과 라이브러리를 하나의 실행 가능한 프로그램으로 결합합니다. 다른 부분 간의 참조를 해결하고 모든 것이 올바르게 연결되도록 보장합니다.
  5. 실행 가능한 프로그램: 링킹 단계의 최종 출력은 실행 가능한 프로그램입니다. 이 프로그램은 운영 체제에 의해 직접 실행될 수 있는 형식으로, 프로그램의 소스 코드에 지정된 작업을 수행하는 데 필요한 모든 명령과 데이터를 포함합니다.
  6. 실행: 실행 가능한 프로그램을 실행하면 운영 체제가 이를 메모리로 로드하고 명령을 한 단계씩 실행하여 프로그램의 소스 코드에 지정된 작업을 수행합니다.

컴파일 언어와 인터프리터 언어의 차이?

주요 차이점은 소스 코드가 실행되고 기계 코드로 번역되는 방식에 있습니다.

컴파일된 언어는 실행 전에 전체 소스 코드를 기계 코드로 번역하여 성능이 우수하지만 다른 프로그램으로의 이식성이 낮을 수 있습니다.

인터프리트 언어는 코드를 한 줄씩 실행하고 별도의 실행 파일을 생성하지 않으므로 이식성이 높지만 일반적으로 더 느립니다.

컴파일된 언어:

  1. 번역 과정:
    • 컴파일된 언어는 실행 전에 컴파일링 과정을 거칩니다. 전체 소스 코드는 컴파일러에 의해 기계 코드로 번역됩니다.
    • 컴파일러는 전체 코드베이스를 분석하고 최적화를 수행하며 실행 가능한 이진 파일이나 오브젝트 파일을 생성합니다.
  2. 실행:
    • 생성된 기계 코드는 컴퓨터의 하드웨어 및 운영 체제에 의해 직접 실행됩니다.
    • 한 번 컴파일된 프로그램은 소스 코드에 변경이 없는 한 여러 번 실행될 수 있습니다.
  3. 성능:
    • 컴파일된 언어는 일반적으로 미리 기계 코드로 효율적으로 번역되므로 성능이 우수합니다.
    • 컴파일 중 최적화는 더 빠른 실행 시간을 가능하게 합니다.
  4. 포터빌리티:
    • 컴파일된 실행 파일은 종종 대상 시스템의 아키텍처 및 운영 체제에 특화됩니다.
    • 여러 플랫폼을 지원하려면 각 대상 플랫폼에 대해 재컴파일이 필요할 수 있습니다.

인터프리트 언어:

  1. 번역 과정:
    • 인터프리트 언어는 별도의 컴파일링 과정을 거치지 않습니다. 소스 코드는 인터프리터에 의해 한 줄씩 실행됩니다.
    • 인터프리터는 각 코드 라인을 실행하기 바로 직전에 해당 라인을 기계 코드나 중간 코드로 번역합니다.
  2. 실행:
    • 인터프리터는 소스 코드를 직접 실행하며 별도의 실행 가능한 파일을 생성하지 않습니다.
    • 코드는 순차적으로 실행되며 코드에 변경이 있으면 재컴파일 없이 즉시 반영됩니다.
  3. 성능:
    • 인터프리트 언어는 실행 시 번역이 발생하므로 일반적으로 컴파일된 언어보다 느립니다.
    • 그러나 현대의 인터프리터는 종종 성능을 향상시키기 위한 최적화 기술을 포함합니다.
  4. 포터빌리티:
    • 인터프리트된 코드는 일반적으로 더 이식성이 높습니다. 재컴파일이 필요하지 않고 다양한 플랫폼에서 실행될 수 있습니다.
    • 인터프리터 자체는 각 플랫폼에 대해 사용 가능해야 합니다.

하이브리드 접근 방식:

  • 일부 언어인 Java와 C#은 컴파일과 인터프리테이션의 조합을 사용합니다. 이들은 소스 코드를 중간 바이트코드로 컴파일하고 이를 가상 머신(JVM 또는 .NET 런타임)에서 인터프리터로 실행합니다.

11. IPC가 무엇이고, 어떤 종류가 있는지 설명해 주세요.

"IPC"는 "Inter-Process Communication"의 줄임말로, 서로 다른 프로세스가 동시에 실행되는 환경에서 통신하고 데이터를 교환하는 메커니즘과 기술을 말합니다. 이런 프로세스는 같은 컴퓨터에서 실행되거나 네트워크를 통해 연결된 다른 컴퓨터에서 실행될 수 있습니다.

IPC가 중요한 이유는 서로 다른 프로세스의 활동을 조정하고 데이터와 자원을 공유하며 큰 소프트웨어 시스템의 다른 구성 요소 간의 협력을 가능하게 하기 때문입니다.

IPC의 종류

  1. 공유 메모리
프로세스는 일부 메모리를 공유함으로써 통신할 수 있으며, 이를 통해 해당 공유 영역에 데이터를 읽고 쓸 수 있습니다. 이 방법은 효율적이지만 데이터 훼손을 방지하기 위해 신중한 동기화가 필요합니다.

  1. 메시지 패싱
    프로세스는 서로에게 메시지를 보내어 통신할 수 있습니다. 이러한 메시지는 파이프, 소켓 및 메시지 큐와 같은 다양한 기술을 사용하여 보낼 수 있습니다.

  2. 동기화 메커니즘

    데이터를 보내는 것뿐만 아니라 프로세스는 종종 활동을 동기화해야 합니다. 세마포어, 뮤텍스(상호 배제) 및 조건 변수와 같은 기술을 사용하여 프로세스가 조정되도록 보장합니다.

  3. 원격 프로시저 호출 (RPC)

    이것은 더 높은 수준의 IPC 형태로, 프로세스가 원격 프로세스에서 로컬인 것처럼 프로시저나 함수를 호출할 수 있습니다. 이것은 분산 시스템에서 흔히 사용됩니다.

  4. 시그널

    시그널은 특정 이벤트를 나타내기 위해 프로세스가 수신하는 알림입니다. 예를 들어 프로세스는 다른 프로세스에게 특정 이벤트가 발생했음을 알리기 위해 시그널을 보낼 수 있습니다.

  5. 파일 시스템

    일부 운영 체제는 프로세스가 공통 파일이나 파일과 유사한 객체에 읽고 쓰는 방식으로 간접적으로 통신할 수 있는 메커니즘을 제공합니다.

Shared Memory 와 사용할 때의 주의점

"공유 메모리(Shared memory)"는 여러 프로세스 또는 스레드에서 접근 가능한 메모리 영역을 의미합니다.

이 공유 메모리 영역을 통해 프로세스와 스레드는 동일한 메모리 위치를 읽고 쓰면서 데이터를 직접 교환할 수 있습니다.

공유 메모리는 프로세스 간 통신(Inter-Process Communication, IPC)의 한 형태로, 프로세스 간 데이터 공유에 높은 성능을 제공할 수 있습니다.

주의사항)

  1. 동기화: 여러 프로세스 또는 스레드가 동시에 동일한 메모리에 접근할 수 있기 때문에 데이터 훼손이나 경쟁 상태(race condition)를 방지하기 위해 적절한 동기화 메커니즘을 사용해야 합니다. 뮤텍스, 세마포어 등의 동기화 원시(Primitive)를 사용하여 공유 메모리 접근을 제어해야 합니다.
  2. 데이터 일관성: 여러 프로세스가 동일한 데이터를 수정하는 경우 데이터 일관성을 유지해야 합니다. 이를 위해서는 락(locking), 크리티컬 섹션, 원자 연산 등의 메커니즘을 구현해야 할 수 있습니다.
  3. 메모리 관리: 적절한 메모리 관리가 중요합니다. 공유 메모리를 올바르게 할당하고 해제하여 메모리 누수나 잘못된 메모리 접근을 방지해야 합니다.
  4. 초기화와 정리: 공유 메모리를 사용하기 전에 올바르게 초기화하고 사용 후에 정리해야 다른 프로세스에 문제를 일으키거나 남은 자원을 방지할 수 있습니다.
  5. 보안: 공유 메모리는 보안 위험을 가질 수 있습니다. 공유 메모리에 접근하는 프로세스는 권한이 없는 데이터를 읽거나 수정할 가능성이 있습니다. 적절한 접근 제어 메커니즘을 사용하여 권한 있는 프로세스만 접근할 수 있도록 해야 합니다.
  6. 경쟁 상태: 여러 프로세스가 데이터에 경쟁적으로 접근하는 것을 피하기 위해 응용 프로그램을 신중하게 설계해야 합니다. 경쟁 상태는 여러 프로세스가 예측할 수 없는 순서로 데이터에 접근하여 잘못된 결과가 발생하는 상황을 의미합니다.

메시지 큐는 단방향인가?

아니요, "메시지 큐(Message Queue)"는 단방향이 아닙니다.

메시지 큐는 단방향 및 양방향 통신을 모두 지원할 수 있습니다.

메시지 큐는 프로세스 간 통신(Inter-Process Communication, IPC)의 한 형태로, 기본 개념은 프로세스나 스레드가 메시지를 큐에 넣고 다른 프로세스나 스레드가 이런 메시지를 가져와 처리하는 것입니다.

  1. 단방향 메시지 큐: 단방향 메시지 큐에서는 프로세스나 스레드가 메시지를 큐에 보낼 수 있지만, 직접적인 응답을 기대하지 않습니다. 다른 프로세스나 스레드는 이러한 메시지를 읽고 처리할 수 있습니다.
  2. 양방향 메시지 큐: 양방향 메시지 큐(요청-응답 패턴으로도 알려짐)에서 프로세스는 요청 메시지를 보내고 응답을 기대합니다. 수신 프로세스는 요청을 처리하고 응답 메시지를 발신자에게 다시 보낼 수 있습니다.

단방향 메시지 큐는 프로세스가 다른 프로세스에게 알림이나 정보를 전달해야 할 경우에 적합하며, 양방향 메시지 큐는 요청이 제기되고 응답이 수신되어야 하는 더 상호작용적인 통신이 필요한 경우에 유용합니다.

12. Thread Safe 하다는 것은 어떤 의미인가요?

"Thread safe" 라고 한다면, 데이터 구조나 함수 또는 코드가 프로그램에서 동시에 사용될 때 여러 스레드에 안전하게 사용될 수 있다는 것을 의미합니다. 다시 말해서, 여러 스레드가 동시에 작업을 수행할 때 데이터 손상, 경합 조건 또는 다른 동기화 문제가 발생하지 않도록 보장한다는 것을 뜻합니다.

스레드는 동시에 변수나 데이터 구조와 같은 공유 리소스에 접근할 수 있기 때문에 적절한 동기화 메커니즘과 스레드 안전한 설계 없이는 스레드 간 충돌이 발생할 수 있습니다.

Thread Safe 를 달성하기 위해서는 락(lock), 뮤텍스(상호 배제), 세마포어 등과 같은 동기화 메커니즘을 구현하는 것이 일반적입니다. 이러한 메커니즘은 코드의 중요한 섹션 또는 공유 리소스에 동시에 하나의 스레드만 접근할 수 있도록 보장하여 데이터 손상을 방지하고 데이터 무결성을 유지합니다.

Peterson’s algorithm? 과 한계점

"피터슨의 알고리즘(Peterson's Algorithm)"은 동시 프로그래밍에서

여러 스레드 또는 프로세스가 데이터 손상이나 동기화 문제를 일으키지 않고 리소스를 안전하게 공유하는 도전 과제에 대해 classic한 소프트웨어 기반 해결책을 내놓은 것입니다.

이 알고리즘은 두 프로세스가 서로 번갈아가면서 자신의 critical section 으로 진입하도록 하고 한 번에 하나의 프로세스만 critical section에 들어갈 수 있도록 보장합니다.

피터슨의 알고리즘의 작동 방식

  1. turn과 flag 두 개의 플래그를 사용하여 두 프로세스의 상태를 추적합니다.
  2. 각 프로세스는 자신의 플래그를 설정하여 critical section에 들어갈 의도를 나타냅니다.
  3. 프로세스는 또한 turn을 설정하여 다른 프로세스의 차례를 나타냅니다.
  4. 그런 다음 프로세스는 루프에 들어가 자신의 플래그가 true로 설정되고 차례인 경우(값이 turn에 기반)에만 대기합니다.
  5. 프로세스가 임계 구역을 마치면 플래그를 지우고 다른 프로세스가 들어갈 수 있도록 합니다.

(Pseudo Code)

// Assume two processes: Process 0 and Process 1
int turn = 0; // Indicates whose turn it is
bool flag[2] = {false, false}; // Flags for each process

// Process 0
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1) {
    // Wait until it's your turn and the other process isn't in its critical section
}
// Critical section for Process 0
flag[0] = false;

// Process 1
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0) {
    // Wait until it's your turn and the other process isn't in its critical section
}
// Critical section for Process 1
flag[1] = false;

피터슨의 알고리즘의 한계점

  1. 두 프로세스에 한정됨

    피터슨의 알고리즘은 두 개의 프로세스만이 공유 리소스에 대한 접근을 경쟁하는 시나리오를 대상으로 특별히 설계되었습니다. 두 개 이상의 프로세스를 처리하기 위해 직접 확장할 수 없습니다.

  2. Busy-Waiting

    프로세스가 반복적으로 루프에서 조건을 확인합니다. 이는 CPU 사이클의 낭비로 이어질 수 있으며 비효율적입니다.

  3. 공유 메모리 필요

    이 알고리즘은 프로세스 간 통신을 위해 공유 메모리를 가정합니다. 프로세스가 별도의 기계에서 실행되는 분산 시스템에서는 이 알고리즘을 추가 수정 없이 사용하기 어려울 수 있습니다.

  4. 모든 동기화 문제 해결 불가

    상호 배제 문제를 해결하더라도 deadlock 방지나 우선순위 역전을 피하는 등의 보다 복잡한 동기화 문제는 다루지 않습니다.

이러한 한계와 하드웨어 및 동기화 기술의 발전을 고려할 때, 피터슨의 알고리즘은 주로 현대 다중 스레드 프로그래밍에 대한 실용적인 해결책이 아닌 역사적 참조로 간주됩니다.

Race Condition?

경쟁 조건(Race condition)은 동시 프로그래밍에서 여러 스레드 또는 프로세스의 상대적인 실행 순서나 타이밍에 따라 프로그램의 동작이 달라지는 현상을 나타냅니다.

즉, 두 개 이상의 스레드나 프로세스가 변수나 데이터 구조와 같은 공유 리소스에 동시에 접근하고, 그들의 작업이 실행되는 순서에 따라 최종 결과가 달라지는 상황에서 발생합니다.

두 개의 스레드, 스레드 A와 스레드 B가 공유 변수 counter를 증가시키려고 할 때의 상황을 상상해 보겠습니다.

  1. 스레드 A가 counter의 현재 값을 읽습니다 (예를 들어 5).
  2. 스레드 B도 같은 값인 counter를 읽습니다 (또한 5).
  3. 스레드 A가 counter의 값을 1만큼 증가시킵니다 (이제 6).
  4. 스레드 B도 counter의 값을 1만큼 증가시킵니다 (이제 다시 6).

이 시나리오에서 두 스레드 모두 카운터를 증가시키지만, 기대되는 결과는 두 증가 후에 카운터가 7이어야 합니다. 그러나 경쟁 조건으로 인해 스레드의 교차 실행으로 인해 최종 카운터 값이 잘못 입력됩니다 (6).

Thread Safe를 구현하기 위해 반드시 락을 사용해야 할까요? 그렇지 않다면, 어떤 다른 방법이 있을까요?

아니요, 락을 사용하는 것은 유일한 방법이 아닙니다.

대안)

  1. 원자적 연산(Atomic Operations)

    현대의 많은 프로그래밍 언어는 원자적 연산을 제공하며, 원자적 연산은 스레드 안전한 연산입니다.

    이런 연산은 여러 스레드가 값을 읽거나 업데이트할 때 서로 간섭하지 못하도록 보장합니다.

  2. Lock-Free and Wait-Free Algorithms

    이러한 고급 알고리즘은 구현은 복잡하지만 락을 사용하지 않고 동시성을 달성할 수 있습니다.

  3. 메시지 패싱(Message Passing)

    데이터를 직접 공유하는 대신 스레드 간에 메시지 패싱을 통해 통신할 수 있습니다. 이로써 공유 리소스와 락이 필요하지 않으며, 각 스레드는 자체 데이터 복사본에서 작업합니다.

  4. 소프트웨어 트랜잭션 메모리 (Software Transactional Memory, STM): STM은 공유 메모리를 트랜잭션과 유사한 방식으로 관리하는 추상화를 제공합니다. 스레드는 공유 데이터에 대한 일련의 작업을 수행하여 이를 원자적 및 일관성 있게 처리합니다. STM은 경우에 따라 동기화를 단순화할 수 있지만, 구현이 복잡할 수 있습니다.

13. Thread Pool, Monitor, Fork-Join에 대해 설명해 주세요.

  1. Thread Pool
    스레드 풀은 미리 초기화된 스레드들을 관리하는 모음으로, 작업을 수행하기 위해 준비되어 있습니다.
    개별 작업마다 스레드를 생성하고 소멸시키는 대신, 스레드 풀은 기존 스레드를 재사용해서 성능을 향상시키고 스레드 생성에 따른 오버헤드를 감소시킵니다. 

스레드 풀은 일반적으로 고정된 수의 스레드를 가지며, 작업은 풀에 제출되어 실행됩니다. 이로써 시스템은 활성 스레드 수를 제어하고 리소스를 효율적으로 관리할 수 있습니다.
  2. Monitor
    모니터는 상호 배제와 조건 동기화를 제공하는 동기화 구조입니다.
    Critical Section을 한 번에 하나의 스레드만 실행할 수 있도록 보장합니다. 모니터는 공유 리소스를 경쟁 조건으로부터 보호하기 위해 사용되며, 한 번에 하나의 스레드만 리소스에 접근할 수 있도록 합니다. 

모니터는 또한 조건 변수를 제공하여 스레드가 특정 조건이 충족될 때까지 대기할 수 있도록 합니다. 모니터는 다중 스레드 환경에서 공유 리소스의 정돈된 접근을 관리하며, 스레드 안전성을 촉진하고 데이터 손상을 방지합니다.
  3. Fork-Join
    문제를 더 작은 하위 문제로 분할하고 이를 병렬 실행을 위해 여러 스레드에 분산시키는 병렬 컴퓨팅 기법입니다. 
    하위 문제가 해결되면 결과를 결합하여 원래 문제를 해결합니다. 

“포크" 작업은 새로운 작업을 생성하며, "조인" 작업은 이러한 작업의 결과를 결합합니다.

포크-조인 프레임워크는 작업의 병렬 실행을 관리하기 쉽도록 추상화를 제공하며, 작업을 스레드 간에 분배하고 사용 가능한 리소스를 효율적으로 활용합니다.

Thread Pool을 사용한다고 가정하면, 어떤 기준으로 스레드의 수를 결정할 것인가요?

  1. CPU 코어 수
일반적으로는 스레드 수를 대략 사용 가능한 CPU 코어 수와 비슷하게 유지하는 것입니다. 이렇게 하면 시스템이 사용 가능한 처리 능력을 최대한 활용할 수 있습니다.

  1. 작업 성격에 따라

    스레드 풀에서 수행되는 작업의 성격이 중요합니다. 작업이 계산 집약적이고 대기 시간이 크지 않은 경우, 더 많은 스레드가 유리할 수 있습니다. 반면에 I/O 작업이나 대기가 많은 작업의 경우, 더 적은 수의 스레드로 충분할 수 있습니다.

  2. 메모리 사용량

    각 스레드는 리소스를 사용하여 메모리를 소비하기 때문에 너무 많은 스레드가 있으면 메모리 사용이 과도해지고 시스템이 메모리 부족 상태가 될 수 있습니다.

  3. 컨텍스트 전환 오버헤드

    스레드 간 컨텍스트 전환에는 오버헤드가 발생합니다. 너무 많은 스레드가 CPU 시간을 경합하면 컨텍스트 전환이 과도해질 수 있어 시스템이 느려질 수 있습니다.

14. 캐시 메모리 및 메모리 계층성에 대해 설명해 주세요.

  1. 캐시 메모리(Cache Memory)
    캐시 메모리는 고속 데이터 접근을 제공하는 휘발성 컴퓨터 메모리로, 자주 사용되는 컴퓨터 프로그램이나 데이터를 저장하는 역할을 합니다. 그 목적은 주 메모리(RAM)와 CPU 사이에 버퍼 역할을 하도록 하는 것입니다.
     캐시 메모리는 RAM보다 훨씬 빠르며 CPU가 자주 필요한 데이터 및 명령을 더 빠르게 액세스하여 CPU가 주 메모리에서 데이터를 가져 오는 시간을 줄입니다.

캐시 메모리는 시간과 공간 지역성 원리를 활용하여 작동합니다.

시간 지역성은 특정 메모리 위치에 액세스하는 경우, 가까운 미래에 다시 액세스될 가능성이 높다는 개념을 나타내고, 공간 지역성은 메모리 위치가 액세스되면 근처 메모리 위치도 곧 액세스될 가능성이 높다는 것을 의미합니다.

캐시 메모리는 일반적으로 L1, L2, L3 캐시로 불리는 레벨로 구성됩니다.

L1 캐시는 CPU에 가장 가깝고 지연 시간이 가장 낮지만 크기가 가장 작습니다.

L2 및 L3 캐시는 더 크지만 조금 느립니다. 메모리 계층은 CPU가 캐싱 원리를 사용하여 데이터에 빠르게 액세스할 수 있도록 보장하는 것을 목표로 합니다.

  1. 메모리 계층(Memory Hierarchy)
    메모리 계층은 컴퓨터 메모리를 크기와 속도, 비용을 기준으로 여러 계층으로 구성하는 개념을 나타냅니다. 즉, 속도와 비용 사이의 균형을 조정하면서 CPU가 데이터와 명령을 효율적으로 액세스할 수 있도록 설계되었습니다.
  • 레지스터(Registers): CPU 자체 내에 위치한 가장 작고 빠른 저장 위치입니다. 가장 빠른 액세스를 제공하지만 용량 면에서는 가장 제한적입니다.
  • 캐시 메모리(Cache Memory): 위에서 언급한 대로 캐시 메모리는 레지스터와 주 메모리 간의 연결 역할을 수행하여 주 메모리보다 빠른 액세스를 제공합니다.
  • 주 메모리(RAM): RAM은 컴퓨터의 기본 메모리로 CPU가 활발하게 사용하는 데이터를 저장합니다. 저장 장치(하드 드라이브 또는 SSD와 같은)보다는 빠르지만 캐시 메모리보다는 느립니다.
  • 보조 저장소(Secondary Storage): 하드 드라이브와 SSD와 같은 저장 장치를 포함합니다. RAM보다 훨씬 큰 저장 용량을 제공하지만 액세스 속도면에서는 더 느립니다.

캐시가 데이터를 관리하는 방법

캐시 메모리는 캐시 관리 정책 이라고하는 원칙을 사용하여 데이터를 관리합니다.

캐시 관리의 목표는 자주 사용되는 데이터를 캐시에 저장하여 데이터 액세스의 효율성을 극대화하고 캐시 미스(요청한 데이터가 캐시에서 찾을 수 없는 경우)를 최소화하는 것입니다.

  1. 캐시 교체 정책:
    캐시 공간은 제한되어 있으므로 새 데이터를 캐시로 로드해야 할 때 기존의 어떤 캐시 항목을 대체할 것인지 결정해야 합니다.
    - 최근에 사용하지 않은 것(Least Recently Used, LRU): 가장 오랫동안 사용되지 않은 캐시 항목을 대체합니다.
    - 가장 적게 사용된 것(Least Frequently Used, LFU): 가장 적게 사용된 캐시 항목을 대체합니다.
    - 랜덤 교체(Random Replacement): 임의의 캐시 항목을 대체합니다.
    - 선입선출(FIFO, First-In, First-Out): 가장 오래된 캐시 항목을 대체합니다.
  2. 쓰기 정책:
    캐시 메모리는 읽기 및 쓰기 데이터를 모두 저장할 수 있습니다. 쓰기 정책은 쓰기가 어떻게 처리되는지 결정합니다:
    - 쓰기 직통(Write-Through): 데이터는 캐시와 주 메모리 모두에 동시에 쓰입니다. 이로 인해 주 메모리가 항상 최신 상태가 되지만 더 많은 메모리 트래픽을 유발할 수 있습니다.
    - 쓰기 지연(Write-Back): 데이터는 먼저 캐시에 쓰이고 캐시 항목이 대체될 때 주 메모리가 업데이트됩니다. 이는 메모리 트래픽을 줄이지만 더 복잡한 관리가 필요합니다.
  3. 캐시 일관성:
    여러 캐시를 가진 시스템(멀티 코어 프로세서 또는 분산 시스템)에서 캐시 일관성은 동일한 데이터의 복사본을 보유한 다른 캐시가 일관되게 유지되도록 보장합니다. 하나의 캐시가 데이터를 수정할 때 다른 캐시가 변경 내용을 반영하여 데이터 일관성을 유지합니다. 이로써 시스템의 서로 다른 부분 간의 데이터 불일치를 방지합니다.
  4. 미리 로딩:
    캐시 관리 시스템은 요청되기 전에 데이터를 예측하고 캐시로 로드하기 위한 미리 로딩 기술을 사용할 수 있습니다. 다음에 필요한 데이터를 예측하여 캐시 미스를 줄이는 데 도움이 될 수 있습니다.
  5. 캐시 레벨:
    현대 CPU는 일반적으로 L1, L2 및 때로는 L3와 같은 여러 캐시 레벨을 갖추고 있습니다. 캐시 레벨은 데이터 액세스를 최적화하기 위해 함께 작동합니다. 더 작고 빠른 캐시(L1)는 가장 자주 사용되는 데이터를 저장하고, 더 큰 캐시(L3)는 더 넓은 범위의 데이터를 저장합니다.

본질적으로 캐시 관리는 어떤 데이터를 캐시에 유지할지, 캐시 미스를 어떻게 처리할지, 여러 캐시 간의 데이터 일관성을 어떻게 보장할지 신중하게 결정하는 과정입니다. 이러한 전략은 CPU가 데이터를 기다리는 시간을 최소화하고 처리 효율성을 극대화하기 위한 것입니다.

캐시 동기화는 어떻게 이루어질까?

캐시 동기화, 다른 말로 캐시 일관성이란 동일한 데이터의 복사본을 가진 여러 캐시가 일관되게 유지되는 과정을 말합니다.

캐시 동기화는 다양한 프로토콜을 통해 달성되는데, 가장 잘 알려진 프로토콜 중 하나는 MESI 프로토콜입니다. MESI는 Modified, Exclusive, Shared, 그리고 Invalid의 줄임말로, 캐시 동기화가 어떻게 작동하는지에 대한 개요는 다음과 같습니다:

  1. Modified 상태:
    하나의 프로세서 캐시에서 캐시 라인이 수정되면 "Modified" 상태로 들어갑니다. 이는 캐시에 있는 데이터가 주 메모리의 데이터와 다르다는 것을 의미합니다. 동일한 데이터를 가진 다른 캐시는 복사본이 더 이상 유효하지 않다는 것을 알립니다(Invalid 상태). 다른 프로세서가 데이터를 읽으려면 소유한 캐시로부터 데이터를 요청해야 합니다. 쓰기가 요청되면 데이터는 먼저 주 메모리로 다시 기록되고 캐시 라인은 "Exclusive" 상태로 전환됩니다.
  2. Exclusive 상태:
    "Exclusive" 상태에서 캐시 라인은 주 메모리의 데이터와 일치하는 데이터를 포함합니다. 다른 캐시는 "Shared" 상태로 데이터의 복사본을 가질 수 있습니다. 프로세서가 데이터를 수정하려면 먼저 캐시 라인의 소유권을 요청해야 하며, 이로 인해 캐시 라인은 "Modified" 상태로 전환됩니다.
  3. Shared 상태:
    "Shared" 상태에서는 여러 캐시가 데이터의 복사본을 가질 수 있으며 해당 캐시의 데이터는 주 메모리의 데이터와 일치합니다. 하나의 프로세서가 데이터를 수정하면 캐시 라인은 "Modified" 상태로 전환되고, 다른 캐시는 복사본을 무효화하도록 알립니다.
  4. Invalid 상태:
    "Invalid" 상태에서는 캐시 라인이 유효하지 않은 데이터를 포함합니다. 이는 다른 프로세서가 데이터를 수정하거나 프로세서가 캐시 라인에 데이터를 쓰려고 할 때 발생합니다.

다른 캐시 일관성 프로토콜(MOESI, MESIF, Dragon 등)은 기본 MESI 프로토콜을 기반으로 다양한 시나리오에서 성능과 효율성을 더욱 최적화하기 위해 만들어졌습니다. 이러한 프로토콜은 멀티 코어 및 멀티 프로세서 시스템에서 캐시 일관성을 유지하고 데이터 불일치를 방지하는 데 도움이 됩니다.

캐시의 메모리 매핑에 대하여

캐시 메모리 매핑 기법은 크게 세 가지가 존재하는데,

직접 매핑(Direct Mapping), 완전 연관 매핑(Fully Associative Mapping), 그리고 집합 연관 매핑(Set-Associative Mapping)이 있습니다.

  1. 직접 매핑(Direct Mapping):
    직접 매핑에서는 각 메모리 블록이 정확히 하나의 특정 캐시 블록과 매핑됩니다. 매핑은 메모리 주소를 캐시 크기로 나눈 후 나머지를 사용하여 캐시 인덱스를 결정하는 간단한 공식을 사용하여 결정됩니다. 이로 인해 모든 메모리 위치는 캐시 내의 특정 위치에만 배치될 수 있습니다.
    장점:

- 간단하며 구현하기 쉽습니다.
- 하드웨어 복잡성이 낮습니다.

단점:

- 여러 메모리 블록이 동일한 캐시 블록에 매핑되어 캐시 충돌을 일으킬 수 있으며 이로 인해 캐시 교체가 발생할 수 있습니다.
- 캐시 배치 관련 유연성이 제한됩니다.
  2. 완전 연관 매핑(Fully Associative Mapping):
    완전 연관 매핑에서는 어떤 메모리 블록도 어떤 캐시 위치에도 배치될 수 있습니다. 미리 결정된 매핑 공식은 없습니다. 각 캐시 블록은 해당하는 메모리 블록을 식별하는 태그를 가지고 있습니다. 메모리 블록을 가져와야 할 때 모든 캐시 블록의 태그가 비교되고 일치하는 태그를 가진 블록이 선택됩니다.
    장점:

- 캐시 배치에 대한 최대한의 유연성을 제공합니다.
- 직접 매핑에 따른 캐시 충돌과 교체의 필요성을 제거합니다.

단점:

- 태그 비교를 병렬로 수행해야 하기 때문에 하드웨어 복잡성이 높습니다.
- 태그 비교 과정으로 인해 액세스 시간이 느려집니다.
  3. 집합 연관 매핑(Set-Associative Mapping):
    집합 연관 매핑은 직접 매핑과 완전 연관 매핑 사이의 절충안입니다. 캐시를 여러 집합으로 나누고 각 집합은 일정 수의 캐시 블록을 포함합니다. 메모리 블록이 액세스되면 해당 집합 내의 어떤 캐시 블록에도 배치될 수 있습니다. 매핑은 메모리 주소를 여러 필드로 나누어 처리되는데, 집합 인덱스와 태그가 포함됩니다. 집합 인덱스는 블록을 배치할 수 있는 집합을 결정합니다.
    장점:

- 유연성과 하드웨어 복잡성을 균형있게 제공합니다.
- 직접 매핑에 비해 캐시 충돌 가능성을 줄입니다.

단점:

- 여전히 태그 비교를 수행하므로 직접 매핑에 비해 약간의 액세스 시간 오버헤드가 발생합니다.
- 완전 연관 매핑만큼 유연하지 않습니다.

캐시의 locality 를 고려했을 때, 이차원 배열에서 가로로 탐색하는 것과 세로로 탐색하는 것의 차이가 뭘까요?

  • 가로 방식 검색:
    2차원 배열을 행을 따라 탐색하게 되면, 같은 행의 인접한 요소가 연속적으로 액세스됩니다.
 이로 인해 메모리에서 가져온 데이터가 캐시에 로드되고 인접한 캐시 라인에 저장될 가능성이 높아집니다.

이로 인해 캐시에서 연속적인 메모리 액세스가 가능하므로 캐시 히트 비율이 높아질 수 있습니다.
  • 세로 방식 검색:
    2차원 배열을 열을 따라 탐색하게 되면, 다른 행이지만 같은 열의 요소가 연속적으로 액세스됩니다.
     여전히 열 내에서 일부 지역성이 존재할 수 있지만, 가로 검색에 비해 연속적으로 메모리에 위치한 데이터에 대한 액세스가 상대적으로 떨어질 수 있습니다. 

이로 인해 캐시 라인이 연속적인 요소를 포함하기 어려워져 캐시 히트 비율이 낮아질 수 있습니다.

캐시는 어떤 단위로 저장되고 관리될까요?

캐시 메모리는 일반적으로 캐시 라인 또는 캐시 블록이라는 단위로 저장되고 관리됩니다.

캐시 라인은 캐시로 로드될 수 있는 가장 작은 단위인 고정 크기의 메모리 블록입니다. 각 캐시 라인에는 주 메모리의 데이터 일부가 포함됩니다.

캐시 라인의 크기는 하드웨어 아키텍처에 따라 결정되며 일반적으로 32바이트, 64바이트 또는 128바이트와 같은 2의 거듭제곱 크기입니다. 데이터가 주 메모리에서 가져와질 때, 해당 데이터는 캐시 라인에 로드됩니다. 이후 액세스에서 동일한 캐시 라인의 데이터가 필요한 경우, 해당 데이터는 캐시에서 직접 제공되어 지역성의 원칙으로 인해 액세스 시간이 개선됩니다.

캐시 자체는 집합으로 구성되며, 각 집합에는 여러 개의 캐시 라인이 포함됩니다. 집합 내 캐시 라인의 수는 캐시의 연관성에 의해 결정됩니다. 예를 들어 4-way set-associative 캐시의 경우, 각 집합에는 네 개의 캐시 라인이 포함됩니다.

캐시 메모리는 이러한 단위로 관리되며 효율적인 캐시 활용과 공간 및 시간 지역성을 활용하도록 합니다. 데이터를 캐시 라인에 저장하고 집합으로 구성함으로써 캐시 시스템은 메모리 액세스 시간을 최적화하고 전반적인 시스템 성능을 향상시키기 위해 노력합니다.

15.메모리의 연속할당 방식 세 가지를 설명해주세요. (first-fit, best-fit, worst-fit)

연속 메모리 할당은 연속적인 사용 가능한 메모리 블록에서 메모리 블록을 할당하는 프로세스를 의미합니다.

  1. First Fit:
    First Fit 할당 방법에서 운영 체제는 요청된 프로세스 크기를 수용할 수 있는 첫 번째 사용 가능한 메모리 블록을 찾습니다. 크기 요구 사항을 충족하는 첫 번째 블록이 프로세스에 할당되며, 남은 부분은 사용되지 않았다고 표시됩니다. 이 방법은 검색 없이 빠르게 메모리를 할당하므로 간단하고 효율적입니다. 그러나 시간이 지남에 따라 메모리 조각화를 유발할 수 있으며, 할당된 블록과 할당되지 않은 블록 사이에 작은 간격이 남을 수 있습니다.
  2. Best Fit:
    Best Fit은 프로세스 크기를 수용할 수 있는 사용 가능한 메모리 블록 중 가장 작은 블록을 찾는 방법입니다. 요구된 크기를 충족시키는 사용 가능한 블록 중에서 가장 크기가 작은 블록이 선택됩니다. 이 방법은 할당에 가능한 가장 작은 간격을 사용하여 메모리 낭비를 최소화하려는 목표를 가지고 있습니다. 그러나 모든 사용 가능한 블록을 검색하여 가장 적합한 블록을 찾아야 하므로 First Fit에 비해 상대적으로 느리고 효율이 떨어질 수 있습니다. 또한 작은 간격으로 인해 조각화가 발생할 수 있습니다.
  3. Worst Fit:
    Worst Fit 방법에서는 프로세스를 수용할 수 있는 가장 큰 사용 가능한 메모리 블록이 선택됩니다. 이 방식은 할당된 블록 사이에 가장 큰 간격을 남기려는 목표를 가지고 있으며, 일부 조각화를 어느 정도 방지할 수 있습니다. 그러나 작은 프로세스가 더 큰 간격에 맞지 않을 수 있기 때문에 비효율적인 메모리 활용을 초래할 수 있습니다. Best Fit과 마찬가지로 Worst Fit도 모든 사용 가능한 블록을 검색하여 선택하므로 상대적으로 느립니다.

Worst-Fit allocation 을 사용해야 할 때는?

일반적으로 Worst-fit 할당은 메모리 조각화, 메모리 효율성이 다른 전략과 비교해서 좋지 않다는 점 때문에 권장되지 않는 방식입니다.

하지만 다음과 같은 상황에서는 고려해 볼 수 있습니다.

  1. 큰 블록 낭비 방지: 큰 메모리 블록의 낭비를 최소화하려는 경우 최악의 적합 할당을 사용할 수 있습니다. 크게 큰 메모리 블록이 필요한 프로세스가 있고 사용 가능한 메모리 블록 중 어느 것도 충분히 크지 않은 경우, 최악의 적합은 해당 프로세스를 수용할 수 있는 더 큰 블록을 찾는 데 도움이 될 수 있습니다. 이는 특정 작업을 위해 큰 메모리 청크를 할당해야 하는 상황에서 유용할 수 있습니다.
  2. 일시적 할당: 효율적인 메모리 활용을 필요로하지 않는 일시적 할당 요청이 있는 경우 최악의 적합을 고려할 수 있습니다. 예를 들어 장기적인 조각화 문제를 초래하지 않을 것으로 예상되는 짧은 기간 동안 실행되는 작업을 위해 메모리를 할당하는 경우, 최악의 적합을 비교적 걱정 없이 사용할 수 있습니다.
  3. 한정된 자원: 제한된 수의 메모리 블록이 있는 경우 메모리 조각화가 주요한 걱정 사항이 아니라면, 비효율적인 메모리 활용을 초래하더라도 더 큰 프로세스가 할당되도록 하기 위해 최악의 적합을 사용할 수 있습니다.

세 가지 방식 중에 가장 성능을 기대해 볼 만한 알고리즘은?

일반적으로는 "Best Fit" 알고리즘이 메모리 활용과 조각화 관리 측면에서 가장 우수한 성능을 제공하는 것으로 알려져 있습니다. 하지만 시스템의 특성과 작업 부하에 따라서 언제든지 유리한 상황이 달라질 수 있음을 생각해야 합니다.

Best Fit 알고리즘이 선호되는 이유

  1. 더 나은 메모리 활용: Best Fit은 프로세스에 맞는 가장 작은 사용 가능한 블록을 선택하여 메모리 낭비를 최소화하려는 목표를 가지고 있습니다. 이로 인해 메모리의 효율적인 활용이 이루어지며, 작은 간격이 할당에 사용됩니다.
  2. 조각화 감소: Best Fit 알고리즘은 할당 후 더 작은 빈 메모리 간격을 만들어 조각화를 시간이 지남에 따라 감소시키는 데 도움이 됩니다.
  3. 균형 잡힌 할당: Best Fit은 메모리의 효율적인 활용과 할당 속도 사이의 균형을 제공합니다. 가장 적합한 블록을 찾기 위한 검색 때문에 First Fit보다 약간 느릴 수 있지만 메모리 활용이 더 우수합니다.
  4. 큰 낭비 가능성 감소: Worst Fit와 비교하여 큰 메모리 블록이 할당되지 않은 상황이 적어집니다.

일부 경우에는 간단함과 빠른 할당 속도 때문에 First Fit이 선택될 수 있습니다. Worst Fit은 일반적으로 가장 큰 사용 가능한 블록을 할당하는 경향이 있어 메모리 낭비와 큰 빈 간격을 초래할 가능성이 있어 효율적이지 않다고 여겨집니다.

profile
최민수
CS, 개발 공부기록 🌱
이전 포스트

운영체제 스터디

다음 포스트

CS 스터디

0개의 댓글