[CS 스터디] 운영체제 3

16. Thrashing 이란 무엇인가요?

• CPU가 프로세스들의 작업을 처리하는 과정에서 페이지 폴트가 자주 발생하는 것을 쓰레싱이라고 합니다.
• 멀티 프로그래밍 환경에서 다수의 프로그램이 실행될 때, 특정 프로그램에 너무 적은 메모리가 할당되는 경우에 부족한 메모리 만큼 페이지 폴트가 자주 발생하게 됩니다.
• 이러한 상황을 쓰레싱이라고 할 수 있습니다.

Thrashing 발생 시, 어떻게 완화할 수 있을까요?

• 스레싱 완화 방법은 아래와 같습니다.
  • 다중 프로그래밍 정도를 낮춘다.
  • 프로세스들에게 충분한 페이지 프레임을 할당
  • 프로세스들이 가지는 페이지 프레임 수를 증가
• 스레싱 발생 방지 알고리즘은 다음과 같습니다.
  • 워킹셋 알고리즘
    • 지역성 집합을 가진 데이터를 메모리에 동시에 올라가도록 보장하는 메모리 관리 알고리즘입니다.
    • 지역성 집합은 일정 시작 동안 프로세스는 특정 주소 영역을 집중적으로 참조하는 경향이 있다는 의미입니다.
    • 이를 통해, 프로세스가 집중적으로 사용하는 메모리를 우선적으로 주기억 장치에 로드해 스레싱을 방지할 수 있습니다.
  • 페이지 부재 빈도 알고리즘(Page Fault Frequency Algorithm)
    • 페이지 폴트를 주기적으로 조사하고 결과를 근거로 프로세스 별 할당 메모리 양을 동적으로 조절하는 알고리즘입니다.
    • 상한값이나 하한값을 정해두고 그 안에서 프로세스 수를 조절할 수 있습니다.

17. 가상 메모리란 무엇인가요?

• 메모리 관리 기법 중 하나로 보조기억 장치의 일부를 주기억 장치로 사용할 수 있게끔 해주는 방식입니다.
• 가상 메모리는 페이지 단위로 구분되며 페이지란 가상 메모리를 사용하는 최소 크기 단위라고 생각할 수 있습니다.
• OS는 이러한 가상 메모리의 페이지를 관리하기 위해 페이지 테이블을 사용하며 페이지 테이블에는 페이지와 관련된 데이터가 저장되어 있는 주소값을 관리합니다.

가상 메모리가 가능한 이유가 무엇일까요?

참고 자료

1. 프로세스 하나씩 전체적으로 처리하는 방식으로 동작하지 않습니다. 즉, 필요한 순건에 필요한 데이터에 대한 접근만 가능하다면 정상적으로 프로세스 처리가 가능합니다. 그렇기 때문에 가상 메모리를 통해 필요한 메모리만 물리 메모리에서 사용할 수 있게 해주면서 메모리 용량은 늘려주는 효과를 가져올 수 있습니다.
2. 프로세스 별로 구분된 메모리 공간을 할당 받기 때문에 필요한 데이터에 대한 주소를 구분되게 구성할 수 있습니다. 이를 페이지 단위로 구성합니다.

Page Fault가 발생했을 때, 어떻게 처리하는지 설명해 주세요.

참고 자료

• Page Fault란, 주기억 장치에 필요한 데이터가 존재하지 않아 보조기억 장치에서 해당 페이지 정보를 가져와야 하는 상황을 의미합니다.
• 페이지 폴트가 발생했을 때 처리 과정은 다음과 같습니다.
  • 페이지 폴트 발생
  • CPU 동작 일시 중지
  • 페이지 테이블에서 요구된 페이지 조회
  • 찾아온 페이지를 주기억 장치 비이있는 프레임에 로드
  • 페이지 테이블 최신화
  • CPU 동작

페이지 크기에 대한 Trade-Off를 설명해 주세요.

참고 자료

