Paging & Segmentation

[JoisFe]

Paging & Segmentation

• 페이지와 프레임의 차이에 대해 설명해 주세요.
• 내부 단편화와, 외부 단편화에 대해 설명해 주세요.
• 페이지에서 실제 주소를 어떻게 가져올 수 있는지 설명해 주세요.
• 어떤 주소공간이 있을 때, 이 공간이 수정 가능한지 확인할 수 있는 방법이 있나요?
• 32비트에서, 페이지의 크기가 1kb 이라면 페이지 테이블의 최대 크기는 몇 개일까요?
• 32비트 운영체제는 램을 최대 4G 까지 사용할 수 있습니다. 이 이유를 페이징과 연관 지어서 설명해 주세요.
• C/C++ 개발을 하게 되면 Segmentation Fault 라는 에러를 접할 수 있을텐데, 이 에러는 세그멘테이션/페이징과 어떤 관계가 있을까요?

[JoisFe]

Q) 페이지와 프레임의 차이에 대해 설명해 주세요.

Paging

• process를 일정한 크기의 page로 분할해서 메모리에 적재하는 방식
• external fragmentation 해결 (반대로 internal fragmentation 문제 생길 수 있음)

Segmentation

• 가상 메모리를 서로 크기가 다른 논리적 단위로 분할한 것을 의미함
• process를 물리적 단위인 page가 아닌 논리적 단위인 segment로 분할해서 메모리에 적재하는 방식
• internal fragmentation 해결 (반대로 external fragmentation 문제 생길 수 있음)

	Paging	Segmentation
Block Size	고정	유동적
Linear address space	1	여러개
Memory Adressing (virtual address)	page number + offset	segment + offset
Replacement	쉬움 (모두 같은 사이즈)	어려움 (각기 사이즈가 다르기 때문에)
Fragmentation	Internal	External
Disk Traffic	효율적	비효율적
Transparent to be Programmer	O (연속적인 주소를 가지므로 프로그래머가 신경 쓸 필요 없음)	X

Q) 내부 단편화와, 외부 단편화에 대해 설명해 주세요.

Internal Fragmentation

• 메모리를 할당할 때 process에서 필요한 메모리 크기보다 더 크게 할당되어 process에서 사용하는 메모리 공간이 낭비되는 상황

Internal Fragmentation 해결법

1. Segmentation
2. Memory Pooling (Internal, External Fragmentation 모두 해결)

• 필요한 메모리 크기와 개수를 지정해 미리 할당을 받아 memory poll에 만들어 놓고 필요한 경우 사용 후 반납
• 미리 할당받았던 메모리 공간을 사용 후 반납 하기에 메모리 할당과 해제로 인해 External Fragmentation 발생되지 않음
• 필요한 크기만큼 할당을 해놓기 때문에 Internal Fragmentation 또한 발생하지 않음
• 메모리가 많이 필요하지 않지만 미리 너무 많이 할당해두고 poll 에 넣어두는 것은 비효율적!

External Fragmentation

• 메모리 할당 후 해제가 될때 할당된 메모리와 메모리 사이에 사용하지 않는 작은 메모리가 발생
• 이 때 작은메모리 공간의 합 (남아 있는 총 메모리 공간)은 충분하나 남아 있는 메모리 공간이 연속적이지 않아 실제 할당 가능한 공간이 부족한 상황

External Fragmentation 해결법

1. 압축 (Compaction)

• 메모리 재배치 통해 단편화 되어 있는 공간을 하나로 합침

2. 통합 (Coalescing)

• 단편화로 인한 분산된 메모리 공간들 중 인접해 있는 공간끼리 통합시켜 큰 메모리 공간으로 합침
• 압축은 재배치가 일어나지만 통합은 인접한 공간끼리 합쳐짐

4. Paging
5. Memory Pooling

Q) 페이지, 세그멘테이션 에서 실제 주소를 어떻게 가져올 수 있는지 설명해 주세요.

• OS에선 Virtual Address -> Physical Address로 변환하여 메모리에 접근

Page 주소 변환 과정

• Virtual Address = Page Number + Offset 으로 구성
• Virtual Address의 Page Number를 통해 Page Table에서 해당 페이지의 Frame Number (물리 프레임 번호) 를 찾음

Physical Address = Frame Number x Page Size + Offset

EX)

• Page Size = 4KB
• Frame Number = 3
• Virtual Address = 0x2F3A
  • 상위 4bit = Page Number
  • 하위 12bit = Offset

==>

• Page Number = 0x2 -> page table에서 조회하여 frame number인 F를 조회했다고 가정
• Physical Address = frame number (3) X Page Size (4KB = 4096B) + offset (0xF3A)
  • 3 x 4096 + 0xF3A

