[기말 정리]

운영체제

 

운영체제

 

• 프로세스 간 데이터 동기화 (Synchronization)
  
  • IPC ( Inter-Process Communication ) ★
    - 통신 방향에 따른 분류 : Simplex(단방향), Half-duplex(반이중), Full-duplex(전이중)
    - 대기 여부에 따른 분류 : 동기화를 지원하는 통신(Interrupt, 대기 O), 동기화 지원하지 않는 통신(Polling, 대기 X)
    - 범위에 따른 분류 : 내부 데이터 통신(Thread), 프로세스간 통신, 네트워크간 통신
    
    
  • 통신 방법 ( 방법들 간 우열은 존재하지 않으며, 상황에 따른 적절한 이용이 중요하다. )
    - PIPE (무명 파이프), FIFO (명명 파이프)
     PIPE는 부모 자식간 단방향 통신, FIFO는 다른 프로세스 간의 단방향 통신에 사용되며 파일 시스템에 이미지를 갖는다.
    - Memory Queue
     커널 메모리 공간을 활용해 Queue를 만들어 데이터 처리, 구조체 기반, 다른 프로세스와 단방향 통신에 사용.
    - Shared Memory
     커널이 관리하는 일정 크기의 공유 메모리 공간을 통해 통신, 다른 프로세스와 양방향 통신에 사용
    - Memory Map
     파일을 프로세스 메모리에 맵핑하여 사용, 대용량 데이터 공유에 유리하지만,
     Page 단위로 작동하므로 공간 낭비 및 불필요한 작업이 발생할 수 있음. 다른 프로세스와 양방향 통신에 사용
    - Socket
     네트워크 간 컴퓨터들이 자신의 소켓과 상대의 소켓을 연결해 통신한다. 다른 시스템간 양방향 통신에 사용.
    ※ socket(), bind(), listen(), accept(), read(), write(), close()
    
    
  • 동기화 ( Synchronization )
    - 공유 자원에 대해 접근하는 다수에 대해, 데이터 오염을 막기 위한 방법이다.
    - 한 프로세스/쓰레드가 공유자원을 배타적 독점하여 상호 배제를 수행한다.
    상호 배제 ( Mutual Exclusion ) : 임계 구역이 오직 한 프로세스만 사용할 수 있게 하는 기술. Lock 사용. ★
    ※ enterCS() // 접근 가능한지 검사, 불가능 시 대기, exitCS() // 임계 구역 작업이 종료되었음을 알림.
    
    
  • Lock을 만드는 방법
    - 조건 : 상호 배제 수행, 한정된 시간 대기(기아X), 진행의 융통성(다른 프로세스 block X)
    - 소프트웨어적 방법 : Dekker, Peterson, Lamport ... // busy-wait 방식으로 현재는 잘 사용되지 않음.
    - 하드웨어적 방법 :
      Interrupt금지 ( Context Switching 차단 => 진행의 융통성 조건 불충족 )
      전역변수 선언 ( 전역변수도 공유데이터이므로, 문제 해결 불가능 )
      지역변수로 상대 lock 변수 설정 ( Context Switching으로 인해 deadlock 발생 가능성 )
       => 원자명령(Atomic Instruction) : 동시에 Load + set을 수행하는 Instruction
    
    
  • 동기화 방식
     - TestAndSet(TAS) : 하드웨어의 lock을 위한 Atomic Instruction ★
      lock을 읽는 명령과 lock 변수를 1로 저장하는 2개의 명령을 한번에 처리하는 명령어이다.
    
     - Lock 방식 : 동기화 대상이 1개일 때 사용, 상호 배제를 수행하는 Lock을 생성
      ※ Spinlock (Busy-wait를 수행하며 Lock을 대기, 기아 발생 가능성 있음, 단일코어에서 비효율적)
      ※ Mutex (Sleep-wait를 수행하며, Queue에 대기 프로세스를 넣어둔다.) ★
    
    - Wait-Signal 방식 : N 개의 공유 자원에 대해 다수의 프로세스가 공유하여 사용할 수 있도록 함.
     ※ Semaphore ( P연산(Enter), V연산(Exit)이 있고, n개의 자원, 대기 Queue, Cnt변수로 구성 ) ★
     - P,V연산이 반대로 사용되거나, 세마포 없이 임계구역에 진입하면 보호 불가능.
     - P만 2번 사용하면, 세마포가 풀리지 않으므로, 큐가 무한 대기한다.
    ※ Binary Semaphore : 공유 자원 1개, 접근 가능 스레드도 1개, 그렇다면 Mutex와 무엇이 다른가?
     => Mutex는 자원을 소유, 소유한 스레드만 해제 가능, Semaphore는 그 반대이다.(소유X, 소유X 스레드 해제O)
    
    - 동기화 문제 해결법
     Monitor : 공유 자원을 내부적으로 숨기고, 접근을 돕는 Interface만 제공 (추상화)
      이는, 요청받은 작업을 Queue에 저장 후 순서대로 처리하며, 처리 결과만 전달.
    우선순위 역전 : 동기화 대기작업으로 인해, 높은 순위의 스레드가 늦게 스케줄링 될 수 있음.
      이는, 공유 자원을 소유한 스레드의 우선순위를 일시적으로 올려서 순서대로 수행되게 함.
    
    
  • 생산자-소비자 문제 ( Producer-Consumer Problem )
     - 생산자는 꽉 찬 Queue에 더 집어넣으려하면 안되고, 소비자는 빈 Queue에서 꺼내려고 하면 안됨.
     - 버퍼 Queue에 읽기/쓰기가 가능한 수를 cnt로 두는, 세마포를 2개 설치해서 해결한다.
    
