7장 메모리 관리 메모리 관리를 위한 메모리 할당 기법과 경영에 대해 알아본다. 단편화 현상의 원인과 해결 방법을 알아본다.

Presentation on theme: "7장 메모리 관리 메모리 관리를 위한 메모리 할당 기법과 경영에 대해 알아본다. 단편화 현상의 원인과 해결 방법을 알아본다."— Presentation transcript:

1 7장 메모리 관리 메모리 관리를 위한 메모리 할당 기법과 경영에 대해 알아본다. 단편화 현상의 원인과 해결 방법을 알아본다.
메모리 관리를 위한 메모리 할당 기법과 경영에 대해 알아본다. 단편화 현상의 원인과 해결 방법을 알아본다. 연속 적재와 분산 적재의 장단점을 이해한다. 페이지 및 세그먼트 메모리 할당 기법을 이해한다.

2 메모리 관리 개념 (1) 메모리 관리 기법 모든 프로세스는 실행되기 전 메모리에 저장 - 프로세스의 크기 : 물리적 메모리의 크기에 제한 받음 메인 메모리 구분 운영체제를 위한 영역(상주 모니터, 커널) 현재 실행되고 있는 프로그램을 위한 영역 다중 프로그래밍 시스템 - 메모리의 사용자 영역을 여러 프로세스들이 상주할 수 있도록 세분화 - 메모리 관리(=세분화 작업) - 운영체제에 의해 동적으로 이루어진다. 메모리 기본 단위- 바이트 또는 워드로 표현되는 물리적 주소

3 메모리 관리 개념 반입 기법(Fetch Strategy) 배치 기법(Placement Strategy)
◆ 주기억장치 구성 정책이 결정된 상태에서 시스템의 성능을 최대로 높이기 위해 사용할 수 있는 주기억장치 관리 기법은 반입기법, 배치기법, 교체기법, 할당 기법이 있다. ⇒ 특정 시스템에 어떤 기억장치 구성을 채택하느냐에 관계없이, 최적의 효율을 얻기 위해서 어떤 전략을 사용해야 할 것인가를 결정해야 한다. 반입 기법(Fetch Strategy) 배치 기법(Placement Strategy) 교체 기법(Replacement Strategy) 할당 기법(Allocation Strategy)

4 메모리 관리 개념 메모리 관리 기법 1) 반입(fetch) 정책 페이지를 메인 메모리로 가져올 시기를 결정하는 정책 즉, 메인 메모리에 적재할 다음 프로세스의 반입 시기를 결정하는 방법 ① 요구 반입 전략 (Demand fetch) : 필요로 할 때 적재(load)하는 방법 -  다음에 실행될 프로세스를 참조될 시기, 즉 운영체제나 시스템 프로그램, 사용자 프로그램 등의 참조요구가 있을 경우 메인 메모리에 적재하는 방법 ② 예상 반입 전략 (Anticipatory fetch) : 미리 적재해 놓는 방법 시스템의 요구를 예측하여 미리 메모리에 적재하는 방법 요구되는 페이지 이외 다른 페이지도 함께 불러들이는 방법으로 탐색시간과 회전 지연시간을 갖는 디스크와 같은 보조기억장치의 특성을 참조한 정책 2) 배치(placement)정책 디스크로부터 반입한 프로세스를 메인 메모리 어느 위치에 저장할 것인가 결정 하는 방법으로 최초 적합, 최적 적합, 최악 적합 등이 있음.

5 메모리 관리 개념 메모리 관리 기법 3) 교체(replacement)정책 교환(재배치) 전략으로 메인 메모리에서 어느 프로세스를 제거 할 것인가를 결정하는 방법으로 시기에 따라, 사용빈도에 따라 결정하는 등 여러 방법이 있다. 4) 할당 기법(Allocation Strategy) 새로 생성되는 프로세스에 대하여 “공간 할당을 어떻게 할 것인가” 하는 문제.

6 메모리 관리 개념 (2) 메모리의 두 가지 관점 물리적 공간(물리적 주소) - 실제 자료나 프로그램이 저장되는 공간
메모리 칩(chip) 또는 디스크 공간으로 만들어진다. : 사용단위-> 바이트(byte) 단위 논리적 공간(논리적 주소) - 프로그래머가 프로그래밍 시 사용하는  공간 목적코드(object code)가 저장된 공간과 프로그램에서 사용하는 자료 구조 등이 해당된다. P A -시작 P A -끝 P B -시작 P B -끝 P C -시작 P C -끝 논리적 관점 (논리적 주소 공간) 물리적 관점 (물리적 주소 공간) [그림7-1] 메모리의 두 가지 관점

7 메모리 관리 개념 메모리의 두 가지 관점 CPU Memory MMU
논리적 메모리 크기 - 시스템에서 정의한 워드의 길이에 따라 다름 [예]16비트 공간  64(216)KB, 24비트  16(224)MB, 32비트  4(232)GB 물리적 메모리는 논리적 주소보다 크거나 작거나 같을 수 있음 비트 - 물리적 공간이 크고, 32비트 - 논리적 공간이 큼 논리적 주소와 물리적 주소의 연결 - 메모리 사상(mapping)을 통하여 이루어 지며 - 메모리 관리장치(MMU; Memory Management Unit)로 알려진 하드웨어에 의해 실행  하드웨어 (물리 또는 실제) 주소 프로그램 (논리 또는 가상) 주소 주소 변환 CPU MMU Memory [그림7-2] 메모리 관리장치에 의한 메모리 사상 ◆ 사상 방법 - 재배치 레지스터를 이용한 변환 방법 물리적 주소 논리적 주소 프로세서 메모리 재배치 레지스터 ╂ 14346 14000 346 재배치 레지스터를 이용한 물리적 주소 생성

8 메모리 관리 개념 (3) 주소 바인딩 프로세스 수행 - 프로세스가 수행되기 위해서는 메모리 내에 적재되어야 하며 대부분의 프로세스는 이진 실행 가능 파일로서 디스크에 존재 함. - 디스크에 있는 프로세스들이 수행되기 위해서는 입력 큐를 통하여 메모리로 적재되어야 함 - 절 차 : 입력 큐에서 하나의 프로세스를 선택 - 메모리에 적재 - 수 행 : 프로세스는 메모리의 명령어와 자료에 접근 - 프로세스 종료 : 사용했던 기억공간은 다른 프로세스가 사용 가능 기억공간으로 변함 바인딩(binding) - 논리적 주소(변수)를 물리적 주소로 변환 과정 즉, 프로그램에 있어서의 모든 번지를 절대 번지로 바꾸어 메인 메모리의 고정된 부분에 적재하는 것 기억장치 주소공간에서 명령어와 자료의 바인딩은 그 방식에 따라 컴파일 시간, 적재 시간, 실행 시간 단계로 구분함, 컴파일 시간(compile time) 적재 시간(load time) 수행 시간(execution time)

9 메모리 관리 개념 주소 바인딩 - 계속 원시 프로그램 1) 컴파일 시간(compile time) - 프로세스가 메모리 내에 적재될 위치를 컴파일 과정에 알 수 있다면 컴파일러는 물리적 주소(절대주소) 생성 할 수 있다. - 절대 재배치 : 메인 메모리의 실제 주소로 변환되는 과정 - MS-DOS의 COM 프로그램 : 컴파일 시간에 바인딩 된 절대 코드 이다. 2) 적재 시간(load time) - 프로세스가 메모리 내의 어디에 적재되어야 할 것인가를 컴파일 과정에 알려주지 않으면 컴파일러는 재배치 가능 상대주소를 생성한다 - 상대주소 : 프로그램의 시작주소를 0 으로 가정 하고 생성되므로 최종 바인딩은 적재 시간이 될 때까지 연기 - 정적 재배치 : 시작 주소가 변하면 사용자 코드는 변화 된 값을 반영 위해 재 적재하는 것 3) 수행 시간(execution time) - 한 프로그램이 동일한 장소에서 작동된다면 적재시간 과정에서 바인딩 된다. - 만약 프로세스 수행 중 세그먼트로부터 다른 세그먼트로 이동 되면 바인딩은 수행시간까지 연기 됨 현대 운영체제 - 수행시간에 바인딩 된다. 컴파일러 또는 어셈불러 목적 모듈 원시 프로그램 연결 편집기 적재 모듈 적재기 내장된 2진 코어 이미지 사용자 프로그램의 처리 단계