• 페이지 크기가 작을 경우
  • 장점 : 내부 단편화 문제를 완화시킬 수 있습니다.
  • 단점 : 페이지 테이블에서 매핑하는 과정이 증가하므로 과할 경우 성능상 영향을 줄 수 있습니다.
• 페이지 크기가 클 경우
  • 장점 : 페이지 테이블의 매핑 과정이 감소하면서 성능상 이점이 있을 수 있습니다.
  • 단점 : 메모리 단편화 문제가 발생할 수 있습니다.

페이지 크기가 커지면, 페이지 폴트가 더 많이 발생한다고 할 수 있나요?

• 아무래도 주기억 장치의 메모리 크기는 한정적이므로 로드될 수 있는 범위가 작습니다.
• 그렇기 때문에 주기억 장치의 메모리 크기에 비해 페이지 크기가 큰편이라면 외부 단편화 문제라 발생할 가능성이 커집니다.
• 그러다 보면 메모리 로드에 실패할 수 있으므로 페이지 폴트가 증가할 가능성이 커진다고 생각합니다.

18. 세그멘테이션과 페이징의 차이점은 무엇인가요?

참고 자료

• 페이징은 물리적으로 동일한 크기의 페이지 단위로 프로세스에 필요한 데이터를 분리 관리하는 방식입니다.
• 일정한 크기로 나누기 때문에 외부 단편화 문제는 해결되지만 내부 단편화 문제가 발생할 가능성이 있습니다.
• 이는 프로세스의 크기가 페이징 크기의 배수가 아니라면 발생 가능합니다.
• 세그멘테이션은 물리적인 크기가 아니라 프로세스를 논리적인 단위로 분리해 관리하는 방식입니다.
• 즉 method, procedure, function, object, variables, stack 등 함수 단위와 같이 메모리의 목적과 형태에 따라 분리해 관리하는 방식을 의미합니다.
• 이로 인해 세그멘트의 크기는 다를 수 있습니다.
• 그래서 내부 단편화 문제는 방지할 수 있지만 외부 단편화가 발생할 수 있습니다.

페이지와 프레임의 차이에 대해 설명해 주세요.

• 페이지는 가상 메모리 입장에서 나눈 물리적인 단위이며 프로세스가 바라보는 페이징 테이블의 물리적 단위입니다.
• 프레임은 페이지가 저징된 실제 보조 기억 장치의 메모리 단위입니다.
• 보통 페이지와 프레임은 동일한 크기를 가집니다.

내부 단편화와, 외부 단편화에 대해 설명해 주세요.

• 물리적인 메모리 단위를 기준으로 본다면 두 개념은 다음과 같습니다.
  • 내부 단편화 : 하나의 메모리 범위에서 남은 공간보다 새로운 프로세스의 메모리 크기가 작아서 활용하지 못하는 문제를 의미합니다.
  • 외부 단편화 : 하나의 메모리 범위 전체보다 새로운 프로세스의 메모리 크기가 커서 활ㅇ요하지 못하는 문제를 의미합니다.

페이지에서 실제 주소를 어떻게 가져올 수 있는지 설명해 주세요.

• 페이징 테이블을 통해 실제 메모리 주소를 가져옵니다.
• 페이지 위치와 매핑된 실제 메모리 주소를 페이징 테이블이 저장하고 있어 테이블을 통해 실제 주소로 접근합니다.

어떤 주소공간이 있을 때, 이 공간이 수정 가능한지 확인할 수 있는 방법이 있나요?

참고 자료

• 페이지 테이블에 저장된 개체를 페이지 테이블 엔트리라고 할 수 있으며 엔트리의 구성은 메모리 구성은 아래와 같습니다.
• 페이지 기본주소(Page base address)
• 플래그 비트는 다음과 같습니다.(이는 종류에 따라 달라질 수 있습니다.)
  • 접근 비트(Accessed bit) : 페이지에 대한 접근이 있었는지를 나타낸다.
  • 변경 비트(Dirty bit) : 페이지 내용의 변경이 있었는지를 나타낸다.
  • 존재 비트(Present bit) : 현재 페이지에 할당된 프레임이 있는지를 나타낸다.
  • 읽기/쓰기 비트(Read/Write bit) : 읽기/쓰기에 대한 권한을 표시한다.
