전체 글 (34) 썸네일형 리스트형 11. 운영체제 - Persistence(1) File and Directories File System : 디스크의 block 단위 인터페이스를 파일, 디렉토리 등의 인터페이스로 변환해주는 것 파일 시스템 특징 Disk Management : 디스크 블록을 파일로 모아 관리해줌. Naming : 이름을 이용해 파일을 찾을 수 있도록 해줌. Protection : 권한을 이용해 데이터를 보호함. Reliability/Durability : 파일을 영속적으로 저장함. 파일은 이름이 있는 영속적인 저장소로, 각 파일은 inode number라는 하위수준의 이름을 갖고있다. 그리고 유저는 상위레벨의 파일 이름만을 알고 inode number는 유저에게 노출되지 않는다. 파일은 디스크의 블록을 가리키는 데이터와 파일의 추가적인 정보들을 담고있는 메타데이터로.. 13. 자료구조론 - Hashing Hashing 해시 테이블은 특정 값을 삽입, 삭제, 탐색하는 것을 상수시간 내에 할 수 있게 해주는 자료구조입니다. 해시 테이블은 고정된 사이즈의 배열로 이루어져있고, 키값이 주어지면 해시 함수를 통해 배열의 인덱스로 맵핑됩니다. 이렇게 해시함수를 이용해 임의의 범위의 키값을 일정 범위 안으로 맵핑시켜 배열에 들어가도록 할 수 있습니다. 하지만 다른 키 값이더라도 해시함수에 통과시켰을 때 같은 값이 도출될 수 있는데, 이 경우 collision이 발생했다고 합니다. Collision의 해결 Collision을 해결하는 대표적인 두가지 방법이 있습니다. Separate chaining : 같은 인덱스로 맵핑되는 모든 키에 대한 값들을 리스트로 연결해두는 방법 Open addressing : 키가 충돌하면.. 12. 자료구조론 - Dijkstra's algorithm 다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점으로부터 다른 모든 정점으로의 최단 거리를 구하는 알고리즘입니다. 이때 그래프의 가중치는 음수이면 안됩니다. 음수인 가중치가 있으면 계속 해당 간선을 지나며 무한한 음수가 될 수 있기 때문입니다. 알고리즘 다익스트라 알고리즘에서 그래프의 각 노드의 상태는 다음 두 가지 중 하나입니다. 최단거리가 결정된 노드 아직 최단거리가 구해지지 않은 노드 알고리즘의 진행을 간단히 살펴보면 다음과 같습니다. 시작 정점 S로부터 각 정점 V로 가는 최단거리를 의미하는 d[V]를 초깃값으로 초기화해놓는다. 이때 초깃값은 어떤 최단거리보다도 큰 임의의 최댓값으로 설정해야함. 시작 정점 S에서 연결된 노드들의 d[V]를 간선의 가중치로 업데이트해준다. 모든 노드v에 대해 .. 10. 운영체제 - Memory Virtualization(5) Swapping 앞서 Memory Virtualization의 단순화를 위해 했던 가정들 중 Address space가 Physical memory 사이즈에 항상 다 들어갈 수 있다는 가정을 없애보자. 프로세스의 주소공간이 physical memory에 fit하지 않더라도 프로세스는 실행될 수 있어야한다. 이를 위해 HDD나 SDD같은 DRAM보다 싸고 큰 저장장치의 일부를 사용하여 조금 느리더라도 프로세스가 죽지 않고 실행될 수 있도록 하는 것이 Swapping 이다. Swap Space physical memory에 올라가지 못하고 밀려난 페이지들을 담아두기 위해 페이지와 같은 크기로 디스크에 swap space를 마련해둔다. 그리고 physical memory에 존재하지 않고 swap space에 .. 09. 운영체제 - Memory Virtualization(4) Paging Linear Table 보통 각 프로세스마다 하나의 page table을 가진다. 앞선 게시글에서 언급했던 것 처럼 32bit address space의 4KB 페이지, 4byte의 PTE 에서 페이지테이블의 사이즈는 4MB이다. 이 경우 Page table의 사이즈가 너무 크고 메모리를 너무 많이 잡아먹는다. Smaller Table 32bit address space를 16KB 의 페이지로 나누면, PTE의 개수가 2^16개로 줄어드므로 page table의 사이즈가 1MB로 줄어들지만, 페이지의 크기가 커지면 internal fragmentation이 더 많이 발생한다. Hybrid Approach page table의 메모리 오버헤드를 줄이기 위해 paging과 segmentation.. 08. 운영체제 - Memory Virtualization(3) Paging Segmentation의 문제점 앞선 게시글에서 다룬 Segmentation 방식으로 memory virtualization을 구현하는 것에는 문제점이 있다. segment의 사이즈가 가변이기 때문에 fragmentation으로 인한 공간의 낭비가 발생할 수 있다. 이때 external fragmentation은 할당된 chunk 사이의 작은 free space 구멍들 때문에 나타나고, internal fragmentation은 프로세스가 할당된 청크의 모든 공간을 사용하지 않기 때문에 발생한다. 이렇게 되면 physical memory가 낭비되고 utilization이 작아진다. (가용한 공간이 있어도 사용하지 못하는 문제) segment의 사이즈를 줄여 fine-grained segmen.. 07. 운영체제 - Memory Virtualization(2) Segmentation Base-and-Bounds Approach 앞선 게시글의 base-and-bounds 방법에는 문제점이 있다. 이전에 단순화를 위해 가정했던 "모든 프로세스가 같은 사이즈이다" 라는 가정을 제거해보자. 프로세스의 주소공간을 physical memory에도 연속적으로 올리기 때문에 base와 bound만 알면 되었고, 모든 프로세스가 같은 사이즈라면 다른 프로세스가 종료되어 생긴 free space를 또 다른 프로세스가 그대로 채워줄 수 있기 때문에 문제되지 않았다. 하지만 위의 가정이 없어지면 큰 프로그램을 올릴 때 문제가 생긴다. 그만큼의 연속된 free space가 physical memory에 존재하지 않으면 프로그램을 올리기 힘들어진다. 또한 중간중간 작고 분산된 free.. 06. 운영체제 - Memory Virtualization(1) OS는 CPU뿐만 아니라 physical memory 또한 가상화한다. 이를 통해 OS는 각 프로세스에게 독립적인 메모리공간을 사용하는 것과 같은 착각을 준다. (각 프로세스가 전체 메모리를 사용하는 것과 같이 만들어줌) Memory Virtualization의 이점 프로세스마다 메모리 공간을 관리하지 않아도 되기 때문에 프로그래밍을 쉽게 할 수 있다. 프로세스를 잘못된 접근으로부터 보호할 수 있다. 시/공간 측면에서 효율적이다. (아래 과거 OS와의 차이를 비교해보면 알 수 있음) OS in the Early System 초창기 OS는 메모리에 단 하나의 프로세스만을 올렸다. 이렇게 되면 프로세스가 메모리를 조금만 사용하더라도 모든 메모리를 프로세스에게 할당해주어야하기 때문에 utilization 측면.. 이전 1 2 3 4 5 다음
