[크래프톤 정글 3기] 12/18(월) TIL

ClassBinu·2023년 12월 18일

크래프톤 정글 3기 TIL

목록 보기

63/120

수원 가는 기차에서 강의 들음

OS 특강 2차

파일 시스템

가상 메모리는 물리 메모리와 매핑된다.
파일 시스템은 디스크의 블록에 매핑한다.

파일시스템은 소프트웨어적으로 구현된다.
디스크는 원래 워낙 느려서 하드웨어로 구현한다고 해서 성능상의 이점이 없다.

파일 시스템은 종류가 다양하다.
(반면에 메모리는 단일 시스템이다.)
다양한 시스템을 어떻게 같은 API로 동작 시키냐?
추상화 레이어다.
-> VFS(Virtual File System)

시스템 콜이 VFS를 통해 알맞은 파일 시스템으로 맵핑

파일 시스템 내부에 퍼버 캐시가 구현되어 있음.

데이터 동기화 문제

어떤 데이터를 기준으로 동기화를 할 것인가?(일관성)
원자성 보장

파일 시스템은 일관성을 저널링을 통해 해결한다.
원자성은 파일 시스템이 하지 않고, 유저가 해야 됨
(운영체제가 하기에는 비쌈)

롤백 로깅

로그를 만든다.
백업 -> 업데이트 -> 잘 끝나면 로그 지움

개발자로서 어플리케이션 레벨에서 crash consistency를 꼭 이해해야 한다.

OS 역할

Prorection

커널을 보호하는 것

어떻게 구현할까?
어플리케이션한테 특정한 인스트럭션 실행을 막는다.(인스트럭션 분리)
(셧다운, 로드 페이지 테이블 등)

다른 어플리케이션의 메모리 읽기/쓰기를 막기(메모리 분리)

OS가 주기적으로 애플리케이션을 컨트롤한다.
주기적으로 OS한테 컨트롤 권한을 넘김.
(= 타이머 인터럽트)

인스트럭션을 체크해야 함

파이썬 같은 언어는 인터프리터가 체크함.
하지만 이건 너무 느림
그래서 하드웨어가 함.
안되는 경우 발생하는 게 트랩, 익센셥 -> 커널에 넘김 -> 커널이 판단 -> 킬 or 실행

프리빌리지 결정 권한 관계
APP < OS < HW
하드에어는 OS에게 권한을 대행시키는 것!
OS는 HW에게 privilege를 endors한다.

메커니즘(exception)은 HW가 하고 policy는 OS가 구현
하드웨어는 그냥 값을 참조, 킬 여부 등은 소프트웨어적으로 구현

모든 프로젝션을 하드웨어가 할 수 없어서 일부 권한을 OS에게 위임하는 것!

isolation

어플리케이션 고립

다른 어플리케이션 데이터 접근하면 안 됨
다른 어플리케이션 코드로 점프하면 안 됨(내 컨텍스트에서)

isolation: 데이터와 코드 플로우 컨트롤을 막는 것

프로세스마다 페이지 테이블을 생성하고,
컨텍스트 스위칭에서는 페이지 테이블 시작점만 바꿔주면 된다.

파일 isolation은?

권한으로 구현 가능(file permission)
모든 파일은 커널을 통해서 접근해야 함.

권한 체크 코드는 refeerence monitor에 있음.(policy)

Access control method

DAC & MAC
Capability based access control

IPC

Shared Memory(근데 폴링이나 시그널로 변경 상황 알려줘야 해서 느림): 성능 좋음
Message Passing: 데이터가 적으면 카피 비용이 적음 이거 씀, 편리함

스케줄러

response time
turn around time

메모리

Momory

최초 할당 : 0으로 밀어서 할당
swap 할당: 스왑 영역에서 가져온다
파일: 로드

메모리가 차 있으면 메모리를 내려야 함.
이때 과거를 참고함. recency, frequency
(지역성 이론에 근거)

반복문을 쓰기 때문에 시간 지역성이 생김.
배열을 쓰기 때문에 공간 지역성이 생김.

OS가 기본적으로 반복문과 배열을 쓴다는 가정으로 미래를 예측함.

교체 정책 중 Clock

(LRU는 링크드 리스트로 구현함, 근데 비싸다)
시계처럼 돌면서 엑세스가 안 된 페이지를 찾아서 내림

TLB 플로우 차트

가상 주소 요청
TLB 조회
3-1. TLB 히트 -> 물리주소 변환 후 메모리 접근
3-2. TLB 미스
페이지 테이블 조회
5-1. 페이지 테이블 히트 -> 물리 주소 변환 -> TLB 업데이트 -> 메모리 접근
5-2. 페이지 폴트 -> 스왑 인&아웃 -> 페이지 테이블, TLB 업데이트 -> 초기 가상 주소 재요청

