Colin's Blog
[기술면접] OS

Unix File System

부트블록, 슈퍼블록, i-node, 데이터블록 영역을 가지며, 운영 체제에서 보조 기억 장치와 그 안에 저장되는 파일을 관리하는 시스템의 통칭. 보조 기억 장치에 저장된 각 파일과 그 구조 Unix의 모든 파일은 파일명과 하나의 유일한 inode 를 가짐

1. 유닉스 파일 시스템의 구성

http://www.jidum.com/jidums/view.do?jidumId=481

계층구조

  1. Boot Block

    운영체제 부트, 초기화와 관련된 Bootstrap 프로시저를 저장

  2. Super Block

    전체적인 파일 시스템의 상태에 대한 meta-data
    (크기, 상태, metadata structure 에 관한 포인터 등)

  3. Bitmap Block

    i-node 와 data-block 의 할당 현황 표시

  4. i-node

    파일과 디렉토리 각각에 대한 속성 정보 영역

  5. Data Block

    파일과 디렉토리의 실제 데이터를 저장하는 영역

유닉스 파일 시스템 유형

  1. 일반파일

    사용자가 정의한 실행가능한 파일 (텍스트, 바이너리)

  2. 디렉토리 파일

    디렉토리에 포함되어 있는 여러가지 파일들, 디렉토리에 관련한 정보 등을 저장하는 논리적 영역

  3. 특수파일

    주변 장치, 파이프와 소켓 같은 프로세스간의 상호 통신 및 표준입출력 시스템 호출

  4. i-node

    각 파일에 대한 정보를 기억하는 구조체

i-node 의 개념과 구성요소

위의 그림처럼 흔히 말하는 심링크는 inode 를 두번 걸쳐서 (첫번째 inode 는 원본 파일에 대한 포인터를 가지고 있음) 원본 파일 데이터를 메모리에 사상하는 것이고, 하드 링크 파일은 원본과 직접 연결되는 inode 룰 통해 원본을 바로 자려올 수 있다.

OS / Kernel

운영체제란?

각 유저 프로세스에 가상의 컴퓨터들을 적절히 제공하며,
사용자와 하드웨어 간의 인터페이스 소프트웨어라고 할 수 있다.

주요한 특징은 아래와 같다.

(1) Resource Manager (자원관리)

(2) API (Application Programing Interface)

응용 프로그램 등등을 위한 여러가지 서비스를 지원한다.

Kernel 이란?

OS의 API 기능을 담당하는 부분이다.
운영체제의 다른 모든 부분에 필요한 서비스를 제공한다.

흔히 말하는 System Call 이 Kernel 서비스에 대한 인터페이스이고,
운영체제 위의 많은 Application 들은 System Call 을 이용하여 Kernel 이 제공하는 서비스들을 받을 수 있다.

System Call?

OS가 제공하는 서비스를 어플리케이션에 제공하는 인터페이스

1. 시스템콜 종류

  1. 프로세스 제어 (생성, 종료, 시그널)

  2. 파일 및 IO 관리

    • 생성 / 종료
    • 열기 / 닫기
    • read / write

  3. 통신

  4. 프로세스간 통신 (IPC)

Thread / Process

Program

어떤 작업을 위해 실행할 수 있는 파일

Process

프로그램의 인스턴스 (실행된 프로그램 / 운영체제로 부터 자원을 할당받는)
ref) 자원 : CPU시간, 주소공간, 메모리

Thread

thread

Java Thread

Java ThreadLocal

멀티프로세서 vs 멀티스레드

멀티스레드가 더 좋겠지..

1. 좋은 이유

  1. 자원의 효율성 증대

    • 프로세스 간의 Context Switching시 단순히 CPU 레지스터 교체 뿐만 아니라 RAM과 CPU 사이의 캐시 메모리에 대한 데이터까지 초기화되므로 오버헤드가 크기 때문
    • 스레드는 프로세스 내 메모리 공유하기 때문에 간단하고, 자원도 덜 든다.

  2. 처리비용 감소 / 응답시간 단축

    • IPC 필요 없으니 통신 오버헤드 줄어듬
    • 스레드 Context Switching 은 Stack 만 갈아치우면 되니 훨씬 빠름
    • 스레드는 PCB에 프로세스에 비해 적게 저장 (스택 및 간단한 정보만 저장)
    • 따라서 PCB 관련 오버헤드도 적음

2. PCB (Process Control Block)

프로세스 제어 블록(Process Control Block, 줄여서 PCB)은 특정한 프로세스를 관리할 필요가 있는 정보를 포함하는, 커널의 자료구조이다. PCB는 운영 체제가 프로세스 를 표현한 것이라 할 수 있습니다.

PCB 내 표현되는 정보

1) 프로세스 식별자(Process ID)

2) 프로세스 상태(Process State) :
생성(create), 준비(ready), 실행 (running), 대기(waiting), 완료(terminated)

3) 프로그램 계수기(Program Counter) :
프로그램 계수기는 이 프로세스가 다음에 실행할 명령어 의 주소를 가리킵니다.

