24.03.10 운영체제, PintOS 정리

운영체제

13. 빈공간 관리

• 빈공간 관리는 관리하고 있는 공간이 고정 크기의 단위로 나누어져 있는 경우 쉽다. 그런 경우 고정 크기 단위의 리스트를 유지하면 된다. 클라이언트가 그 중 하나를 요청하면 첫 번째 항목을 반환하면 된다.
• 빈공간 관리가 더 어렵고 흥미로운 경우는 관리하는 공간이 가변 크기 빈 공간들의 집합으로 구성되어 있는 경우다. 이 경우 malloc()과 free()에서 처럼 사용자 수준 메모리 할당 라이브러리에서 그리고 세그멘테이션으로 물리 메모리를 관리하는 운영체제에서 발생한다. 어느 경우에도 외부 단편화가 존재한다.

13.1 가정

• malloc()과 free()에서 제공하는 것과 같은 기본 인터페이스를 가정한다.
• 이 라이브러리가 관리하는 공간은 역사적으로 힙으로 불리며, 힙의 빈공간을 관리하는 데는 일반적인 링크드리스트가 사용된다.
• 우리는 또한 클라이언트에게 할당된 메모리는 다른 위치로 재배치 될 수 없다고 가정한다.

13.2 저수준의 기법들

분할과 병합

• 분할(Splitting)
  • 요청이 왔을 때, 요청을 만족 시킬 수 있는 빈 청크를 찾아 이를 둘로 분할한다. 첫 번째 청크는 호출자에게 반환되고, 두 번째 청크는 리스트에 남게된다. 요청이 빈 청크의 크기보다 작은 경우 분할기법이 사용된다.
• 병합(Coalescing)
  • 메모리 청크를 반환할 때 해제되는 청크의 주소와 바로 인접한 빈 청크를 검사한다. 새로 해제된 빈 공간이 기존에 존재하는 빈 청크와 바로 인접해 있다면 그들을 하나의 더 큰 빈공간으로 병합한다.

할당된 공간의 크기 파악

• 대부분의 할당기는 추가 정보를 헤더(header) 블럭에 저장한다. 헤더 블럭은 메모리에 유지되며 보통 해제된 청크 바로 직전에 위치한다.
• 헤더는 할당된 공간의 크기를 저장해야 한다. 또한, 해제 속도를 향상시키기 위한 추가의 포인터, 부가적인 무결성 검사를 제공하기 위한 매직 넘버, 및 기타정보를 저장할 수 있다.
• 사용자가 free(ptr)을 호출하면 라이브러리는 헤더의 시작 위치를 파악하기 위해 간단한 포인터 연산을 한다.
• 헤더를 가리키는 포인터를 얻어내면 라이브러리는 매직 넘버가 기대하는 값과 일치하는지 비교하여 안정성 검사(sanity check)를 실시한다. 그리고 새로 해제된 영역의 크기를 간단한 수학을 통해 계산한다.
• 빈 영역의 크기는 헤더 크기 + 사용자에게 할당된 영역의 크기다.

힙의 확장

• 힙 공간이 부족한 경우 가장 쉬운 방법은 단순히 실패를 반환하는 것이다. 어떤 경우에는 이 방법이 유일한 대안이며, 따라서 NULL을 반환하는 것은 훌륭한 접근법이다.
• 대부분 전통적인 할당기는 적은 크기의 힙으로 시작하여 모두 소진하면 운영체제로 부터 더 많은 메모리를 요청한다. 할당기는 힙을 확장하기 위하여 특정 시스템 콜을 호출한다. 그런 후 확장된 영역에서 새로운 청크를 할당한다. sbrk 요청을 수행하기 위해 운영체제는 빈 물리 페이지를 찾아 요청 프로세스의 주요 공간에 매핑한 후 새로운 힙의 마지막 주소를 반환한다.

13.3 기본전략

최적 적합(Best Fit)

• 빈 공간 리스트를 검색해서 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾는다. 그 후, 후보자 그룹중에서 가장 작은 크기의 청크를 반환한다. 이 청크는 최적 청크라고 불린다. 빈 공간 리스트를 한번만 순회하면 반환할 정확한 블럭을 찾을 수 있다.

최악 적합(Worst Fit)

• 가장 큰 빈 청크를 찾아 요청된 크기만큼만 반환하고 남은 부분은 빈 공간 리스트에 계속 유지한다. 최악 적합의 목적은 최적 적합의 방식에서 발생될 수 있는 작은 청크들을 방지하는 것이다.
• 그러나, 한번 항상 빈 공간 리스트 전체를 탐색해야 하는 오버헤드가 존재한다.

최초 적합(First Fit)

