UNIX 운영 체제의 설계 - Chapter 4. 파일의 내부 표현

Presentation on theme: "UNIX 운영 체제의 설계 - Chapter 4. 파일의 내부 표현"— Presentation transcript:

1 UNIX 운영 체제의 설계 - Chapter 4. 파일의 내부 표현
안 재 윤

2 목차 Ⅰ 슈퍼 블럭 Ⅱ 새로운 파일의 i-node 할당과 반환 Ⅲ 디스크 블록의 할당과 반환

3 Ⅰ 슈퍼 블럭 Ⅱ 새로운 파일의 i-node 할당과 반환 Ⅲ 디스크 블록의 할당과 반환

4 슈퍼 블럭 File System File System File System Super Block Super Block
파일 시스템의 크기 파일 시스템 내의 프리 블럭의 수 파일 시스템 내에서 사용 사능한 프리블럭 리스트 프리 블럭 리스트 중의 다음 프리 블럭에 관한 인덱스 i-node 리스트의 크기 파일 시스템 내에서 사용 가능한 프리 i-node의 수 파일 시스템 중의 프리 i-node 리스트 프리 i-node 중에서 다음 프리 i-node에 관한 인덱스 프리 블럭과 프리 i-node의 리스트를 위한 잠금 필드 슈퍼 블럭이 수정 되었음을 표시하는 플래그

5 슈퍼 블럭 File System File System File System Super Block Super Block
슈퍼 블록은 파일에 i-node를 할당 할 때나, 새로운 블록을 할당할 때 적절한 블록을 찾아서 할당할 수 있도록 해준다. 슈퍼 블록이 수정 되어 지면 커널은 슈퍼 블록을 주기적으로 디스크에 저장 함으로써, 실제 데이터와의 일관성을 유지한다.

6 Ⅰ 슈퍼 블럭 Ⅱ 새로운 파일의 i-node 할당과 반환 Ⅲ 디스크 블록의 할당

7 새로운 파일의 i-node 할당과 반환 슈퍼 블럭 . . . . . 커널은 i-node 리스트를 선형 리스트 형태로 관리한다.
프로세스간의 동시 접근을 막기 위한 필드이다. 프리 i-node 리스트 프리 i-node 총 갯수 잠금 필드 . . 커널은 i-node 리스트를 선형 리스트 형태로 관리한다. 어떤 i-node의 형태 필드가 0이면 이는 미사용 상태를 의미한다. 프로세스가 i-node가 필요하면, iget 알고리즘을 이용하여 비어있는 아이노드의 번호를 찾고, ialloc 알고리즘을 이용하여 해당 프로세스에 i-node를 할당한다. 이론적으로는 비어있는 i-node를 찾기 위해 커널이 모든 i-node를 적어도 1회의 읽기 동작을 해야 하지만, 이러한 부담을 덜기 위해 슈퍼 블록에는 프리 i-node 번호를 캐쉬하고 있는 배열이 포함 되어 있다. . . .

8 새로운 파일의 i-node 할당과 반환 슈퍼 블럭 . . . . . 커널은 i-node 리스트를 선형 리스트 형태로 관리한다.
프로세스간의 동시 접근을 막기 위한 필드이다. 프리 i-node 리스트 프리 i-node 총 갯수 잠금 필드 . . 커널은 i-node 리스트를 선형 리스트 형태로 관리한다. 어떤 i-node의 형태 필드가 0이면 이는 미사용 상태를 의미한다. 프로세스가 i-node가 필요하면, iget 알고리즘을 이용하여 비어있는 아이노드의 번호를 찾고, ialloc 알고리즘을 이용하여 해당 프로세스에 i-node를 할당한다. 이론적으로는 비어있는 i-node를 찾기 위해 커널이 모든 i-node를 적어도 1회의 읽기 동작을 해야 하지만, 이러한 부담을 덜기 위해 슈퍼 블록에는 프리 i-node 번호를 캐쉬하고 있는 배열이 포함 되어 있다. . 프로세스가 i-node가 필요하면, 비어있는 i-node의 번호를 찾고, ialloc 알고리즘을 이용하여 해당 프로세스에 i-node 할당. . .

9 i-node의 할당