4) CPU 레지스터 및 일반 레지스터

5) CPU 스케줄링 정보 : 우선 순위, 최종 실행시각, CPU 점유시간 등

6) 메모리 관리 정보 : 해당 프로세스의 주소 공간 등

7) 프로세스 계정 정보 : 페이지 테이블, 스케줄링 큐 포인터, 소유자, 부모 등

8) 입출력 상태 정보 : 프로세스에 할당된 입출력장치 목록, 열린 파일 목록 등

9) 포인터 : 부모프로세스에 대한 포인터, 자식 프로세스에 대한 포인터, 프로세스가 위치한 메모리 주소에 대한 포인터, 할당된 자원에 대한 포인터 정보 등.

3. Context Switching

현재 진행하고 있는 Task(Process, Thread)의 상태를 저장하고 다음 진행할 Task의 상태 값을 읽어 적용하는 과정을 말합니다. 참고로 프로세스 마다 PCB가 있습니다.

  1. Context Switching이 발생하게 되면 많은 Cost가 소요된다.

    • Cache 초기화
    • Memory Mapping 초기화
    • Kernel은 메모리 접근을 위해 항상 실행되어야 함

  2. 작동 방식

    • Task의 대부분 정보는 Register에 저장되고 PCB(Process Control Block)로 관리되고 있습니다.
    • 현재 실행하고 있는 Task의 PCB 정보를 저장하게 됩니다. (Process Stack, Ready Queue)
    • 다음 실행할 Task의 PCB 정보를 읽어 Register에 적재하고 CPU가 이전에 진행했던 과정을 연속적으로 수행을 할 수 있습니다.
    • PCB를 저장하고 가져올때는 CPU가 아무런 일도 하지 못하게 된다. (오버헤드)
    • 컨텍스트 스위칭을 하는 주체는 스케줄러이다.

  3. 컨텍스트 스위칭이 일어나는 상황

    • I/O interrupt
    • CPU 사용시간 만료
    • 자식 프로세스 Fork

Thread Safe

멀티스레드 환경에서 여러 스레드가 동시에 하나의 객체 및 변수(공유 자원)에 접근할 때, 의도한 대로 동작하는 것을 말한다.

뮤텍스와 세마포어

https://worthpreading.tistory.com/90

뮤텍스

세마포어

세마포어와 뮤텍스의 차이

모니터

wait / notify

  1. wait
  1. notify

Critical Section

임계 구역으로 프로세스 또는 스레드들이 공통 변수들에 접근, 및 수정하고 테이블을 갱신하며, 파일의 읽기, 쓰기 작업들을 수행하는 영역을 말한다. 즉 race condition이 발생하는 영역을 뜻한다. 이미 한 스레드가 Critical Section에 들어갔을 때 다른 스레드들은 이 곳으로의 접근을 막아야한다.

한 프로세스 혹은 한 스레드가 메모리의 어떤 부분을 접근하고 있을 때 다른 프로세스 혹은 스레드가 그 부분을 접근하여 값을 변경하면 안된다. 따라서 그 부분을 막기 위해 우리는 동기화를 해야한다는 개념이 나오는 것이다.

가상 메모리

http://www.jidum.com/jidums/view.do?jidumId=473

가상 메모리란 어떤 프로세스를 실행할때, 프로세스 전체가 메모리에 다 적재되지 않고도 실행이 가능하도록 하는 기법이다. 부분부분 올려서 쓰는것.
CPU - RAM 관계에서 Cache 같은 역할 수행

1. 메모리 단편화

https://jeong-pro.tistory.com/91

메모리를 효율적으로 사용하지 못하는 상황을 나타낸다.

  1. 내부 단편화

    어떠한 프로세스가 사용해야 하는 메모리는 1kb인데, 실제 할당된 메모리 블럭은 4kb일 경우 사실상 3kb 의 메모리가 낭비되는 것이다.

  2. 외부 단편화

    어떠한 프로세스가 메모리 블럭을 사용하고 반납 했을때, 해당 공간이 작게 작게 비어서 큰 놈이 한번에 들어가지 못하는 것이다. (연속으로 비어있지 않아서 발생하는 문제)

2. 단편화 해결방안

  1. Paging

    물리 메모리를 사용할 때, 페이지를 고정크기의 프레임 단위로 나눕니다. 가상 메모리도 같은 프레임단위인 페이지로 나누어 프레임과 페이지를 페이지 테이블을 통해 맵핑하여, 연속적인 물리메모리 가 아니더라도 원하는 크기의 프레임을 사용할 수 있도록 하는 기능이다.

    따라서 외부 단편화 문제는 해결되겠지만, 여전히 페이지 단위에 따라 메모리 공간이 낭비되는 내부 단편화 문제가 발생한다.
    페이지를 더 작은 단위로 쪼개면 내부 단편화 문제가 해결될 수 도 있지만, 그만큼 Page Mapping 이 자주 발생하기 떄문에 주의해야 한다.

  2. Segmentation

    세그멘테이션 기법 같은 경우는 같은 페이지 사이즈로 가상 메모리 영역을 나누는 것이 아니라, 각각 다른 사이즈인 세그멘트 로 나누게 된다. 사용 시 마다 다른 단위로 메모리를 할당해야 하므로 미리 메모리 영역을 나누어 놓을 수 없다.

    따라서 내부 단편화 문제는 해결되었지만 (수요에 따라 메모리 공간 효율적으로 세팅) 미리 얼마나 뜯어갈 지 예측할 수 없으므로, 메모리 사용 후 반납 시 외부 단편화 문제로 중간에 메모리 공간들이 뻥뻥 뚤려 있을 수 있다.

