크래프톤 정글 TIL : 0921

lazyArtisan·2024년 9월 21일
TIL
0

정글 TIL

목록 보기
83/147

📝 배운 것들

🏷️ mmap

mmap(2)에 있는 2의 의미 : 시스템 콜이라는 뜻

mmap(2) 분류 : 파일 매핑, 익명 매핑

파일 매핑 (File Mappings)

  • 파일 기반 매핑은 디스크에 있는 파일을 메모리에 매핑하여, 프로세스가 메모리에서 해당 파일을 읽거나 쓸 수 있게 하는 방식입니다. 즉, 파일의 내용이 메모리로 올라와서 프로세스가 파일을 직접 접근하는 것처럼 메모리에서 그 데이터를 접근할 수 있습니다.
  • 사용 예: 라이브러리 파일, 실행 파일의 섹션 등이 메모리에 매핑될 때.

익명 매핑 (Anonymous Mappings)

  • 익명 매핑은 파일과 연결되지 않은 메모리 영역을 생성합니다. 이름처럼 익명(anonymous)이라는 것은 실제로 파일을 사용하지 않기 때문에, 메모리의 해당 부분이 외부의 파일과 연결되지 않음을 뜻합니다. 이 매핑은 프로세스의 힙(heap)이나 스택(stack)처럼 주로 파일과 무관한 메모리 공간에 사용됩니다.
  • 사용 예: 프로그램 실행 시 동적으로 할당되는 메모리(힙, 스택 등).

mmap(2) 동작 모드 : 공유 매핑, 개인 매핑

SHARED (공유 매핑)

  • 공유 매핑에서는 메모리의 변경 내용이 실제 파일이나 다른 프로세스에 공유됩니다. 예를 들어, 파일 기반의 SHARED 매핑에서는 프로세스가 매핑된 메모리에서 데이터를 변경하면 파일에도 직접 반영됩니다.
  • 사용 예: 프로세스 간에 파일을 공유하거나, 파일의 내용을 다른 프로세스와 공유할 때.

PRIVATE (개인 매핑)

  • 개인 매핑에서는 메모리의 변경 내용이 프로세스 내에서만 유지됩니다. 파일 기반의 PRIVATE 매핑에서는 메모리에서 파일 데이터를 읽을 수는 있지만, 변경사항은 파일에 반영되지 않고 해당 프로세스에만 영향을 미칩니다.
  • 사용 예: 프로세스가 파일의 데이터를 읽되, 수정이 파일에 반영되지 않도록 할 때.


🖥️ PintOS

🔷 Virtual Memory

📌 키워드 정리

Virtual Memory : 물리 메모리 공간의 제약, 메모리 단편화, 보안을 위해 OS가 프로세스에게 제공하는 주소. 이를 통해 프로세스에게 자신이 메모리를 독점하고 있다는 환상을 제공한다.

Page Table : 각 가상 메모리 주소가 어떤 물리 메모리 주소에 매핑돼있는지 적혀있는 테이블. 그 밖에도 읽기 권한 등 해당 페이지에 대한 정보가 적혀있다.

Translation Lookaside Buffer(TLB) : MMU(Memory Management Unit)가 가상 주소를 물리 주소로 변환할 때 TLB라는 캐시에서 변환 정보를 읽어온다.

Page Fault : 메모리는 페이지 단위로 나뉜다. 프로세스가 메모리에 접근하면 가상 주소가 물리 주소로 변환된다. 주소는 페이지 단위로 요청한다. 이때 요청한 페이지가 메모리의 물리 메모리에 없고 디스크(스왑 영역)에 있다면 페이지 폴트가 발생한다. 페이지 폴트 발생하면 Trap 발생함.

Trap : 오류 발생하거나 시스템 콜 요청하면 일어남. 커널 모드로 전환돼서 트랩 핸들러 실행.

스왑 공간 : 물리 메모리 꽉 찼을 때 메모리 데이터를 디스크에 임시로 저장하는 공간
https://www.geeksforgeeks.org/swap-space-in-operating-system/

Major Page Fault: 페이지가 물리 메모리에 없고 디스크의 스왑 영역에 있는 경우. Disk I/O가 발생하여 성능에 영향을 미침.
Minor Page Fault: 페이지가 물리 메모리에 있으나, 페이지 테이블에 반영되지 않은 경우. Disk I/O 없이 페이지 테이블만 업데이트함.
Invalid Page Fault: 잘못된 메모리 참조 시 발생하며, 세그멘테이션 폴트가 발생할 수 있음.

Lazy Loading : 웹 개념인듯. 처음 웹페이지 로딩할 때 유저가 필요한 것만 로딩하고, 나중에 요청하면 해당하는 부분을 마저 로딩하는 거.

Demand Paging : 시작할 때 물리 메모리에 프로그램을 전부 다 로드하는게 아니라 요청할 때 필요한 페이지만 로드하는거. 그래서 처음 로딩할 땐 페이지 폴트난다. 물리 메모리 주소 공간 아낄 순 있는데 disk I/O 때문에 성능이 느려진다.
https://www.geeksforgeeks.org/what-is-demand-paging-in-operating-system/