Segmentation 주소 변환 과정

• Virtual Address = Segment Number + Offset
• Segment Number 를 사용해 Segment Table 에서 Base Address와 Limit (Segment Size) 를 가져옴
• Offset 이 Limit 보다 작은지 검사 (크면 오류가 발생함)

Physical Address = Base Address + Offset을

EX)

• Segment Table에서 Segment Number(2)의 Base Address = 0x4000 (Segment Table에서 찾아옴)
• Segemnt 2의 Limit = 0x1000 (4096B) (Segment Table에서 찾아옴)
• offset (0x034A)가 limit (0x1000) 보다 작은지 검사
• Physical Address = Base Address(0x4000) + Offset(0x034A) = 0x434A

Q) 어떤 주소공간이 있을 때, 이 공간이 수정 가능한지 확인할 수 있는 방법이 있나요?

방법	일반 사용자 접근 가능	비고
mprotect()	PROT_WRITE 설정 시도	리눅스 시스템콜
/proc/self/maps	가능	리눅스 환경
Page Table 조회	커널 접근 필요
Segment Table 조회	커널 접근 필요

Q) 32비트에서, 페이지의 크기가 1kb 이라면 페이지 테이블의 최대 크기는 몇 개일까요?

Page Tabel 최대 크기

• Page Table 최대 크기 = 주소 공간 / Page 크기

32 비트 주소 공간

• 32 Bit Virtual Address Space = 2 ^ 32 byte = 4GB

Page 크기 (1KB = 2 ^ 10 byte)

• 각 page 크기가 1KB (2 ^ 10 byte) 임
• Page 수 = 2 ^ 32 (주소 공간 크기) / 2 ^ 10 (페이지 크기) = 2 ^ 22 = 4194304 (페이지 갯수)
• ==> 4194304 개 필요

Q) 32비트 운영체제는 램을 최대 4G 까지 사용할 수 있습니다. 이 이유를 페이징과 연관 지어서 설명해 주세요.

• 32 bit OS이면 메모리 주소를 표현하는데는 32 bit를 사용
• --> 표현할 수 있는 범위는 2 ^ 32 = 4 GB 입니다. 따라서 이론적으로 32 bit system에서는 최대 4GB 메모리 주소를 다룰 수 있기에 최대 4G 까지 사용할 수 있습니다.

Q) C/C++ 개발을 하게 되면 Segmentation Fault 라는 에러를 접할 수 있을텐데, 이 에러는 세그멘테이션/페이징과 어떤 관계가 있을까요?

Segmentation Fault (SIGSEGV)

• OS가 Process에게 허용한 메모리 범위를 벗어난 주소를 접근할 때 발생하는 오류

EX)

• segmentation 은 memory 여러 개의 segment로 나누어 관리하는 기법으로 OS 는 각 process의 code ,data, data ,stack 등을 개별적인 segment에 배치
  • Code segment (읽기 전용)에 쓰기를 시도하면 SIGSEGV 오류가 발생합니다.
  • heap 에서 해제된 memory에 접근하면 SIGSEGV 오류 발생
• NULL 포인터 역참조
• 배열 인덱스 초과
• 잘못된 메모리 접근

참고

• https://unstop.com/blog/difference-between-paging-and-segmentation
• https://jun-n.tistory.com/164
• https://data-flair.training/blogs/paging-vs-segmentation-in-operating-system/
• https://velog.io/@tlsdnxkr/CS-%EB%8B%A8%ED%8E%B8%ED%99%94-%EC%84%B8%EA%B7%B8%EB%A9%98%ED%85%8C%EC%9D%B4%EC%85%98-%ED%8E%98%EC%9D%B4%EC%A7%95%EB%82%B4%EB%B6%80%EB%8B%A8%ED%8E%B8%ED%99%94-%EC%99%B8%EB%B6%80%EB%8B%A8%ED%8E%B8%ED%99%94
• https://zu-techlog.tistory.com/132

[Tokwasp]

❓ Paging & Segmentation

🌱 [ Paging ] :

• 일정한 크기인 페이지 단위로 나누어 메모리에 할당 하는 방법

[ Paging 장점 ] :

• 심플 하기 때문에 부하(overhead) 적다.
• 외부 단편화가 발생 하지 않는다.

[ Paging 단점 ] :

• 논리적인 단위로 나눠 지지 않아 보호/공유가 어렵다.
• 내부 단편화가 발생 한다.

🌱 [ Segmentation ] :

• 논리 단위인 세그먼트로 나누어 메모리에 할당 하는 방법