10 새로운 파일의 i-node 할당 슈퍼 블럭 . . . . . 프리 i-node 리스트가 공백이 아닐 경우 프리 i-node
커널은 슈퍼블럭의 잠금필드를 확인하여 슈퍼 블록이 선점되어 있는지를 확인 프리 i-node 총 갯수 잠금 필드 . . 커널은 i-node 리스트를 선형 리스트 형태로 관리한다. 어떤 i-node의 형태 필드가 0이면 이는 미사용 상태를 의미한다. 프로세스가 i-node가 필요하면, iget 알고리즘을 이용하여 비어있는 아이노드의 번호를 찾고, ialloc 알고리즘을 이용하여 해당 프로세스에 i-node를 할당한다. 이론적으로는 비어있는 i-node를 찾기 위해 커널이 모든 i-node를 적어도 1회의 읽기 동작을 해야 하지만, 이러한 부담을 덜기 위해 슈퍼 블록에는 프리 i-node 번호를 캐쉬하고 있는 배열이 포함 되어 있다. . . .

11 새로운 파일의 i-node 할당 슈퍼 블럭 . . . . . 프리 i-node 리스트가 공백이 아닐 경우 프리 i-node
커널은 슈퍼블럭의 잠금필드를 확인하여 슈퍼 블록이 선점되어 있는지를 확인 프리 i-node 총 갯수 프리 i-node 리스트 중 다음 i-node의 인덱스 번호를 얻어 오고, 리스트에서 해당 i-node를 제거한다. 잠금 필드 . . 커널은 i-node 리스트를 선형 리스트 형태로 관리한다. 어떤 i-node의 형태 필드가 0이면 이는 미사용 상태를 의미한다. 프로세스가 i-node가 필요하면, iget 알고리즘을 이용하여 비어있는 아이노드의 번호를 찾고, ialloc 알고리즘을 이용하여 해당 프로세스에 i-node를 할당한다. 이론적으로는 비어있는 i-node를 찾기 위해 커널이 모든 i-node를 적어도 1회의 읽기 동작을 해야 하지만, 이러한 부담을 덜기 위해 슈퍼 블록에는 프리 i-node 번호를 캐쉬하고 있는 배열이 포함 되어 있다. . . .

12 새로운 파일의 i-node 할당 슈퍼 블럭 . . . . . 프리 i-node 리스트가 공백이 아닐 경우 프리 i-node
커널은 슈퍼블럭의 잠금필드를 확인하여 슈퍼 블록이 선점되어 있는지를 확인 프리 i-node 총 갯수 프리 i-node 리스트 중 다음 i-node의 인덱스 번호를 얻어 오고, 리스트에서 해당 i-node를 제거한다. 잠금 필드 . . 커널은 i-node 리스트를 선형 리스트 형태로 관리한다. 어떤 i-node의 형태 필드가 0이면 이는 미사용 상태를 의미한다. 프로세스가 i-node가 필요하면, iget 알고리즘을 이용하여 비어있는 아이노드의 번호를 찾고, ialloc 알고리즘을 이용하여 해당 프로세스에 i-node를 할당한다. 이론적으로는 비어있는 i-node를 찾기 위해 커널이 모든 i-node를 적어도 1회의 읽기 동작을 해야 하지만, 이러한 부담을 덜기 위해 슈퍼 블록에는 프리 i-node 번호를 캐쉬하고 있는 배열이 포함 되어 있다. . 3. 얻어온 i-node의 세팅하고 ialloc 알고리즘을 이용하여 해당 프로세스에 할당한다. 또 프리 i-node의 총 개수를 1만큼 감소시킨다. . .

13 프리 i-node 리스트가 공백이 아닐 경우의 예제
282 230 228 215 49 50 인덱스 인덱스 이동 요청한 프로세스에 할당

14 새로운 파일의 i-node 할당 슈퍼 블럭 . . . . . 프리 i-node 리스트가 공백일 경우 프리 i-node 리스트
커널은 슈퍼블럭의 잠금필드를 확인하여 슈퍼 블록이 선점되어 있는지를 확인 프리 i-node 총 갯수 잠금 필드 . . 커널은 i-node 리스트를 선형 리스트 형태로 관리한다. 어떤 i-node의 형태 필드가 0이면 이는 미사용 상태를 의미한다. 프로세스가 i-node가 필요하면, iget 알고리즘을 이용하여 비어있는 아이노드의 번호를 찾고, ialloc 알고리즘을 이용하여 해당 프로세스에 i-node를 할당한다. 이론적으로는 비어있는 i-node를 찾기 위해 커널이 모든 i-node를 적어도 1회의 읽기 동작을 해야 하지만, 이러한 부담을 덜기 위해 슈퍼 블록에는 프리 i-node 번호를 캐쉬하고 있는 배열이 포함 되어 있다. . . .

