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

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

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

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

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

메모리 관리 개념 주소 바인딩 프로세스 수행 - 입력 큐를 통하여 메모리로 적재되어야 함 프로세스 : 이진 실행 가능 파일로서 디스크에 존재 절차 : 입력 큐에서 하나의 프로세스를 선택 - 메모리에 적재 주소를 재배치하거나 필요 - 외부 참조를 연결하는 결과 수행 : 프로세스는 메모리의 명령어와 자료에 접근 프로세스 종료 : 사용했던 기억공간  다른 프로세스가 사용 가능 기억공간으로 변함 바인딩(binding) - 논리적 주소(변수)를 물리적 주소로 변환 과정 프로그램에 있어서의 모든 번지를 절대 번지로 바꾸어 메인메모리의 고정된 부분에 적재하는 것 고도의 운영체제 - 바인딩 시간을 늦춤 기억장치 주소공간에서 명령어와 자료의 바인딩 방식에 따라 컴파일 시간(compile time) 적재 시간(load time) 수행 시간(execution time) 으로 구분

메모리 관리 개념 주소 바인딩 - 계속 컴파일 시간(compile time) - 프로세스 적재 위치를 컴파일 과정에서 결정  컴파일러는 물리적 주소(절대주소) 생성 - 메인메모리의 실제 주소로 변환되는 과정 : 절대재배치 [예] - 프로세스가 R 에서 시작 : 컴파일러 코드는 그 위치에서 확장, 시작 위치가 변하면 이 코드를 다시 컴파일 필 요 - MS-DOS의 COM - 컴파일 시간에 바인딩된 절대 코드 적재 시간(load time) - 프로세스 적재 위치 미정  컴파일러는 재배치 가능 상대주소 생성 - 상대주소 - 프로그램의 시작주소를 0 으로 가정 - 최종 바인딩은 적재 시간이 될 때까지 연기 - 시작 주소가 변하면 사용자 코드는 변화값 반영 위해 재적재 : 정적 재배치 수행 시간(execution time) 한 프로그램이 동일한 장소에서 작동 → 적재시간과정에서 바인딩 프로세스 수행 중 세그먼트로부터 다른 세그먼트로 이동 → 바인딩은 수행 시간까지 연기 현대 운영체제 - 수행시간에 바인딩 사용자 프로그램의 처리 단계

메모리 관리 개념 동적 적재 주소 바인딩 시간 늦추어서 실행되기 직전에 주소 확정 → 시스템 운영과 메모리 활용에 도움: 동적 적재 (Dynamic Loading) 사용 호출될 때까지 재배치 가능한 형태로 디스크에 저장 유지되며 주프로그램은 메모리에 적재되어 수행되는 형태 [과정] 주프로그램(호출 루틴)이 다른 루틴의 호출을 필요로 할 때, 호출 루틴은 다른(호출될) 루틴이 적재되었는지를 조사 적재 안됨 : 재배치 가능 연결 적재기는 요구된 루틴을 메모리로 적재하기 위해 호출 이러한 변화 반영 : 테이블 갱신 장점 사용되지 않은 루틴들은 적재되지 않음 오류 루틴 발생하면서도 많은 양의 코드를 필요로 하는 경우 유용 프로그램의 전체 양이 많아도 실제로 사용된 구역(실제 적재된)은 적음 운영체제로부터 특별한 지원 블필요 동적 링크 적재기는 제공되어야 함 사용자 자신이 프로그램의 설계 책임

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

메모리 관리 개념 중첩 - 계속 사용자 프로그램 - 초기 모듈, 처리 모듈, 출력 모듈로 구별 초기 모듈을 적재한 후 실행  처리 모듈 : 출력 모듈을 적재한 후 실행

메모리 관리 개념 중첩 - 계속

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

메모리 관리 개념 중첩 - 계속 운영 체제로부터 특별한 지원을 필요로 하지 않음 [구현] 사용자에 의해 파일들을 메모리로 읽어 들이고 메모리로 이동, 새로운 읽기 명령 수행 : 간단한 파일 구조 사용 프로그래머 중첩 구조를 적절하게 설계하고 프로그램 해야 함 프로그램 구조와 코드 또는 자료 구조 이해 필요 중첩 사용 현재의 마이크로 컴퓨터나 실제 메모리 크기가 제한된 하드웨어에서 사용 현재 메모리를 확장 사용하여 해결

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

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