[ Segmentation 장점 ] :

• 논리 단위로 나누어 보호/공유에 좋다.
• 내부 단편화 발생 하지 않는다.

[ Segmentation 단점] :

• 논리 단위로 나누어 관리가 어려워 부하가 크다.
• 외부 단편화가 발생한다.

🌱 [ Hybrid paging/segmentation ] :

• 논리 단위인 세그먼트로 나누고 메모리에 올릴때는 페이징으로 나누어 올리는 방법

[ Hybrid 장점 ] :

• 세그먼트로 나누어 관리/보호에 좋다.
• 메모리에 올리는 단위는 page 이기 때문에 부하가 적다.
• 외부 단편화가 발생 하지 않는다.

[ Hybrid 단점] :

• 내부 단편화가 발생한다.
• 메모리 접근이 3배 이다.

❓ 페이지와 프레임의 차이에 대해 설명해 주세요.

• [ 페이지 ] : 가상 주소 매핑에서 자르는 단위를 페이지
• [ 프레임 ] : 실제 메모리에서 자른 부분을 페이지 프레임

❓ 내부 단편화와, 외부 단편화에 대해 설명해 주세요.

🌱 내부 단편화 & 외부 단편화

• [ 내부 단편화 ] : 메모리를 고정으로 할당 하였으나 사용되지 않아 낭비 되는 메모리
• [ 외부 단편화 ] : ( 남은 메모리 크기 > 프로세스 크기 ) 메모리는 충분 하지만 비연속적인 메모리 때문에 할당 할수 없는 상태

❓ 페이지에서 실제 주소를 어떻게 가져올 수 있는지 설명해 주세요.

🌱 [ 가상 주소 매핑 ] :

• 실제 메모리는 연속적이지 않지만 가상 메모리는 연속적으로 할당된 것처럼 사용 하는 방법

🌱 [ 매핑 방법 ] :

• [ 직접 매핑 ] ( Direct Mapping ) : PMT를 통해 물리 페이지 주소를 찾는 방법
• [ 연관 매핑 ] ( Association Mapping ) : PMT의 단점인 메모리 두번 참조를 TLB을 이용해 빠르게 물리 페이지 주소를 찾는 방법

❓ 어떤 주소공간이 있을 때, 이 공간이 수정 가능한지 확인할 수 있는 방법이 있나요?

🌱 [ 페이지 보호 ] :

• 페이지에 대한 권한을 설정 하는 방법 ( 읽기, 쓰기, 실행 )

• 리눅스 에서는 mprotect() 시스템 콜을 사용하여 메모리 보호 속성을 설정할 수 있고, mincore()를 사용하여 보호 상태를 추적 가능

❓ 32비트에서, 페이지의 크기가 1kb 이라면 페이지 테이블의 최대 크기는 몇 개일까요?

• [ 32 비트 ] 의미 : 가상 주소 공간의 크기
• [ 32비트 표현 가능한 주소 크기 ] : 2의 32승 = 4GB
• 1kb = 2의 10승 바이트 -> 전체 페이지 수 : 2^22 페이지
• 페이지 테이블 엔트리의 크기는 일반적으로 4bye -> 2^22 * 4 = 2 ^20 * 16 = 16MB

❓ 32비트 운영체제는 램을 최대 4G 까지 사용할 수 있습니다. 이 이유를 페이징과 연관 지어서 설명해 주세요.

• 페이징은 가상 주소공간을 물리 메모리에 매핑하는 기법 이기 때문에 4GB 까지 매핑이 가능 하다?

❓ C/C++ 개발을 하게 되면 Segmentation Fault 라는 에러를 접할 수 있을텐데, 이 에러는 세그멘테이션/페이징과 어떤 관계가 있을까요?

🌱 [ 직접 매핑 과정 ] :

1. 주어진 SMT 주소를 통해 커널에서 SMT 를 찾는다.
2. SMT 의 row를 entry라고 하며 (s, d)를 통해 몇번째 entry인지 s * entrySize를 구하여 세그먼트를 찾는다.
3. SMT 에서 존재 비트를 보았을때 메모리에 존재 하지 않는다면 usleep 상태가 되며 메모리에 올린다.
4. 실제 메모리 물리 주소의 세그먼트 주소를 구한다.

[ 세그먼트 예외 ] :

• SMT는 RWE 보호를 할수 있기 때문에 권한이 없을 경우 예외가 발생하며 세그먼트 길이 < d 에도 예외가 발생 한다.

자료 출처 : https://www.youtube.com/watch?v=es3WGii_7mc&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=24
한기대 교수님 운영체제 유튜브