• 교착상태 (Deadlock) ★
  - 서로 자원을 요구하기만 하고 처리하지 못하는 상태
  - 프로그램이 스스로 인지하고 해체하는게 불가능하므로 디자인을 잘 해야함.
  - 교착상태를 직접적으로 막는 것은 높은 비용이 들어가므로, 일반적으로 적극적으로 대처 X
  - 자원 할당 그래프 모델링[Virtex:자원(사각형),프로세스(원), Edge:요청]을 통해 데드락을 찾아볼 수 있음.
  
  
  • 교착상태의 원인과 해결방안 ★
     - 자원적 특성 ( 상호 배제 수행, 비선점 알고리즘 ) -> 제한하기 어려움
     - 행위적 특성 ( 점유와 대기, 환형 대기 ) -> 한번에 요청/한번에 반환, 우선순위 ( 이것도 어려움 )
    ※ 4개 조건 중 하나라도 수행된다면 Deadlock이 발생할 수 있다.
     => 예방(4가지 조건 성립 안되게 시스템 구성), 회피(할당시 마다 가능성 검사),
    감지 및 복구(백그라운드에서 교착상태를 계속 감시, 발견하면 복구), 무시(발생하면 알아서 재시작하겠지)
    
    
  • 기아와 교착의 차이
     - 기아 : OS정책의 문제로, 특정 프로세스 작업이 지연되는 현상
     - 교착 : 여러 프로세스가 작업을 진행하던 도중 불규칙적으로 발생하는 현상
    
  • 은행원 알고리즘 (Banker Algorithm) ★
    - 각 고객들이 대출하려는 최대 금액 [Max], 현재 빌린 돈 [Allocated], 빌려줄 수 있는 돈 [Available]
    이 때, 각 고객은 원하는 최대 금액을 대출받아야 상환 가능하며, 대출받기만 하면 상환 100% 가능
    ※ 이 때, 은행이 적절한 순서로 대출을 지급하여 모든 고객이 대출받고 상환하면 Safe한 상태
    ※ 만약, 각 고객에게 조금씩 빌려줘서, 남은 돈으로 아무도 최대 금액을 대출해줄 수 없으면 UnSafe한 상태
     => 이 때, Unsafe한 상태에서만 Deadlock이 발생한다. (무조건 발생하지는 않는다. 누가 중도상환한다거나..)
     => 은행은 safe한 상태를 유지하기 위해, 최소 고객 한 명에게 대출할 금액은 보유하고 있어야함.
    
    단점 :
     - 할당할 수 있는 자원의 수, 사용자의 수, 최대 자원 요구량을 미리 파악해야함.
     - 프로세스는 유한한 시간 내에 자원을 반납해야함.
     - 항상 Unsafe한 상태를 방지해야 하므로, 자원을 자유롭게 이용하지 못함.
    