페이지 교체 알고리즘

  • First In First Out (FIFO) : 제일 먼저 온 놈이 빠짐
  • Optimal Page replacement : '미래에' 제일 적게 사용될 놈 빠짐 (현실에선 불가능)
  • Least Recently Used : 최근에 제일 적게 사용된 놈 빠짐
  • Most Recently Used (MRU) : 가장 최근에 사용된 놈 빠짐

Belady’s Anomaly : 페이지 수 늘어나면 페이지 폴트 횟수도 늘어난다

Anonymous page : 파일로 백업되지 않아서 파일과 연결되지 않고 순수하게 메모리만 사용하는 페이지. 힙과 스택 같은 동적 메모리 할당에서 사용됨. 파일과 관련이 없기 때문에 물리 메모리가 꽉 차면 익명 페이지는 스왑 공간으로 간다. (파일 매핑된 이미지는 파일에서 다시 읽어오면 됨)
https://stackoverflow.com/questions/13024087/what-are-memory-mapped-page-and-anonymous-page

DMA (Direct Memory Access) : 입출력 장치가 CPU를 거치지 않고 메모리에 직접 접근하여 데이터를 전송하는 기능. 사실 CPU가 아예 개입 안 하는건 아니고 DMA 컨트롤러한테 어디 가서 얼마만큼 전송하라고 명령은 내린다.



📖 OSTEP

13. 주소 공간의 개념

초기 컴퓨터는 물리 메모리 주소 일정 부분은 운영체제, 일정 부분은 현재 프로그램을 담음.

나중에 시분할 구현하긴 했는데 하나의 프로세스를 짧게 실행시킨 다음 죄다 디스크(물리 메모리 포함)에 적재하고 또 다음 거 실행하고 죄다 적재해서 느렸다. (요즘은 필요한 것만 왔다갔다)

대화식 이용(interactivity) : 현재 실행 중인 작업으로부터 즉시 응답

프로세스가 다른 프로세스 안 터트리게 하려고 주소 공간 만들었다.

프로그램 코드는 반드시 메모리에 있어야 되고
스택은 함수 호출 체인 상의 현재 위치, 지역 변수, 함수 인자와 반환 값 등을 저장. 높은 주소에서 낮은 주소로 자란다.
힙은 동적으로 할당되는 메모리. 낮은 주소에서 높은 주소로 자란다.
(근데 이것들은 가상 주소고 실제로는 임의의 물리 주소에 적재됨)

물리 메모리를 공유하는 다수의 프로세스에게 프로세스 전용의 커다란 주소 공간이라는 개념을 제공하는 방법 : 야 이거 네꺼야 하고 가상 메모리 주소 공간 준 다음에 실제로는 그렇게 예쁘게 안 주고 맘대로 물리 메모리 할당했다가 할당 취소했다가 함.

격리 : 한 개체가 실패하더라도 상대 개체에 아무 영향을 안 준다

가상 메모리 주요 목표

  • 투명성: 실행 중인 프로그램이 가상 메모리의 존재를 인지 못하도록
  • 효율성: 시간 공간 측면에서 효율적
  • 보호: 다른 프로세스로부터 프로세스를 보호, 운영체제 자신도 보호

14. 막간: 메모리 관리 API

UNIX 메모리 관리 인터페이스 알아볼 것

C 프로그램이 실행되면 두 가지 유형의 메모리 공간이 할당됨.
첫번째는 스택임. 함수 안에서 int x; 선언하면 정수 x를 위한 메모리 선언됨. 함수가 리턴하면 컴파일러가 메모리 반환해줌. 함수 리턴 이후에도 유지돼야 하는 정보는 스택에 저장하지 않는게 좋음.
두번째는 힙임. 오랫동안 값이 유지돼야 하는 변수를 위한 공간임. 모든 할당과 반환이 프로그래머에 의해 명시적으로 처리됨.

malloc() : 바이트 단위로 필요 공간 크기 적어줘야 됨. sizeof() 함수 써라. 문자열을 위한 공간 선언할 땐 +1 해줘야 문자열 끝 나타내는 문자도 저장됨. void * 타입을 반환하므로 프로그래머가 필요한 타입으로 변환해줘야됨.

자주 저지르는 실수

  • 메모리 할당 까먹음 : 할당 안한 다음 접근하면 segmentation fault 일어남.
  • 메모리 부족하게 할당받기 : 버퍼 오버플로우 일어남.
  • 할당받은 메모리 초기화 안 하기 : 새로 할당받은 데이터 타입에 값 넣는거 잊음.
  • 메모리 해제하지 않기 : 메모리 누수 일어나서 결국 메모리 부족해짐. 프로세스 종료되면 다 반환되긴 함.
  • 메모리 사용 끝나기 전에 메모리 해제 : dangling pointer
  • 반복적으로 메모리 해제 : 이중 해제. 메모리 할당 라이브러리가 온갖 이상한 짓 하게 됨. 가장 흔하게는 그냥 크래시 남.
  • free 잘못 호출 : malloc() 받은 포인터만 전달해야되는게 이상한 포인터 전달함.

