gansal 태그를 달 수 있을 정도로 조금만 살펴볼 예정이다.

Keyword

Semaphore

운영체제의 커널이 관리하거나 사용자 수준에서 관리하는 공유 변수로 프로세스와 스레드의 접근 개수를 제한함.
어떤 한 프로세스가 독점적으로 가지고 있는 값이 아니며, 접근하는 모든 프로세스와 스레드가 이 값을 공통적으로 확인하고 변경함.

멀티 프로그래밍 환경에서 상호 배제나 동기화를 위해 사용됨.

• 기본 원리

  • 정수 값을 가지는 변수로, 이 값이 공유 자원에 접근할 수 있는 프로세스나 스레드의 최대 개수를 의미한다.
  • 값이 0이면 자원을 사용할 수 없다는 의미이고, 0보다 크면 그 값만큼 프로세스가 접근이 가능하다.
  • 두 가지의 원자적 연산을 통해 semaphore의 값을 변경할 수 있다.
    • wait(P) 세마포어의 값을 1 감소시키며, 값이 0이하면 프로세스는 대기 상태가 됨.
    • signal(V) 세마포어의 값을 1 증가시키고, 대기 중인 프로세스가 있다면 하나를 깨워 실행시킴.

• 종류

  • 이진(Binary) 세마포어: 값을 0 또는 1만 가질 수 있어 뮤텍스와 유사하게 동작하며 상호 배제에 활용
  • 계수(Counting) 세마포어: 0 이상의 정수값을 가질 수 있으며, 여러 개의 자원을 동시에 관리할 때 사용됨.

• 동작

  • 세마포어 값이 n인 경우, n개의 프로세스가 동시에 자원에 접근할 수 있음.
  • n+1 번째 프로세스가 접근을 시도하면 세마포어 값이 0이므로 대기 상태(큐에서 관리)가 됨.
  • 기존 프로세스 중 하나가 작업을 마치고 signal 연산을 수행하면, 대기 중이던 프로세스가 자원에 접근하 수 있음.

• 특징 및 활용

  • 동기화: 여러 프로세스/스레드 간에 작업 순서를 맞추거나, 특정 조건이 충족될 때까지 대기하게 함.
  • 상호 배제: 임계 구역*에 동시에 여러 프로세스가 진입하지 못하도록 제한함.
  • 자원 관리: 제한된 자원을 여러 프로세스가 사용할 때 접근 가능한 최대 개수를 제한하는 데 사용됨.

* 임계 구역: 둘 이상의 프로세스나 스레드가 동시에 접근해서는 안 되는 공유 자원

Mutex

여러 프로세스나 스레드가 동시에 하나의 공유 자원에 접근하는 것을 막기 위한 상호 배제 동기화 도구. 오직 하나의 스레드/프로세스만이 특정 시점에 임계구역에 들어갈 수 있도록 보장함.

• 동작

  • 락과 언락 메커니즘
    • 임계구역에 진입하려는 스레드는 먼저 뮤텍스를 획득(lock)해야 함.
    • 이미 다른 스레드가 뮤텍스를 획득 중이라면, 나머지 스레드는 뮤텍스가 해제(unlock)될 때까지 대기함.
    • 임계구역에서 작업을 마친 스레드는 반드시 뮤텍스를 해제해야 하며, 이때 대기 중인 다른 스레드가 뮤텍스를 획득할 수 있음.

• 소유권

  • 뮤텍스는 소유 개념이 있어 뮤텍스를 획득한 스레드만이 해당 뮤텍스를 해제할 수 있음.
  • 의도치 않은 해제나 예기치 않은 동작을 방지함.
  • 각 공유 자원마다 뮤텍스 객체가 프로세스 내부 메모리에 생성됨.
  • 운영체제가 뮤텍스 객체에 소유자를 기록함.

• 특징

  • 임계구역 보호: 오직 하나의 스레드만 임계구역에 진입할 수 있도록 보장.
  • 동기화 대상이 1개: 뮤텍스는 한 번에 하나의 자원만 보호함. 여러 자원을 동시에 보호하려면 각각의 뮤텍스가 필요함.
  • 운영체제 또는 라이브러리에서 제공: 뮤텍스는 OS 또는 동기화 라이브러리에서 제공하는 객체로, 커널 수준에서 관리되는 경우가 많음.
  • 프로세스 간/스레드 간 동기화: 뮤텍스는 여러 스레드뿐 아니라, 프로세스 간에도 사용할 수 있음.

