OS - 8. Memory Management 연습문제

8.2 다음은 이진 파일을 만드는 과정을 설명한 것이다. 컴파일러는 각각의 모듈에 대한 목적코드를 생성하고 연결 편집기는 여러 개의 모듈을 하나의 이진 프로그램으로 조합한다. 연결 편집기가 어떻게 명령어와 데이터들의 메모리 주소에 대한 바인딩을 변화시키는가? 어떠한 정보가 연결 편집기의 메모리 바인딩 작업을 원활하게 수행하기 위해서 컴파일러에서 연결 편집기로 전달되어야 하는가?

answer)링커는 최종 프로그램 이진파일 속의 변수들의 가상(symbolic) 주소를 실제 주소로 바꿔주어야 한다. 하나의 상위 프로그램이 다른 하위 프로그램을 참조하는 것은 Symbol이라는 것을 통해 이루어지는데, 링커의 작업은 이러한 Symbol의 위치를 알아내어 상위 프로그램의 목적코드에 하위 프로그램의 주소를 기입하여 참조를 해석하도록 한다. 따라서 컴파일러에서는 링커에 Symbol들의 참조 정보를 보내주어야 한다.

8.3 300KB, 600KB, 350KB, 200KB, 750KB, 125KB 순으로 분할된 메모리가 주어지고, 115KB, 500KB, 358KB, 200KB, 375KB의 순서로 메모리를 할당한다고 할 때, 최초 적합, 최적 적합, 최악 적합 알고리즘을 사용했을 경우 메모리는 어떻게 되는가? 메모리를 얼마나 효율적으로 사용했느냐를 기준으로 순위를 매기시오.

	300KB->185	600KB->100	350KB->150	200KB	750KB->392	125KB
최초 적합	115KB	500KB	200KB		358K / 375KB

185KB, 100KB, 150KB, 200KB, 17KB, 125KB 남음

	300KB	600KB->100	350KB	200KB	750KB->392	125KB->10
최적 적합		500KB		200KB	358K / 375KB	115KB

300KB, 100KB, 350KB, 0KB, 17KB, 10KB 남음

	300KB	600KB->242	350KB->150	200KB	750KB->635	125KB
최악 적합		358KB	200KB		115KB /500KB

300KB, 242KB, 150KB, 200KB, 135KB, 125KB가 남아서 375KB가 할당 받지 못함

- 위 상황에서는 최적 최적 최악 순으로 효율적으로 메모리를 사용하였다.

8.4  대부분의 시스템은 프로그램이 자신의 주소 공간에 메모리를 할당하는 것을 지원하고 있다. 프로그램의 힙 세그먼트에 할당된 데이터는 이러한 메모리 할당이 수행되는 대표적인 예라고 할 수 있다. 다음 기법들에서 동적 메모리 할당을 지원하기 위해서 어떤 것들이 요구되는가?

  a. 연속적 메모리 할당

   > 현재 할당된 메모리의 공간을 키울 때 여유 공간이 넉넉하지 않으면 프로그램 전체의      재배치를 요구 할 수도 있다.

  b. 순수 세그먼테이션

   > 세그먼트의 할당된 공간이 커질 때 여유 공간이 부족하면 여유 공간이 부족한 세그먼트만 재배치를 요구 할 수도 있다.

  c. 순수 페이징

   > 증가하는 새로운 페이지들의 할당은 프로그램 주소공간의 재배치 없이 가능하다.

8.5 다음의 쟁점들을 참고하여 연속적 메모리 할당, 순수 세그먼테이션, 순수 페이징 기법들을 비교하시오.

 a. 외부 단편화

 b. 내부 단편화

 c. 프로세스 사이의 코드 공유 가능성

1. 연속적 메모리 할당:

외부 단편화가 발생한다. 주소공간이 연속적으로 되어 있어서 내부 단편화는 발생하지 않는다. 또한 프로세스의 가상 메모리 때문에 프로세스 사이의 코드 공유가 불가능하다.

2.순수 세그먼테이션(가상메모리를 서로 크기가 다른 논리적 단위인 세그먼트로 분할, 각각의 세그먼트들은 연속적인 공간에 저장되어있음): 

서로 다른 크기의 세그먼트들에 대해 메모리를 올리고 내리는 작업을 반복하면 외부 단편화가 발생한다.  내부단편화는 발생하지 않는다.

세그먼트를 통해 프로세스 사이의 코드 공유가 가능하다.