10 메모리 관리 개념 (4) 동적 적재 메모리 공간 이용의 효율적 운영을 위하여 동적 적재 (Dynamic Loading) 기법 사용 - 주소 바인딩 시간 늦추어서 실행되기 직전에 주소를 확정하면 시스템 운영과 메모리 활용에 도움을 줄 수 있다. = 동적 적재 (Dynamic Loading) 사용 - 주 프로그램(호출 루틴)이 다른 루틴의 호출을 필요로 할 때, 호출 루틴은 다른(호출될) 루틴이 적재되었는지를 조사한다. 만약 적재되지 않았다면 재배치 가능 연결 적재기는 요구된 루틴을 메모리로 적재하기 위해 호출하고, 이러한 변화를 반영하기 위해서 테이블을 갱신한다. 이러한 일련의 과정을 동적 적재라 한다. ◆ 장점 - 사용되지 않은 루틴들은 적재되지 않음 오류 루틴 발생하면서도 많은 양의 코드를 필요로 하는 경우 유용 프로그램의 전체 양이 많아도 실제로 사용된 구역(실제 적재된)은 적음 운영체제로부터 특별한 지원 불필요하지만 동적 링크 적재기는 제공되어야 함 ◆ 단점 사용자 자신이 프로그램 설계를 책임져야 함.

11 메모리 관리 개념 (5) 중첩 - 프로세스의 모든 논리 주소 공간은 그 프로세스가 수행되기 전 메모리에 적재되어야 하므로 프로세스의 크기는 실제 기억 장치의 크기로 제한된다. - 한 프로세스에 할당된 메모리보다도 큰 프로그램은 중첩(Overlay)기법을 사용하여 해결 중첩(Overlay) - 운영체제 영역과 메모리 공간의 일부 영역에 프로그램(작업)실행에 반드시 필요한 명령어와 자료를 적재시키고 나머지 영역(중첩 구동기 영역)에는 실행기간 동안에 필요한 각종 사용자 코드 등을 적재하여 각각 필요한 시기에 해당되는 프로그램을 불러들여 수행하는 방법 예) 사용자 프로그램 초기 모듈, 처리 모듈, 출력 모듈로 구별 초기 모듈을 적재한 후 실행  처리 모듈  출력 모듈을 적재한 후 실행

12 메모리 관리 개념 중첩 - 계속 [예] 단계 1 - 심볼 테이블 작성 단계 2 - 기계어 코드 생성 어셈블러
단계 1 - 심볼 테이블 작성 단계 2 - 기계어 코드 생성 어셈블러 (two-pass assembler) ▶ 요소의 크기 - 패스1 : 70K(1K=1024Byte) 패스2 : 80K   - 심볼 테이블 : 20K ,  공통 루틴 : 30K, 오버레이 드라이버 : 10K 공통 루틴 오버레이 드라이버 심볼 테이블 패스 1 패스 2 ◆ 모든 내용 적재 : 210K 필요 ◆ 사용자 영역 : 200K (수행될 수 없음) ◆ 두 개의 중첩 정의 - 패스 1과 패스 2과 동시에 메모리 내에 있을 필요가 없으므로 다음과 같은 두 개의 중첩 사용     (A) 심볼 테이블, 공통루틴, 패스1     (B) 심볼 테이블, 공통루틴, 패스2 [해결]   10K : 오버레이 드라이버 추가 중첩A를 시작하고, 패스 1이 끝날 때 중첩 B를 메모리로 읽어 들이고 중첩 A상에 기록, 제어를 패스 2로 옮김 : A(120K), B(130K) 필요로 함 중첩 A에 대한 코드 위에 중첩 B에 대한 코드를 입출력 하므로 다소 늦게 수행 [그림7-6] 2단계 어셈블러를 위한 중첩

13 메모리 관리 개념 중첩 - 계속 [구현] - 사용자에 의해 파일들을 메모리로 읽어 들이고, 메모리로 이동, 새로운 읽기 명령을 수행시키는 간단한 파일 구조를 사용함으로 구현할 수 있다. 프로그래머 - 중첩 구조를 적절하게 설계하고 프로그램 해야 함으로 프로그램 구조와 코드 또는 자료 구조를 완전한 이해가 필요, 그러나 충분히 이해하는 것은 어려운 일이다. 중첩 사용 - 현재의 마이크로 컴퓨터나 실제 메모리 크기가 제한된 하드웨어에서 사용하며 대부분 메모리를 확장 사용하여 해결하고 있음.

14 메모리 관리 개념 (6) 교체 ■ 다중프로그래밍 환경 사용자 프로그램 완료까지 메인 메모리에 저장됨을 원칙 그러나 순환 할당,우선 순위에 바탕을 둔 프로세서 알고리즘에서 불편 ■ 프로세스 수행 시 프로세스가 메모리 내에 있어야 하나 일시적으로 메모리에서 보조 기억 장치로 이동되었다가 다시 수행되기 위해 메모리로 되돌아 올 수 있다. [예] 프로세서 할당 시간이 끝나면, 메모리 관리기는 방금 끝난 프로세스를 보조 기억장치로 이동, 다른 프로세스를 사용가능 공간 안으로 이동한다. 운영 체제 보조(예비) 기억장치 사용자 영역 메인 메모리  롤인(roll-in), 롤-아웃(roll-out)⇒교체의 변형 더 높은 우선순위를 가진 프로세스가 도착하면 메모리 관리기는 더 높은 우선순위 프로세스를 적재해서 수행 시키기 위해 낮은 우선순위 프로세스와 교체(swapping)할 수 있음 [그림7-7] 예비 기억장치로 디스크를 사용하는 경우의 교체과정

15 메모리 관리 개념 교체 - 계속 교체 과정 - 주소 바인딩의 방법에 따라 다름. - 어셈블리나 적재 시간에 바인딩 : 프로세스는 다른 위치에 이동 될 수 없음 - 수행 시간에 바인딩 : 교체할 수 있음 교체 시스템 -  빠른 디스크 보조기억 장치 필요 - 문맥 교환 시간(context-switch time) 중요 [예] ▶ 사용자 프로세스: 100K ▶ 보조기억장치 : 초당 1MB 전송율 ▶ 보조기억 장치로부터 100K 프로세스의 실제 전송 시간 : 100ms =100K/초당 1,000K = 1/10초 = 100ms(100X1/1000) ▶ 평균 8ms의 회전 지연 시간 가정하여 교체 시간 : 108ms ▶ 총 교체시간(swap out + swap-in) : 약 216msec 효과적인 프로세서 사용 - 각 프로세스에 대한 수행시간이 교체 시간보다 길어야 하므로 순환 할당 프로세서 스케줄링 알고리즘에서 시간 할당량은 실제적으로 0.216초보다 커야 실제적인 처리가 가능

16 메모리 관리 개념 (7) 메모리 경영의 변천 메인 메모리 경영 연속 적재 - 프로그램 적재 : 연속적인 메모리 할당
분산 적재 - 페이지나 세그먼트 단위로 나누어 여러 곳에 나누어 적재 - 초기 컴퓨터 시스템 - 연속적 메모리 할당 즉, 연속된 하나의 블록 차지하는 방식 [예] 직접 배치, 중첩(오버레이), 분할 기법  등 분할 기법 ▶ 메모리 영역을 여러 개의 고정된 크기로 분할하여 프로세스에게 제공하는 기법 프로세스의 크기가 각각 다르기 때문에 메모리의 낭비(내부 단편화)를 가져옴. [해결 방법] 프로세스의 크기에 맞는 동적 분할 메모리 할당 방식 제공 동적 분할 메모리 할당 방식 ▶ 동적 분할 메모리 할당방식 즉, 가변분할 다중 프로그래밍이 적용되면서  분산 메모리 할당의 유용함 인식 분산 메모리 할당방식 ▶ 프로세스(페이지나 세그먼테이션으로 구성)가 보조기억장치에 적재되어 있다가  프로세서 요구로 메인 메모리 여러 영역에 할당되는 방식으로 ⇒ 현재의 가상 메모리 관리기법으로 발전

17 메모리 관리 개념 메모리 경영의 변천 [동적 분할 메모리 할당방식의 예] [그림7-8] 동적 분할 방식

18 연속 메모리 할당 02 (1) 단일 사용자 연속 메모리 할당
▶ 초기의 컴퓨터 시스템, MS-DOS 환경 한 번에 한 사용자만 기계 사용 모든 자원 - 사용자 단독 사용 프로그램의 크기 – 메인 메모리 용량 범위 내 직접 배치 과정 수행 - 같은 메모리 위치(절대 적재)에 적재 메모리 - 사용자 공간, 운영 체제(모니터), 미사용 부분으로 나누는 단순한 기법 사용 운영체제 - 메모리의 하위나 상위에 둠 (A) 운영 체제 사용자 512 K (B) 경계 레지스터 [그림7-9] 사용자 프로세스의 상위 메모리 적재(A)와 메모리 보호(B) 

