🖥️ PintOS
📌 권영진 교수님 PintOS 특강
간단한 복습
가상 주소를 물리 주소로 변환하는 데에 쓰이는 자료구조 : 페이지 테이블
가상 주소를 물리 주소로 변환하는 부품 : mmu
페이지 폴트 나면 물리 주소 할당하는 방법 : 디맨드 페이징
anonymous memory : 0으로 초기화
i/o 장치가 메모리 직접 접근 : dma
CPU가 제어권 뺏어오기 : 인터럽트
File System
자주 접근되는 데이터를 DRAM으로 올려놓으면 DRAM 속도로 데이터를 읽을 수 있음
page cache는 어느 레이어에서 구현돼있는가? : vfs - posix api, file system 두 레이어 모두에 가능하지만 공통되게 사용할 수 있도록 다들 vfs에서 구현.
DRAM에 있는 최신 데이터를 주저장장치와 동기화시켜야 하는 문제.
저장할 때 주저장장치로 보내면 됨
근데 쉽지가 않음
중간에 crash나면 데이터나 메타데이터 둘 중 하나가 제대로 저장 안 될 수 있음
inconsistent 해결 : 분량 기니까 ostep 책에서 journaling 기법 찾아볼 것
data의 여러 블럭들을 저장할 때 그것들이 온전하게 저장되는지
file system을 만드는 프로그래머들이 확인해줘야 함
저장 전(Bar)과 저장 후(Foo) 2가지 atomic한 상태 뿐
대충 write 써버리면 (한꺼번에 보내면) atomic하지 않게 저장된다. 일부분만 저장됨
logging할 때 log 파일 저장과 file 저장의 순서가 바뀔 수 있음
fsync해서 order을 맞춰줘야 함
하나 빼먹으면 로그 unlink해버림
리눅스에선 디렉토리도 file이라 생성이 안될 수가 있음
그래서 디렉토리에도 fsync를 먹여줘야 한다
file system에 있는 journaling 키면 이것들 해주긴 하는데 너무 느림.
그래서 프로그래머가 직접 구현해줘야 됨.
Isolation & Security
함부로 메모리 접근하게 하면 문제들 생김
프로세스 사이, OS와 유저프로그램 사이 선 그어서 Protection
어떻게 protection?
- app이 중요한 명령어는 실행 못하게 막아야 된다. -> 유저 모드 / 커널 모드
- app이 다른 app 메모리 못 건드리게 해야된다 -> memory protection (가상 메모리)
- OS가 contorl을 주기적으로 계속 얻어야 된다 -> 타이머 인터럽트
os보다 cpu가 privilege가 높은 이유? 이전의 명령을 verify할 수 있다 (과장, 부장, 부서장)
ring으로 나눠서 바깥쪽에 있는 놈이 안쪽 access하려고 하면 하드웨어가 reject
write read bit, 커널 주소인지 유저 주소인지
verify하고 protection
intel은 2가지로 나뉨 (바뀌긴 했는데 남아있으니까 설명)
sementation, paging
DPL이 ring을 의미
부트로더가 커널 로딩할 때 커널 코드 올려놓고 DPL을 0 0 선언
app 올릴 땐 1 1
1 1에 있는 놈이 0 0에 있는거 접근하면 세그멘테이션 폴트 (privilege rule 위반)
페이지 테이블에 적힌 권한 정보 : User/Supervisor 1인지 0인지
web server process
php process 분리
성능과 protection trade-off해서 프로세스 나눈다
컨텍스트 스위치로 address space를 바꾸는 식으로 Isolation
file isolation은 file permission system으로 구현
open은 시스템 콜. 열어도 되냐 안되냐 확인
Reference Monitor (RM) 이 Policy Store에서 정책 보고 파일 열어도 되는지 안되는지 결정
755 : 이 파일을 소유하고 있는 유저가 만든 프로세스는 rax에 접근할 수 있다
분량이 길어서 self study하쇼
IPC
- pipe, socket : 정보 주고받는 통로 만들기
- shared memory : 일부 영역만 같은 물리 주소 매핑
서로 다른 프로세스가 같은 내용을 볼 때 똑같이 유지하려면
cache coherence
파이프에 카피했다가 하면 동기화 문제를 해결할 수 있어서 구현이 쉬움
messeage passing이 구현이 쉬운데
shared memory는 속도가 critical할 때
sharing
time sharing : cpu -> scheduling
space sharing : memory -> page replacement (page eviction + swap)
preemptive : 유저가 쓰는거 (반응속도 빠르다)
non preemptive : 서버 (쓰루풋 좋다)
FIFO
pro : easy to implement
con : convoy effect (작업 시간 짧은 놈이 오래 기다림)
SJF (Shortest Job First)
pro : No convoy effect
con : starvation
Round robin
pro : no starvation
con : bad turnaround time (특정 프로젝트에 걸리는 작업 시간)
장단점
victim page selection
page fault count가 좋은 알고리즘에 대한 지표
cache miss 수
앞으로 얼마나 쓰일지 알면 oracle인데 불가능
Least Recent Used : 과거에 얼마나 쓰였는지 기준으로 판단 (그 중에서도 가장 최근에 접근한 페이지가 중요)
시간 지역성 : 최근에 쓴거 또 쓴다
공간 지역성 spatial locality : 쓴거 근처에 있는거 쓴다
time locality의 이유 : loop 써서
spatial locality : array 써서
페이지들을 linked list로 구현하면 LRU로 만들 때 문제. 모든 access마다 page fault를 일으킴. 그래서 굉장히 비쌈.
Clock은 page fault 없고 LRU를 approximate한다
⚔️ 백준
📌 2573 빙산
# 가다가 빙산 만나면 bfs로 다 칠해버리는데
# 마저 순회하다가 빙산 덩어리 수가 2개 되면 날짜 출력
# 순회 다 끝냈으면 빙산 녹이기
N,M=map(int,input().split())
arctic=[list(map(int,input().split())) for _ in range(N)]
year = 0
dx, dy = [1,-1,0,0], [0,0,1,-1]
while 1:
year+=1
visitied=[[False for _ in range(M)] for _ in range(N)]
# 빙산 세기
ice_cnt=0
for i in range(N):
for j in range(M):
if not visitied[i][j] and arctic[i][j] > 0:
ice_cnt += 1
stack = [(i,j)]
while stack: # bfs 때려버리기
x, y = stack.pop()
visitied[x][y] = True
for k in range(4):
if 0<x+dx[k]<N and 0<y+dy[k]<M and arctic[x+dx[k]][y+dy[k]]>0 and not visitied[x+dx[k]][y+dy[k]]:
visitied[x+dx[k]][y+dy[k]] = True
stack.append((x+dx[k],y+dy[k]))
if ice_cnt > 1:
break
# 빙산 녹이기
stack=[]
for i in range(N):
for j in range(M):
if arctic[i][j]>0:
melt=0
for k in range(4):
if 0<=x+dx[k]<N and 0<=y+dy[k]<M and arctic[x+dx[k]][y+dy[k]]==0:
melt+=1
stack.append((i,j,melt))
while stack:
i,j,melt = stack.pop()
arctic[i][j] -= melt
if arctic[i][j] < 0:
arctic[i][j] = 0
print(year) 시간 초과 당함
합치긴 했는데 x,y가 아니라 i,j로 담아서 한 곳에 몰빵당하는 바보짓 (바로 전에는 x=x+d[k],y=y+d[k]로 업데이트를 해버려서 매번 이상하게 움직여버림)
# 가다가 빙산 만나면 bfs로 다 칠해버리는데
# 마저 순회하다가 빙산 덩어리 수가 2개 되면 날짜 출력
# 순회 다 끝냈으면 빙산 녹이기
N,M=map(int,input().split())
arctic=[list(map(int,input().split())) for _ in range(N)]
iceberg=[]
year = 0
dx, dy = [1,-1,0,0], [0,0,1,-1]
melting=[]
while 1:
visitied=[[False for _ in range(M)] for _ in range(N)]
# 빙산 세기
ice_cnt=0
for i in range(N):
for j in range(M):
if not visitied[i][j] and arctic[i][j] > 0:
ice_cnt += 1
stack = [(i,j)]
while stack: # bfs 때려버리기
x, y = stack.pop()
visitied[x][y] = True
melt=0
for k in range(4):
near_x, near_y = x+dx[k], y+dy[k]
if 0<=x<N and 0<=y<M:
if arctic[near_x][near_y]>0 and not visitied[near_x][near_y]:
visitied[near_x][near_y] = True
stack.append((near_x,near_y))
elif arctic[near_x][near_y]<=0:
melt+=1
melting.append((x,y,melt))
if ice_cnt > 1:
break
year+=1
# 빙산 녹이기
while melting:
i,j,melt=melting.pop()
arctic[i][j]-=melt
print(year)이것도 시간초과 당해버림.
if 0<=x<N and 0<=y<M:
if arctic[near_x][near_y]>0 and not visitied[near_x][near_y]:
visitied[near_x][near_y] = True
stack.append((near_x,near_y))
elif arctic[near_x][near_y]<=0:
melt+=1
melting.append((x,y,melt))
if ice_cnt > 1:
break
if ice_cnt > 1:
break
if ice_cnt > 1:
break억지 최적화도 해봤는데 이것도 통과가 안됨.
while stack: # bfs 때려버리기
x, y = stack.pop()
visitied[x][y] = True
melt=4
for k in range(4):
near_x, near_y = x+dx[k], y+dy[k]
if 0<=x<N and 0<=y<M:
if arctic[near_x][near_y]>0:
melt-=1
if not visitied[near_x][near_y]:
visitied[near_x][near_y] = True
stack.append((near_x,near_y))내가 할 수 있는 최대한의 최적화 했는데 계속 시간초과 뜸.
분명 판떼기 한 번 순회할 때 최대 10만개뿐인데 왜지;
순회를 전부 다 돌아버리면 칼같이 시간초과시켜버리는듯.
빙산 정보 기준으로 필요한 것만 순회돌면 될듯?
# 가다가 빙산 만나면 bfs로 다 칠해버리는데
# 마저 순회하다가 빙산 덩어리 수가 2개 되면 날짜 출력
# 순회 다 끝냈으면 빙산 녹이기
from collections import deque
N,M=map(int,input().split())
arctic=[list(map(int,input().split())) for _ in range(N)]
icebergs=deque()
for i in range(N):
for j in range(M):
if arctic[i][j] > 0:
icebergs.append((i,j))
year = 0
dx, dy = [1,-1,0,0], [0,0,1,-1]
melting=[]
while 1:
visitied=[[False for _ in range(M)] for _ in range(N)]
ice_cnt=0
# 빙산 순회하다가
for ice in icebergs:
x,y = ice
# 빙산 만나면 bfs해서 방문 다 때려버리기
if arctic[x][y] > 0 and not visitied[x][y]:
ice_cnt+=1
stack=[(x,y)]
while stack:
a,b = stack.pop()
# 빙산 있고 방문 안했으면 방문때리기. 녹일 정보도 기록해두기.
melt=0
for k in range(4):
i,j = a+dx[k], b+dy[k]
if 0<=i<N and 0<=j<M:
if arctic[i][j] > 0 and not visitied[i][j]:
visitied[i][j] = True
stack.append((i,j))
elif arctic[i][j] <= 0:
melt+=1
melting.append((a,b,melt))
if ice_cnt > 1:
break
year+=1
# 빙산 녹이기
while melting:
i,j,melt=melting.pop()
arctic[i][j]-=melt
print(year)
20몇퍼에서 틀렸습니다 뜸
"만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다." 아 이거 놓쳤네
# 가다가 빙산 만나면 bfs로 다 칠해버리는데
# 마저 순회하다가 빙산 덩어리 수가 2개 되면 날짜 출력
# 순회 다 끝냈으면 빙산 녹이기
from collections import deque
N,M=map(int,input().split())
arctic=[list(map(int,input().split())) for _ in range(N)]
icebergs=deque()
for i in range(N):
for j in range(M):
if arctic[i][j] > 0:
icebergs.append((i,j))
year = 0
dx, dy = [1,-1,0,0], [0,0,1,-1]
melting=[]
while 1:
visited=[[False for _ in range(M)] for _ in range(N)]
ice_cnt=0
is_there_any_ice = False
ty_ice = len(icebergs)
# 빙산 순회하다가
for _ in range(ty_ice):
x,y = icebergs.popleft()
# 빙산 만나면 bfs해서 방문 다 때려버리기
if arctic[x][y] > 0 and not visited[x][y]:
icebergs.append((x,y))
is_there_any_ice = True
ice_cnt+=1
stack=[(x,y)]
while stack:
a,b = stack.pop()
# 빙산 있고 방문 안했으면 방문때리기. 녹일 정보도 기록해두기.
melt=0
for k in range(4):
i,j = a+dx[k], b+dy[k]
if 0<=i<N and 0<=j<M:
if arctic[i][j] > 0 and not visited[i][j]:
visited[i][j] = True
stack.append((i,j))
elif arctic[i][j] <= 0:
melt+=1
melting.append((a,b,melt))
elif arctic[x][y] > 0:
icebergs.append((x,y))
if not is_there_any_ice:
year=0
break
if ice_cnt > 1:
break
year+=1
# 빙산 녹이기
while melting:
i,j,melt=melting.pop()
arctic[i][j]-=melt
print(year)
예외조건도 추가하고 최적화도 내가 할 수 있는 극한으로 했는데
틀렸습니다 떠서 테케 만들어서 디버깅 돌려보니까
3 3
0 2 0
2 1 2
0 2 0이 테케에서
뭔가 빙하가 이상하게 녹고 있었음
맨 처음 방문한 시작 빙하의 방문 체크를 안해줘서 한 번 더 녹고 있었던 것.
# 가다가 빙산 만나면 bfs로 다 칠해버리는데
# 마저 순회하다가 빙산 덩어리 수가 2개 되면 날짜 출력
# 순회 다 끝냈으면 빙산 녹이기
from collections import deque
N,M=map(int,input().split())
arctic=[list(map(int,input().split())) for _ in range(N)]
icebergs=deque()
for i in range(N):
for j in range(M):
if arctic[i][j] > 0:
icebergs.append((i,j))
year = 0
dx, dy = [1,-1,0,0], [0,0,1,-1]
melting=[]
while 1:
visited=[[False for _ in range(M)] for _ in range(N)]
ice_cnt=0
is_there_any_ice = False
ty_ice = len(icebergs)
# 빙산 순회하다가
for _ in range(ty_ice):
x,y = icebergs.popleft()
# 빙산 만나면 bfs해서 방문 다 때려버리기
if arctic[x][y] > 0 and not visited[x][y]:
icebergs.append((x,y))
is_there_any_ice = True
ice_cnt+=1
stack=[(x,y)]
while stack:
a,b = stack.pop()
visited[a][b] = True
# 빙산 있고 방문 안했으면 방문때리기. 녹일 정보도 기록해두기.
melt=0
for k in range(4):
i,j = a+dx[k], b+dy[k]
if 0<=i<N and 0<=j<M:
if arctic[i][j] > 0 and not visited[i][j]:
visited[i][j] = True
stack.append((i,j))
if arctic[i][j] <= 0:
melt+=1
melting.append((a,b,melt))
elif arctic[x][y] > 0:
icebergs.append((x,y))
if not is_there_any_ice:
year=0
break
if ice_cnt > 1:
break
year+=1
# 빙산 녹이기
while melting:
i,j,melt=melting.pop()
arctic[i][j]-=melt
print(year)
고쳤더니 통과.
코드도 더럽고
저번에 풀 때처럼 예외조건 제대로 안 읽었었고
30분 안에 여유롭게 풀어야 하는 골드 4 문제를
2시간 조금 안되게 걸려서 풀어냈지만
저번에는 도저히 못 풀 것만같은 절망감을 느끼며
이틀에 걸쳐 겨우겨우 풀어냈었고
이번에는 푸는 건 당연한거니 틀려도 당황할 필요 없다는 마인드로 풀었다.
거기에 공간도 시간도 훨씬 더 최적화를 할 수 있었다
성장했다는 뜻.
다음번엔 더 빠르고 깔끔하게 풀 수 있는 사람이 되자.
그러기 위해선 일단 자잘한 실수를 많이 줄여야 함.
내가 이것을 왜 하는지? 그리고 어떻게 하면 깔끔하게 내가 잘 알아볼 수 있는 코드를 짤 수 있을지 생각하며 풀 것.
아 근데 백준에 제출된 다른 사람들 코드 보니까 아직 멀었다는 생각도 든다
나보다 깔끔하고 짧고 빠르게 잘 짜는 사람들 많네
from collections import deque
import sys
N,M = map(int,sys.stdin.readline().split())
directions = [(0,1),(1,0),(-1,0),(0,-1)]
northpole = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
que = deque([])
def find_iceberg():
for i in range(N):
for j in range(M):
if northpole[i][j]!=0 and visited[i][j]==0:
que.appendleft((j,i))
visited[i][j]=1
return True
return False
def bfs():
iceberg = 0
while True:
flag = find_iceberg()
if flag:
iceberg += 1
while que:
x,y = que.popleft()
count=0
for dx,dy in directions:
nx,ny = x+dx,y+dy
if northpole[ny][nx]!=0 and visited[ny][nx]==0:
que.append((nx,ny))
visited[ny][nx]=1
if northpole[ny][nx]==0 and visited[ny][nx]==0:
count+=1
northpole[y][x]-=count
if northpole[y][x]<0: northpole[y][x]=0
flag = False
else: break
return iceberg
year = 0
while True:
visited = [[0]*M for _ in range(N)]
iceberg = bfs()
if iceberg>=2:
print(year)
break
if iceberg==0:
print(0)
break
year+=1이 사람 코드 좀 멋있게 잘 짠듯.
시간도 내 반절 정도.