15 새로운 파일의 i-node 할당 슈퍼 블럭 슈퍼 블록의 i-node 리스트를 다시 채워야 함 . . . . .
커널은 슈퍼블럭의 잠금필드를 확인하여 슈퍼 블록이 선점되어 있는지를 확인 프리 i-node 총 갯수 프리 i-node 리스트가 비어 있다!!! 잠금 필드 . . 커널은 i-node 리스트를 선형 리스트 형태로 관리한다. 어떤 i-node의 형태 필드가 0이면 이는 미사용 상태를 의미한다. 프로세스가 i-node가 필요하면, iget 알고리즘을 이용하여 비어있는 아이노드의 번호를 찾고, ialloc 알고리즘을 이용하여 해당 프로세스에 i-node를 할당한다. 이론적으로는 비어있는 i-node를 찾기 위해 커널이 모든 i-node를 적어도 1회의 읽기 동작을 해야 하지만, 이러한 부담을 덜기 위해 슈퍼 블록에는 프리 i-node 번호를 캐쉬하고 있는 배열이 포함 되어 있다. . . 슈퍼 블록의 i-node 리스트를 다시 채워야 함 .

16 새로운 파일의 i-node 할당 프리 i-node 리스트 업데이트 비어 있는 슈퍼 블록 i-node 리스트 삽입
공백 인덱스 삽입 디스크 검색으로 찾아낸 프리 i-node 들 215 228 230 282

17 새로운 파일의 i-node 할당 프리 i-node 리스트 업데이트 업데이트된 슈퍼 블록 i-node 리스트 282 230
228 215 50 인덱스 숫자 순으로 i-node 들을 넣고 인덱스를 초기화한다. 이 때, 가장 큰 수는 기억 i-node로 설정 된다.

18 새로운 파일의 i-node 할당 프리 i-node 리스트 업데이트 업데이트된 슈퍼 블록 i-node 리스트 282 230
228 215 50 “기억 i-node” 란? 인덱스 커널은 슈퍼 블록의 프리 i-node 리스트가 빌 때마다 디스크 i-node 를 검색하여 프리 i-node 들을 찾아서 리스트를 채운다. 이때 리스트에서 가장 숫자가 큰 i-node 의 번호를 “기억 i-node”로 저장해 두었다가, 차후에 다시 검색을 할 때 해당 번호를 검색의 출발점으로 삼아 효율성을 높인다.

19 <디스크 내 프리 i-node 탐색을 통한 프리 i-node 리스트 업데이트>
할당되지 않은 i-node 기억 i-node 할당된 i-node 디스크 i-node 214 186 178 175 284 282 248 215 302 290 288 285 <디스크 내 프리 i-node 탐색을 통한 프리 i-node 리스트 업데이트>

20 새로운 파일의 i-node 할당 슈퍼노드의 잠금 필드 확인 잠김 열림 프리 i-node의 총 개수로 리스트의 공백 여부 확인
즉시 복귀하여 경쟁 회피 i-node 존재 i-node 존재하지 않음 얻어온 i-node를 요청한 프로세스에 할당 디스크 검색으로 얻어온 i-node로 프리 i-node 리스트 업데이트 잠금 필드를 열고 복귀 얻어온 i-node를 요청한 프로세스에 할당 잠금 필드를 열고 복귀

21 i-node의 반환