19 연속 메모리 할당 02 단일 사용자 연속 메모리 할당-계속
▶ 단일 사용자 연속 메모리 할당 시스템 사용자 : 메인 메모리에 대한 제어 권 유지 사용자 프로그램이 주소를 잘못 지정하면 운영체제 파괴 가능 운영체제 보호 - 경계 레지스터 사용 ▶ 문제점 : 사용자 프로세스의 적재 사용자  프로그램의 처음 주소는 0000번지가 아니고 기준 레지스터 값 이후가 되므로 기준 주소가 변하면 다시 재 적재 되어야 함 ▶ 운영체제의 동적 변화를 위한 방법 ① 사용자 프로그램을 기준으로부터 상위 주소에 적재하지 않고 기준 레지스터로부터 내려가는 상위 메모리에 적재하는 것 [장점] 사용되지 않은 공간이 중간에 있으므로 운영체제나 사용자는 필요에 따라 사용되지 않은 공간으로 확장 가능 ② 수행할 때까지 주소 바인딩 연기 : 기준 레지스터(재배치 레지스터) 필요

20 연속 메모리 할당 + 02 단일 사용자 연속 메모리 할당-계속 [예] 기준 값 : 1400
물리적 주소 논리적 주소 프로세서 + 메모리 기준 레지스터 1746 1400 346 MMU [예] 기준 값 : 1400 - 주소 0에 대하여 동적으로 으로 재배치 - 346에 대한 접근은 1746으로 재배치됨 [그림7-10] 기준레지스터를 이용한 동적 재배치 [장점] 단순하고 이해가 쉬우나 [단점] 다른 프로그램을 사용할 수 없으므로 메모리 낭비가 심함 다중 프로그래밍이 불가능 메인 메모리보다 큰 프로그램을 수행할 수 없으며 논리적 메모리가 물리적 메모리보다 작을 때만 프로그램 수행 의미 - 교체 기법 이용하여 메인 메모리보다 더 큰 프로그램 실행할 수 있기 때문에 제한된 메인 메모리를 확장시키는 방법 제공

21 연속 메모리 할당 02 단일 사용자 연속 메모리 할당-계속
▶ 프로세서 중심의 작업 : 프로세서를 집중적으로 사용 ▶ 입출력 작업이 교대로 발생 경우 : 프로세서 유휴 상태가 자주 발생 [그림7-11] 단일사용자의 프로세서 이용도 [장점]- 시스템 단순 - 사용자 공간 확대(운영체제 부분이 작아도 가능) [문제점] - 자원의 낭비(프로그램이 차지하고 남은 부분에 대한 활용이 불가능) - 교체 비용이 크고, 입출력 때 프로세서는 유휴상태 - 사용되지 않는 프로그램 적재

22 연속 메모리 할당 02 (2) 고정 분할 다중 프로그래밍
▶ 연속 메모리 할당 기법 가장 간단한 방법은 여러 개의 고정된 크기로 분할(정적 분할) 하는 방법 분할 : 하나의 프로세스(job)을 포함하고, 분할된 작업 큐에는 해당 크기 이내의 작업들이 지정된 분할에서만 실행될 수 있다 다중 프로그래밍의 정도 : 분할의 수에 의해 제한 받음 MFT(Multiprogramming with a Fixed number of Tasks) 기법 = 고정수 태스크 다중 프로그래밍 분할이 비어 있으면 프로세스는 프로세스 큐에서 하나 선택하여 빈 분할에 적재하고, 프로세스가 끝날 때 그 분할은 다른 프로세스를 위해 이용하는 것 ⇒ IBM OS/360에서 사용되었으나 현재는 사용되지 않음  [예] ▶ 준비 큐  2K 크기(Q2), 6K 크기(Q6), 12K 크기(Q12) ▶ 작업량이 2K 미만은 Q2로, 6K 미만은 Q6으로, 12K 미만은 Q12로 보냄 ▶ 큐에 할당되는 과정 - 최대 메모리 요구량 표시하여 자동적으로 처리 ▶ 큐 - 자신의 기억 영역을 갖고 있기 때문에 큐 사이에 경쟁은 없음

23 연속 메모리 할당 02  고정 분할 다중 프로그래밍 [문제점] Q12 큐가 가득 차 있고 다른 큐(Q2, Q6) 가 비어 있더라도 이용할 수 없음 [개선 방법] 모든 작업을 통합 큐에 넣고 운영 각 영역에 독립된 큐를 갖는 고정 분할 시스템 [문제점] 작업 스케줄러는 수행할 다른 작업을 선택해서 그 크기의 메모리 공간 이용할 수 있을 때 까지 기다림 발생 통합 큐 운영 고정 분할 시스템

24 연속 메모리 할당 02 고정 분할 다중 프로그래밍 - 계속 [예] 작업이 5K, 2K, 3K, 7K 등으로 도착한 경우
 고정 분할 다중 프로그래밍 - 계속 [예] 작업이 5K, 2K, 3K, 7K 등으로 도착한 경우 - 작업1(5K)을 6K 영역에, 작업2(2K)를 2K영역에 할당 - 작업3(3K)을 할당할 6K 영역은 작업 1에 의해 사용되므로, 작업1 완료까지 기다림  다음에 작업 3이 6K 영역에 할당 - 작업 4는 작업 4를 위한 영역(12K)이 비어 있다고 해도 작업 스케줄러가 선입 선처리 이기 때문에 작업 3이 할당될 때까지 기다림 ▶ 결정 사항 ① 분할 영역의 크기 - 어느 정도의 크기를 가진 영역을 몇 개 설정할 것인가를 결정해야 함. - 영역의 개수 : 다중 프로그래밍의 정도에 따라 결정됨. [예] 전체 용량(32KB), 상주 모니터의 크기(10KB)이면 매우 작은 작업 4K, 평균 작업 6K, 큰 작업 12K로 영역 배정 가능함 - 영역의 크기 결정 - 시스템 전체 효율을 나타내는 요인 ②  영역의 배정  - 작업을 어느 영역에 배정하는가에 대한 결정하기 위해서는 작업 스케줄러 필요

25 연속 메모리 할당 02 (3) 고정분할 다중 프로그래밍에서의 단편화
(3) 고정분할 다중 프로그래밍에서의 단편화 ■ 메모리 단편화(fragmentation) - 메모리 구성에 관계없이 시스템에서 발생 함. ■ 고정 분할 다중 프로그래밍에서 단편화 사용자 작업의 크기가 지정된 분할에 정확히 맞지 않거나 분할이 너무 작아서 대기중인 작업 중에서 그 분할을 사용할 수 없을 때 발생함. [예] ▶ 18,464 바이트의 사용가능 공간이 있을 때 다음 프로세스가 18,462 바이트 요구 - 요구된 블록을 할당하면 2바이트의 사용가능 공간이 남음 - 사용가능 공간 처리 부담 문제 발생 ? 이러한 남는 부분 - 내부 단편화(대부분 사용 못함)

26 연속 메모리 할당 02 고정분할 다중 프로그래밍에서의 단편화 - 계속
 고정분할 다중 프로그래밍에서의 단편화 - 계속 [예] 32K 메모리 시스템 : 운영체제(10K), 사용자 공간(22K) 작업 큐 : 7K, 3K, 6K, 6K를 요구하는 작업 -10K영역과 3개의 4K영역으로 나눔 7K 작업 10K영역에[3K 내부 단편화] 3K 작업  4K 영역 하나에 [1K 내부 단편화] 할당 6K 작업  할당될 수 없음 10K, 8K, 4K 영역으로 나눔 K 작업  8K 영역에 3K 작업  4K영역에 6K 작업  10K 영역에 할당 수행 6K의 내부 단편화 발생 7K 작업  10K 영역에 할당 가능 P1 P3 P4 7K P2 3K 6K 10 K 1 K 4 K 3 K 운영체제 8 K 작업 큐 4K 내부 단편화

27 연속 메모리 할당 02 고정분할 다중 프로그래밍에서의 단편화 - 계속
 고정분할 다중 프로그래밍에서의 단편화 - 계속 ● 단편화 : 작업 스케줄러와 분할의 크기에 의해서 좌우된다. 이러한 제한은 메모리 낭비를 가져오기 때문에 어느 분할에서도 실행 가능한 재배치 가능 프로그램을 만들 수 있도록 구성할 수 있다. ● 고정 분할 - 메모리의 효율적인 운영이 되나, 기억 장소의  낭비를 해결하지 못함 ● 프로세스가 동시에 메모리에 상주해야 하므로 메모리의 보호가 필요 함 ● 해결 방법 : 분할된 영역 보호하기 위해 기준 레지스터와 한계 레지스터사용 해결 기준 레지스터 한계 레지스터 고정 분할에서의 메모리 보호

