24.03.09 운영체제, PintOS

운영체제

12. 세그멘테이션

• 스택과 힙 사이의 공간은 사용되지 않더라도 주소 공간을 물리메모리에 재배치 할 때 물리 메모리를 차지한다. 베이스 바운드 레지스터 방식은 메모리 낭비가 심하다. 또한, 주소 공간이 물리 메모리보다 큰 경우 실행이 매우 어렵다. 이런 측면에서 베이스와 바운드 방식은 유연성이 없다.

12.1 세그멘테이션 : 베이스/바운드의 일반화

• 세그멘테이션 아이디어는 MMU에 하나의 베이스와 바운드 값이 존재하는 것이 아니라 세그멘트마다 베이스와 바운드 값이 존재한다. 세그멘트는 특정 길이를 가지는 연속적인 주소 공간이다. 우리가 기준으로 삼은 주소 공간에는 코드, 스택, 힙의 세 종류의 세그멘트가 있다.
• 세그멘테이션을 사용하면 운영체제는 각 세그멘트를 물리 메모리의 각기 다른 위치에 배치할 수 있고, 사용되지 않는 가상 주소공간이 물리 메모리를 차지하는 것을 방지할 수 있다.
• 세그멘트의 베이스와 바운드 쌍을 이용하여 세그멘트들을 독립적으로 물리 메모리에 배치할 수 있다.
• 사용중인 메모리에만 물리공간이 할당된다. 사용되지 않은 영역이 많은 대형 주소 공간을 수용 할 수 있다. 바운드 레지스터는 세그멘트의 크기를 저장한다.
• 힙의 마지막을 벗어난 주소를 접근하려고 한다면 하드웨어가 그 주소가 범위를 벗어났다는 것을 감지하고 운영체제에 트랩을 발생시킨다. 운영체제는 아마도 문제의 프로세스를 종료시킬 가능성이 크다.

12.2 세그먼트 종류의 파악

• 하드웨어는 변환을 위해 세그멘트 레지스터를 사용한다. 하드웨어는 가상주소가 어느 세그멘트를 참조하는지 오프셋은 얼마인지 어떻게 알 수 있는가?
• 일반적인 접근법은 가상 주소의 최상위 비트 몇 개를 세그멘트 종류를 나타내는데 사용하는 것이다. 주소공간을 세그멘트로 나누기 위해서는 2 비트가 필요하다. 최상위 비트가 00이면, 하드웨어는 가상주소가 코드 세그멘트를 가리킨다는 것을 알고, 코드 세그멘트의 베이스와 바운드 쌍을 사용하여 주소를 정확히 물리 메모리에 재배치 한다. 최상위 2비트가 01 이면 주소가 힙 세그멘트 라는 것을 인지하여 힙의 베이스와 바운드를 사용한다.
• 하드웨어는 세그멘트 레지스터를 파악하는데 처음 2비트를 이용하고 세그멘트 오프셋으로 다음 비트를 취한다. 오프셋에 베이스 레지스터 값을 더하여 하드웨어는 최종 물리 주소를 계산한다. 오프셋은 바운드 검사도 쉽게 만든다. 오프셋이 바운드보다 작은지 여부만 검사하면 된다. 그렇지 않으면 주소가 잘못된 것이다.
• 세그멘트 종류를 나타내는 데 최상위 2비트를 사용하고 주소 공간에는 세 개의 세그멘트만 존재하기 때문에 지정 가능한 세그멘트 하나는 미사용으로 남는다. 즉 전체주소 공간의 1/4는 사용이 불가능하다. 가상 주소공간을 모두 활용하기 위해(그리고 사용되지 않는 세그멘트가 없도록 하기 위해) 일부 시스템은 코드와 힙을 하나의 세그멘트에 저장하고 세그멘트 선택을 위해 1비트만 사용한다.
• 상위 비트를 사용하여 세그멘트를 선택하는 것의 또 다른 문제점은 가상주소 공간의 활용도를 제한한다는 것이다. 각 세그멘트는 최대 크기로 정해진다.
• 특정 주소의 세그멘트를 하드웨어적으로 파악하는 다른 방법들이 있다. 묵시적(implicit) 접근 방식에서는 주소가 어떻게 형성되었나를 관찰하여 세그멘트를 결정한다.

12.3 스택

• 스택은 다른 세그멘트들과는 반대 방향으로 확장된다.(낮은 주소 방향으로 확장) 물리 메모리 28KB에서 시작해서 26KB까지 차지한다. 가상 주소 16KB에서 14KB에 해당한다. 다른 방식의 변환이 필요하다.
• 첫 번째, 간단한 하드웨어가 추가로 필요하다. 베이스와 바운드 값 뿐 아니라 하드웨어는 세그멘트가 어느 방향으로 확장하는지도 알아야한다. 하나의 비트를 사용하여 주소가 커지는 쪽으로 확장하면 1, 작아지는 쪽으로 확장하면 0으로 설정할 수 있다.
• 하드웨어는 세그멘트가 반대 방향으로 늘어날 수 있다는 것을 알고 있기 때문에 그런 가상주소에 대해서는 다른 방식으로 변환한다.

12.4 공유자원