메모리 관리 개념 교체 - 계속 전체 전송 시간 : 교환되는 메모리의 양에 비례 [예] - 메인메모리 : 1MB - 상주 운영체제 : 100K - 사용자 프로세스의 최대크기 : 900K 900K 교체 : 908 ms 100K 크기를 갖는 프로세스 : 108 ms 900k를 9번에 걸쳐 교환된다면 972 ms 소요 교체 미결정 입출력을 가진 프로세스를 교체하지 말고, 입출력 동작을 운영 체제 버퍼 내에서만 수행 운영 체제와 프로세스 메모리 사이의 전송은 프로세스가 교체되어 들어올 때만 이루어져야 함 교체 작업은 초기 시분할시스템에서 채용되었으나 근래에는 페이지 시스템으로 발전

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

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

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

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

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

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

연속 메모리 할당 02 CPU utilization as a function of number of processes in memory Degree of multiprogramming

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

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

연속 메모리 할당 02 Multiprogramming with Fixed Partitions (a) separate input queues for each partition (b) single input queue

연속 메모리 할당 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로 영역 배정 가능 영역의 크기 결정 - 시스템 전체 효율을 나타내는 요인  영역의 배정  작업을 어느 영역에 배정하는가에 대한 결정 :작업 스케줄러 필요

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

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

연속 메모리 할당 02 고정분할 다중 프로그래밍에서의 단편화 - 계속 단편화 : 작업 스케줄러와 분할의 크기에 의해서 좌우  고정분할 다중 프로그래밍에서의 단편화 - 계속 단편화 : 작업 스케줄러와 분할의 크기에 의해서 좌우 메모리 낭비, 실행 가능한 재배치 가능 프로그램 구성 고정 분할 - 메모리 효율적인 운영 기억 장소의  낭비를 해결하지 못함 프로세스가 동시에 메모리에 상주 :메모리의 보호 필요 분할된 영역 보호 기준 레지스터와 한계 레지스터사용 해결 기준 레지스터 한계 레지스터 고정 분할에서의 메모리 보호

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

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

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

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

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

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

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

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

연속 메모리 할당 02  가변 분할에서의 메모리 보호-계속

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

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

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

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

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

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

연속 메모리 할당 02 버디 시스템 - 계속 메모리 블록(K) : L≤K≤U L : 할당 가능한 가장 작은 블록, U : 가장 큰 블록(전체 메모리) 블록 : 전체크기 또는 2U-1의 크기를 갖는 2개의 버디로 나누어짐, 크기가 b인 빈 버디 블록 쌍  크기가 2b인 큰 블록 하나로 만듬    64KB의 초기 블록 사용 예.  8KB 요청  블록을 두 개의 버디로 쪼갠다(b), 각 블록의 크기는 32KB 다시 블록을 두 개의 버디로 쪼갠다(c, d)  블록의 크기는 8KB이므로 요청에 할당

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

연속 메모리 할당 02 버디 시스템 - 참고 buddy system - binary buddy system 블록 크기 : 2n 으로 표시되며 2등분으로 정확하게 나누어지고 합쳐질 때는 같은 크기의 2배로 늘어남 2n 크기의 블록들은 항상 n 최하위비트 0에서 메모리 주소 시작 블록크기 1(20) : 어떤 주소라도 관계없이 시작 가능 블록크기 2(21) : 짝수 주소에서 시작 블록크기 4(22) : 0과 같은 최하위비트에서 주소 시작 http://www.cs.uiowa.edu/~jones/syssoft/fall00/notes/14alloc.html

연속 메모리 할당 02 버디 시스템 - 참고 typedef void * pointer; /* pointers to the free space lists */ pointer freelists[sizes]; /* blocks in freelists[i] are of size 2i. */ #define blocksize(i) (1 << (i)) pointer allocate( int size ) { int i; /* compute i as the least integer such that i >= log2(size) */ for (i = 0; blocksize( i ) < size; i++); if (i >= sizes) { error( "no space available" ); return NULL; } else if (freelists[i] != NULL) { /* we already have the right size block on hand */ pointer block; block = freelists[i]; freelist = *(pointer *)freelist[i]; return block; } else { /* we need to split a bigger block */ pointer block, buddy; block = allocate( blocksize( i + 1 ) ); buddy = (pointer)((int)block ^ blocksize( i )); /* put extra on a free list */ *(pointer *)buddy = freelists[i]; freeliest[i] = buddy; return block; } }

연속 메모리 할당 02 버디 시스템 - 참고 http://www.cs.uiowa.edu/~jones/syssoft/fall00/notes/14alloc.html