28 연속 메모리 할당 02 (4) 가변 분할 다중프로그래밍
(4) 가변 분할 다중프로그래밍 ■ 가변 분할은 작업이 필요한 만큼의 메모리 차지하며  단편화 개선 가능하다고 생각하고 고정된 경계 제거를 없애는 방법이다. -> 가변분할(MVT; Multiprogramming with a Variable number of Tasks) 다중프로그래밍이라 함.   ■ 가변분할 할당 : 운영체제는 메모리의 어떤 부분이 사용될 수 있고, 어떤 부분이 사용 중인가를 알 수 있는 테이블 유지 정보가 필요함. [예] 256K - 메모리 40K - 운영 체제 [그림7-17] 메모리와 작업 큐

29 연속 메모리 할당 02 가변 분할 다중프로그래밍 - 계속
 가변 분할 다중프로그래밍 - 계속 ▶ 작업(job)1, 작업2, 작업3에 메모리 할당 - [그림(a)] ▶ 작업2는 5 시간단위 후 끝나게 되어 사용 중이던 메모리 할당량 해제[그림 (b)] ▶ 작업4가 스케줄 되어 할당[그림 (c)] ▶ 작업1은 10 시간단위 후 끝나게 되어 사용 중이던 메모리 할당량 해제[그림 (d)] ▶ 작업5가 스케줄 되어 할당[그림 (e)] [그림7-18] 메모리 할당과 스케줄

30 연속 메모리 할당 02 가변 분할 다중프로그래밍 - 계속 [예]에서 ▶ 여러 크기를 갖는 사용가능 공간이 메모리에 흩어져 있음
 가변 분할 다중프로그래밍 - 계속 [예]에서 ▶ 여러 크기를 갖는 사용가능 공간이 메모리에 흩어져 있음  작업 큐에서 선택된 프로세스에 충분한 공간 영역을 찾음 ▶ 새로운 공간 블록이 다른 공간 블록과 인접 - 두 개의 블록 합침 ▶ 공간이 크면 두 개의 공간으로 나눔 (나머지 공간 남겨둠)  ⇒ 이와 같이 가변 분할(동적 메모리 할당) 문제는 사용가능 공간으로부터 요구된 크기 (n)를 어떻게 만족시켜 줄 수 있느냐 하는 것이다. ◆ 사용가능 공간에 대한 작업(프로세스) 할당 기법 : 기억 장치 배치 전략 ① 최초 적합(first-fit) ② 최상 적합(best-fit) ③ 최악 적합(worst-fit)

31 연속 메모리 할당 02 (5) 메모리 배치 기법 1) 최초 적합 기법
(5) 메모리 배치 기법 - 최상 적합, 최악 적합 : 리스트 정렬 필요(크기 순서) - 최상 적합 : 가장 작은 또 다른 사용 가능공간 생성 - 최악 적합 : 가장 큰 또 다른 사용 가능공간 생성 1) 최초 적합 기법    - 사용 가능 공간 리스트에서 큰 첫 번째 공백 분할 공간에 할당 ▶ 검색 : 사용가능 공간 집합의 시작에서 또는 이전의 최초 적합 검색이 끝났던 곳에서 시작 ▶ 특징 : 빠를 수 있지만 공간 활용율이 떨어질 수 있음 최초 적합 기법

32 연속 메모리 할당 02 메모리 배치 기법 - 계속 2) 최상 적합 기법 - 사용가능 공간 중 가장 작은 크기의 사용 공간 할당
 메모리 배치 기법 - 계속 2) 최상 적합 기법     - 사용가능 공간 중 가장 작은 크기의 사용 공간 할당 ▶ 검색 - 리스트 크기 순서로 정렬 필요, 아니면 전 리스트 검색 ▶ 특징 사용가능 공간에 대한 지속적인 정렬과정 필요 함 부담되어 비효율적 수 도 있음 사용가능 공간 이용율은 향상될 수 있으나 할당 과정에서 더 많은 시간 소요될 수 있음 최상 적합 기법

33 연속 메모리 할당 02 메모리 배치 기법 - 계속 3) 최악 적합 기법 - 가장 큰 사용가능 공간에 할당
 메모리 배치 기법 - 계속 3) 최악 적합 기법     - 가장 큰 사용가능 공간에 할당 ▶ 검색 : 리스트가 크기 순서로 되어 있지 않으면 전 리스트 검색 최악 적합 기법 ▶ 특징 : 사용가능 공간에 대한 지속적인 정렬과정 필요  부담되어 비효율적 가장 큰 사용가능 공간에 할당 최상 적합 경우 작은 사용가능 공간 생성 또는 다른 사용 가능공간을 만들어 내는 것보다 더 유용 함 ▶[모의실험 결과] - 최초 적합과 최상 적합 : 메모리 이용률을 감소 ->최악 적합보다 더 좋음 - 메모리 이용에 있어 최초 적합이 일반적으로 더 빠름

34 연속 메모리 할당 02 (6) 가변 분할에서의 메모리 보호
■ 메모리 보호가 필요 - 상한 값과 하한 값을 갖는 경계 레지스터사용 제공  [예] 프로세스  하한 값: , 크기: 프로세스의 상한 값은 ( ) - 사용자 주소 범위 : 하한 값과 상한 값 사이 하한 값 레지스터 상한 값 레지스터 주소 yes ≥ < 메모리 프로세서 no [그림7-22] 두 개의 레지스터로 표시한 사용자 주소 범위

35 연속 메모리 할당 02 가변 분할에서의 메모리 보호 ■ 기준 및 한계 레지스터 - 수행 시간에 동적 재배치 허용
 가변 분할에서의 메모리 보호 ■ 기준 및 한계 레지스터 - 수행 시간에 동적 재배치 허용 - 기준 레지스터(물리적 주소): , 한계 레지스터(논리적 주소): 사용자 주소 범위 : 0에서 범위 - 논리주소 < 한계 레지스터 : 기준 레지스터에 추가하여 동적 재배치 ∼ 범위 내에서 동적으로 재배치 기준 기준 + 한계 주소 프로세서 메모리 트랩 : 주소 지정 오류 [그림7-23] 기준 및 한계 레지스터를 이용한 보호

36 연속 메모리 할당 02 (7) 외부 단편화 ■ 가변 분할 알고리즘 - 외부 단편화 문제 발생
사용가능 기억공간 : 일부 적재,  나머지 공간은 작은 조각으로 나누어짐 프로세스들이 연속된 메모리 차지하는 과정에서 각각의 공백 발생됨 많은 수의 작은 사용가능 공간으로 단편화 됨 공백 크기가 작아짐 - 다른 사용자를 위해서 메모리 할당 못함 ⇒ 외부 단편화 : 가변분할 다중 프로그래밍에서도 발생 [그림 (a)] : 26K의 외부 단편화 존재 ⇒ 작업 4 와 작업 5를  적재 못함 [그림 (c)] : 56K(=30K + 26K)의 외부 단편화 ⇒ 이 공간은 2개의 조각으로 나누어짐 직업 5의 메모리 요구를 만족시킬 수 없음 : 기다려야 함 [그림7-18] 외부 단편화

37 연속 메모리 할당 02 외부 단편화 - 계속 외부 단편화 : 최초적합, 최상적합의 선택은 결정적 해결책은 아님
 낭비의 해결방안 : 통합과 압축방법  ▶ 공백의 통합 과정 - 하나의 공백으로 합하는 과정 - 기억장소가 비어있는 다른 기억장소(공백)와 인접되어 있는지 점검 후

38 연속 메모리 할당 02 (8) 압축 (compaction) 메모리 내용 이동 ⇒ 사용가능 메모리를 하나의 큰 블록으로 구성
 [예] 10K, 30K, 26K의 3개의 사용가능 영역이 66K의 하나의 공간으로 통합 ▶ 작업 4와 작업 3 이동  내부 주소들이 재배치되어야 함 ▶ 재배치가 정적이면서 어셈블리나 적재할 때 실행 ⇒ 압축은 수행될 수 없음 ▶ 특징 - 재배치가 동적인 경우만 가능하고 수행 시간에 이루어짐 ▶주소 동적 재배치 ⇒ 기준 레지스터 변화로 새로운 기준 주소 반영