스터디에서 의문이었던 것.
TLB는 언제 업데이트 되나?
스왑 인&아웃 후 물리 메모리에 접근하는 게 아니라
TLB와 페이지 테이블 업데이트 후 처음으로 돌아가서
다시 가상 주소로 메모리 접근을 요청하는 것!

일반적으로 페이지 폴트 시 페이지 테이블을 업데이트하고 이후에 TLB도 업데이트(선택) 함

멀티 레벨 페이지 테이블

가상주소: <페이지 디렉토리 인덱스> + <페이지 테이블 인덱스> + <오프셋> (10 + 10 + 12 bit)

PTBR: Page Table Base Register
PDBR: Page Directory Base Register

역 페이지 테이블

모든 페이지에 대해서 테이블을 만들면 프로세스마다 페이지 테이블이 필요하다. 이걸 시스템에서 전역적으로 사용하는 프레임 기준의 역 페이지 테이블을 만들면 모든 시스템이 하나의 역 페이지 프레임으로 페이지 관리가 가능하다.

단, 주소를 찾을 때마다 처음부터 역 페이지 테이블을 순회해야 해서 오버헤드가 발생한다.

스왑

익명 페이지와 파일 기반 페이지의 처리 방식은 다르다.

익명 페이지

더티 비트가 0이면 메모리에서 그냥 지움
더티 비트가 1이면 스왑 영역에 기록 후 메모리에서 지움

파일 기반 페이지

더티 비트가 0이면 메모리에서 그냥 지움
더티 비트가 1이면 원본 파일에 해당 변경 사항 기록

파일 기반 페이지 예시
1. 메모리 매핑된 파일(mmap)
2. 공유 라이브러리
3. 실행 파일 코드 섹션

Pintos: VM git book

논리주소 64비트는 다음 구성이다.

63          48 47            39 38            30 29            21 20         12 11         0
+-------------+----------------+----------------+----------------+-------------+------------+
| Sign Extend |    Page-Map    | Page-Directory | Page-directory |  Page-Table |    Page    |
|             | Level-4 Offset |    Pointer     |     Offset     |   Offset    |   Offset   |
+-------------+----------------+----------------+----------------+-------------+------------+
              |                |                |                |             |            |
              +------- 9 ------+------- 9 ------+------- 9 ------+----- 9 -----+---- 12 ----+
                                          Virtual Address

물리주소 64비트는 다음과 같다.

                          12 11         0
    +-----------------------+-----------+
    |      Frame Number     |   Offset  |
    +-----------------------+-----------+
              Physical Address

구현해야 하는 것

(보충) 페이지 테이블

페이지 폴트 핸들러로 구현해야 함.
엑세스 되거나 수정되었을 때 엑세스 비트와 더티 비트도 수정해야 함.

프레임 테이블

스왑 테이블

이런 게 결국 다 자료구조로 있는 거구나?!

구조체 페이지 살펴보기

struct page {
	const struct page_operations *operations;
	void *va;              /* Address in terms of user space */
	struct frame *frame;   /* Back reference for frame */

	/* Your implementation */

	/* Per-type data are binded into the union.
	 * Each function automatically detects the current union */
	union {
		struct uninit_page uninit;
		struct anon_page anon;
		struct file_page file;
#ifdef EFILESYS
		struct page_cache page_cache;
#endif
	};
}

구조체 요약
1. 페이지 조작 함수 포인터
2. 가상 주소
3. 매핑된 프레임
4. 페이지 타입

페이지 유형마다 필요한 작업이 다름.

// 식별자 v로부터 page를 스왑 인
#define swap_in(page, v) (page)->operations->swap_in ((page), v)

// page를 스왑 아웃
#define swap_out(page) (page)->operations->swap_out (page)

// page를 지움(리소스 해제)
#define destroy(page) \
	if ((page)->operations->destroy) (page)->operations->destroy (page)

추가 페이지 테이블 구현

// 보충 페이지 테이블 초기화. 프로세스 시작 및 분기 시 호출
void supplemental_page_table_init (struct supplemental_page_table *spt);

// va에 해당하는 페이지 찾기
struct page *spt_find_page (struct supplemental_page_table *spt, void *va);

// page를 테이블에 삽입(가상 주소 존재 여부 확인 필요)
bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);

프레임 관리

/* The representation of "frame" */
struct frame {
  void *kva;  // 커널 가상 주소
  struct page *page;  // 페이지
};

// 새로운 물리 페이지를 사용자 풀에서 얻고, 프레임 할당 및 초기화
static struct frame *vm_get_frame (void);

// 주어진 페이지에 물리 프레임을 할당, 가상 주소와 물리 주소 매핑
bool vm_do_claim_page (struct page *page);