• 위처럼 읽기/쓰기 비트를 통해 수정 가능 여부를 확인할 수 있으며 기타 다른 상태 정보도 함께 확인할 수 있습니다.

32비트에서, 페이지의 크기가 1kb 이라면 페이지 테이블의 최대 크기는 몇 개일까요?

• 32비트라면 4GB의 메모리에 접근이 가능합니다. (32비트에 저장할 수 있는 정수가 약 0 ~ 4,000,000,000, 2^32)
• 그래서 페이지 테이블은 최대 4000개의 페이지 크기를 가져갈 수 있습니다.

C/C++ 개발을 하게 되면 Segmentation Fault 라는 에러를 접할 수 있을텐데, 이 에러는 세그멘테이션/페이징과 어떤 관계가 있을까요?

• Segmentation Fault은 프로그램이 허용되지 않은 메모리 영역에 접근을 시도하거나, 허용되지 않은 방법으로 메모리 영역에 접근을 시도할 경우 발생합니다.
• 즉 하나의 프로세스가 할당 받은 메모리에서 분리한 범위에서 벗어나 다른 메모리 주소로의 접근을 시도했을 때 발생하는 에러입니다.
• 그러므로 세그멘테이션이나 페이징을 활용한 형태에서 다른 프로세스의 주소로 접근할 경우가 Segmentation Fault가 발생할 수 있는 지점이라고 생각합니다.

19. TLB는 무엇인가요?

• TLB(Translation Look-aside Buffer)는 페이지 테이블의 성능을 효율적으로 지원하기 위해 일부 페이지 정보를 임시 저장하는 캐시 역할을 합니다.

TLB를 쓰면 왜 빨라지나요?

• 페이지 테이블을 통해 물리 메모리로 접근할 때, 테이블에서 논리 주소와 매핑되는 물리 주소를 확인하고, 해당 물리 주소로 접근해 데이터 여부를 확인(태그) 후 가져옵니다.
• 이러한 방식은 오버헤드가 많이 발생하며 성능이 느릴 수 있습니다.
• TLB는 이러한 논리적 주소와 물리적 주소를 그래도 캐싱하고 있어 좀 더 빠른 메모리 접근이 가능합니다. 즉, 메모리 접근 과정을 단축시켜주는 역할을 합니다.

MMU가 무엇인가요?

• 위에서 설명한 가상 메모리 관리 체계에서 가상 메모리 주소를 물리 메모리 주소로 변환하는 하드웨어 종류 중 하나라고 할 수 있습니다.
• 즉, CPU의 주기억장치의 메모리 부족 문제를 해결하기 위해 가상 메모리 관리를 지원해주는 장치입니다.

TLB와 MMU는 어디에 위치해 있나요?

• TLB는 MMU 내부에 존재하며 캐시로서의 역할을 합니다.
• MMU는 대부분 CPU 내부에 탑재되어 있다고 알고 있습니다.

코어가 여러개라면, TLB는 어떻게 동기화 할 수 있을까요?

참고 자료

1. 스누피 프로토콜(snoopy protocol)
   • 각각 CPU의 캐시들은 공유되는 캐시 데이터를 파악하고 있으며, 공유되는 캐시 데이터가 갱신 되었을 경우 이를 기반으로 갱신되지 않은 나머지 데이터를 무효화한다.
   • 공유되는 버스 구조가 Broadcasting 및 Snooping에 유리하므로 버스 기반 다중 프로세서 시스템에 적합한 방식이다.
2. 디렉토리 프로토콜(directory protocol)
   • 주기억장치의 중앙 제어기가 캐시 일관성을 관리하는 형태이다.
   • 주기억장치의 중앙 제어기는 각각 CPU의 캐시 데이터들을 가지고 있으며, 모든 지역 캐시 제어기의 동작을 제어하고 보고받으며 캐시 일관성을 관리한다.

20. 동기화를 구현하기 위한 하드웨어적인 해결 방법에 대해 설명해 주세요.