22 파일의 i-node 반환 슈퍼 블럭 . . . . . 프리 i-node 커널은 슈퍼블럭의 잠금필드를 확인하여 리스트
슈퍼 블록이 선점되어 있는지를 확인 잠겨 있을 경우 즉시 복귀하여 경쟁상태 회피 한다. 프리 i-node 총 갯수 잠금 필드 . . 커널은 i-node 리스트를 선형 리스트 형태로 관리한다. 어떤 i-node의 형태 필드가 0이면 이는 미사용 상태를 의미한다. 프로세스가 i-node가 필요하면, iget 알고리즘을 이용하여 비어있는 아이노드의 번호를 찾고, ialloc 알고리즘을 이용하여 해당 프로세스에 i-node를 할당한다. 이론적으로는 비어있는 i-node를 찾기 위해 커널이 모든 i-node를 적어도 1회의 읽기 동작을 해야 하지만, 이러한 부담을 덜기 위해 슈퍼 블록에는 프리 i-node 번호를 캐쉬하고 있는 배열이 포함 되어 있다. . . .

23 파일의 i-node 반환 슈퍼 블럭 . . . . . 프리 i-node 커널은 슈퍼블럭의 잠금필드를 확인하여 리스트
슈퍼 블록이 선점되어 있는지를 확인 잠겨 있을 경우 즉시 복귀하여 경쟁상태 회피 프리 i-node 총 갯수 프리 i-node 리스트에 공간이 있으면 반환된 i-node를 리스트에 넣고 기존 기억 i-node와 비교하여 번호가 더 작은 노드를 새로운 기억 i-node로 저장한다. 잠금 필드 . . 커널은 i-node 리스트를 선형 리스트 형태로 관리한다. 어떤 i-node의 형태 필드가 0이면 이는 미사용 상태를 의미한다. 프로세스가 i-node가 필요하면, iget 알고리즘을 이용하여 비어있는 아이노드의 번호를 찾고, ialloc 알고리즘을 이용하여 해당 프로세스에 i-node를 할당한다. 이론적으로는 비어있는 i-node를 찾기 위해 커널이 모든 i-node를 적어도 1회의 읽기 동작을 해야 하지만, 이러한 부담을 덜기 위해 슈퍼 블록에는 프리 i-node 번호를 캐쉬하고 있는 배열이 포함 되어 있다. . . .

24 파일의 i-node 반환 슈퍼 블럭 . . . . . 프리 i-node 커널은 슈퍼블럭의 잠금필드를 확인하여 리스트
슈퍼 블록이 선점되어 있는지를 확인 잠겨 있을 경우 즉시 복귀하여 경쟁상태 회피 프리 i-node 총 갯수 프리 i-node 리스트에 공간이 있으면 반환된 i-node를 리스트에 넣고 기존 기억 i-node와 비교하여 번호가 더 작은 노드를 새로운 기억 i-node로 저장한다. 잠금 필드 . . 커널은 i-node 리스트를 선형 리스트 형태로 관리한다. 어떤 i-node의 형태 필드가 0이면 이는 미사용 상태를 의미한다. 프로세스가 i-node가 필요하면, iget 알고리즘을 이용하여 비어있는 아이노드의 번호를 찾고, ialloc 알고리즘을 이용하여 해당 프로세스에 i-node를 할당한다. 이론적으로는 비어있는 i-node를 찾기 위해 커널이 모든 i-node를 적어도 1회의 읽기 동작을 해야 하지만, 이러한 부담을 덜기 위해 슈퍼 블록에는 프리 i-node 번호를 캐쉬하고 있는 배열이 포함 되어 있다. . 3. 프리 i-node의 총 갯수를 증가 시킨다. . .

25 리스트에 빈 공간이 없을 때, i-node 반환하는 2가지 경우(1/2)
1. 반환하는 i-node 번호가 기존의 “기억 i-node”보다 큰 경우 282 230 228 224 50 기억 i-node 인덱스 기존의 기억 i-node가 반환된 i-node의 번호보다 작으면 반환된 i-node를 리스트에 넣지 않는다. 294 반환 i-node

26 리스트에 빈 공간이 없을 때, i-node 반환하는 2가지 경우(1/2)
1. 반환하는 i-node 번호가 기존의 “기억 i-node”보다 큰 경우 282 230 228 224 50 기억 i-node 인덱스 282 230 228 224 50 기억 i-node의 변화가 없음 인덱스

27 리스트에 빈 공간이 없을 때, i-node 반환하는 2가지 경우(2/2)
2. 반환하는 i-node 번호가 기존의 “기억 i-node”보다 작은 경우 282 230 228 224 50 기억 i-node 인덱스 기존의 기억 i-node가 반환된 i-node의 번호보다 크면 반환된 i-node를 새로운 기억 i-node로 설정한다. 271 반환 i-node

