728x90
1. 아침 문제 풀이
1. 2023번 - 신기한 소수
import sys
N = int(sys.stdin.readline())
result = []
#소수인지 판별하는 함수
def isPrime(n) :
for i in range(2, int(n**(1/2))+1) :
if n % i == 0 :
return False
return True
#백트래킹 방식을 사용한 탐색
def dfs(depth, n) :
if depth == N :
if isPrime(n) :
result.append(n)
return
for i in range(10) :
nn = n*10 + i
if isPrime(nn) :
dfs(depth+1, n*10+i)
prime = [2, 3, 5, 7]
for p in prime :
dfs(1, p)
for r in result :
print(r)
예전 같았으면 풀이를 참고할 법한 문제였다.
여기서 2가지 정리하면
1. 소수 판별
소수란 1과 자기 자신만을 약수로 가져야하므로 자기보다 작은 수들을 나눠 떨어지는 것이 없으면 된다.
이때 자신의 제곱근보다 큰 수들까지 셀 필요는 없다.
2. 백트래킹 탐색
문제 상에서 왼쪽부터 1자리, 2자리 등 모두 소수여야 하므로 소수일 경우 재귀를 사용
2. 가상 메모리 관련 개념 정리
1. 메모리 공유
- 메모리 : 각각 주소가 할당된 일련의 바이트들로 구성
- CPU는 Program Counter가 지시하는대로 메모리로부터 다음 수행할 명령어를 읽는다.
- CPU 스케줄링의 결과로 CPU 이용률과 사용자에게 제공하는 컴퓨터 응답속도를 향상
- 이러한 성능 향상을 실현하려면 많은 프로세스를 메모리에 유지할 필요가 있다.
- 즉, 메모리를 여러 프로세스들이 공유할 필요가 있다.
- 각각의 프로세스가 독립적인 메모리 공간을 가지도록 보장
- 프로세스별 메모리 공간은 서로 보호하고 병행 실행을 할 수 있도록 한다.
- base register : 가장 작은 합법적인 물리 메모리 주소
- limit register : 주어진 영역의 크기 저장
- base 값 <= addr < base + limit
- 이러한 레지스터의 값 변경을 커널 모드에서만 변경 가능
- 사용자 프로그램이 이 값들을 변경하는 것을 방지
2. 페이지
가상 주소의 분할된 영역으로 가상 메모리의 연속 영역
- Paging 기법
- 고정 분할 방식 = 메모리를 모두 같은 크기의 블록으로 편성
- 이때 일정한 크기를 가진 블록을 page라고 한다.
- 장점 ✅
- 프로세스의 물리 주소 공간이 연속적이지 않아도 된다.
- 외부 단편화 해결
- 페이지 개수가 n개인 프로그램을 실행하기 위해 n개의 프레임을 찾아서 로드할 필요가 있다.
- pintos에서의 페이지 크기 : 4096byte = 2^12byte = 4kiB
- 페이지는 항상 정렬되어있어야 한다.
- 즉, 각 페이지는 페이지 크기로 균등하게 나누어지는 가상 주소에서 시작!
- 시작 위치 = 항상 페이지 크기로 나누어 떨어지는 위치
- 64bit 가상 주소(논리 주소)
- 상위 52bit = 페이지 테이블의 인덱스를 나타내는 데 사용 = page number
- 하위 12bit = offset으로 사용
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
3. 프레임
물리적 프레임 또는 페이지 프레임으로 물리적 메모리의 연속 영역
- 실제 메모리를 page와 크기가 같은 블록을 frame이라고 한다.
- 물리 주소 : 위의 논리 주소와 형식은 같음
- frame number : 상위 52bit
- frame offset : 하위 12bit = page offset과 동일하다
- 프레임 테이블 Frame Table (후에 구현해야할 것)
- 어느 프레임이 할당되어 있고, 어느 프레임이 사용 가능한지, 총 프레임은 몇 개나 되는지 등에 대한 정보를 담는 자료구조
- 각 프레임에 대해 하나의 항목을 포함
- 현재 이를 차지하고 있는 페이지가 있는지
- 있을 경우에는 차지하고 있는 프로세스에 대한 포인터 저장
- 있을 경우에는 차지하고 있는 프로세스에 대한 포인터 저장
- 가장 중요한 작업은 사용하지 않는 프레임을 얻는 것
- 프레임이 비어 있으면 비어있는 프레임 사용하면 된다.
- 그러나 사용 가능한 것이 없으면 프레임에서 일부 페이지를 제거하여 프레임을 사용 가능하게 만들어야 한다.
- 이 테이블을 사용하여 빈 프레임이 없을 때 제거할 페이지를 선택하여 Pintos가 제거 정책을 효율적으로 구현
- 페이지 교체 알고리즘
- FIFO : 가장 먼저 들어온 페이지 선택
- Optimal Page Replacement : 앞으로 가장 오랫동안 사용되지 않을 페이지 선택
- Least Recently Used : 가장 오랫동안 참조되지 않은 페이지 선택
- Least Frequntly Used : 참조 횟수가 가장 적은 페이지 선택
- Most Frequently Used : 참조 횟수가 가장 많은 페이지 선택
- 현재 이를 차지하고 있는 페이지가 있는지
4. 페이지 테이블
프로세스의 페이지 정보를 저장하고 있는 테이블
CPU가 페이지에서 프레임으로 변환하는데 사용하는 데이터 구조
- 즉,논리 주소를 물리 주소로 변환
- 하나의 프로세스는 하나의 페이지 테이블을 가진다.
- page number는 frame number로 변환되고 offset과 결합
- page offset = frame offset 항상 같다!
- 추가 페이지 테이블 (후에 구현해야 할것)
- 각 페이지에 대한 추가 데이터로 페이지 테이블을 보완
- 페이지 테이블의 형식에 따른 제한 때문에 필요하다.
- 사용 이유
- page falut 시 커널이 추가 페이지 테이블에서 폴트가 발생한 가상 페이지를 조회하여 어떤 데이터가 있어야 하는지 알아내는 것
- 커널은 프로세스가 종료될 때 추가 페이지 테이블을 참조하여 해제할 리소스를 결정
- page fault가 발생하면 file 또는 swap slot에서 페이지를 가져와야 한다.
- page fault handler()
- 추가 페이지 테이블에서 오류가 발생한 페이지 찾기
- 페이지를 저장할 프레임 얻기
- 데이터를 읽어 프레임으로 가져오기
- fault가 있는 가상 주소에 대한 페이지 테이블 항목에 물리적 페이지를 가리키는 포인터 저장
5. swap slot
swap partition 내의 디스크 공간에 있는 페이지 크기의 영역
- swapping
- 프로세스는 임시적으로 디스크로 교체되어 나갔다가 다시 메모리로 돌아올 수 있다.
- 실제로 사용하는 부분만을 swap하여 시간을 줄인다.
- 스왑 테이블 Swap Table (구현해야 할것)
- 사용 중 및 사용 가능한 swap slot을 추적
- 프레임에서 swap partition으로 페이지를 제거하기 위해 사용되지 않은 swap slot을 선택
- lazy swapper
- 프로세스를 실행하고 싶으면 읽어 들이되, 필요한 페이지만 적재
- 게으르게 할당되어야 한다.
- 즉, 실제 필요할 때만 할당
< 참고 >
3. Pintos 관련 정리(gitbook)
1. 메모리에 접근하는 방법
- 물리 메모리에 접근하기 위해서는 커널 가상 메모리를 통해 접근한다.
- 커널 가상 메모리의 첫 번째 페이지는 물리적 메모리의 첫번째 프레임에 매핑
- 물리 주소와 커널 가상 주소 사이를 변환하는 함수
//물리적 주소에 해당하는 커널 가상 주소를 반환
#define ptov(paddr)
//커널 가상 주소에 해당하는 물리적 주소를 반환
#define vtop(vaddr)
🗒️ Pintos 가상 메모리 영역
//include/threads/vaddr.h
//include/threads/mmu.h
//커널 가상 메모리의 기본 주소
#define KERN_BASE 0x8004000000
- 사용자 가상 메모리 범위 = 0 ~ KERN_BASE
- 커널 가상 메모리 범위 = KERN_BASE ~ 나머지 공간
- 전역적이다.
- 항상 같은 방식으로 매핑된다.
- 모든 유저 프로세스의 가상 메모리의 커널 가상 메모리는 항상 동일하다.
728x90
'KraftonJungle2기 > Today I Learned' 카테고리의 다른 글
[TIL] Pintos Project1 - Threads 정리 (0) | 2023.06.28 |
---|---|
[TIL] Pintos - 가상 메모리 관련 개념 공부2 (0) | 2023.06.15 |
[TIL] 1377번 - 버블 정렬 (0) | 2023.06.07 |
[TIL] OS - System Call (0) | 2023.06.07 |
[TIL] OS 용어 정리 (0) | 2023.05.26 |