39 연속 메모리 할당 02 압축 (compaction) - 계속
■ 메모리 테이블 관리 유지 - 과부하 발생(조각이 많을 때 더욱 심함) [예] 10,240바이트(빈 공간)에 10,238바이트 작업 배정 : 2 바이트 조각 발생 ⇒ 조각(공간)으로 관리 보다는, 10,240바이트 전부 배정 옳음  압축 알고리즘 - 커다란 기억 장소를 만들어내지만 비용이 많이듬 ▶ 작업3과 작업4  총 600K 이동 ▶ 작업 3을 작업 4 밑으로 이동  200K만 이동 ▶450K를 요구하는 작업 경우  작업2를 다른 위치로 이동 : 요구 만족 [그림7-26] 압축 과정의 여러 방법

40 연속 메모리 할당 02 압축 (compaction) - 계속 ■ 압축 방법에 따라 비용에 차이 - 최적의 압축 정책 선택
[장점] 작은 공백들을 하나의 큰 공백으로 변환 ⇒ 새로운 작업에 할당 [단점] - 압축하는 동안 시스템 정지 대화형 사용자 : 응답시간이 일정하지 않음 실시간 시스템 : 심각한 문제로 대두될 수 있음 - 메모리에 있는 작업들이 이동하므로 프로그램 적재 시 제거되는 재배치관련 정보를 액세스 가능한 형태 보관해야 함 - 자주 압축 작업이 요구되어 시스템 자원의 소모가 큼

41 연속 메모리 할당 02 (9) 버디 시스템 ■ 단편화란? 자원이 연속된 단위로 존재하는 것이 아니라 부분적으로 나뉘어 흩어져 있는 상태 발생장소: 메모리와 디스크에서 고정되지 않은 자원 배분(할당) 과정에서 발생 정의 : 메모리를 배당(회수)하는 과정에서 사용하지 않는 자원이 흩어져 사용(배정)이 불가능한 상태 해결 방법 : 버디 시스템(buddy system) 알고리즘 ■ 버디(짝) 시스템 : 둘씩 짝 짓는 방법 큰 버퍼들을 반복적으로 이등분하여 작은 버퍼들을 만들며 가능할 때마다 인접한 자유로운(free) 버퍼들을 합치는 과정을 반복 하는 기법 버디 : 버퍼(블록)가 나누어 질 때 각각을 서로 버디라고 함 자유 블록의 리스트 배열 유지 리스트에 있는 모든 블록은 같은 크기 배열은 크기로 인덱스(목록) 됨 ■ 내부 단편화 해결 방법 : 다양한 블록크기 활용

42 연속 메모리 할당 02 버디 시스템 - 계속 ■ 메모리 블록(K)의 범위 : L≤K≤U
L : 할당 가능한 가장 작은 블록, U : 가장 큰 블록(전체 메모리) 블록 : 전체가 할당 되지 않으면 2U-1의 크기를 갖는 2개의 버디로 나누어짐, 예) 전체 메모리 64K(26 ) 이면, 2U-1의 크기는 32K(26-1)이다. 크기가 b인 빈 버디 블록 쌍  크기가 2b인 큰 블록 하나로 만듬    ※ 64KB의 초기 블록 사용 예.  ① 첫 번 째 8KB 요청  먼저 블록을 두 개의 버디로 쪼갠다(b)  각 블록의 크기는 32KB ▶ 다시 블록을 두 개의 버디로 쪼갠다(c, d)  블록의 크기는 8KB이므로 요청에 할당 2 32 16 8 4 32 2 4 16 16 32 8 16 8

43 연속 메모리 할당 02 버디 시스템 - 계속 ② 두 번째 요청도 8KB라면 바로 할당 가능(e)
③ 세 번째 요청이 4KB : 다시 블록을 두 개의 버디로 나누어(f) 요청에 할당(g) ④ 두 번째로 요청한 8KB가 해제되고(h), 첫 번째 요청한 8KB가 해제되면서 통합(i) 2 32 16 8 4 ■ 버디 시스템 ⇒ 고정 분할이나 동적 분할의 단점 해결 방법 ■ UNIX의 커널 메모리 할당 또는 병렬처리 시스템에서 응용 ■ 최근의 운영체제 ⇒ 페이징이나 세그먼테이션을 활용한 가상메모리 기법 선호

44 분산 메모리 할당 03 ■ 연속 메모리 할당 - 고정 분할이나 동적 분할 기법은 메모리 활용에 그다지 효과적인 방법이 아님 내부 또는 외부 단편화 발생에 해결 방법 제시하지 못함 ■ 내부 단편화 해결방법으로 제안된 압축 : 프로세서 시간 낭비, 비용 부담 큼 압축 과정에서 제기된 동적 재배치 기능 : 외부 단편화 해결,내부 단편화 최소화하는 ⇒ 분산 메모리 할당 기법이 제안 됨 ■ 분산 메모리 할당 기법 - 페이징 기법, 세그먼트 기법, 요구 페이징 기법

45 분산 메모리 할당 03 페이징 기법 ◆ 처리할 작업을 동일한 크기의 페이지로 나누어 처리하는 개념
◆ 처리할 작업을 동일한 크기의 페이지로 나누어 처리하는 개념 ▶ 페이지 – 메인 메모리의 블록, 디스크의 블록(섹터)의 크기와 동일한 크기로 정함. ▶ 실제 메모리를 프레임(페이지 프레임)이라는 고정 크기 블록 나누고 프로세스도 페이지라 불리는 동일(고정된) 크기의 영역으로 분할 ▶ 페이지이라 불리는 프로세스의 영역들이 프레임이라 불리는 메모리의 영역에 할당됨 ▶ 논리 메모리도 페이지라 불리는 같은 크기의 블록으로 나누어지며 보조기억 장치도 프레임 같은 크기로 구성된 크기의 블록으로 나누어짐 논리적 주소 논리적 주소 공간 물리적 주소 물리적 주소 공간 [그림7-29] 논리와 물리적 메모리의 페이징 모델

46 분산 메모리 할당 03 페이징 기법 ① 프로세스 수행 보조기억 장치  이용 가능한 프레임 안으로 적재 ⇒ 효율적인 동작이 이루어짐 ② 메모리 시스템 작업(프로그램) 수행 시 준비 사항   - 프로그램에 소요되는 페이지 결정 ⇒ 페이지 번호 부여   - 프로그램 적재하도록 메모리의 빈 프레임 조사 ⇒ 위치 파악   - 프로그램 페이지를 빈 페이지 프레임에 적재 ⇒ 준비 ③ 페이징 기법의 장, 단점 - 메모리 효율적 사용  빈 페이지 프레임이 프로세스의 어떤 페이지에도 사용 가능 - 페이지 프레임들간에 외부 단편화도 발생하지 않음 - 페이지가 메모리의 여러 위치에 분산 적재  페이지들의 위치 정보(페이지 관리가 복잡): 운영체제의 부담이 커짐

47 분산 메모리 할당 03 페이징 기법 - 계속 ■ 페이징 기법 - 내부 단편화 발생(프레임 단위로 할당되기 때문) [예]
■ 페이징 기법 - 내부 단편화 발생(프레임 단위로 할당되기 때문) [예] 조건1 : 페이지 = 2048바이트 조건2 : 72,766바이트의 프로세스가 존재 함 → (72,766/2048) = 35페이지와 1086바이트 필요 함 ▶ 36개 프레임 할당  ( )=962 바이트의 내부 단편화 발생 ▶ 최악의 경우 : n페이지와 1워드만 필요(n+1개의 프레임 할당) ▶ 프로세스의 크기가 페이지의 크기와 독립적  평균 반 페이지의 내부 단편화 예상 ▶ 내부 단편화 현상 고려 - 작은 페이지 크기가 바람직함. ⇒ 페이지 테이블 유지에 부담(overhead)이 큼 : 페이지 크기 증가시켜 감소 할 수 있음

48 분산 메모리 할당 03 페이징 시스템 하드웨어 프로세서 생성 주소(논리 주소) : 페이지 번호(p)와 변위(d)
페이지 번호 : 페이지 테이블 색인(메모리에서의 각 페이지의 기준주소(f) 유지) 변위: 상대주소(페이지 시작위치로부터 프레임내 위치 표시) 실제 메모리 주소 = 기준 주소 + 페이지 변위 페이지 맵 테이블(PMT;Page Map Table) : 페이지에 대한 정보 유지 [예] 페이지 번호와 이에 대응되는 페이지 프레임 주소 ⇒ 레지스터로 구성되거나 메인메모리의 일부로 배정 프로세서 페이징 시스템 하드웨어 물리적 메모리 페이지 테이블

