오늘 한일
1. 운영체제 12강~14강 공부 및 요약
2. 데이터 베이스 특강 과제제출
[12. 메모리관리, 가상메모리]_프로세스마다 페이지 테이블을 사용하는구나!! 프레임으로 나뉘니까! 전용 논리주소였네, 연관매핑 TLB(변환색인버퍼), 집합연관매핑, 역매핑, 세그먼트와 페이지 차이, 세그먼트 테이블 구조는 p13을 참고, 페이지화된 세그먼트 기법. 중첩영역과 가상메모리의 차이. 블록매핑, 가상메모리 페이지테이블 엔티티 페이지 변위비트. 페이지 부재 처리과정 24
- 프로세스가 늘어나며 페이지 테이블의 수가 늘어났기에, 워드 페이징 기법 혹은 2차레벨 페이징 기법이 도입.
1차 페이지테이블의 항목은 2차 페이지 테이블의 기준 레지스터를 가리킴.- 페이지 테이블 주소매핑 방식
- 직접매핑: (PTBR+페이지번호p)값 + 변위
- 연관매핑: PTBR에 연관된 페이지를 모두 동시에 TLB(Translation Look-aside Buffer)에서 조사하고 없으면 직접매핑.
- 집합연관매핑: p1, p2로 세분화하여 2레벨 페이징. 페이지 테이블을 일정 집합으로 잘라 뭉텅이로 가져오고, 이를 관리하는 페이지
테이블을 하나 더 생성. p1은 디렉터리 테이블 번호, p2는 묶음 페이지 테이블 번호를 의미하고 VA=<p1, p2, D>로 표시한다.
디렉터리 테이블에서 p1으로 얻어낸 주소를 또다른 기준주소처럼 여기고 거기서부터 p2만큼 떨어진 값을 물리주소로 가져온다.
- 역매핑: 물리주소(프레임번호)를 기준응로 페이지 테이블을 생성하여 기존 페이지수x프로세스수에서 프레임수로 메모리 공간 줄임.
CPU에서 프로세스pid와 페이지값이 기준주소로부터 얼마나 떨어져있는지(몇번 째 프레임인지)로 물리주소를 얻음. 테이블 크기 작음
- 세그먼트 메모리 할당: 페이지 매핑 테이블 자원 절약, 속도상승, 내부단편화(프레임!) 방지를 위함.
고정크기인 페이징과 달리 연관된 기능을 수행하는 하나의 모듈인 가변적 세그먼트를 이용. 프레임으로 나뉘지않고 가변동적분할할당.- 페이지는 하나의 프로세스를 페이지로 나누어 프레임에 넣었다면, 세그먼트는 모듈들을 그대로 물리메모리에 크기에 따라 분산적재한다.
- 세그먼트 매핑은 STBR(Segment Table Base Register)와 STLR(Length)를 따지는데, STLR을 넘으면 실패, STBR+s에서 얻은 값 SL, 보호비트, SB중에서 d가 SL보다 작으면 실패, 정상이면 SB에 변위를 더해 물리주소로. (SL과 STLR+s은 별개. SL은 실제 메모리에서 기준)
- 페이지의 내부 단편화, 동적할당으로 인한 세그먼트의 외부 단편화를 해결한 페이지화된 세그먼트.
세그먼트 테이블에서 페이지 테이블 기준레지스터값을 얻어와 페이지번호를 이용해 얻은 페이지 프레임으로 물리주소를 얻는다.
즉, 어차피 논리주소에 세그먼트 번호(18bit)와 페이지 번호(6bit) 변위(10bit)가 다 있기에 세그먼트 테이블에서는 페이지 테이블 기준위치만 알아내면 된다.- 물리메모리와 디스크가 논리메모리
- 가상 메모리에서의 매핑
- 실제로 불연속배치되지만 연속배치된 것 처럼하는 기술이 가상메모리의 동적주소변환(DAT)
- DAT의 주기억장치 낭비를 막기위해 mapping내용을 가상메모리의 block단ㅌ위로 저장하고, 시스템은 블록이 위치하는 장소를 참조
BTOR에서 블록사상테이블 시작주소에 블록번호를 더해 엔티티(블록존재비트, 블록길이, 메모리주소)에서 메모리주소를 얻어 변위와
더한다(이 때, OR연산으로도 처리가 가능)- 가상메모리의 페이징: PTBR에서 마찬가지로 페이지 테이블 기준 값을 가져와 접근하는데, 페이지 번호에 항목크기를 곱하는 점이 차이!
이 때, 페이지 테이블 항목(PTE)에는 페이지 변위 12비트(P, R/W, U/S, ...etc), 프레임 번호 20비트 총 32비트로 구성된다.- 요구 페이징: 지연 교환기를 통해 페이지 요구가 있을 때 페이지를 메모리에 교체한다. 모든 페이지의 교체를 수행하지 않아 시간과
공간이 감소되고, 사용되지 않을 메모리를 읽지 않으며 다중 프로그래밍 정도를 높인다.- 페이지 부재 시 접근을 막기 위해 페이지 테이블 요소에 타당/비타당 비트를 사용한다. 만약 접근해야하는 것에 비타당 비트가 발견된다면, 운영체제에 트랩을 보내 예비기억장치에서 부재중인 페이지를 물리 메모리에 가져온 뒤, 페이지 테이블을 재설정하고 명령어를 재실행
- 순수 요구페이징은 요구될 때 까지 절대 메모리에 넣지않아 필요할 때 마다 페이지 부재가 발생한다.
v/i가 1이면 페이지가 메모리에 있으므로 f는 프레임 번호를, vi/i가 0이면 페이지가 디스크에 있고 f는 페이지 파일 변위를 나타낸다.- 페이징 시스템 성능: 1-p확률로 페이지 히트 시 유효접근시간은 메모리접근시간(Ma),
p확률로 페이지 부재 시 유효접근시간= P x 페이지부재서비스시간 + (1-p)*Ma. 1000us는 1ms- 유효 접근시간을 10%보다 더 적게 하고싶다면 p는? 유효접근시간 공식<기존 유효접근시간*0.1해서 풀면 됨.
[13. 가상 메모리 관리] 페이지 대치 공간, 작업설정모델
- 페이지 참조 테이블의 프레임 수가 증가하면 당연히 부재수가 감소..?할줄알았는데 벨레디의 변이
- 메인메모리 공간이 부족하여 페이지 대치할 때 희생프레임 선택해야함(모든 페이지 프레임은 초기에 비어있다)
- FIFO(FCFS): 히트했던말던 먼저들어왔던걸로 대치.
- OPT(MIN)_Optimal: 앞으로 가장 늦게 사용되는 페이지로 대치(SJF과 비슷)
- LRU(Least Recently Used): 메모리의 지역성, 과거에 가장 사용안했던 페이지로 대치
ㄴ각 페이지 테이블 항목, 사용시간 레지스터 관련 프로세서에 clock이나 counter를 붙여 참조마다 증가. 가장 작은 값으로 대치
ㄴ참조하면 stack에 계속 넣다가 참조하면 Top에 옮김. 오버헤드를 이중연결리스트스택으로 해결.- LRU 근접대치 알고리즘
- 부가된 참조비트: 참조 시 1을, 아니면 0을 왼쪽에 추가하며 rshift. 참조비트 작은 페이지 프레임을 희생함.
- 2차적 기회대치(시계): 원형버퍼 FIFO스타일로, 참조되면 1세팅하고 페이지 대치할거 찾으며 지나갈 때 0으로 바꿈. 0인걸 대치
- LFU(Least Frequently): 참조 가장 작은 것을 대치(카운터)
- MFU(Most): 참조 가장 많은 것을 대치
- 가상 메모리 적재정책: 스레싱, 지역성,
- 스레싱은 페이지 부재가 잦아 수행시간보다 page switching이 더 오래걸리는 경우를 의미.
새로운 프로세스 도입으로 CPU이용률 감소되며 스레싱이 발생.- 프로세스 실행 시 지역성, 국부성 특징을 가지기에 페이지 중 일부 지역적인 부분을 집중적으로 참조한다. 시간지역성 공간지역성
- 작업설정모델: Denning(Locality)를 설명하기 위한 것으로, 페이지 폴트를 줄이기 위해 참조가 많은 페이지들을 메모리에 지속상주.
Working-Set은 t-w~t동안의 참조가 많은 페이지 번호의 집합이다. WS(t1)={1,2,5,6,7}로 표기한다. 현재시점에서 가까운- p17문제: WS(t1)={1,2,3}, WS(t2)={4,5,6} / WS(t1)={1,2,3}, WS(t2)={4,5,6}
WSSi(프로세스 i의 Working-Set Size)를 의미. D=sigma(WSSi) 즉 전체 요구 페이지 프레임보다 실제 프레임이 적다면 스레싱이 발생하기에, 프로세스 실행을 연기해야한다. 적절한 윈도우 크기값은 10000이다.- 페이지 부재율이 높으면 더 필요하다는거고, 낮으면 이미 많이 갖고있다는 거기에 상한값과 하한값을 정해 스레싱을 방지한다.
이 과정에서 일부 프로세스가 중지될 수 있으며, 새로운 지역성으로 이동하는 과도기에는 시간단위까지 그대로 있기에 작동이 어렵다?- 대치 범위: 프로세스 프레임 내에서 선택하는 지역대치(프로세스 프레임 수 변하지 않음), 상관없이 선택하는 전역대치(타프로세스영향)
- 프리페이징: 프로세스 실행 초기에 많은 페이지 부재를 막기위해 미리 여러 페이지를 가져온 뒤 수행. 프로그램 실행 직전, 입출력 대기,
유효프레임이 없는 경우 수행된다. 성능은 페이즈 크기 S, 사용율 A일때 AS가 1에 가까우면 좋다.- 4KB에서 8KB로 페이지 크기를 늘리면, 처리속도증가, 교체감소, 부재감소, 페이블 및 페이지가 감소하지만 디스크 처리 시간이 증가되고 내부 단편화가 많아져 메모리 효율성이 떨어진다.
- 리눅스: 요구페이징, 전역대치, active list와 inactive list(2차적 기회대치와 유사)로 희생프레임을 선정. 참조시 access bit셋.
- 윈도우: 지역성을 고려한 클러스터링 요구페이징, Working set(50<=size<=345)기반 페이지 할당, LRU페이지 대치 알고리즘, 지역과 전역대치 혼합한 Memory Compression(Free frame list, modified frame list, Compressed frame list)
ㄴFree frame list에서 나가리된 modified frame list의 내용을 빈 페이지에 압축해서 compressed frame list에 넣음. Swap out을 시키지 않는다.
[14. 입출력 시스템] 프로그램 제어 입출력, 인터럽트 입출력, 디스크 인터리빙, SLTF??,
- 입출력 시스템과 프로세서 간의 실행 속도 차이를 동기화해줘야 한다.
- 프로그램 제어(Pooling)방식은 Busy Waiting으로 상태 Flag를 주기적으로 검사해야하기에 폴링 간격이 빠르면 성능이 저하된다.
- 인터럽트 입출력방식은 Busy Waiting없지만 인터럽트 핸들러와 스택공간이 필요하다. 인터럽트 발생 시 모든 데이터가 프로세서의 레지스터로 전송.
- DMA방식의 사이클스틸링은 다음과 같다. 프로세스가 전송방향,크기,블록주소를 DMA제어기에 전송->DMA제어기는 디스크제어기에게 데이터 전송을 요청->디스크제어기는 메인 메모리에 데이터 직접 전송->디스크 제어기가 DMA제어기에 완료신호전송->DMA제어기 프로세서 인터럽트 전송. 프로세서는 전송 시작, 끝만 관여.
- 섹터 32Byte, 트랙당 4~32섹터, 디스크 표면 당 20~1500트랙
- 디스크 접근 시간= 탐색시간(트랙)+회전지연시간(섹터)+전송시간(데이터 시작 끝). 고정헤드일 시 탐색시간이 없음.
- 디스크 인터리빙: 전송하는 동안 읽을 섹터를 지나치는 문제를 간격에 맞추어 데이터를 저장하고 읽어 성능을 향상.
- 디스크는 블록 단위로 저장하기에 11K섹터에 3K파일을 저장할 때 ext4(linux)처럼 블록이 4K인 경우, 단편화가 생긴다.
- 디스크 스케줄링_ 전체 Head 이동량이 몇 실린더인지 구하시오.
탐색시간 최적화
- FCFS: 무기한 연기없이 공평하지만 요청이 흩어져 있으면 처리량이 감소
- SSTF: 가장 가까운 것 부터 기아발생가능
- SCAN:디스트 끝까지 도달한 뒤 역방향 오면서 처리. 현재 헤드의 위치와 방향을 알아야함. 새 요청이 즉시처리될수도 늦게처리될수도
- C-SCAN: 한쪽으로 이동하다가 다시 처음으로 돌아와서 정방향
- Look: 끝까지는 말고 요청 있는데까지만 가자
회전시간 최적화- SLTF: 회전지연시간이 가장 짧은것부터. 고정헤드가 특정 실린더에 도착했을때 트랙이 대기중이면 도착순서와 관계없이 요청을 처리
고정헤드에 적합하며 섹터별로 Queue를 생성- SPTF: 위치결정시간(탐색+회전지연) 짧은것부터. 기아가능
- SATF: 접근시간(탐색+회전지연+전송시간) 짧은것부터. 가장 계산할거 많음.
- 비휘발성메모리 NVM는 탐색시간, 지연시간이 없어 RW가 빠르고 기계이동이 없어 신뢰성이 높다. 저전력이지만 비싸다.
Page단위로만 연산하기에 Update시 기존페이지를 invalid처리, 삭제시에는 블록단위로 하는데, 모든 블록이 invalid면 GC로 전체삭제- SSD의 디스크 스케줄링: SSD는 헤드이동이 필요없기에 그냥 IO발생시 개선된 FIFO(읽는건 걍 읽고 쓸때는 여러개 묶어서 씀)로 처리
- SSD의 Write연산 시 RW외에도 GC에서 Write amplification이 발생하기에 전체 블록간 ERASE비율을 균등화 시킨다(Wear leveling)
[부록]
-1KB같은거 곱할 때 1024로 계산!! 시간은 제외! 용량일 경우에만.
이제 3학년..