목적

  • 좋은 성적을 위한 시험 공부
  • 내용 정리

배경

  • 월요일에 있는 운영체제 시험을 위해서 운영체제 시험범위를 공부해야한다.

시험 범위

  • 동시성/락/세마포/교착상태
  • 파일 시스템
  • 메모리 관리

내용

동시성/락/세마포/교착상태

동시성

  • 여러 스레드가 공유 자원에 동시에 접근할 때, 스케줄링 순서가 제어되지 않아 발생하는 문제이다.
  • 주요개념
    • 경쟁 상태: 실행 순서에 따라 결과가 달라진다.
    • 상호 배제: 하나의 스레드만 임계 구역에 들어갈 수 있다.
    • 원자성: 특정 연산이 중간에 중단되지 않고 한번에 실행됨

락

  • lock과 unlock 함수를 이용해서 임계 구역을 보호하는 것 -> 상호 배제를 달성한다.
  • 락 구현 방법
    • 인터럽트 제어: 가장 원시적인 방법으로 인터럽트를 비활성화해 컨텍스트 스위칭을 막는다. 단일 프로세서에서만 작동한다. 인터럽트 유실 문제나 시스템 독점 문제가 있다.
    • 하드웨어 원자적 연산
      • Test-and-Set: 특정 메모리 위치의 값을 확인하고 새로운 값을 설정한다.
      • Compare-and-Swap (CAS): 특정 메모리 값이 예상과 다르면 새로운 값으로 교체한다.
      • Fetch-and-Add: 값을 원자적으로 증가시키고 이전 값 반환 -> 공정한 티켓락 구현 가능
  • 스핀락
    • 락을 얻을 때까지 CPU를 소모하며 busy-waiting을 한다.
    • 임계 구역이 짧으면 효율적
  • 슬립락
    • 락을 얻을 수 없으면 스레드가 대기 상태로 전환되어 CPU 양보
    • 임계 구역이 길면 효율적이고 컨텍스트 스위칭이 일어난다.

동시성 자료구조

  • Sloppy Counter: 전역 카운터와 CPU 코어별 지역 카운터를 두어 락 경쟁을 줄이고 확자성을 높인 카운터
  • 지역 카운터의 값을 주기적으로 전역 카운터에 반영한다.
  • 동시성 연결 리스트, 큐, 해시 테이블: 세밀한 단위의 락을 사용해 병렬성 극대화

세마포

  • 조건 변수
    • 목적: 상호 배제를 넘어 스레드 간의 실행 순서를 제어(동기화)하기 위해 사용됨
    • 주요함수
      • pthread_cond_wait: 락을 해제하고 대기 상태로 들어감.
      • pthread_cond_signal: 대기 중인 스레드 하나를 깨운다.
    • 생산자 소비자 문제
      • 유한한 버퍼를 두고, 생산자 스레드와 소비자 스레드가 동기화하는 고전적 문제
      • 조건변수를 사용해 버퍼가 가득 찼을 때 생산자가, 비었을 때 소비자가 대기한다.
  • 세마포
    • 개념: 정수 값을 가지는 동기화 도구로, sem_wait 과 sem_post 으로 조작한다.
    • 종류
      • 바이너리 세마포: 값이 바이너리이고, 뮤텍스(락)처럼 사용될 수 있다.
      • 카운팅 세마포: 여러 개의 자원을 관리하는데 유용하다. (e.g. 생산자-소비자 문제의 빈 버퍼/찬 버퍼 개수)

교착상태 (데드락)

  • 정의: 둘 이상의 스레드가 서로 점유한 자원을 기다리며 무한 대기하는 상태
  • 발생 조건 (4가지 조건 모두 총족시 발생)
    • 상호 배제
    • 점유 및 대기
    • 비선점
    • 순환 대기
  • 교착상태 해결 전략
    • 예방: 조건 4개 중 하나를 막는다. 보통 순환대기를 막는 것이 현실적이다.
    • 회피: 자원 할당시 교착상태를 유발할 가능성이 있으면 할당하지 않는다.
    • 탐지 및 복구: 교착상태을 일어나도록 두고 주기적으로 탐지해 하나를 죽인다.