Race condition

둘 이상의 프로세스나 스레드가 동시에 같은 공유 자원에 접근하여 읽기/쓰기 작업을 수행할 떄, 실행 순서에 따라 결과가 달라지는 예측 불가능한 현상.
여러 작업이 동시에 실행되는 환경에서, 공유 자원에 대한 접근 순서가 프로그램의 정상 동작을 보장하니 못하는 상황이 발생함.

• 원인

  • 공유 자원에 대한 동시 접근: 여러 스레드/프로세스가 같은 변수, 파일, 메모리 등 공유 자원에 동시에 접근할 때
  • 비원자적 연산: 읽기-연산-쓰기 과정이 하나의 불가분한 단위로 처리되지 않을 때
  • 동기화 부족: 뮤텍스, 세마포어 등 동기화 도구를 사용하지 않아 실행 순서가 보장되지 않을 때

• 문제점

  • 데이터 불일치: 실행 결과가 매번 달라질 수 있어, 신뢰할 수 없는 결과가 나옴
  • 디버깅 어려움: 항상 재현되는 문자가 아니어서, 테스트나 디버깅이 매우 어려움
  • 시스템 결함: 심각한 경우, 시스템 오류나 보안 취약점으로 이어질 수 있음.

• 예방 방법

  • 상호 배제: 한 번에 하나의 스레드/프로세스만 공유 자원에 접근하도록 제한
  • 임계 구역 보호: 공유 자원 접근 코드를 임계 구역으로 지정하고, 동기화 도구로 보호
  • 원자적 연산 사용: CPU나 라이브러리에서 제공하는 원자적 연산을 활용해 연산 단위로 보호

Context Switching

운영체제에서 CPU가 현재 실행 중인 프로세스나 스레드의 상태를 저장하고 다른 프로세스나 스레드의 상태를 복원하여 실행을 전환하는 과정

• 목적
  • 멀티태스킹 환경에서 CPU 자원을 여러 프로세스가 공유할 수 있게 함.
  • 프로세스가 실행을 잠시 멈추고 다른 프로세스가 실행되도록 함으로써 사용자에게 여러 작업이 동시에 수행되는 것처럼 보이게 함.
  • 인터럽트 처리, 우선순위에 따른 프로세스 교체, 사용자 모드와 커널 모드 전환 시에도 발생함.
• 스위칭 과정
  • 현재 실행 중인 프로세스의 상태 저장
    CPU레지스터, 프로그램 카운터, 스택 포인터, 메모리 맵 등 프로세스 실행에 필요한 모든 정보를 프로세스 제어 블록(PCB)*에 저장
  • 프로세스 상태 변경 및 스케줄링
    현재 프로세스 상태를 적절히 변경하고, 다음 실행할 프로세스를 선택
  • 새 프로세스의 상태 복원
    선택된 프로세스의 PCB에서 저장된 상태를 CPU 레지스터 등에 복원하여 실행을 재개

* 프로세스 제어 블록: 운영체제가 각 프로세스를 효과적으로 관리하고 제어하기 위해 사용하는 핵심 자료 구조
운영체제 커널 내부에 존재하며, 각 프로세스마다 하나씩 생성되어 해당 프로세스의 모든 중요한 정보를 저장함
(프로세스 식별자, 프로세스 상태, 프로그램 카운터, CPU 레지스터 값, 스케줄링 정보 등이 들어감)

• 컨텍스트 스위칭 주요 트리거
  • 멀티태스킹: 시간 할당량이 끝나거나 우선 순위가 높은 프로세스가 실행되어야 할 때
  • 인터럽트 발생: 하드웨어나 소프트웨어 인터럽트 처리 시
  • 유저 모드와 커널 모드 전환: 시스템 호출 등 권한 변경 시
• 컨텍스트 스위칭의 비용과 영향
  • CPU 상태 저장 및 복원 작업에 시간이 소요되므로 잦은 스위칭은 시스템 성능 저하를 초래함.
  • 운영체제는 효율적인 스케줄링과 최소한의 컨텍스트 스위칭을 목표로 설계됨

Multi-Level Feedback Queue Scheduler

운영체제에서 다양한 유형의 작업(예: 배치 작업, 대화형 작업)을 효과적으로 처리하기 위해 고안된 동적 우선순위 기반 프로세스 스케줄링 알고리즘.
프로세스의 실행 패턴(과거의 CPU 사용량 등)에 따라 우선순위를 실시간으로 조정하며, 여러 개의 우선순위 큐를 사용해 프로세스를 관리함.