• 메모리 관리
  - 참조의 지역성 : 공간지역성(참조된 곳 근처 참조, Array), 시간지역성(최근 사용된 곳 다시 참조, Loop)
  - 메모리 계층구조 : 레지스터 < 캐시 < 램 < 저장소
  - 메모리 관리 정책 : 적재정책(언제?), 배치정책(어디에?), 재배치,교체정책(가득차면 뭘 뺄까?)
  
  • 메모리 주소 ★
    - 물리주소 : 하드웨어 관점의 주소로, 물리 메모리에 매겨진 주소
    - 논리/가상주소 : 프로세스 내에서 사용되는 주소, CPU가 실행되는 동안 다루는 모든 주소는 논리주소.
     ※ 프로세스 내에서 매겨진 논리주소는, 물리메모리에 접근하기 위해 MMU를 이용해 물리주소로 변환된다.
    MMU (Memory Management Unit) : 논리주소를 물리주소로 변환하는 하드웨어 장치, CPU에 내장됨.
     - Base Register(프로세스 할당 위치), Limit Register(메모리 경계, 프로세스 할당 끝)
     - 매핑 테이블을 통해 변환됨.
    ASLR (Address Space Layout Randomization) : 메모리 주소가 누출되면, 이를 이용해 임의코드 실행가능.
     - 이를 방지하기 위해, 프로세스 내 스택/힙 영역 랜덤배치(직접 참조 어려움), 실행마다 메모리 논리주소 변경
    
  • 주소 바인딩
    - 프로그램이 메모리의 어떤 물리적 위치에 저장될지 결정하는 과정
    - Compile-time (물리주소=논리주소, Batch에서 사용)
    - Load-time (상대주소 지정, 프로그램 로드 때 반영, 계산할게 많으면 로드시간이 길어짐)
    - Runtime ( 상대주소에 대한 계산을 실행시간에 반영, 실행 중에 MMU가 연산 )
    
  • 메모리 할당 ★
    - OS가 새로운 프로세스를 실행하거나, 실행중인 프로세스가 요구하면 물리메모리가 할당됨.
    - 이 때, 연속성 여부와 분할크기에 따라 분류된다.
    
    연속 메모리 할당 [ 현재에는 주로 사용되지 않는 방식, 초기 OS에서 사용됨 ]
     - 가변크기 할당 : 프로세스의 크기에 맞춰 메모리 할당
     - 고정크기 할당 : 메모리 전체를 고정크기 n Byte로 분할하여, 프로세스마다 하나씩 할당 (최대 프로세스 수도 고정)
      ※ 메모리 할당의 유연성이 떨어져 외부 단편화 문제가 발생하기 쉬움
      ※ 최초적합, 최적적합, 최악적합 // First > Best > Worst, 그러나 Case-by-Case
    
    불연속 메모리 할당 [ 메모리를 정해진 크기로 분할, 프로세스도 그 크기에 맞춰 분할 ]
    - 가변크기 할당 :
      Segmentation (프로세스를 세그먼트 크기로 나눠 할당, 관리, 세그먼트 매칭테이블) ★
      ※ 소프트웨어로 구현, 외부 단편화 문제 발생
      Buddy System (메모리를 절반으로 분할하면서, 프로세스를 넣을 수 있는 가장 작은 공간에 할당)
      ※ 비슷한 크기의 조각들이 모여, 큰 조각을 완성할 수 있다, 내부 단편화 문제 발생
    - 고정크기 할당 :
      Paging
    ※ 외부 단편화 : 가변크기 할당에서, 할당된 메모리들 사이에 사용하기 어려운 좁은 공간들 발생 ★
    ※ 내부 단편화 : 고정크기 할당에서, 할당된 메모리 내부에 낭비되는 공간 발생
     => 해결하기 위해, 조각모음, 압축 등의 방법이 있으나, 실행을 위해 프로세스가 일시적으로 중단되어야함
    
    
  • 페이징 (Paging) ★
     - 프로세스 주소 공간을 동일한 크기로 분할한 Page와 물리메모리를 분할한 Frame을 매칭함.
     - 각 프로세스 별로 페이지 테이블을 PCB에 저장하며, OS에서 한 곳에 모아 관리함.
     - 구현이 쉽고, 이식성이 높으며, 페이지 크기를 변경할 수 잇어 융통성이 좋고, 단편화 가능성이 적다.
    ※ 구현 방법 : 하드웨어의 PTBR(Page Table Base Register), MMU
                              소프트웨어의 OS를 통한 프레임 동적할당,반환, 테이블관리
    ※ 매핑 방식 : 직접매핑(메모리 주소와 페이지 순서 일치), 연관매핑(Tag를 이용한검색),
         직접-연관매핑(Tag단위로 묶어서 순서 일치), TLB
     - TLB ( Translation Look-aside Buffer ) : 페이지와 프레임을 연관 매핑으로 저장하는 캐시메모리 ★
     - CAM ( Content-Addressable Memory ) : 접근한 테이블 데이터를 보관하여, 다음 접근을 빠르게 함
     - TLB는 병렬적으로 작동하므로, 검색속도가 매우 빠름, 그러나 지역성이 떨어지면 TLB Miss 높음.
    
    
  • 페이지 테이블 (Page Table) ★
    - 페이지 개수 : (물리 메모리 용량 / 페이지 크기), 32bit 환경에서 페이지 개수는 2^20개
    - 32bit 환경에서, 위치 20bit + offset 12bit = 4byte, 테이블 크기 : 4*(2^20) = 4MB
    - 페이지 테이블은 각 프로세스마다 존재하므로, 4MB*(프로세스 개수)만큼 공간 차지
    
    1. IPT(Inverted Page Table) : 프레임 번호를 기준으로 테이블 작성. 한개만 존재하나, 전체 검색 필요
     ※ VA = <PID, PageNum, Offset> // PID = 4Byte, PageNum = 4Byte -> 8*(2^20) = 8MB
    
    2. Multi-level Page Table : 페이지 주소를 10bit씩 쪼개서 디렉토리를 만든다. (Index?)
     ※ VA = <PageDirIndex, PageTableIndex, Offset> // 최소 4KB ~ 최대 4MB 4KB, 레이턴시 발생
    
     ! 1,2번 방식은 64bit환경에서는 사용 불가 [ Page 52bit + Offset 12bit -> 8*(2^52)Byte = 32,000 TB ]
    
    3. Hash Page Table : Page Index들에 대한 Hash function을 만듬. Hash는 O(1)이므로 매우 빠름.
     ※ 각 항목은 <페이지 번호, 프레임 주소, 다음 번호>의 구성을 가지고, 페이지 번호가 일치하면 프레임주소 반환, 불일치시 다음 번호 조회.
    
  • 캐시 메모리 ( Cache Memory ) ★
    - 빠르고 비싸고 작은 메모리. ( 평균 엑세스 시간 : Hit Latency + (Miss rate * Miss latency) )
    - 캐시의 투명성 ( Transparency ) : 프로그래머는 캐시 조작 불가능, 하드웨어에서 알아서 동작함.
    - 메모리 동기화 방식 : Write-Through (작성될때마다 업데이트), Write-Back (블록 교체시 업데이트, Dirty bit)
    - 블록 사이즈 32Byte, 개수 2^10개 => Index 10bit, offset 5bit, tag 17bit
     ※ 캐시 검색은 CPU->Index->Tag로 지연되는데, 이를 줄이기 위해 먼저 데이터를 가져온뒤, 잘못 가져왓으면 cancel한다.
    
  • 가상 메모리 ( Virtual Memory )
    - 물리 메모리의 크기에는 한계가 있다. 이를 해결하기 위해, 저장소에 가상 메모리를 만든다.
    - Swapping ( Swap in, Swap out )을 통해 메모리와 보조기억장치에 프로세스를 이동한다.
    - 문제점 : 가상메모리에 대한 페이지 테이블의 용량, Page Fault, Page Allocation, 교체 알고리즘, Thrashing
    ※ Page Fault : 참조하려는 메모리가 물리메모리에 적재되기 전에 참조됨. ★
    ※ Page Allocation : Swap in 과정에서, 어느 위치에 메모리를 저장해야 하는가?
    ※ 교체 알고리즘 : 물리 메모리에 자리가 없다면, 어떤 메모리를 Swap-out해야 하는가?
    ※ Thrashing : Page-fault가 빈번하게 발생하여 Swapping이 자주 일어나게 되는 것 (CPU의 착각)
     => Working set 모델 : 지역성을 기반으로, 일정시간 동안 참조한 페이지의 집합 ★
     - Page-fault의 발생으로 CPU가 노는시간이 길어지면, CPU가 프로세스를 더 참조하려고 하게 된다.
    
  • 요구 페이징 ( Demand-Paging )
    - 페이지 테이블에 권한을 확인하는 R(Read), W(Write), X(eXecute), A(Accessed), M(Modified), V(Virtual) 비트가 존재한다.
    - 보조기억장치는 메모리에 비해 많이 느리므로, Write-Back으로 기능한다.
    - Page A에 대한 접근
    ※ Table[A].V == 1  => return Table[A].Address;
    ※ Table[A].V == 0  => Page Fault, Table[A].Address 는 가상메모리 주소.
    
    