• 메모리를 절약하기 위해 때로는 주소 공간들 간에 특정 메모리 세그멘트를 공유하는 것이 유용하다. 특히 코드 공유가 일반적이며, 현재 시스템에서도 광범위하게 사용중이다.
• 공유를 지원하기 위해, 하드웨어에 Protection bit의 추가가 필요하다. 세그멘트 Protection bit를 추가하여 세그멘트를 읽거나 쓸 수 있는지 혹은 세그멘트 코드를 실행 시킬 수 있는지를 나타낸다. 코드 세그멘트를 읽기 전용으로 설정하면 주소공간의 독립성을 유지하면서도, 여러 프로세스가 주소 공간의 일부를 공유할 수 있다.
• Protection bit를 사용하면 앞서 언급한 하드웨어 알고리즘이 수정되어야 한다. 가상주소가 범위내에 있는지 확인 하는 것 이외에 특정 액세스가 허용되는지를 확인해야 한다. 사용자 프로세스가 읽기 전용 페이지에 쓰기를 시도하는 경우 또는 실행 불가 페이지에서 실행하려고 하면 하드웨어는 예외를 발생시켜서 운영체제가 위반 프로세스를 처리할 수 있게 해야 한다.

12.5 소단위 대 대단위 세그멘테이션

• 지금까지의 세그멘테이션을 대단위(Coarse-grained)라고 한다. 주소 공간을 비교적 큰 단위의 공간으로 분할하기 때문이다. 일부 초기 시스템은 주소공간을 작은 크기의 공간으로 잘게 나누는 것이 허용되었기 때문에 소 단위(fine-grained) 세그멘테이션이라고 부른다.
• 많은 수의 세그멘트를 지원하기 위해서는 여러 세그멘트의 정보를 메모리에 저장할 수 있는 세그멘트 테이블 같은 하드웨어가 필요하다. 세그멘트 테이블을 이용하면 매우 많은 세그멘트를 손쉽게 생성하고 융통성 있게 세그멘트를 사용할 수 있다.

12.6 운영체제의 기원

• 시스템이 각 주소공간(세그멘트) 단위로 가상 주소공간을 물리 메모리에 재배치 하기 때문에, 전체 주소공간이 하나의 베이스-바운드 값을 갖는 방식에 비해 물리 메모리를 절약할 수 있다. 스택과 힙 사이 사용하지 않는 공간에 대해서는 물리 메모리를 할당할 필요가 없기 때문이다.
• 세그멘테이션의 도입을 위해서는 운영체제가 몇 가지 문제를 해결해야 한다.
  • 첫 번째 문제는 문맥교환이다. 세그멘테이션을 사용할 경우 문맥교환시 운영체제는 세그멘트 레지스터의 저장과 복원을 해야한다.
  • 두 번째 문제는 세그멘트 크기의 변경이다. 어떤 프로그램이 malloc()을 통해 객체를 할당 했을 때 빈 공간이 없다면 힙 세그멘트의 크기를 증가시켜야 한다. 메모리 관리 라이브러리가 힙을 확장하기 위해서 시스템 콜을 호출할 것이다. 운영체제는 공간을 할당한다. 세그멘트 크기 레지스터를 새로운 크기로 갱신하고 라이브러리에게 성공을 알린다. 그러면 라이브러리는 새로운 객체에 공간을 할당하고 할당된 공간에 대한 포인터를 호출한 프로그램에게 반환하게 된다. 시스템에 존재하는 메모리가 고갈되었거나, 프로그램이 이미 과도하게 많은 메모리를 사용 중이라면, 운영체제는 메모리 할당 요청을 거절할 수 있다.
  • 마지막으로, 가장 중요한 문제는 미 사용중인 물리 메모리 공간의 관리다. 새로운 주소 공간이 생성되면 운영체제는 이 공간의 세그멘트를 위한 비어있는 물리 메모리 영역을 찾을 수 있어야 한다.
• 일반적으로 생길 수 있는 문제는 물리 메모리가 빠르게 작은 크기의 빈 공간들로 채워진다는 것이다. 이 작은 빈 공간들은 새로이 생겨나는 세그멘트에 할당하기도 힘들고 기존 세그멘트를 확장하는데도 도움이 되지 않는다. 우리는 이 문제를 외부 단편화(external fragmentation)라고 부른다.
• 이 문제의 해결책 중 한 가지는 기존의 세그멘트를 정리하여 물리메모리를 압축(Compact)하는 것이다. 운영체제는 현재 실행중인 프로세스를 중단하고, 그들의 데이터를 하나의 연속된 공간에 복사하고, 세그멘트 레지스터가 새로운 물리 메모리 위치를 가리키게 하여, 자신이 작업할 큰 빈 공간을 확보할 수 있다. 이렇게 함으로써 운영체제는 새로운 할당 요청을 충족시킬 수 있다. 하지만 세그멘트 복사는 메모리에 부하가 큰 연산이고 일반적으로 상당량의 프로세서 시간을 사용하기 때문에 압축은 비용이 많이 든다. 이미 존재하는 세그멘트를 처리하지 못할 경우에 압축작업이 해당 세그멘트의 크기를 키우는 요청을 할 수 있기 때문에 그 요청을 위한 공간을 만들기 위해 재배치를 하기도 한다.
• 간단한 방법은 빈 공간 리스트를 관리하는 알고리즘을 사용하는 것이다. 빈공간 관리 알고리즘은 할당 가능한 메모리 영역들을 리스트 형태로 유지한다. 최적적합(Best-fit), 최악적합(Worst-fit), 최초 적합(First-fit)및 버디 알고리즘(buddy algorithm)과 같은 알고리즘을 포함하여 수많은 방식이 존재한다.

PintOS

• 진짜 짜증나는 부분에서 많이 막혔다.
• 작은 부분 포인터나 주소값의 문제나 #define같은 문제에서 막혀서 5-6시간을 날리니까 너무 화가난다. 그래도 진짜 많이 노력한 만큼 많이 풀어나간 것 같다.
• 일요일이나 월요일에 정리해서 올리도록 하겠다.

진행상태

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.