파일 시스템

IO 장치 및 디스크

  • IO 제어방식
    • 폴링: CPU가 주기적으로 장치 상태를 확인하는 방법. CPU낭비가 심함
    • 인터럽트: 장치가 작업 완료 시 CPU에게 신호를 보내줘서 알려주는 방법. CPU 효율 좋음
    • DMA (Direct Memory Access): CPU 개입 없이, DMA 컨트롤러가 메모리와 장치 간 데이터 전송을 해주는 거. CPU 부하 줄임
  • 하드 디스크 (HDD)
    • IO 시간: 탐색 + 회전 지연 + 전송 시간
    • 특징: 순차 IO가 임의 IO보다 훨씬 빠르다.
    • 디스크 스케줄링: SSTF, SCAN, C-SCAN 등의 알고리즘으로 헤드 이동거리를 최소화해서 성능을 향상시킨다.

파일과 디렉터리

  • 파일: 바이트의 선형 배열
  • 디렉터리: 파일 이름과 해당 파일의 위치정보 (inode)를 담고 있는 특수 파일
  • 링크
    • 하드 링크: 동일한 inode를 가리키는 또 다른 파일 이름이다. 링크 카운트가 0이 되어야 파일이 삭제됨
    • 심볼릭 링크: 원본 파일의 경로를 담고 있는 특수 파일이다. 원본이 삭제되면 댕글링 래퍼런스가 된다.

파일 시스템의 구현

  • 디스크 구조
    • 슈퍼 블록: 파일 시스템 전체의 메타 데이터를 저장한다.
    • 비트맵: 데이터 블록과 inode의 사용 여부를 비트로 관리한다.
    • 아이노드: 파일 하나당 하나씩 존재하며, 파일의 메타데이터를 저장한다.
    • 데이터 블록: 실제 데이터가 들어간다.
  • inode 포인터: 작은 파일은 직접포인터, 큰 파일은 간접 포인터를 사용해서 효율을 높인다.
  • 캐싱: 자주 사용하는 데이터 블록이나 inode는 DRAM에 캐싱한다.
  • 버퍼링: 지연된 쓰기를 통해 여러 쓰기 작업을 한번에 처리해 디스크의 효율을 높인다.

FFS (Fast File System)

  • 목표: 기존 파일 시스템의 파편화와 긴 탐색 시간 문제를 해결해 성능을 향상시킨다.
  • 핵심 아이디어: 지역성 활용. 연관된 데이터를 디스크 상에서 가깝게 배치한다.
  • 실린더 그룹: 디스크를 여러그룹으로 만들고, 각 그룹이 자체 슈퍼블록, 비트맵, inode, 데이터 블록을 가지게 한다. 그리고 파일의 inode와 데이터 블록을 같은 그룹에 할당한다.

충돌 일관성 (Crash Consistency)

  • 문제: 파일 생성/수정 시 여러 블록을 수정해야하는데… 중간에 시스템이 꺼지면 일관성이 깨질 수 있다.
  • 해결책
    • fsck: 시스템 부팅 시 파일 시스템을 검사해서 복구한다.
    • 저널링
      • 원리: 데이터를 디스크에 쓰기 전에 변경 내역을 전부 저널에 적는다.
      • 과정: 저널 쓰기 -> 저널 커밋 -> 데이터 쓰기
      • 복구: 충돌 시점의 저널을 보고 redo나 undo를 해서 보장 -> 빠르게 복구 가능
      • 종류
        • 데이터 저널링: 데이터 + 메타데이터 전부 보관 -> 안전하지만 느림
        • 메타데이터 저널링: 메타데이터만 기록 -> 성능, 안정성 절충안