3. 순수 페이징 기법(가상메모리를 크기가 같은 블록으로 분할): 연속된 공간을 할당하지 않아도 된다.

외부 단편화는 발생하지 않는 대신 내부 단편화가 발생한다.

page를 통해서 프로세스 사이의 코드 공유가 가능하다.

8.8 Android는 부트 디스크에서는 스와핑을 지원하지 않더라도, 별도의 SD 비휘발성 메모리 카드를 사용하여 스왑 공간을 설정하는 것이 가능하다. Android가 부트 디스크에서는 스와핑을 불허하지만 보조 디스크에서는 허용하는 이유는 무엇인가?

-  일반적으로 모바일 장치는 하드디스크보다 flash memory를 사용한다. 여기서 스와핑을 지원하지 않는 가장 큰 이유는 메모리 저장 장소의 공간이 작기 때문이고, 또 다른 이유는 flash memory가 사용의 허용되는 쓰기 횟수가 정해져 있고 flash memory와 CPU사이에 처리량이 저조하기 때문이다.

8.10 주소 공간 식별자(ASIDs)가 필요한 이유를 설명하시오.

해당 프로세스의 주소 공간 보호를 위해 유일하게 지정되는 식별자이다.

ASID를 사용하면 TLB내에 여러 프로세스의 페이지를 저장가능하다.

8.12  1KB 크기의 페이지를 가정할 때, 다음 주소 참조에 해당하는 페이지 번호와 변위는 무엇인가(주소는 십진수로 표현되어 있다.).

  a. 3085 > 0000 1100 0000 1101

     페이지 번호 : 000011

     변위 : 0000001101

  b. 42095 > 1010 0100 0110 1111

     페이지 번호 : 101001

     변위 : 0001101111

  c. 215201 > 11 0100 1000 1010 0001

     페이지 번호 : 11001010

     변위 : 0010100001

  d. 650000 > 1001 1110 1011 0001 0000

     페이지 번호 : 1001111010

     변위 : 1100010000

  e. 2000001 > 1 1110 1000 0100 1000 0001

     페이지 번호 : 11110100001

     변위 : 0010000001

8.13 BTV 운영체제는 21-비트 가상 주소를 사용하지만, 특정 임베디드 장치의 경우 물리 메모리 주소로 16-비트를 사용한다. 다음 테이블의 항목의 개수는 몇 개인가?

a. 전통적인 1단계 페이지 테이블 : 페이지의 크기를 라고 한다면 논리적 메모리 내 페이지 개수와 페이지 테이블 내 페이지 개수가 같아야 한다. 따라서 개다.

b. 역 페이지 테이블 : 페이지의 크기를 라고 할 때 물리적 메모리 내의 페이지 개수와 페이지 테이블 내의 페이지 개수가 같아야하기 때문에  개다.

8.15 4-KB 페이지를 사용하고 총 256페이지로 구성된 논리 주소 공간을 고려하자, 이 논리 주소 공간은 64프레임의 물리 메모리로 사상된다.

프레임(Frame) : 물리 메모리를 일정된 한 크기로 나눈 블록이다.

페이지(Page) : 가상 메모리를 일정된 한 크기로 나눈 블록이다.

 a. 논리 주소는 몇 비트로 구성되는가?

   256페이지이므로 8비트로 구성된다

 b. 물리 주소는 몇 비트로 구성되는가?

   64프레임이므로 6비트로 구성된다.

8.16  32비트 논리 주소와 4KB 페이지 크기를 가지는 컴퓨터 시스템을 고려하자. 이 시스템은 최대 512MB의 물리 메모리를 장착할 수 있다. 다음 각 테이블에는 각각 몇 개의 항목이 존재하는가?

  a. 전통적인 1단계 페이지 테이블

   액세스 제어 비트, 물리적 페이지 번호로 구성

  b. 역 페이지 테이블

   프로세스 식별자, 가상 페이지 번호로 구성

8.17 메모리에 페이지 테이블을 저장하는 페이징 시스템을 생각해보자.

a. 만약 메모리 참조가 50nsec 걸린다면 메모리 참조는 얼마나 걸리는가?

answer)100nsec(50nsec(pagetable접근시간) + 50nsec(memory에 있는 word에 접근하는시간))

b. TLB를 추가하여 모든 페이지 테이블 참조의 75%를 TLB에서 찾을 수 있다면 실제 메모리 접근 시간은 얼마인가?