• 파일 시스템 ( File System )
  - 파일(File) : 사용자나 응용프로그램 관점에서는 정보를 저장 및 관리하는 논리적인 단위.
    컴퓨터 시스템 관점에서 정보 저장의 컨테이너, 저장장치에 저장.
  
  저장장치
   - 자기장기반 : HDD, 플로피, 테이프 등 => 자기장에 반응하는 물질을 바르고, Head를 이용해 특정위치 값 Read
   - 반도체기반 : SSD, USB => 플래시메모리, 수많은 트랜지스터에서 전자를 주고받아 저장, 전기충전안하면 초기화
   - 광학기반 : CD,DVD => 플라스틱을 녹여 홈을 파고, 발사한 레이저의 반사여부로 0,1 판별
  ※ 반도체 기반이 빠른 이유 : 하드나 CD는 모터 필요, 반도체는 전자적으로만 작동.
  
   디스크
   - 플래터(정보가 저장되는 원형판) + 헤드(플래터를 읽고 쓰는 장치) + 제어모듈로 구성
   - 제어모듈:  프로세서(명령을 분석) + 디스크캐시(메모리와 디스크 사이의 중간 버퍼)
   - 섹터 ( 정보 저장의 최소단위, 0.5KB~4KB ), 트랙 ( 여러 섹터를 포함하는 동심원 )
     실린더 ( 같은 반지름을 가진 트랙의 집합 ), 블록 ( OS가 데이터를 입출력하는 논리적 단위, 섹터로 구성 )
   - 디스크 용량 : 실린더 개수 * 실린더 당 트랙 수 * 트랙당 섹터 수 * 섹터 크기
    ※ 디스크 헤드는 한 방향으로만 돌며, 전송시간 : 헤드 탐색시간 + 시작지점 검색시간 + 전송시간
   - HDD는 각회전, CD는 선회전을 하며, 파일 헤드 위치가 분산되면 조각모음이 필요하다. (SSD는 X)
    ※ 각속도 일정 : 바깥쪽 트랙속도가 안쪽보다 빠른 그대로, 구동장치가 단순하고 조용함.
    ※ 선속도 일정 : 헤드가 안/바깥 위치에 따라 회전속도 변경, 모터 제어가 복잡하고 소음 발생
   - 데이터 주소 : <Cylinder #, Head #, Sector #, CHS>
   ※ OS는 저장매체를 1차원 배열로 보며, 모든 블럭을 0번부터 본다. 프로그램은 Offset으로 참조.
   ※ 주소 변환 : 파일 내 바이트 -> 논리블록 주소 -> CHS 물리 주소
  
  파티션 
   - 운영체제가 저장장치를 논리적으로 분할하여 관리를 편하게 한다.
   - 여러 디스크를 하나로 묶는 Raid System도 존재함.
  ※ Raid 0 :
  ※ Raid 1:
  ※ Raid : 5
  ※ Raid : 6
  
  
  