// 주어진 가상 주소에 페이지를 할당
bool vm_claim_page (void *va);

익명 페이지

백업 파일, 장치가 없음.
스택 및 힙에서 실행 파일에 사용됨.

// 익명 페이지 구조체
struct anon_page {
};

비어있는 게 정상이 아니라 내가 구현해야 되는거네. -_-;

익명 페이지 초기화(지연 로딩)

initialize->(page_fault->lazy-load->swap-in>swap-out->...)->destroy

메모리 매핑

mmp, munmap

스왑인/아웃

메모리 회수 기술

파일 기반 페이지의 I/O도 스왑인/아웃으로 표현하나?
그렇다! gitbook에 나와 있다!

쓰기 시 복사

인상 깊은 표현!
실제 복사 작업은 첫 번째 쓰기로 연기됩니다.

Pintos 고민

그래서 구현해야 하는 건?

보충 페이지 테이블
프레임 테이블
익명 페이지 관리
스택 성장 기능
메모리 매핑(mmap, munmap)
익명/파일 페이지의 스왑 인/아웃
쓰기 시 복사(extra)

vm.c와 vm.h에 맞춰서 구현해야 함!
우선 그걸 살펴보자!

vm.c

static struct frame *vm_get_victim (void);
static bool vm_do_claim_page (struct page *page);
static struct frame *vm_evict_frame (void);

vm.h

void supplemental_page_table_init (struct supplemental_page_table *spt);
bool supplemental_page_table_copy (struct supplemental_page_table *dst,
		struct supplemental_page_table *src);
void supplemental_page_table_kill (struct supplemental_page_table *spt);
struct page *spt_find_page (struct supplemental_page_table *spt,
		void *va);
bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);
void spt_remove_page (struct supplemental_page_table *spt, struct page *page);

void vm_init (void);
bool vm_try_handle_fault (struct intr_frame *f, void *addr, bool user,
		bool write, bool not_present);

#define vm_alloc_page(type, upage, writable) \
	vm_alloc_page_with_initializer ((type), (upage), (writable), NULL, NULL)
bool vm_alloc_page_with_initializer (enum vm_type type, void *upage,
		bool writable, vm_initializer *init, void *aux);
void vm_dealloc_page (struct page *page);
bool vm_claim_page (void *va);
enum vm_type page_get_type (struct page *page)

보충 페이지 테이블 구조를 결정해야 함

struct supplemental_page_table {
		struct hash spt_hash;
};

https://casys-kaist.github.io/pintos-kaist/appendix/hash_table.html

리눅스에서 제공하는 해시 테이블 사용 가능

/* Hash table. */
struct hash {
	size_t elem_cnt;            /* Number of elements in table. */
	size_t bucket_cnt;          /* Number of buckets, a power of 2. */
	struct list *buckets;       /* Array of `bucket_cnt' lists. */
	hash_hash_func *hash;       /* Hash function. */
	hash_less_func *less;       /* Comparison function. */
	void *aux;                  /* Auxiliary data for `hash' and `less'. */
};

/* A hash table iterator. */
struct hash_iterator {
	struct hash *hash;          /* The hash table. */
	struct list *bucket;        /* Current bucket. */
	struct hash_elem *elem;     /* Current hash element in current bucket. */
};

C는 클래스는 없지만 구조체에 함수 포인터를 넣어서 클래스처럼 사용함.

이거 쓰는 김에 해시테이블 좀 살펴보기!

보충 페이지 테이블 초기화

/* Initialize new supplemental page table */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	
}

ClassBinu

이전 포스트

[크래프톤 정글 3기] 12/15(금) TIL

다음 포스트

[크래프톤 정글 3기] 12/18(월) TIL

크래프톤 정글 3기 TIL

OS 특강 2차

파일 시스템

데이터 동기화 문제

롤백 로깅

OS 역할

Prorection

인스트럭션을 체크해야 함

isolation

파일 isolation은?

IPC

sharing

Time sharing

Space sharing

Momory

교체 정책 중 Clock

TLB 플로우 차트

멀티 레벨 페이지 테이블

역 페이지 테이블

스왑

익명 페이지

파일 기반 페이지

Pintos: VM git book

구현해야 하는 것

(보충) 페이지 테이블

프레임 테이블

스왑 테이블

구조체 페이지 살펴보기

추가 페이지 테이블 구현

프레임 관리

익명 페이지

익명 페이지 초기화(지연 로딩)

메모리 매핑

스왑인/아웃

쓰기 시 복사

Pintos 고민

그래서 구현해야 하는 건?

vm.c

vm.h

보충 페이지 테이블 구조를 결정해야 함

보충 페이지 테이블 초기화

[크래프톤 정글 3기] 12/15(금) TIL

[크래프톤 정글 3기] 12/19(화) TIL

0개의 댓글