• 요청보다 큰 첫 번째 블럭을 찾아서 요청만큼 반환한다.
• 장점은 속도가 빠르다 원하는 블럭을 찾기 위해 항상 빈 공간 리스트 전체를 탐색할 필요가 없다.
• 그러나 때떄로 리스트의 시작에 크기가 작은 객체가 많이 생길 수 있다. 따라서 할당기가 빈 공간 리스트의 순서를 관리하는 방법이 쟁점이다. 한 가지 방법은 주소-기반 정렬(address-based ordering)을 사용하는 것이다. 리스트를 주소로 정렬하여 병합을 쉽게하고, 단편화로 감소시킨다.

다음 적합(Next Fit)

• 항상 리스트의 처음부터 탐색하는 대신 다음 적합 알고리즘은 마지막으로 찾았던 원소를 가리키는 추가의 포인터를 유지한다. 아이디어는 빈 공간 탐색을 리스트 전체에 더 균등하게 분산시키는 것이다. 리스트의 첫 부분에만 단편이 집중적으로 발생하는 것을 방지한다.

13.4 다른 접근법

개별 리스트(Segregate List)

• 특정 응용 프로그램이 한 두개 자주 요청하는 크기가 있다면, 그 크기의 객체를 관리하기 위한 별도의 리스트를 유지하는 것이다. 다른 모든 요청은 더 일반적인 메모리 할당기에 전달된다.
• 이 방법의 장점은 특정 크기의 요청을 위한 메모리 청크를 유지함으로써 단편화 가능성을 상당히 줄일 수 있다. 요청된 크기의 청크만이 존재하기 때문에 복잡한 리스트 검색이 필요하지 않으므로 할당과 해제 요청을 신속히 처리할 수 있다.

특수 목적 할당기 - 슬랩 할당기(Slab Allocator)

• 커널이 부팅될 때 커널 객체를 위한 여러 객체 캐시(Object cache)를 할당한다. 커널 객체란 락, 파일 시스템 아이노드등 자주 요청되는 자료구조들을 일컫는다. 객체 캐시는 지정된 크기의 객체들로 구성된 빈 공간 리스트이고, 메모리 할당 및 해제 요청을 빠르게 서비스 하기 위해 사용된다. 아이노드들로 구성된 객체 캐시가 있고, 락 구조만을 담고있는 객체 캐시도 있다. 기존에 할당된 캐시공간이 부족하면 상위 메모리 할당기에게 추가 슬랩을 요청한다. 요청의 전체 크기는 페이지 크기의 정수 배이다. 반대로, 슬랩 내 객체들에 대한 참조 횟수가 0이되면 상위 메모리 할당기는 이 슬랩을 회수할 수 있다.
• 슬랩 할당 방식은 빈 객체들을 사전에 초기화된 상태로 유지한다는 점에서 개별리스트 보다 우수하다. 반납된 객체들을 초기화된 상태로 리스트에 유지하여 슬랩 할당기는 객체당 잦은 초기화와 반납의 작업을 피할 수 있어서 오버헤드를 현저히 감소시킨다.

버디 할당(Buddy Allocator)

• 빈 메모리는 처음에 개념적으로 크기 2^n 인 하나의 큰 공간으로 생각된다. 메모리 요청이 발생하면, 요청을 충족시키기에 충분한 공간이 발견될 때까지 빈 공간을 2개로 계속 분할한다. 이 시점에서 요청된 블럭이 사용자에게 반환된다. 이 방식은 2의 거듭제곱 크기만큼의 블럭만 할당 할 수 있기 때문에 내부단편화로 고생할 수 있다.
• 버디 할당기가 해제될 때, 8KB블럭을 빈 공간 리스트에 반환하면 할당기는 ‘버디’ 8KB가 비어 있는지 확인한다. 비어있다면 두 블럭을 병합하여 16KB로 만든다. 할당기는 다음 16KB의 버디가 비어있는지 확인한다. 비어있다면 이 두 블럭을 다시 합병한다. 이 재귀 합병은 트리를 따라 전체 빈 공간이 복원되거나 버디가 사용 중이라는 것이 밝혀질 때까지 계속 올라간다.

기타 아이디어

• 앞서 설명한 접근 방식들의 한 가지 문제점은 확장성이다. 빈 공간의 개수가 늘어남에 따라 리스트 검색이 매우 느려질 수 있다. 좀 더 정교한 할당기는 복잡한 자료구조를 사용하여 이 비용을 줄인다.

PintOS 정리

Alarm