• 파일 시스템 관리
   - 탐색(Seek) : 디스크 장치 내 모터를 이용해, 디스크 헤드가 목표 실린더로 이동하는 과정
  ※ Seek dist, Seek time, 평균적 5ms 내외.
   - 회전지연 : 탐색 후 플래터가 회전하여, 헤드 밑에 목표섹터가 도달할 때 까지 기다리는 시간.
   - 전송시간 : 내부전송( 플래터->디스크캐시) + 외부전송(디스크캐시->호스트)
   - 오버헤드 : 디스크 장치가 명령을 해석하는 시간 (매우 작으므로, 입출력 시간에서 배제)
  
  
• 디스크 스케쥴 알고리즘 ★
  - FCFS : 디스크 Queue에 도착한 순서대로 요청 처리, 구현이 쉽고 기아가 없으나 성능이 낮음.
  - SSTF : 디스크 헤드 실린더에서 가장 가까운 요청을 먼저 선택, 먼 위치의 것에 기아 발생 가능성
  - SCAN : 안쪽->바깥쪽->안쪽을 번갈아 검색하면서 진행함. 중간에 비해 양끝의 조회 빈도가 낮음.
  - LOOK : SCAN기반, 진행 방향에 더 이상 요청이 없을 시 이동 방향 반전
  - C-SCAN : SCAN기반, 단방향으로만 이동. 끝지점 도착시 처음으로 돌아가서 다시 검색.
  - C-LOOK : C-SCAN + LOOK
  
  야유 모르겟다 귀찮아

손코딩문제 대비
Mutex : pthread_mutex_init(&mutexVariable, NULL); pthread_mutex_lock/unlock(&mutexVariable); pthread_mutex_destory(&mutexVariable);
Semaphore : sem_init(&semVariable, 0, CNT); sem_post(&semVariable); sem_wait(&semVariable); sem_destory(&semVariable);
WebSocket : socket(), bind(), listen(), accept(), read/write(), close()

FILE : fopen("file.txt", O_RDWR); write(file, text, byte); read(file, out text, byte); lseek(file, pos, SEEK_SET);

PIPE : close(pipe[0]); close(pipe[1]); mkfifo("file.txt", 0666);
SHM : shmget((key_t)7777, byte, 0666|IPC_CHEAT); shmat(shm_id, (void *)0, perm); shmctl(shm_id, IPC_RMID, 0);

MSG_Q : asdf