참고 자료

1. Diabling Interrupts
   • 인터럽트를 꺼서 Lock을 구현하는 방법입니다.
   • 즉, 인터럽트 자체를 막아서 다른 쓰레드의 접근을 막아 자연스럽게 동기화 문제를 해결하는 방식입니다.
   • 이는 멀티코어 환경이 주를 이루는 상황에선 성능상 저하는 물론 극단적인 선택이 될 수 있습니다.
2. Test-And-Set
   • Atomic instruction을 활용하는 방식입니다. 즉, 연산이 전부 수행되던가 아니면 아예 적용하지 않는 것을 의미합니다.
   • 특정 변수를 Test하고 그 값이 원하는 값이라면 새로운 값으로 바꿔주는 식으로 동작합니다.
3. Compare-And-Swap
   • Test-And-Set과 비슷하고 Atomic instruction을 사용하지만 expected 변수가 하나 더 추가되는 방식입니다.

추가 개념

• 메모리 베리어 : 로드 베리어, 스토어 베리어

위 세가지 내용이 왜 하드웨어적 해결 방법인걸까?

• 동기화를 처리해주는 별도의 장치가 있다기 보다 하드웨어 수준의 명령어 집합으로 제공하는 해결방안으로 이해할 수 있습니다.
• 하드웨어를 제어하기 위한 명령어 수준에서 원지적 명령어 방식을 통해 락을 수행한다 정도로 이해할 수 있겠습니다.

volatile 키워드는 어떤 의미가 있나요?

참고 자료

• volatile 키워드가 선언된 변수는 최적화 대상에서 제외된다는 의미가 있습니다.
• 최적화란 하나의 변수가 반복적으로 같은 값을 저장하게 되는 경우, 저장하는 모든 명령어를 수행하지 않고 마지막 하나의 명령어만 수행하도록 하는 것을 의미합니다.
• volatile은 이러한 최적화를 하지 않고 모든 반복 코드를 수행하도록 설정하는 경우에 사용합니다.
• 이는 모든 쓰기 명령어가 레지스터에 대한 쓰기 명령일 경우, 모든 코드가 유의미한 값을 가지고 하드웨어 내에서 정확한 처리를 위한 동작이므로 volatile이 사용될 수 있습니다.

추가 개념

• 동기화 측면에서의 의미?

레지스터

• CPU가 메모리에 연산 결과를 주고 받기 위해 필요한 매우 작은 메모리입니다.
• 명령어의 종류나 메모리의 주소값을 저장할 때 사용합니다.

싱글코어가 아니라 멀티코어라면, 어떻게 동기화가 이뤄질까요?

참고 자료

• 공유 자원에 대해서 동기화가 진행되어야 하며 위에서 설명한 원자적 연산이나 뮤텍스, 세마포어 등을 활용해 동기화를 고려해볼 수 있습니다.
• 추가로 멀티코어에선 각각의 코어가 가지는 캐시에 대한 동기화가 중요합니다.
• 그래서 캐시 일관성을 유지하기 위한 스누피 프로토콜이나 디렉토리 프로토콜을 통해 캐시의 동기화를 고려해볼 수 있습니다.

21. 페이지 교체 알고리즘에 대해 설명해 주세요.

참고 자료