49 분산 메모리 할당 03 페이징 시스템 하드웨어 - 계속 페이지 테이블과 페이징 모델
논리 페이지는 페이지 테이블에서 해당 페이지의 프레임 번호를 확인하여 실제 물리 메모리의 페이지 프레임을 찾음.

50 분산 메모리 할당 03 페이지 번지 페이지(프레임) 크기 - 하드웨어에 의해 정의
페이지 : 512워드 ∼2048워드 ( 2의 누승으로 증가) 논리 주소를 페이지 번호와 페이지 변위의 변환이 쉽게 하기 위함 페이지 : 2n주소 길이 표시  하위 n 비트는 페이지 변위, 나머지 상위 비트는 페이지 번호 표시 [예] IBM 비트에서 0∼7(8 비트) 비트는 미사용 페이지 크기가 4K(4096)인 경우 페이지 번호는 8∼19(12 비트) 비트 페이지내 변위(offset) : 20∼31(12 비트) 비트 [예] 페이지 크기 라인 325 라인의 프로그램  4페이지 필요 페이지번호와 변위 : 4 페이지의 위에서 번째 라인(24라인)에 위치 페이지 번지

51 분산 메모리 할당 03 페이지 번지 [예]16비트 논리주소 이용 4K 페이지 갖는 시스템의 메모리 주소 변환과정
논리주소 : 8196( ) 변위 : 12 비트 페이지 번호 : 4비트 프로그램 : 4K 크기 페이지 16(24)개 구성 페이지 번호  페이지 테이블의 물리적 주소 : 110 변위 : 실제 메모리 주소 ⇒ 24580 논리 주소에서 물리 주소로 변환 과정

52 분산 메모리 할당 03 페이지 번지 [예]16비트 논리주소를 이용하여 4K 페이지 갖는 시스템의 메모리 주소 변환과정
출력 : 메모리 주소 24580 [예]16비트 논리주소를 이용하여 4K 페이지 갖는 시스템의 메모리 주소 변환과정 논리주소 : 8196( ) 변위 : 12 비트 페이지 번호 : 4비트 프로그램 : 4K 크기 페이지 16(24)개 구성 페이지 번호  페이지 테이블의 물리적 주소 : 110 변위 : 실제 메모리 주소 ⇒ 24580 페이지 테이블 12비트 변위 입력에서 출력으로 직접 복사 사용/미사용 비트 2n 페이지 테이블 색인 입력 : 논리적 주소 8196

53 분산 메모리 할당 03 페이지 번지 [예] 메모리의 사용자 관점 논리주소  물리주소 사상과정
[예] 메모리의 사용자 관점 논리주소  물리주소 사상과정 논리 주소 0 : 페이지 0, 변위 0 페이지 테이블 색인 : 페이지 0  프레임 5 확인 논리 주소 0 ⇒ 메모리 주소 20(=5×4+0)으로 사상 논리 주소 3(페이지 0, 변위 3) ⇒ 메모리 주소 23(=5×4+3)으로 사상 논리 주소 4 ⇒ 페이지1, 변위 0 페이지 1⇒ 프레임 6, 메모리 주소 24(=6×4+0)로 사상 논리 주소 13⇒ 메모리 주소 9로 사상 워드 페이지를 이용한 메모리 페이징

54 분산 메모리 할당 03 다중 계층 페이징 - 교재 328페이지 참조
다중 계층 페이징 - 교재 328페이지 참조 페이징 - 동적 재배치의 형태 논리 주소 : 실제 주소로 사상 메모리의 각 프레임에 대한 기준 레지스터 테이블을 사용하는 것과 유사 예) 논리주소 : 2차 수준 페이지 테이블 구성 F1 1 2 3

55 분산 메모리 할당 03 페이지 스케줄링 프로세스 수행 조건 → 프로세스의 크기는 페이지 단위 표현
장기 스케줄러 : 빈 페이지 프레임 리스트 유지, 이용할 수 있는 상태로 준비 - n개 페이지 요구  이용할 수 있는 n개의 빈 프레임이 있어야 함 - n개의 프레임 사용 가능 : 해당 프로세스에 할당 [할당과정] - 프로세스의 최초 페이지는  할당된 프레임들 중 하나에 적재하고, 프레임 번호는 프로세스를 위한 페이지 테이블 속에 기록 한다. - 그 다음 페이지는  또 다른 프레임에 적재, 프레임 번호가 페이지 테이블 속에 기록한다.

56 분산 메모리 할당 03 페이지 스케줄링 사용가능 프레임 리스트에서 해당되는 프레임을 새로운 작업에 할당 과정
새로운 프로세스 새로운 프로세스 새로운 프로세스 페이지 테이블 사용가능 프레임의 할당 전(a)과 후(b)

57 분산 메모리 할당 03 페이지 테이블의 구현 페이지 테이블의 가장 간단한 하드웨어 구성 - 전용 레지스터 사용 구현함
■ 레지스터 : - 초고속 논리 회로로 설계 이유  페이징 주소 변환을 매우 효율적으로 하기 위함 ■ 메모리의 접근 - 페이징 테이블 정보에 의해 수행되므로 -효율이 주요 고려 대상임 ■ 페이지 테이블 구현을 위해 레지스터를 사용하는 경우 - 페이지 테이블이 적으면(예 ; 256항목 정도) : 만족(하드웨어 비용감소) - 페이지 테이블이 큰 경우(예 ; 수백만 개 항목) : 레지스터 구현 부적합 ※ 따라서 페이지 테이블을 메모리에 유지하고 페이지 테이블 기준 레지스터 (PTBR;Page Table Base Register)가  페이지 테이블을 지시하도록 한다. [결과] 이 방법은 하나의 레지스터 변화로 페이지 테이블이 변경되므로 실제적인 문맥 교환 시간의 감소를 가져옴, 하나 메모리의 접근시간이 문제가 됨