3. 페이지 폴트

프로세스가 필요한 페이지가 있는데, 지금 가상메모리에서 프레임에 매핑이 아직 되지 않는 상태에서 페이지 폴트가 난다.

대응

  1. CPU는 물리 메모리에서 찾는 페이지가 없으면, TRAP 을 발생시켜 커널 모드로 진입한다.

  2. 커널은 CPU 동작을 잠깐 멈춘다.

  3. 페이지 테이블을 확인하여, 해당되는 페이지가 스왑파일 어디에 위치하는지 확인하고 혹시 없다면 프로세스를 중지한다.

  4. 페이지 테이블에 엔트리가 있다면, 물리 메모리에 빈 프레임이 있는지 확인한다.
    • 의문점 : 빈 프레임이 없다면? (아래에서 답변)

  5. 비어있는 프레임에 가상 메모리의 페이지를 맵핑하고, 페이지 테이블을 최신화 한다.

  6. 중단되었던 CPU를 다시 시작한다.

Q. 빈 프레임이 없다면 ?

페이지 교체 알고리즘을 써서 대응한다!
여기서 나오는 방식이 FIFO, LRU, LRU Approximation 등이 있다.

  1. First In First Out (FIFO)

    가장 먼저 들어간 놈을 교체시킨다

  2. Least Recently Used (LRU)

    사용된지 오래된 놈 교체

    쓴지 오래된놈은 뒤로 보내서 꽉 차면 교체되게 만들고
    방금 쓰인애는 앞으로 보내서 프레임에서 교체되는 것을 방지한다.

  3. LRU Approximation

    LRU 와 교체의 기준은 같지만, 대신 bit 를 하나 사용하여 기회를 한번 더 주는것이다.
    교체 후보로 선정되면 1이였던 Bit 을 0으로 바꾸고,
    한번더 선정되면 얄짤없이 교체하는 방식이다.

지역성 (Locality) 에 대하여

지역성의 이해

프로세스가 메모리를 참조할 때, 이리저리 균일하게 참조하는 것이 아니라 한 순간에 물리적으로 메모리의 한 부분을 집중적으로 참조하는 성질이다.

이것은 Cache Hit 이나, Page Fault 에 모두 관련되어 있는 이야기이다.
복잡하게 생각하기 보다는, 그냥 프로세스가 메인 메모리 까지 안가고 캐시에서 원하는 정보를 찾으면 좋은 것이고, 또 가상 메모리까지 안가도 메인 메모리에서 끝내면 좋은 것을 말하는 것이다.

지역성의 종류

  1. 시간적 지역성

    최근에 참조된 메모리 주소가, 조만간 또 참조될 가능성이 높다는 것
    (LRU 등)

  2. 공간적 지역성

    최근에 참조된 메모리 근처 (실제 물리적으로 근접) 에서 또 참조될 가능성이 높다는 것
    (배열 등)

  3. 순차 지역성

    데이터가 순차적으로 액세스되는 경향 (공간 지역성의 일부로 설명되기도 함)

DMA (Direct Memory Access, Cycle Stealing)

http://www.jidum.com/jidums/view.do?jidumId=470

메모리 버퍼, 포인터, 카운터를 사용하여 장치 제어기가 CPU의 도움 없이 DMA컨트롤러를 이용하여 데이터를 직접 메모리로 전송하는 입출력 방식 (IO 장치 작업을 CPU 도움 없이 한다)

데드락 (DeadLock)

교착상태의 4가지 조건

  1. 상호 배제(mutual exclusion)
    한 번에 한 프로세스만 공유 자원을 사용할 수 있다.
    좀 더 정확하게는, 공유 자원에 대한 접근 권한이 제한된다. 자원의 양이 제한되어 있더라도 교착상태는 발생할 수 있다.

  2. 들고 기다리기(hold and wait) = 점유대기
    프로세스가 자기한테 할당된 자원을 가진 상태에서 다른 자원 요구 및 대기 가능 (욕심쟁이)

  3. 선취(preemption) 불가능 = 비선점
    프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.

  4. 대기 상태의 사이클(circular wait) = 순환대기
    두 개 이상의 프로세스가 자원 접근을 기다리는데, 그 관계에 사이클이 존재한다.

교착상태 방지

4가지 조건들 가운데 하나를 제거하면 된다.

© 2018 Colin. All rights reserved.