LFS (Log-Structured File System)

  • 핵심 아이디어: 모든 쓰기 작업을 버퍼에 로그처럼 디스크에 순차적으로 쓴다.
    • 임의의 쓰기를 순차 쓰기로 변환한다.
  • 특징: 데이터 덮어쓰기가 없고, 항상 새로운 위치에 쓴다.
  • GC (가비리 컬렉션): 더 이상 유효하지 않으면 공간을 회수한다.

SSD (Solid State Drive)

  • 특징: 기계 부품이 없이 임의 읽기가 빠르지만, 덮어쓰기 전 삭제 필요
    • 읽기/쓰기를 하는 단위인 페이지와 삭제를 하는 블록 단위의 크기가 다름
    • 수명이 제한됨
  • FTL (Flash Translation Layer): SSD 컨트롤러의 펌웨어로 SSD를 HDD처럼 보이게 하고 복잡한 특정을 관리
    • 주소 변환: 논리 주소를 페이지 주소로 변환한다.
    • GC: 유효한 페이지만 새로운 블록으로 복사하고 기존 블록을 삭제해 빈 공간 확보
    • 웨어 레벨링: 모든 블록에 쓰기 작업이 균등하게 분산되도록 해서 SSD 수명을 늘린다.

메모리 관리

메모리 가상화

  • 주소 공간: 각 프로세스에게 자신만의 독립적인 메모리 공간을 사용하는 것 같은 착각ㅇ르 제공하는 추상화 (코드, 힙, 스택, 데이터로 구성)
  • 주소 변환: 프로세스가 사용하는 가상 주소를 실제 메모리의 물리 주소로 변환하는 과정
    • MMU (Memory Management Unit)라는 하드웨어가 이 역할을 함

메모리 관리 기법

  • 동적 재배치: 베이스 레지스터 + 한계 레지스터를 사용해서 가상 주소를 물리 주소로 바꾼다. 메모리를 보호한다.
    • 간단하지만 내부 단편화가 발생한다.
  • 세그멘테이션: 주소 공간을 코드, 데이터, 스택 등의 논리적 단위인 세그먼트로 나눠 관리
    • 각 세그먼트마다 별도의 베이스, 한계 레지스터를 가진다.
    • 외부 단편화가 발생할 수 있다.
  • 페이징: 요게 현재 가장 널리 쓰인다.
    • 가상/물리 메모리를 고정된 크기의 페이지와 페이지 프레임으로 나눈다.
    • 페이지 테이블을 사용해 가상 페이지 번호를 물리 프레음 번호로 매핑한다.
    • 외부 단편화가 없지만 내부 단편화는 발생할 수 있다.

페이징 성능 및 공간 문제 해결

  • TLB (Translation Lookaside Buffer)
    • 문제: 페이징은 주소 변환을 위해 매번 메모리의 페이지 테이블에 접근해야 한다. -> 느리다.
    • 해결: 최근에 사용된 주소 변환 정보를 저장하는 고속 하드웨어 캐시인 TLB를 쓴다.
  • 다중 레벨 페이지 테이블
    • 문제: 페이지 테이블 자체의 크기가 너무 클 수 있다.
    • 해결: 페이지 테이블을 계층적으로 구성하여 사용하지 않는 주소 공간에 대해서는 하위 페잊 테이블을 생성하지 않아 메모리를 절약한다.