• 페이지 교체 알고리즘은 페이지 폴트 발생 시 메모리가 부족해 메모리 확보를 위해 삭제할 페이지를 선택하는 방식을 정의한 것을 의미합니다.
• 페이지 교체 알고리즘의 종류는 다음과 같습니다.
  • FIFO(First In First Out) 알고리즘
    • 가장 단순한 알고리즘으로 가장 먼저 들어온 페이지가 우선 삭제 대상이 되는 것을 의미합니다.
    • 큐를 사용하며 구현이 간단하지만 성능은 좋지 않은 편입니다.
    • 성능이 좋지 못한 이유는 Belady`s Anomaly이 발생할 수 있습니다.
    • Belady`s Anomaly 이란, 프레임 개수가 많아지더라도 페이지 폴트가 줄지 않고 늘어나는 현상을 말합니다.
    • 기본적으로 프레임 개수가 많으면 페이지 폴트가 발생할 확률도 줄어야 하는데 아직 사용할 페이지가 우선 들어왔다는 이유로 삭제된다면 반복적인 페이지 폴트가 발생할 수 있습니다.
  • OPT(Optimal) 알고리즘
    • 가장 오래동안 사용하지 않을 페이지를 선택하는 방식입니다.
    • 가장 페이지 폴트도 적고 Belady`s Anomaly도 발생하지 않지만 오래동안 사용하지 않을 페이지를 알 수 있는 방법이 없어 구현이 불가능합니다.
    • 단순 연구 목적으로 사용되는 알고리즘으로 이해됩니다.
  • LRU(Least Recently Used) 알고리즘
    • 메모리에 올라온 후 가장 오래동안 사용되지 않은 페이지를 교체하는 알고리즘입니다.
    • 가장 많이 사용하는 알고리즘이면서 최적화에 가까운 알고리즘입니다.
    • 위 방식들 모두 별도의 메모리를 요구한다는 단점이 있습니다.
  • LFU(Least Frequently Used) 알고리즘
    • 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘입니다.
  • NRU or NUR(Not Used Recently) 알고리즘 또는 클럭 알고리즘
    • 최근에 사용하지 않은 페이지를 교체하는 알고리즘입니다.
    • 참조시점이 가장 오래되었다는 것을 보장하지 못합니다.
    • 페이지마다 참조 비트와 변형 비트가 사용됩니다.(우선 순위는 참조 > 변형)

LRU 알고리즘은 어떤 특성을 이용한 알고리즘이라고 할 수 있을까요?

• 시간 지역성을 사용한 알고리즘이라고 할 수 있습니다. 즉, 최근에 사용한 데이터가 재참조될 가능성이 높다는 가정에서 구현한 알고리즘입니다.
• 특정 기준을 통해 페이지의 사용 횟수를 체크하고 페이지 교체가 발생하는 시점에 가장 적은 참조 횟수를 가지고 있다면 교체 이후 적은 페이지 폴트를 기대할 수 있기 때문입니다.

LRU 알고리즘을 구현한다면, 어떻게 구현할 수 있을까요?

참고 자료

• 페이지 접근 시간 : 페이지 접근 시간을 누적으로 체크해 가장 적은 시간을 사용한 페이지를 교체하는 방식입니다.
• 접근 횟수 카운트 : 접근 시간이 아닌 횟수로 카운팅을 해 가장 적은 카운트를 가진 페이지를 교체하는 방식입니다.
• 참조 비트 시프트 : 참조 비트를 별도로 구성하고 참조될 때마다 1을 가진 비트를 한칸씩 이동시켜 체크하는 방식입니다.

22. File Descriptor와, File System에 에 대해 설명해 주세요.

• File Descriptor
  • 리눅스 혹은 유닉스 계열의 시스템에서 프로세스가 파일을 다룰 때 사용하는 개념으로 특정 파일에 접근할 때 사용하는 추상적인 값입니다.
  • FD는 일반적으로 0이 아닌 정수를 가지며, 기본적으로 할당되는 FD는 다음과 같습니다.
    • 0 : 표준 입력, 1 : 표준 출력, 2 : 표준 에러
  • 프로세스가 파일을 오픈하면 현재 할당된 FD 중 가장 작은 값을 할당하며(보통 3부터 시작), 그 다음 열려있는 파일에 시스템 콜을 통해 접근할 때 FD로 해당 파일을 지칭합니다.
• File System
  • 파일 관리를 위한 방법으로 컴퓨터가 파일을 쉽게 조회/유지할 수 있게 하기 위한 방식입니다.
  • 계층적 디렉터리 구조로 유지되며 메타 영역과 데이터 영역으로 나눌 수 있습니다.
    • 메타 영역 : 파일에 대한 정보가 저장된 영역
    • 데이터 영역 : 실제 파일이 담고 있는 정보가 저장된 영역

I-Node가 무엇인가요?

• 리눅스에서 파일 시스템을 관리하기 위해 사용되는 개체의 일종으로 파일의 정보(메타 데이터)를 가집니다.
• 모든 파일은 하나의 아이노드를 가지며 다음과 같은 정보를 가집니다.
  • I-Node Number : 고유 식별 번호
  • 파일 타입
  • 접근 권한
  • link count : 참조하는 링크 개수
  • 소유자
  • 소유 그룹
  • 파일 크기

23. 동기와 비동기, 블로킹과 논블로킹의 차이에 대해 설명해 주세요.

참고 자료

• 블로킹과 논블로킹의 차이는 다른 주체가 작업할 때, 자신의 제어권이 있는지 없는지로 나눌 수 있습니다.
  • 블로킹 : 다른 주체가 작업할 때, 해당 작업이 마무리될 때까지 대기하고 있어야 하는 상황을 의미합니다.
  • 논블로킹 : 다른 주체가 작업을 하더라도 본인의 작업은 다시 재게할 수 있고 이후에 다른 주체의 작업 결과를 받아볼 수 있는 상황을 의미합니다.
• 동기와 비동기는 결과를 돌려받았을 때, 결과와 순서에 관심이 있는지 없는지에 따라 달라집니다.
  • 동기(Synchronous) : 요청한 내용에 대한 결과를 받은 이후에 결과에 대한 작업을 반드시 진행하는 것을 의미합니다.
  • 비동기(Asynchronous) : 요청한 내용의 결과와 상관없이 본인 작업을 진행하고 결과를 받은 이후에 결과에 따른 작업을 진행할 지 안할지는 모르는 것을 의미합니다.

그렇다면, 동기이면서 논블로킹이고, 비동기이면서 블로킹인 경우는 의미가 있다고 할 수 있나요?

총 4가지 조합이 나올 수 있어 각각의 조합이 어떠한 방식으로 동작하는지 알아보겠습니다.

	Blocking	Non-Blocking
Synchronous	1. 주체가 작업을 하다가 다른 주체에 요청을 보냈을 때, 결과가 나올때까지 기다린다. 2. 기다린 다음 결과가 나오면 그 결과에 대한 작업을 주체가 이어서 진행한다.	1. 주체가 작업을 진행하다가 다른 주체에 요청을 보낸다. 2. 요청 결과가 나올 때까지 주체는 계속해서 결과 여부를 확인한다. 3. 결과가 나오게 되면 그 결과에 대한 다음 작업을 진행한다.
Asynchronous	1. 주체가 작업을 진행하다가 요청을 보낸다. 2. 요청 결과가 나올 때까지 기다린다. 3. 요쳥 결과가 나오면 해당 결과를 처리하기 위한 작업을 진행할 수도 있고 안할수도 있다.	1. 주체가 작업을 진행하다가 요청을 보낸다. 2. 요쳥 결과가 나올때까지 주체는 다른 작업을 계속 진행한다. 3. 결과가 나온 이후 해당 결과에 대한 작업을 진행하거나 하지 않고 나중에 한다.

위와 같은 결과에서 동기/논블로킹과 비동기/블로킹 형태의 동작 방식은 구현이 가능하지만 대부분의 상황에서 비효율적인 형태로 동작하는 것이라고 생각합니다. 특정 상황에선 위와 같은 형태의 동작도 필요할 수 있지만 대부분의 경우 선택하지 않을 가능성이 높다고 생각합니다.

I/O 멀티플렉싱에 대해 설명해 주세요.

• 여러 프로세스를 생성하는 것은 리소스적으로 부담이 크기 때문에 하나의 프로세스 내에서 여러 클라이언트에게 서비스할 수 있도록 하기 위해 구안된 방법으로 여러 파일 디스크립터(예: 소켓, 파일)의 입출력 이벤트를 모니터링하고, 어떤 디스크립터에서 입출력 가능한 상태인지 식별하는 방법으로 작동합니다.
• I/O 멀티플렉싱이 바로 동기/논블로킹 방식으로 동작하는 경우입니다.