malloc()이랑 free()는 시스템 콜은 아니고 라이브러리 함수임.
시스템 콜은 brk 같은 거임. 프로그램의 break 위치를 변경하는 데 사용됨.
break는 힙의 마지막 위치를 나타냄.
brk는 새로운 break 주소를 나타내는 한 개의 인자를 받고 그거대로 힙 크기를 변경함.
sbrk는 증가량만 받아들임.

brk나 sbrk 직접 호출하지는 마라. 큰일난다.

mmap() 함수로 운영체제로부터 메모리를 얻을 수도 있다.
프로그램에 anonymous 메모리 영역을 만든다.
anonymous 영역은 특정 파일과 연결되어 있지 않고 스왑 공간에 연결된 영역을 말한다.

15. 주소 변환의 원리

base and bound
1950년대 후반 첫 번째 시분할 컴퓨터에서 사용됨
물리 주소 = 가상 주소 + 베이스 주소
프로세스가 실행을 시작한 이후에도 주소 공간을 이동하는 동적 재배치(dynamic relocation) 사용함.
바운드 레지스터는 메모리 참조가 합법적인가를 확인한다.

프로세스 구조체(process structure), 프로세스 제어 블럭(process control block, PCB) : 베이스와 바운드 레지스터 값 저장

내부 단편화 : 남아있는 메모리가 충분한데 연속적으로 할당 안돼있어서 할당 못해서 공간 낭비되는거

base and bound 일반화시킨게 세그멘테이션



⚔️ 백준

📌 29773 2023년은 검은 토끼의 해 (Hard)

# 각 자리수를 순회하며
# 1. 1이라면 나머지 자리수에 2023 꽂아넣는 경우의 수
# 2. 2라면 (나머지 자리수에 023 꽂아넣는 경우의 수) + (나머지 자리수에 2023 꽂아넣는 경우의 수)
# 3. 3이상이라면 (나머지 자리수에 023 꽂아넣는 경우의 수) + (자기 자신 - 1) (나머지 자리수에 2023 꽂아넣는 경우의 수)
# 다 더한게 경우의 수

# 숫자가 들어갈 자리 3개만 고르면 순서는 알아서 정해지므로 cntC3 구하면 됨
# cntC3 = cnt(cnt-1)(cnt-2)/6
# 4개면 cntC4 = cnt(cnt-1)(cnt-2)(cnt-3)/12

# (나머지 자리수에 023 꽂아넣는 경우의 수)에 9**(cnt-4) 곱해줘야됨
# (나머지 자리수에 2023 꽂아넣는 경우의 수)에 9**(cnt-5) 곱해줘야됨

N=input()
L=len(N)
cnt=len(N)
res=0

while cnt>3:
    now=L-cnt
    case1=(cnt-1)*(cnt-2)*(cnt-3)*(cnt-4)/12 * (9**(cnt-4)) # 나머지에 2023
    case2=(cnt-1)*(cnt-2)*(cnt-3)/6 # 나머지에 023
    if not (cnt == 4):
        case2*=9**(cnt-5)

    if N[now]=='1':
        res+=case1
    elif N[now]=='2':
        res+=case1
        res+=case2
    else:
        res+=case1
        res+=(int(N[now])-1)*case2
    cnt-=1
print(int(res))

1번째 시도

# 각 자리수를 순회하며
# 1. 1이라면 나머지 자리수에 2023 꽂아넣는 경우의 수
# 2. 2라면 (나머지 자리수에 023 꽂아넣는 경우의 수) + (나머지 자리수에 2023 꽂아넣는 경우의 수)
# 3. 3이상이라면 (나머지 자리수에 023 꽂아넣는 경우의 수) + (자기 자신 - 1) (나머지 자리수에 2023 꽂아넣는 경우의 수)
# 다 더한게 경우의 수

# 숫자가 들어갈 자리 3개만 고르면 순서는 알아서 정해지므로 cntC3 구하면 됨
# cntC3 = cnt(cnt-1)(cnt-2)/6
# 4개면 cntC4 = cnt(cnt-1)(cnt-2)(cnt-3)/12

# (나머지 자리수에 023 꽂아넣는 경우의 수)에 9**(cnt-4) 곱해줘야됨
# (나머지 자리수에 2023 꽂아넣는 경우의 수)에 9**(cnt-5) 곱해줘야됨

N=input()
L=len(N)
cnt=len(N)
res=0

while cnt>3:
    case=(cnt-1)*(cnt-2)*(cnt-3)/6 # 나머지에 023
    case*=(9**(cnt-4))
    temp = (int(N[L-cnt])-1)*case
    res+=(int(N[L-cnt])-1)*case
    cnt-=1
print(int(res))

2번째 시도

1시간 가까이 지나서 일단 마무리. 핀토스 해야됨.
내일 마저 풀어볼 것.

profile
lazyArtisan
이전 포스트

크래프톤 정글 TIL : 0920

다음 포스트

크래프톤 정글 TIL : 0922

0개의 댓글