가상 메모리

  • 스왑 공간: 물리 메모리가 부족할 때 일부 페이지를 디스크의 특정 공간으로 내보내는 매커니즘
  • 요구 페이징: 프로세스 시작 시 모든 페이지를 메모리에 올리지 않고, 실제로 해당 페이지가 필요한 디스크에서 메모리로 가져온다.
  • 페이지 폴트: 필요한 페이지가 메모리에 없으면 생기는 트랩이다. 발생하면 OS가 페이지 폴트 핸들러를 통해 해당 페이지를 디스크에서 가져온다.
  • 페이지 교체 정책
    • 목표: 메모리가 가득 찼을 때 어떤 페이지를 내보낼지 결정하여 페이지 폴트 발생을 최소화하는 것
    • 주요 알고리즘
      • 최적: 가장 먼 미래에 사용될 페이지를 교체 -> 비현실적
      • FIFO: 가장 먼저들어온 페이지 교체 -> 지역성 고려 X
      • LRU (Least Recently Used): 가장 오랫동안 사용되지 않은 페이지를 교체 -> 지역성 활용, 구현비용 UP
      • 클럭 알고리즘: LRU의 근사 알고리즘으로, 각 페이지에 참조 비트를 두어 최근 사용 여부를 확인한다. -> 성능과 구현 복잡도의 절충안
  • 쓰레싱
    • 프로세스가 실제 실행보다 페이징에 더 많은 시간을 소모하여 시스템 성능이 급격하게 저하되는 현상을 말한다.
    • 각 프로세스가 자신의 작업 집합을 유지할 만큼의 메모리를 할당받지 못해 발생.

궁금중

  • 아래는 PPT를 정리하면 든 궁금증과 해결이다.
  • 사실 궁금증 해결은 중간에 하다가 말았다. 시험공부라는 목적에 너무 벗어나는 것 같아서…