연속 메모리 할당 02 버디 시스템 - 참고 This example illustrates three things: First, the successive subdivision of blocks as requests are made, second, the internal fragmentation resulting from allocating more than was requested, and third, the external fragmentation resulting from the breaking up of the free space into multiple fragments. By the end of the example, there are two free blocks of size 32, but there is no way to combine these blocks to get a block of size 64 should one be needed. The cost of external fragmentation is not as easy to measure as that of internal fragmentation, but it can be partially characterized in terms of such statistics as the average number of free blocks and the distribution of free block sizes. The two blocks of size 16 starting at addresses 32 and 48 in Figure 14.5 are buddies. Should the block at address 32 be deallocated, these two must be combined into a new block of size 32 starting at address 32. This new block is the buddy of the block at address 0, and since that block is also free, they must be combined to make a block of size 64. The two blocks of size 32 starting at addresses 64 and 96 are also buddies. http://www.cs.uiowa.edu/~jones/syssoft/fall00/notes/14alloc.html

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

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

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

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

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

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

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

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

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

분산 메모리 할당 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로 사상 워드 페이지를 이용한 메모리 페이징

분산 메모리 할당 03 페이지 번지 페이징 - 동적 재배치의 형태 논리 주소 : 실제 주소로 사상 페이징 - 동적 재배치의 형태 논리 주소 : 실제 주소로 사상 메모리의 각 프레임에 대한 기준 레지스터 테이블을 사용하는 것과 유사 2차 수준 페이지 테이블 구성

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

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

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

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

분산 메모리 할당 03 페이지 테이블의 구현 - 계속 직접사상에 의한 페이지 주소 변환 페이지 사상표 - 메인메모리 혹은 캐시메모리에 유지 메모리 주소(b+p) = 페이지 사상표 시작주소(b) + 페이지 번호(p) ⇒ 페이지 프레임 p‘ = 논리 페이지 p p'는 변위 d와 접속되어 메모리주소 r = p' + d 직접 사상에 위치한 페이지 주소 변환

분산 메모리 할당 03 페이지 테이블의 구현 - 계속 직접사상에 의한 페이지 주소 변환 페이지 테이블 - 메인메모리에 유지하고 PTBR이 페이지 테이블 지정 방법이 바람직 [이유] 페이지 테이블의 변경은 레지스터 변화로 가능 [문제점] 사용자 메모리 위치에 접근 소요 시간 주소 p에 접근 - p에 대한 페이지 번호의 PTBR 변위 값 사용 페이지 테이블로 색인 두 번의 메모리 접근 필요 – 시간 지연 - 페이지 테이블 항목 - 워드를 위한 [지연 해결방법] 연관 레지스터 또는 보조 예비 기억 장치(작은 하드웨어 메모리) 사용

분산 메모리 할당 03 페이지 테이블의 구현 - 계속 연관사상에 의한 페이지 주소변환 논리주소  페이지 번호와 프레임 번호 : 연관 레지스터의 집합 레지스터 : 키와 값으로 구성 연관 레지스터 표현 : 동시에 모든 키와 비교  항목 발견: 대응하는 값 부분이 출력 탐색은 빠르나 하드웨어가 비쌈 연관 레지스터 : 몇 개의 페이지 테이블 항목만을 가짐 페이지 번호가 연관 레지스터를 찾으면 프레임 번호 이용 메모리에 접근하기 위해 사용 페이지 번호가 연관 레지스터에 없으면 그 페이지 테이블에 대한 메모리 참조가 이루어져야 함 프레임 번호가 얻어지면, 메모리 접근을 위해 사용 페이지 번호와 프레임 번호를 연관 레지스터에 더한다면 다음 참조를 빨리 할 수 있음

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

분산 메모리 할당 03 페이지 테이블의 구현 - 계속 연관/직접 사상을 통한 페이지 주소 변환 연관메모리 : 최근의 페이지 유지 직접 사상 : 연관메모리에 없는 페이지 유지(지역성 참고)   [예]  페이지 p 검색 - 연관 메모리의 항목 동시 조사 - 페이지 p에 해당되는 페이지 프레임 p' 발견 ⇒ d와 접속하여 메모리주소 r = p' + d 을 얻음 - p 와 일치하는 항목이 연관사상표에 없으면 ⇒ p+b의 페이지 테이블 p 에 대응하는 페이지 프레임 p‘ 얻고 메모리 주소 r = p'+d 생성

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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