• 프로그래밍을 하다보면 동기화를 하기 위해서 혹은 선행 작업이 끝나기를 기다리기 위해 wait을 하는 경우가 존재한다. 이때 사용하는 방식으로 sleep 방식이 있고, busy-waiting을 하는 방식이 있다. 현재 코드의 경우 busy-waiting으로 되어있다.

문제

• busy waiting을 해결하는 것이 주요 문제였다.
• busy waiting이란 OS에서 원하는 자원을 얻기 위해 기다리는 것이 아니라 권한을 얻을 때까지 확인하는 것을 의미한다.
• 프로세스가 계속해서 검사를 하고 있기 때문에 그에 대한 조건검사 작업을 수행하고 있는 것이고, 그렇기 때문에 CPU자원을 계속해서 활용한다.

해결

• Sleep list를 만들어서 사용해줬다.
• 조건을 만족하지 못하면 쓰레드를 sleep상태에 빠지게 하고, 조건을 만족할 때 wakeup 시켜주는 방식으로 해결했다.

추가 내용

• Sleep은 CPU점유를 하지 않고 조건을 만족할 때까지 잠들어서 CPU 자원 효율성을 늘리는 대기 방식이다. 대부분 시스템 프로그래밍에서는 Sleep and wake up 방식으로 대기하며, 때로는 Context Switching의 부담을 줄여주기 위해서 busy-waiting 방식을 활용하기도 한다.

Priority

• 우선순위 스케줄링, Pintos코드에서는 RR방식을 디폴트로 사용하고 있다.

문제

• 우선순위에 관한 여러 문제
• Donate에 관련된 문제
• 세마포어, 락, 컨디션 변수에 관한 여러 문제.

해결

• 테스트 마다 다른 방법을 사용해서 해결해 주었다.
• 구조체를 바꾸기도 하고, 함수를 새로 추가하거나 원래의 함수를 바꾸는등 여러 작업을 거쳤다.
• 자세한건 핀토스 카테고리에 정리해서 올려두도록 하겠다.

추가 내용

• multiple에서 많이 어려워했다.
  • donate리스트와 락을 기다리고 있는 친구들에 대한 구조체가 특히 어려웠다.
• 포인터 사용과 주소값 사용에 약간 미숙한 부분이 있었다.
• 재귀함수를 사용해볼 수 있었다.

MLFQS

• 멀티 레벨 피드백 큐 스케줄링
• 반환 시간 최적화와 응답 시간을 최적화
• EXTRA 문제, 지금까지의 문제를 압축해놓은 듯한 문제였다.

규칙

1. Priority(A) > Priority(B) 이면, A가 실행된다.(B는 실행되지 않는다.)
2. Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다.
3. 작업이 시스템에 진입하면, 가장 높은 우선순위 즉, 맨 위 큐에 놓여진다.
4. 주어진 단계에서 시간 할당량을 소진하면(CPU를 몇 번 양도하였는지 상관없이), 우선순위는 낮아진다.( 아랫 단계의 큐로 이동한다.)
5. 일정시간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.

• 라는 규칙을 가지고 있지만 Pintos에서는 Queue하나로 이것을 구현하고자 했다.

문제

• 여러 함수의 구현문제
• 부동소수점을 사용할 수 없기에 고정 소수점을 사용해야 하는 문제.

해결

• nice라는 값을 사용한다.
• nice와 최근에 cpu를 많이 사용했다면 우선순위를 낮춰주었다.
• 모든 쓰레드의 우선 순위는 4tick마다 갱신한다.
• 매 clock tick 마다 모든 쓰레드의 우선 순위를 갱신하고, 실행중인 쓰레드의 recent_cpu 값을 1씩 증가시킨다. 또한 모든 쓰레드의 recent_cpu 값을 갱신한다.

추가 내용

• #define에 매크로에서 문제가 생겨 정말 많은 시간을 소비했다. 단 괄호 한쌍의 차이였는데, 매크로 함수가 많이 겹치면서 조금 달라져서 avrg 문제가 계속 틀렸었다.
• 부동소수점에서 고정소수점으로 바꾸는 과정이 어려웠다.

결과

pass tests/threads/mlfqs/mlfqs-block
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
pass tests/threads/mlfqs/mlfqs-load-1
pass tests/threads/mlfqs/mlfqs-load-60
pass tests/threads/mlfqs/mlfqs-load-avg
FAIL tests/threads/mlfqs/mlfqs-recent-1
pass tests/threads/mlfqs/mlfqs-fair-2
pass tests/threads/mlfqs/mlfqs-fair-20
FAIL tests/threads/mlfqs/mlfqs-nice-2
FAIL tests/threads/mlfqs/mlfqs-nice-10
pass tests/threads/mlfqs/mlfqs-block
3 of 27 tests failed.