동시성/락/세마포/교착상태

  • 원자성이 하드웨어적으로 어떻게 구현하는가?
    • 이 의문이 든 이유를 살펴보았다.
      • 원자성이 하드웨어적으로 구현했다는 사실은 정확하다고 가정하자. 그럴경우 멀티프로세서 환경에서 모든 코어가 같은 주소를 지속적으로 접근하면 사실상 병렬처리가 아니라 순차처리처럼 보여지는 것이 맞나? 라는 의문점에서 출발
      • 위 의문점이 맞는 말임 -> 그래서 경쟁이 적은 자료구조를 사용하고 락을 분할하는 등의 방법을 사용한다.
      • 여기서 든 생각
        • 이래서 멀티프로세스를 지원하지 않는 게임들은 하나의 코어의 단일 성능이 중요한 것이구나!
    • 다시 돌아와서 원자성이 하드웨어 적으로 어떻게 구현되는가?
      • 하나의 CPU에서 하나의 메모리 값을 레지스터와 교환한다고 가정하자. -> 이 때 다른 CPU 코어들은 그 메모리 주소를 접근하지 못하도록 하드웨어적으로 락을 건다. -> 원자성 보장
    • 그래서 아래와 같은 대표적인 원자 연산 명령어들이 존재한다.
      • CAS, XCHG, Test-and-Set, Fetch-and-Add
    • 실제로 리눅스 커널에서는 원자적 연산 함수를 제공한다. 이는 위에 나온 하드웨어 원자 명령어를 사용해서 구현된다.
      • 근데 여러개의 명령어로 이루어져 있는 연산은 어떻게 원자성을 보장하는가?
        • CAS를 반복하는 방법이 있다. -> 원자적 조건부 교환명령을 통해서 원자성을 보장하면 된다.
      • 락을 쓴다
    • 인텔의 MESI(M) 캐시 동시성 프로토콜이라는 것이 존재한다. 요게 여러 CPU가 동일한 메모리 영역을 동시에 변경하지 못하도록 한다.
  • 인터럽트 제어가 왜 멀티프로세스 환경에서는 안되는 것인지 더 알아보기
    • 인터럽트 비활성화는 로컬 CPU에서만 적용된다.
      • 한마디로 다른 CPU의 코어에서는 스케줄링이나 임계 구역에 접근할 수 있다.
      • 근데 이건 인터럽트 제어의 문제가 아니지 않나? 애초에 그냥 단일 코어에 한정된 방법이라고 생각이 든다.
  • 하드웨어 원자적 연산이 왜 3개나 있는가? 다 어디에 쓰는가?
    • 질문 쪼개기
      • 왜 여러 종류의 하드웨어 원자적 연산이 존재하는가?
        • 멀티 스레드/멀티 코어 환경에서 동기화를 위해서는 원자 연산이 필요하다.
          • 여기서 동기화라는 의미가 뭔가?
            • 여러 스레드가 동시에 실행될때, 서로 간섭하지 않도록 작업의 순서나 접근을 조정하는 것
            • 데이터의 일관성을 보장하고, 오류 방지, 순서를 보장하기 위해 필요하다.
        • 하나의 원자 연산만으로는 충분하지 않다. 그래서 서로 다른 목적의 원자 연산이 하드웨어에서 제공된다.
      • 왜 더 많은 원자 연산이 하드웨어에 없는가?
        • 연산이 복잡해 질수록 하드웨어 설계가 어렵다. -> 덜 복잡한 것으로 구성
        • 3가지 연산의 확장성을 이용해서 다른 것들을 만들면 된다.
      • 각각의 하드웨어 원자적 연산을 어디에 쓰이는가?
        • Test-and-Set: 주로 락 구현에 쓰인다. 스핀락, 뮤텍스 등 단순한 락 변수에 사용
        • Compare-and-Swap: Lock-free 자료구조, ABA 문제 해결
          • Lock-free 자료구조란?
            • 락 없이 데이터 일관성을 보장하는 자료구조
            • 락을 사용하지 않고 원자적 연산만 사용해서 구현하면 대기 없이 가능하다.
              • ??? 아까 원자적 연산도 계속 같은데 요청하면 대기를 해야한다고 하지 않았나 ???
            • Lock-free란?
              • 최소 하나의 스레드는 항상 작업을 계속할 수 있다는 의미이다.
                • 근데 Lock도 그런거 아닌가?
                  • 데드락도 Lock방식의 구조적 위험이다. 부작용으로 생각할 수 없다.
                  • 근데 Lock-free는 원천적으로 데드락 같은 것들이 발생할 수 없다.
                  • 이점에서 차이가 있다.
          • ABA 문제란?
            • 스레드1이 값을 읽고 나서 쓰기 전에 다른 스레드가 이를 2번 바꿔서 원래대로 돌려 놓으면 스레드1이 감지를 못함
            • CSA에서 어떻게 임계 구역을 다른 스레드가 조작한다고 가정하고 문제를 제기하는가?
              • 락은 말그대로 잡고 있는 동안에는 아예 접근이 불가하다.
              • 그러나 원자적 연산은 쪼갤 수만 없다는 것이지, 다른 스레드도 충분히 접근 가능하다. 근데 값이 바뀌면 실패를 반환해서 사실 락과 비슷한 효과를 가진다.
        • Fetch-and-Add: 카운터, 티켓락에 쓰임
          • 멀티 스레드의 카운터에 쓰임
          • 티켓락 (순서대로 락 잡기)에 쓰임
  • 세밀한 단위의 단위의 락을 사용하면 왜 병렬성이 극대화 되는가?
    • 경쟁이 줄어들면서 동시에 더 많은 작업이 병렬로 진행될 수 있다.
    • 서로 락으로 인해서 간섭될 확률이 줄어든다.
  • 조건 변수가 무엇인가?
    • 공유 자원을 사용할 때 어떤 조건이 만족될 때까지 스레드가 기다렸다가, 그 조건이 만족되면 다른 스레드가 깨워주는 방식으로 작동한다.
    • 왜 필요한가?
      • 스레드가 어떤 조건에 만족될 때까지 효율적으로 대기할 수 있다.
    • 특정 조건이 만족될 때까지 스레드를 잠들게 하고, 조건이 만족될 때 신호로 깨우는 동기화 도구이다.