28 리스트에 빈 공간이 없을 때, i-node 반환하는 2가지 경우(2/2)
2. 반환하는 i-node 번호가 기존의 “기억 i-node”보다 작은 경우 282 230 228 224 50 기억 i-node 인덱스 271 230 228 224 50 새로운 기억 i-node 인덱스

29 왜 반환된 i-node로 기존의 기억 i-node를 대체 하는가?

30 파일의 i-node 반환 리스트에 빈 공간이 없을 때, i-node 반환하는 2가지 경우(2/2)
디스크 i-node 탐색 시에 바뀐 기억 i-node인 271를 출발점으로 탐색을 하므로 이전 기억 i-node 였던 282도 다시 검색할 수 있게 된다. 반환된 이전 기억 i-node 출발점이 되는 바뀐 기억 i-node 282 271 228 224 301 290 284 283 < 디스크 내의 프리 i-node 탐색>

31 파일의 i-node 반환 슈퍼노드의 잠금 필드 확인 잠김 열림 프리 i-node의 총 개수로 리스트가 꽉 찼는지 여부 확인
즉시 복귀하여 경쟁 회피 공간 존재하지 않음 공간 존재 기존의 기억 i-node와 반환된 i-node의 숫자 비교 반환된 i-node를 리스트에 삽입하고 잠금 필드를 열고 복귀 반환된 i-node의 숫자가 더 작음 반환된 i-node의 숫자가 더 큼 반환된 i-node를 새로운 기억 i-node로 설정하고 복귀 기억 i-node의 변화 없이 잠금 필드를 열고 복귀

32 Ⅰ 슈퍼 블럭 Ⅱ 새로운 파일의 i-node 할당과 반환 Ⅲ 디스크 블록의 할당과 반환 32

33 디스크 블록의 할당 슈퍼 블럭 . . . . . 커널은 i-node 리스트를 선형 리스트 형태로 관리한다.
프로세스간의 동시 접근을 막기 위한 필드 프리 i-node 리스트 프리 i-node 총 갯수 잠금 필드 프리 디스크 블록 리스트 커널은 슈퍼 블럭 내의 프리 디스크 블록 리스트를 참조하여 프로세스에 디스크 블록을 할당한다. . . . . .

34 < 프리 디스크 블록 링크드 리스트>
디스크 블록의 할당 프리 디스크 블록 리스트의 형태 슈퍼 블록 리스트 109 106 103 100 211 208 205 202 112 310 307 304 301 214 < 프리 디스크 블록 링크드 리스트>

35 디스크 블록의 할당 디스크 블록 반환 예제 슈퍼 블록 리스트 109 . . . . . . . . . . . .
211 208 205 202 112 102 < 디스크 블록 반환>

36 디스크 블록의 할당 디스크 블록 할당 예제 슈퍼 블록 리스트 109 102 . . . . . . . . . . . .
211 208 205 202 112 디스크 블록 할당 < 디스크 블록 할당>

37 디스크 블록의 할당 디스크 블록 리스트 업데이트 예제(1/2) 슈퍼 블록 내의 디스크 블록 리스트 . . . . . .
211 208 205 202 112 310 307 304 301 214 < 디스크 블록의 업데이트>

38 디스크 블록의 할당 디스크 블록 리스트 업데이트 예제(1/2) 슈퍼 블록 내의 디스크 블록 리스트 . . . . . .
복사 211 208 205 202 112 복사 310 307 304 301 214 < 디스크 블록의 업데이트>

39 디스크 블록의 할당 디스크 블록 리스트 업데이트 예제(2/2) 슈퍼 블록 내의 디스크 블록 리스트 211 208 205 202
112 310 307 304 301 214 < 디스크 블록의 업데이트> 슈퍼 블록 내의 프리 디스크 블록 리스트가 비게 되면 커널은 프리 디스크 블록 리스트 다음에 링크되어 있는 블록을 리스트 내로 복사하여 리스트를 채운다.

40 Key Point i-node 블록의 할당과 반환 과정 기억 i-node 의 설정과 역할 디스크 블록의 구조, 할당과 반환 과정

41 Thank you for your attention!