• MLFQ의 주요 특징

  • 여러 개의 큐: 각 큐는 서로 다른 우선순위를 가짐. 상위 큐일수록 우선순위가 높고, 하위 큐일수록 낮음.
  • 동적 우선순위: 프로세스의 실행 이력에 따라 우선순위가 변동됨. CPU를 많이 사용하는 프로세스는 점차 낮은 우선순위 큐로 이동함. I/O 중심(혹은 짧은 CPU 사용)의 프로세스는 높은 우선순위 큐에 남거나 승격됨.
  • 피드백(Feedback): 프로세스가 할당된 시간(time slice) 내에 작업을 끝내지 못하면 더 낮은 우선순위 큐로 이동(강등)함., 오랜 시간 대기하거나 I/O 중심이면 다시 높은 우선순위 큐로 이동(승격)함.
  • 스케줄링 방식 혼합: 각 큐는 Round Robin, FCFS 등 서로 다른 스케줄링 방식을 사용함.
  • 기아(starvation) 방지: 일정 시간마다 모든 프로세스를 가장 높은 우선순위 큐로 올려주는 등 다양한 기법으로 기아 현상을 완화함.

• MLFQ의 동작 규칙 요약

  • 새로운 프로세스는 항상 가장 높은 우선순위 큐에 삽입.
  • 우선순위가 높은 큐부터 프로세스를 스케줄. 상위 큐에 프로세스가 있으면 하위 큐는 실행하지 않음.
  • 같은 큐 내에서는 Round Robin 등으로 프로세스 배분.
  • 프로세스가 할당된 time slice를 모두 사용하면 더 낮은 큐로 이동(우선순위 하락).
  • 프로세스가 I/O 등으로 CPU를 짧게 사용하면 높은 큐에 남거나 승격.
  • 기아 방지용 리셋: 일정 시간마다 모든 프로세스를 최상위 큐로 올려줌.

• MLFQ의 장점과 목적

  • 대화형(Interactive) 작업에 빠른 응답성 제공: 짧은 CPU burst를 가진 프로세스(예: 사용자 입력 대기)는 항상 높은 우선순위를 유지해 빠르게 처리됨.
  • 배치(Batch) 작업도 효율적으로 처리: CPU를 오래 사용하는 작업은 점진적으로 우선순위가 낮아지지만, 기아 방지 정책으로 완전히 무시되지 않음.
  • 시스템의 다양한 요구에 유연하게 대응: 우선순위, 큐 개수, 승격/강등 정책 등 파라미터를 조정해 다양한 환경에 맞춤 적용 가능

예시를 보면서 이해해보자.

상황1) 10초 프로세스 A

Q2	A(2)
Q1		A(2)
Q0			A(2)	A(2)	A(2)	A(2)	A(2)	A(2)	A(2)	A(2)

• 해결
  타임 슬라이스라는 시간 제한을 두어, 각 큐에서 해당 시간이 지나면 우선 순위가 낮은 큐로 이동함.
  (해당 상황에서 타임 슬라이스는 2초임)

상황2) 10초 프로세스 A, 6초 프로세스 B

Q2	A(2)						B(2)
Q1		A(2)						B(2)
Q0			A(2)	A(2)	A(2)	A(2)			A(2)	B(2)

• 해결
  새로 들어온 프로세스는 우선 순위가 높은 큐에 배치됨

상황3) 10초 프로세스 A, 2초 프로세스 B(6번 반복)

Q2	A(2)			B(2)	B(2)	B(2)	B(2)	B(2)	B(2)
Q1		A(2)
Q0			A(2)							A(2)

• 문제
  B로 인해 A가 CPU를 점유하지 못함. (starvation - 기아 상태)

Q2	A(2)			B(2)	A(2)	B(2)	B(2)	B(2)	A(2)	B(2)
Q1		A(2)
Q0			A(2)

• 해결1
  특정 시간마다 우선 순위를 상향 조정(boost)함.
  (예시에서는 8초)

Q2	A(2)			B(2)	B(2)
Q1		A(2)				B(2)	B(2)
Q0			A(2)					A(2)	B(2)	A(2)

• 해결2
  각 큐별로 프로세스의 시간할당량을 두고, 할당량이 지나면 우선 순위가 낮은 큐로 이동
  (예시에서는 4초)