58 분산 메모리 할당 03 페이지 테이블의 구현 [예] 임의의 주소(i)에 접근과정
 i에 대한 페이지 번호와 PTRB 변위 값을 사용하여 페이지 테이블로 색인 - 메모리 접근 요구하고 실제 주소를 산출하는 페이지 변위와 결합된 프레임 번호 제공 [문제점] - 두 번의 메모리 접근 - 속도가 느려짐 페이지 테이블 항목 접근, 워드를 위한 접근 [해결] 연관 레지스터 또는 변환 우선참조 버퍼(TLBS;Translation Look-aside Buffers) 이용 ■ 사상 방법에 따라 `1. 직접사상(direct mapping)에 의한 페이지 주소변환  2. 연관사상(associative mapping)에 의한 페이지 주소변환 3. 연관/직접 사상을 결합한 페이지 주소변환

59 분산 메모리 할당 03 페이지 테이블의 구현 - 계속 1) 직접사상에 의한 페이지 주소 변환
1) 직접사상에 의한 페이지 주소 변환 페이지 사상표 - 메인메모리 혹은 캐시메모리에 유지 가상주소 V =(p, d) ■ 시스템은 가상주소에 대응하는 메인 메모리 주소를 얻기 위해 – 페이지테이블 시작주소 b를 참조 페이지 번호 p(페이지테이블 색인 역할) 더하여(+) 페이지테이블(b) 내의 색인 p에 관한 메모리주소 p′를 얻는다. 이 항목은 페이지 프레임 p′가 가상페이지(페이지번호) p 에 대응하는 것을 가리킨다. - p'는 변위 d와 접속되어 메모리주소 r = p' + d 직접 사상에 위치한 페이지 주소 변환

60 분산 메모리 할당 03 페이지 테이블의 구현 - 계속 - 페이지 테이블에 레지스터를 사용하는 것보다 메인 메모리에 작성하여 페이지 테이블 기준레지스터가 페이지 테이블을 지정하는 것이 바람직함 이유 : 페이지 테이블의 변경은 레지스터 변화로 가능함 ■ 직접 사상 페이지 주소변환 문제점 - 사용자 메모리 위치에 액세스하는데 소요되는 시간이다.(2번 접근) 예) 주소 p에 접근 시 먼저 p에 대한 페이지번호의 페이지테이블 기준 레지스터 변위 값을 사용하여 페이지 테이블을 색인해야 한다. - 하나의 워드에 접근 시 페이지테이블 한번 접근 - 워드를 위해 다시 접근 결론 : 메모리 접근이 2배로 느려짐 해결방법 : 연관 레지스터 또는 보조 예비 기억장치 사용(특별히 작은 하드웨어 메모리)

61 분산 메모리 할당 03 페이지 테이블의 구현 - 계속 2) 연관사상에 의한 페이지 주소변환
2) 연관사상에 의한 페이지 주소변환 ■ 프로세서에 의해 생성된 논리주소는  프로세서 페이지 번호와 프로세서에 대응되는 프레임 번호를 가지고 있는  연관 레지스터의 집합으로 표현 ※ 레지스터 = 키와 값으로 구성 ※ 연관 레지스터 : 몇 개의 페이지 테이블 항목만을 가짐 ■ 연관 레지스터에 어떤 항목이 표현되면  동시에 모든 키와 비교 한다.  항목 발견되면  대응하는 값 부분이 출력 ■ 장점은 탐색은 빠르나 단점으로 하드웨어가 비쌈 ■ 페이지 번호가 연관 레지스터를 찾으면 연간 레지스터 프레임 번호는 곧바로 이용할 수 있고 메모리에 접근하기 위해 사용된다.

62 분산 메모리 할당 03 페이지 테이블의 구현 - 계속 [예] 페이지 p 검색 : 가상주소 V=(p, d)
- 연관 메모리의 모든 항목을 동시에 조사한다. 그 결과 페이지 p에 해당되는 페이지 프레임 p' 발견되면 d와 접속하여 메모리 주소를 형성한다.  메모리주소 (r) = p' + d  연관사상표로 향하는 화살표 : 모든 단위 항목을 동시 조사 의미 연관메모리를 비싸게 만드는 원인 메모리 주소 순수 연관사상을 통한 페이지 주소 변환

63 분산 메모리 할당 03 페이지 테이블의 구현 - 계속 3) 연관/직접 사상을 통한 페이지 주소 변환
3) 연관/직접 사상을 통한 페이지 주소 변환 - 때로는 연관/직접 사상을 사용하는데, 최근 페이지만 연관메모리에 유지하고 연관메모리에 없을 때는 직접사상 방법을 제안 결론 : 지역성을 이용하여 최근에 참조된 페이지는 곧 다시 사용된다는 것을 적절하게 이용함   [예]  페이지 p 검색 - 연관 메모리의 항목 동시 조사 결과 페이지 p에 해당되는 페이지 프레임 p' 발견 되면 d와 접속하여 메모리주소 r = p' + d 을 얻음 - 만약 p 와 일치하는 항목이 연관사상표에 없으면 논리주소의 페이지번호(p)를 페이지 기준 레지스터의 b와 합하여 p+b의 직접 페이지 테이블 p 에 대응하는 페이지 프레임 p' 얻는다 메모리 주소 r = p'+d 생성

64 분산 메모리 할당 03 페이지 테이블의 구현 - 계속

65 분산 메모리 할당 03 페이지 테이블의 구현 - 계속 적중율 (hit ratio)
페이지 번호가 연관 레지스터에서 발견되는 비율(레지스터 수와 관계 있음) [예] 적중율 : 80 %란 연관 레지스터에서 원하는 페이지 번호를 발견할 확률이 80%라는 것을 의미함 예) 연관 레지스터 탐색 시간 : 50ns(nano seconds) 소요되고, 메모리 접근 시간 : 750ns 인 경우  연관 레지스터에 있을 때 ⇒ 800ns(50+750) 소요  찾지 못하면 ⇒ 1550ns 소요 (연관=50, 페이지 프레임과 프레임번호=750, 메모리 워드 접근=750ns) ※ 유효 접근 시간 = (0.80×800)+(0.20×1550 )= 950ns 메모리 접근 시간 : 26.6%가 늦어짐(750ns  950ns) = 950/750=  90% 적중율 예) 유효 접근 시간 =(0.90×800)+(0.10×1550) = 875ns 메모리 접근 : 16.6%로 감소

66 분산 메모리 할당 03 공유페이지 페이징 시스템 장점 : 시분할  환경에서 공통된 코드 공유 [예] 40명의 사용자가 문장 편집기를 수행 문장 편집기 - 150K, 자료 공간 -50K ⇒ 8000K 필요 P1을 위한 페이지 테이블 프로세스 재진입 가능 코드 경우 - 공유 가능 - 공유 페이지 (ed1, ed2, ed3) P2을 위한 페이지 테이블 프로세스 P3을 위한 페이지 테이블 프로세스 페이징에서의 공유코드

67 분산 메모리 할당 03 공유페이지 재진입 코드(pure code) - 스스로 수정하지 못하는 코드 - 수행 도중 변하지 않음
- 스스로 수정하지 못하는 코드 - 수행 도중 변하지 않음 - 2개 이상의 프로세스가 동시에 같은 코드 수행 가능 - 프로세스 : 자료가 있는 저장 장소 및 레지스터의 복사본 가짐 [예] 편집기(ed1, ed2, ed3) : 하나의 복사본이 실제 메모리에 유지 복사본이 각 사용자의 페이지 테이블에 사상 자료 페이지는 다른 프레임으로 사상 40명의 사용자 지원 ⇒ 하나의 편집기 복사(150K) 사용자를 위한 50K의 자료 공간(복사본 40개) 총 공간 : 2150K (4050K  150K)  자주 사용되는 프로그램 공유 필요 - 재진입 코드 컴파일러, 윈도우 시스템, 데이터베이스 시스템 등  공유된 코드의 읽기 전용(read-only) 성질은 코드의 정확성보다는 운영 체제가 이런 속성을 강화해야 함

68 분산 메모리 할당 03 보호 페이지 테이블 : 보호용 비트 설정 ⇒ 타당/비타당 여부 확인
페이지 테이블의 1개의 보호용 비트에 의해 수행 - 페이지와 연관 1 비트 : 페이지 읽기/쓰기, 읽기 전용(read-only) 정의  메모리 접근 페이지 테이블 실행 → 프레임 번호를 찾고, 동시에 메모리 주소 계산  보호용 비트 - 수행되지 않음을 검증하기 위해 점검 읽기 전용 페이지  기록 접근 ⇒ 하드웨어 트랩 (메모리 보호 위반) 프레임 번호 타당/비타당 비트 페이지 테이블 페이지 테이블 : 보호용 비트 설정 ⇒ 타당/비타당 여부 확인 [그림 7-41] 페이징 테이블의 접근 허용/비허용

69 분산 메모리 할당 03 보호 - 계속 [예] 14 비트의 번지 영역 시스템 - 0∼16383의 주소 영역 사용
14 비트의 번지 영역 시스템 - 0∼16383의 주소 영역 사용 0 ∼ 주소를 필요로 하는 프로세스 경우 2K 크기의 페이지이면 5 페이지(0∼4)  정상적으로 사상 페이지 6, 7인 경우  ‘비타당’으로 분류하여 운영체제로 트랩 이유: 10468번지로 제한되므로 나머지 영역에 대한 참조는 불법적 [과정] 주소가 10468까지 확장되어야 하므로(4 페이지 크기: 10239) 페이지 5 : 12287까지 합법적처리(‘타당’ 분류) 나머지 (12268 ∼ 16383) 영역 : ‘비타당’ 분류 내부 단편화 발생 : 약 2K(= )

70 분산 메모리 할당 03 페이징에 대한 견해 사용자의 메모리에 대한 관점과 메모리 분리
 사용자 프로그램 메모리 - 연속적인 공간 ⇒ 실제 메모리(physical memory)에 분산  메모리의 사용자 관점과 실제 메모리 사이의 차이점 ⇒ 주소 변환 하드웨어에 의해 논리 주소를 실제 주소로 변환 조정 [장점] 공유 페이지 이용 외부 단편화 제거(내부 단편화는 발생) 메모리 활용 - 다중 처리 프로그래밍 실현 압축 기능 제거 [문제점] 페이징 사상을 위한 하드웨어 준비 - 가격 상승과 속도 저하 내부단편화 현상

71 세그먼트 메모리 관리 기법 04 세그먼트 메모리 기법 - 메모리의 사용자 관점을 지원하는 기법
메모리 : ‘세그먼트’ 단위 모임(크기 변함) 페이징 : 고정크기 세그먼트 : 연관된 기능을 수행하는 하나의 모듈 프로그램 서브루틴, 프로시저(procedure), 함수(function), 모듈(module) 등

72 세그먼트 메모리 관리 기법 04 세그먼트 메모리 할당 논리 구조 공간 - 세그먼트의 모임
세그먼트 - 컴파일러(어셈블러)가 입력 프로그램(원시 프로그램)을 이용 작성 경영, 하드웨어 보호 - 페이징과 비슷하거나 동일 [차이] 세그먼트 크기가 다르기 때문에 메모리가 페이지 프레임으로 나누어지지 않고 동적 분할(가변 분할)기법으로 메모리 할당  Intel 8086 : 세그먼테이션 메모리 관리 기법 지원 프로그램 : 코드(code), 데이터(data), 스택(stack) 세그먼트로 분리 사용자 공간 실제 메모리 공간 [그림7-43] 세그먼트의 논리적 관점

73 세그먼트 메모리 관리 기법 04 하드웨어 세그먼트의 논리 주소 : 세그먼트 번호 S와 변위(offset) d로 구성
메모리 - 일련의 1차원적 단어 사용자가 정의한 2차원 주소(S, d)  1차원적 실제 주소로 사상 사상 - 세그먼트 테이블에 의해 이루어짐 세그먼트 테이블 프로세서 세그먼트 트랩 : 주소 오류 [그림7-44] 세그먼트 하드웨어 메인 메모리

74 세그먼트 메모리 관리 기법 04 하드웨어 - 계속 세그먼트 번호 (S) : 세그먼트 사상 테이블에 대한 색인으로 사용
세그먼트 테이블 항목 : 세그먼트의 기준(base)과 한계(limit) 가짐 논리 주소 변위 (d) : 0과 세그먼트 한계 사이의 값 아니면  운영 체제 합당  세그먼트 기준 + 변위 (메모리 주소 생성) 세그먼트 테이블 : 기준/한계 레지스터의 배열 [예] 세그먼트 5개 : 0에서 4까지 번호가 정해짐 세그먼트 : 메인메모리에 저장 세그먼트 테이블 : 메모리 주소의 시작과 그 세그먼트의 끝 표시의 항목 유지

75 세그먼트 메모리 관리 기법 04 하드웨어 - 계속 세그먼트 0 limit
스택 심볼 테이블 메인 프로그램 함수 Sqrt 서브루틴 논리 주소공간 세그먼트 0 세그먼트 1 세그먼트 3 세그먼트 2 세그먼트 4 세그먼트 0 limit 세그먼트 2  400바이트 길이 번지에서 시작 세그먼트 3 세그먼트 2 세그먼트 4 세그먼트 1 메인메모리 세그먼트 2, 워드 53 접근  = 4353의 번지로 사상 세그먼트 3, 워드 852 접근  = 4052으로 사상 세그먼트 0, 워드 1222에 대한 참조 세그먼트가 1000 바이트의 길이로 (초과됨) 운영체제로 넘어감 세그먼테이션의 예

76 세그먼트 메모리 관리 기법 04 하드웨어 - 계속 세그먼트 2 ⇒ 400바이트 길이 4300번지에서 시작
세그먼트 2 ⇒ 400바이트 길이 4300번지에서 시작 세그먼트 2, 워드 53 접근  = 4353의 번지로 사상 세그먼트 3, 워드 852 접근  = 4052으로 사상 세그먼트 0, 워드 1222에 대한 참조 세그먼트가 1000 바이트의 길이로 (초과됨) 운영체제로 넘어감 [그림7-45] 세그먼테이션의 예

77 세그먼트 메모리 관리 기법 04 세그먼트 번지와 세그먼트 테이블 구현 세그먼트 번호 : 28 (256개의 세그먼트)
 IBM 370에서 구성한 세그먼트 번지 예 세그먼트 번호 : 28 (256개의 세그먼트) 세그먼트 크기 : 216 (64K) 프로세스 : 세그먼트 테이블 유지(메인메모리에 적재) 세그먼트 테이블 엔트리 : 세그먼트가 적재될 메인메모리의 시작 주소와 세그먼트의 길이도 알려줌 세그먼트 테이블 : 메인메모리에 유지 길이가 가변적(레지스터에 정보 유지 어려움)

78 세그먼트 메모리 관리 기법 04 세그먼트 번지와 세그먼트 테이블 구현
STBR(Segment-Table Base Register) → 메모리에 있는 세그먼트 테이블의 주소(위치) 표시 STLR(Segment-Table Length Register) → 사용되는 세그먼트 수 세그먼트 논리주소(S, d) : 세그먼트 번호의 유효성(S < STLR) 점검 → 세그먼트 번호와 STBR을 이용하여 실제 메모리의 주소(STBR + S) 산출 길이 시작주소 세그먼트 시스템에서의 주소 변환 과정 STBR + 세그먼트 테이블 프로세서 d 트랩 : 주소 오류 메인 메모리

79 세그먼트 메모리 관리 기법 04 세그먼트 공유 단순 - 선언 즉 정의가 되면 이루어짐
두 개 이상의 다른 프로세스의 세그먼트 테이블 속에 있는 항목들이 같은 메모리 주소를 가르키면 공유 [예] 문서 편집기 공유 과정 세그먼트(43062)지정 해당 세그먼트를 공유 세그먼테이션에서의 세그먼트 공유

80 세그먼트 메모리 관리 기법 04 단편화 메모리 할당 상황 - 페이징과 비슷 가변 크기 분할 기법
동적 메모리 할당 - 최상 적격 알고리즘, 최소 적격 알고리즘 사용 하여 해결되는 방법이 이용된다. 외부 단편화 발생 사용 가능 메모리의 블록 : 작아서 세그먼트를 수용할 수 없을 경우 발생 단순히 기다리거나 압축 : 더 큰 공간 생성 세그먼테이션 : 동적 재배치 알고리즘 원할 때마다 메모리 압축 프로세서 큐 - 낮은 우선권을 가진 프로세스 찾음  외부단편화 문제 - 세그먼트의 크기에 의존 평균 세그먼트 크기가 작으면 외부 단편화 작음

81 세그먼트 메모리 관리 기법 04 페이지화된 세그먼트 메모리 할당 페이징 - 내부 단편화 현상 메모리 효율적 사용
동일한 크기 : 다른 많은 알고리즘 개발 가능 세그먼테이션 - 외부 단편화 가변적인 자료 구조와 모듈 처리 공유와 보호의 지원이 편리 세그먼트를 페이징하는 방법 - 장단점을 해결 페이징 기법은 외부 단편화 문제를 제거하면서 할당 과정을 쉽게 해결 결합된 구조는 Multics 시스템에서 사용, Intel 386 계열에서 사용

82 세그먼트 메모리 관리 기법 04 페이지화된 세그먼트 메모리 할당 - 계속 결합된 페이징/세그먼테이션 시스템(Multics)구조
[그림7-49] GE645(Multics)의 세그먼트 페이징 시스템 구조

83 세그먼트 메모리 관리 기법 04 페이지화된 세그먼트 메모리 할당 - 계속
논리주소 : 세그먼트 번호(18비트)와 변위(16 비트) 구성 변위 : 페이지 번호(6비트)와 페이지 변위(10비트)  [그림7-50] Multics 시스템의 세그먼트 논리 주소 페이지 번호 : 프레임 번호 부여(페이지 테이블에 색인화 됨) 사용자의 주소 공간 → 다수의 세그먼트로 나누어지고 각 세그먼트는 페이지로 나누어짐 메모리 주소 : 프레임 번호 + 페이지 변위 세그먼트의 길이 ≤ 페이지 길 → 세그먼트는 한 페이지를 갖게 됨

84 세그먼트 메모리 관리 기법 04 페이지화된 세그먼트 메모리 할당 - 계속 주소 변환 과정
프로세서 : 세그먼트 번호와 STBR 이용 → 세그먼트 테이블 확인 세그먼트를 위한 페이지 테이블 찾음 페이지 번호 이용 → 페이지 테이블을 색인, 해당 페이지 프레임 찾음 메모리 주소 생성(페이지 변위와 결합) [그림7-51] 세그먼트 메모리 주소 생성 과정

85 세그먼트 메모리 관리 기법 04 페이지화된 세그먼트 메모리 할당 - 계속 프로세스 : 하나의 세그먼트 테이블 보유
세그먼트 : 자신의 페이지 테이블 보유 프로세스 실행 중 레지스터가 그 프로세스에 대한  세그먼트 테이블의 시작 주소 유지 세그먼트의 마지막 페이지 - 내부 단편화를 가져올 수 있음 외부 단편화는 제거되지만 내부 단편화는 발생 현상 테이블 공간에 대한 부담 증가 결과 세그먼트 번호(18 비트) - 262,144 개의  세그먼트 지정 큰 세그먼트 테이블 요구 Multics - 세그먼트 테이블도 페이징 주소 : 세그먼트 번호 사용 세그먼트 테이블에서의 페이지 테이블에 색인을 주기 위한 페이지 색인을 지정하기 위함