answer) 0.75*(50nsec)+0.25*(100nsec)=62.5nsec

8.18 세그먼테이션과 페이징 기법을 결합하여 사용하는 이유는 무엇 때문인가?

세그먼트 기법 : 사용자의 메모리 관점은 실제 물리 메모리 관점과는 다르다. 사용자의 관점은 물리 메모리로 사상되는데 이러한 사상을 논리 메모리와 물리 메모리가 달라도 상관없도록 만든다. 논리 구조 공간을 세그먼트(서브루틴, 스텍, 주프로그램, 심볼 테이블)들의 집합으로 정의한다.

페이징 기법 : 우선 프로그램 전체를 메모리에 적재할 필요가 없다. 이러한 이유로 프로그램을 적당한 크기의 블록(페이지)으로 나눈다.

해당 세그먼트들은 블록(페이지)로 나누어져 있으며 세그먼트의 특정 요소를 찾아갈 때 어떤 세그먼트의 몇 번째 블록과 같이 찾아간다. 이와 같이 결합하여 사용하면 프로그램의 크기가 메모리의 사용가능 공간에 제한받지 않고, 페이지 테이블의 크기를 줄여 메모리의 효율적 이용이 가능하여 CPU의 효율을 중가 시킬 수 있다.

8.20  다음 세그먼트 테이블을 생각해보자.

세그먼트	기본	길이
0	219	600
1	2300	14
2	90	100
3	1327	580
4	1952	96

다음의 논리 주소에 대한 실제 주소는 무엇인가?

a. 0,430 b. 1,10 c. 2,500 d. 3,400 e. 4,112

<segment-number,offset> 구조

a. 219+430=649

 b. 2300+10=2310

 c. 에러 , 세그먼트의 범위를 넘는다.

 d. 1327+400=1727

 e. 에러 , 세그먼트의 범위를 넘는다.

8.23 segmented paging 기법과 큰 주소 공간을 관리하기 위한 해시 페이지 테이블을 비교하시오. 어떤 조건하에서 한 기법이 다른 기법보다 더 선호되는가?

- 주소 공간이 32비트보다 커지면 가상 주소를 해시값으로 사용하는 해시 페이지 테이블이 더 많이 사용된다. 해시 페이지 테이블의 각 항목은 연결 리스트를 가지고 있다. 연결리스트는 충돌을 일으켜서 같은 곳으로 해시되는 원소들을 연결 리스트를 이용하여 연결한다. 따라서 주소 공간이 커질수록 페이지가 많아지기 때문에 충돌 발생 확률이 많아지며 이들을 모두 관리하기에는 segmented paging 기법보다는 해시 페이지 테이블이 더욱 좋다.

8.22 VAX구조에서 사용하는 계층적 페이징 기법에서 사용자 프로그램이 메모리에 적재 연산을 수행하기 위해서 얼마나 많은 메모리 연산이 수행되는가?

answer)VAX 시스템은 이단계 페이징을 사용하므로, 메모리 연산은 3회 정도 수행된다.(바깥페이지테이블연산 , 페이지테이블의 페이지 연산, 물리주소에서의 적재연산)

연습문제 8.24   그림 8.22에서 설명하고 있는 Intel 주소 변환 기법을 참고하시오.

  a. Intel Pentium 프로세스에서 논리주소가 물리주소로 변환되는 모든 과정을 설명하시오.

   처음에 limit가 주소의 유효성을 검사하기 위해 사용된다. 만약 주소가 유효하지 않다면 메모리 폴트를 발생시키고 운영체제에 트랩을 발생시킨다. 만일 유효하다면 offset 값은 selector에 의해 선택된 segment descriptor값과 더해져 32비트 linear address를 만들어 낸다

  b. 복잡한 메모리 변환을 지원하는 하드웨어가 운영체제에게 어떠한 유익이 되는가?

   하드웨어로 이 기능이 구현되면 커널이 더 단순해지고 더욱 효율적이다.

  c. 이 주소 변환 시스템에 단점은 없는가? 있다면 무엇인가? 없다면 왜 모든 업체에서 이 기법을 사용하지 않는가?

   주소 변환은 다수의 테이블 검색이 일어날 수 있어서 오랜 시간이 걸릴 수 있다는 단점이 있다. 캐시가 도와주기는 하지만 그래도 여전히 캐시 미스가 있다.