제10,11,12장 파일시스템 디스크 스케줄링.

Presentation on theme: "제10,11,12장 파일시스템 디스크 스케줄링."— Presentation transcript:

1 제10,11,12장 파일시스템 디스크 스케줄링

2 개요 파일 시스템(file system) 전체적인 정보 관리 시스템의 한 부분
현재의 컴퓨터와 시스템은 주로 디스크 시스템 중심의 처리 파일 시스템은 사용자가 운영체제에서 가장 관찰하기 쉬운 부분 운영체제는 디스크나 CD-ROM 같은 기억용량이 큰 기억장치를 관리·운영

3 디스크 구조 섹터(sector) 트랙(track) 블록(block) 실린더(cylinder)
디스크 구조에서 부채꼴 모양으로 자른 것처럼 나누어진 구역 트랙(track) 중심축에 대해 동심원으로 나누어진 것 블록(block) 몇 개의 섹터를 모아 블록이라 함 실린더(cylinder) 동일한 인덱스 번호를 가진 트랙의 모임

4 디스크 구조 이동헤드 디스크의 구성도

5 디스크 구조 탐색시간(seek time) 회전지연시간(latency time) 전송시간(transmission time)
실제 원하는 실린더를 찾는 데 소요되는 시간 회전지연시간(latency time) 원판이 회전하면서 처리할 데이터가 있는 위치까지 오는 시간 전송시간(transmission time) 읽은 데이터를 주기억장치에 전달하는 데 소요되는 시간 디스크 접근 시간 디스크로부터 데이터를 접근하는 데 소요되는 시간 탐색 시간, 회전 지연 시간, 전송 시간의 총 합

6 디스크 구조 디스크 접근의 구성 단계

7 CD-ROM 구조 CD-ROM(Compact Disk-Read Only Memory)
적은 비용으로 많은 데이터 저장용량(650MB 이상)을 보유 디스크 저장 매체의 두 가지 저장방식 : CAV, CLV CAV(Constant Angular Velocity) 일정한 속도로 회전, 읽어 들이는 데이터 양이 달라진다. 하드디스크와 플로피디스크가 이 방식 CLV(Constant Linear Velocity) 회전 속도를 조절하여, 데이터를 읽고 쓰는 속도가 일정 데이터는 연속된 나선형 트랙을 따라 저장 연속적인 오디오 또는 비디오 트랙에 적합 CLV는 저장용량이 큰 반면, 데이터 접근시간이 느린 단점

8 CD-ROM 구조 CAV와 CLV의 구조

9 디스크 스케줄링 디스크 스케줄링(disk scheduling)
현재의 헤드 위치를 근거로 가장 적은 기계적 이동으로 이러한 요청들을 처리할 수 있도록 대기 큐를 재배열 과정 2가지 방법 탐색 시간을 최적화하는 방법 회전 지연 시간을 최적화하는 방법 일반적으로 탐색 시간을 최소화하는 스케줄링 방법 이용

10 디스크 스케줄링 FCFS(First Come First Served) 스케줄링 가장 간단한 스케줄링 형태
먼저 도착한 요청을 우선적으로 서비스하는 기법 공평성이 보장되고 프로그래밍하기가 쉽다. 일반적으로 효율이 낮음

11 디스크 스케줄링 FCFS 스케줄링

12 디스크 스케줄링 SSTF(Shortest Seek Time First) 스케줄링
현재 헤드의 위치에 가장 가까운 요청을 먼저 서비스하는 기법 본질적으로 SJF(Shortest Job First) 알고리즘 형태 어떤 요청의 경우는 기근(starvation) 현상이 발생 FCFS 보다 처리율(throughput)이 높고 평균 응답시간이 짧음

13 디스크 스케줄링 SSTF 스케줄링

14 디스크 스케줄링 SCAN 및 LOOK 스케줄링
실제로 구현되는 대부분의 디스크 스케줄링의 기본 전략 LOOK 스케줄링은 헤드가 각 방향의 트랙 끝까지 이동하지 않고 마지막 요청 트랙까지만 이동

15 디스크 스케줄링 SCAN 스케줄링

16 디스크 스케줄링 C-SCAN 및 C-LOOK 스케줄링
C-SCAN(Circular SCAN)은 한쪽 방향으로 헤드를 이동하면서 ‘진행 방향’상의 가장 짧은 거리에 있는 요청을 처리 한쪽 끝에 다다르면 다시 처음 시작 방향으로 이동하여 서비스 한다. 가장 안쪽과 바깥쪽 트랙의 차별 대우를 개선하고, 대기 시간의 편차가 매우 작음 C-LOOK 스케줄링을 적용하면 헤드가 각 방향의 트랙 끝까지 이동하지 않고 마지막 요청 트랙까지만 이동

17 디스크 스케줄링 C-LOOK 스케줄링

18 디스크 스케줄링 SLTF(Shortest Latency Time First)스케줄링 알고리즘 선택 회전지연시간 최적화 알고리즘
디스크 서비스에 대한 요청은 파일 할당 방법에 따라 많은 영향 연속적으로 할당되어 있는 파일의 관리를 위한 것은 결과적으로 헤드의 움직임은 큰 문제가 되지 않는다. 링크된 파일(linked file)이나 색인화 된 파일(indexed file)은 헤드의 이동에 관심을 가지고 더 좋은 디스크 이용 방안을 모색해야 디렉터리를 디스크의 끝 부분에 두는 것보다 중간 부분에 두는 것이 디스크 헤드의 이동을 상대적으로 감소

19 파일 시스템 파일 시스템은 두 부분으로 구성 데이터의 계층 구조
관련된 정보를 포함하는 실제적인 파일들의 집합체와 시스템 내의 모든 파일에 대한 정보를 제공하는 디렉터리 구조 파일이란 일반적으로 작성자와 사용자에 의해 그 의미가 정의된 비트, 바이트, 행(line), 또는 레코드들의 연속체 데이터의 계층 구조 필드(field) : 상호 관련 있는 문자들(숫자, 영문자, 특수 기호 등)의 집합 레코드(record) : 서로 관련이 있는 필드들의 집합 파일(file) :상호 관련 있는 레코드들의 집합 데이터베이스(database) : 상호 관련 있는 파일들로 구성

20 파일 시스템 블로킹 물리적 레코드(physical record)나 블록(block) 논리적 레코드(logical record)
기억매체에 출력되거나 기억매체로부터 입력되는 실제 정보의 단위 논리적 레코드(logical record) 사용자 관점에서 취급되는 자료 집단의 단위 블로킹되지 않은 레코드(unblocked record) 물리적 레코드가 단 하나의 논리적 레코드로 구성 블로킹된 레코드(blocked record) 여러 개의 논리적 레코드가 하나의 물리적 레코드를 구성 고정길이 레코드(fixed­-length record) 구성된 파일에서의 레코드 길이가 모두 같음 가변길이 레코드(variable­length record) 구성된 파일에서의 레코드 길이는 다양 최대 크기는 블록의 크기와 동일

21 파일 시스템 파일 시스템의 기능 사용자가 파일을 생성(create), 수정(modify), 삭제(delete) 가능
적절한 제어 방법 제공 파일 공유 방법 제공 다양한 형태로 파일을 재구성 방법 제공 백업(backup)과 복구(recovery)를 위한 기능 사용자와 장치 간의 독립성(device independence)을 유지하기 위하여 기호화된 이름(symbolic name) 제공 정보의 암호화(encryption)와 복호화(decryption) 사용자에게 친숙한 인터페이스(user friendly interface)를 제공

22 파일 시스템 파일의 구조 순차 파일(sequential file)
논리적인 레코드를 물리적인 순서에 따라 순차적으로 저장하고 검색하도록 저장 디스크, 자기 테이프, 프린터로 된 출력 등에 주로 사용 순차접근 기억장치(SASD : Sequential Access Storage Device)에 저장 일괄처리에서 많이 사용 색인된 순차 파일(indexed sequential file) 순차 및 직접 접근을 모두 처리할 수 있는 파일 구조 보통 디스크와 같은 직접 접근 기억장치(DASD : Direct Access Storage Device)에 저장 일괄처리 및 대화형 처리를 목적으로 하는 파일을 지원 융통성이 많고 검색 성능이 우수함. 단점은 설계 시 고려할 사항이 많다.

23 파일 시스템 파일의 구조 직접 파일(direct file) 임의 레코드를 직접 접근할 수 있는 파일 구조
키 값에서 보조기억장치의 주소로 사상시키는 사상함수가 필요 대화형 처리에 유용 직접 접근 기억장치(DASD : Direct Access Storage Device)에 저장 특정 레코드의 검색, 삽입, 수정, 삭제가 쉬우며, 단점은 키 값의 순서에 의한 순차 검색이 어렵다.

24 파일 시스템 파일 공간의 할당과 회수 파일 공간 할당 기법: 파일을 보조기억장치에 저장할 때 어떤 파일을 어떻게 할당할 것이며, 보조기억장치 공간의 효율적 이용과 얼마나 빠르게 접근할 수 있도록 할 것인가를 결정 보조기억장치상의 공간은 할당과 회수의 반복으로 작은 공간들로 단편화(fragmentation)되는 현상이 발생 단편화 문제를 해결하기 위한 방법은 주기적인 집약(compaction)을 수행 비트 벡터 비트 맵 또는 비트 테이블이라고도 함 각 디스크 블록 당 하나의 비트가 할당되어서 관리하는 방법 해당 블록이 자유 공간이면 1로 표현되고, 0이면 파일이 할당된 공간을 나타냄. 예) 자유 블록이나 연속된 자유 블록들을 찾기 쉬운 장점이 있음

25 파일 시스템 파일 공간의 할당과 회수 연속 할당(contiguous allocation)
보조기억장치 내의 연속적으로 인접된 공간에 파일을 할당 단점은 사용자가 새로운 파일을 생성하기 위해서는 필요한 공간의 크기를 미리 명시해야 함 만약 원하는 만큼의 기억 공간이 확보되지 않으면 그 파일은 생성되지 못함 연속 할당

26 파일 시스템 파일 공간의 할당과 회수 불연속 할당(non­contiguous allocation) : 연결 리스트
동일 파일에 속해 있는 섹터(sector)들이 서로 연결 리스트의 형태를 취하면서 다른 것과의 연결을 위한 포인터(pointer)를 지님 디렉터리에는 처음 해당 파일이 시작되는 시작 주소 및 마지막 주소에 대한 포인터(pointer) 정보 유지 문제점 연속된 블록들의 검색에는 긴 시간이 요구됨 연결 리스트 구조를 유지하는 데 필요한 시간이 추가적으로 소요됨 연결된 리스트 내에 있는 포인터들은 파일 데이터를 위한 가용 공간을 감소시킴

27 파일 시스템 연결 리스트를 이용한 불연속 할당

28 파일 시스템 파일 공간의 할당과 회수 불연속 할당(non­contiguous allocation) : 색인 블록
각 파일마다 하나의 색인 블록(indexed block)을 두고, 여기에 파일의 블록 항목이 산재해 있는 주소에 대한 포인터 정보 유지 단편화의 문제 없이 해당 블록에 대한 직접 접근이 가능 연결 리스트 방법보다 기억장소의 낭비를 더 초래할 수도 있음

29 파일 시스템 색인 블록을 이용한 불연속 할당

30 파일 시스템 파일의 보호(protection)
물리적인 손상으로부터의 보호(신뢰성의 문제)와 파일에서의 부당한 접근으로부터의 보호(보호의 문제) 보호 기법 파일 이름(naming) 다른 사용자 파일의 이름을 알지 못하는 경우에는 접근 대상에서 제외 암호(password) 각 사용자마다 서로 다른 암호를 제공하여 그 암호를 알아야만 파일을 이용할 수 있게 한다. 접근 제어(access control) 명시된 접근 가능한 사용자와 가능한 동작을 운영 체제가 참조하여 접근 여부를 결정

31 디렉터리 구조 파일 시스템 내부에 있는 많은 파일들을 조직화하는 메커니즘 장치들 간을 연결해줌 디렉터리에서 실행되어야 할 기능
탐색(search), 파일 생성(file create), 파일 삭제(file delete) 디렉터리 리스트(directory list), 백업(back up) 디렉터리 내에 저장되어 있는 각 파일에 대한 정보 파일명(file name), 파일 형태(file type), 위치(location) 크기(size), 보호(protection), 사용 횟수(usage count), 시간, 날짜, 프로세스 식별(time, date and process identification)

32 디렉터리 구조 일단계 구조 디렉터리 가장 간단한 구조 모든 파일들을 같은 디렉터리 내에 위치
같은 디렉터리 내에 모두 상이한 이름을 가져야 함 일단계 구조 디렉터리

33 디렉터리 구조 이단계 구조 디렉터리 마스터 파일 디렉터리(MFD : Master File Directory),
사용자 파일 디렉터리(UFD : User File Directory)로 구성 일 단계 디렉터리에서의 단점인 서로 다른 사용자들 간의 파일명의 혼란을 해결 이단계 구조 디렉터리

34 디렉터리 구조 트리구조 디렉터리 디렉터리 또는 서브디렉터리는 일단의 파일이나 또 다른 서브디렉터리들을 가짐
UNIX파일 시스템은 트리로 구성 경로 이름 절대 경로이름과 상대 경로이름 트리 구조 디렉터리

35 디렉터리 구조 비 순환 구조 디렉터리 디렉터리들이 서브디렉터리나 파일을 공유할 수 있도록 허용하고 순환(cycle)은 허용하지 않음 단순한 트리 구조보다 융통성은 좋으나 그 구조가 너무 복잡함 비순환 구조 디렉터리

36 디렉터리 구조 일반적 그래프 구조 디렉터리 트리 구조의 디렉터리에 링크를 첨가  트리 구조는 파괴됨
순환(cycle)이 허용됨 무한 순환(infinite loop)이 가능하므로 전역 탐색에는 신중해야함 각 디렉터리마다 불필요한 파일의 제거를 위한 쓰레기 수집(garbage collection)을 수행해야 함 일반적 그래프 구조 디렉터리

37 파일시스템의 예 FAT(File Allocation Table) NTFS(New Technology File System)
FAT12 구조 MS-DOS 3.0까지의 파일시스템 FAT32는 Windows 95, 98, Me에서 제공됨 NTFS(New Technology File System) 마이크로소프트가 개발 대용량의 파일을 표현 EPS(Encrypting File System)라는 암호 기능을 제공 Windows NT, Windows XP, Windows Vista, Windows 7에서 제공함

38 파일시스템의 예 UFS(Unix File System) Ext(Extended File System)
유닉스 및 유닉스 계열 운영 체제에 쓰이는 파일 시스템 대부분의 유닉스 계열 파일 시스템의 기본 파일 시스템임 Ext(Extended File System) 리눅스의 기본적인 파일시스템임 Ext3은 Ext2 파일 시스템에 저널링(journaling) 기능이 추가됨 2010년 4월에 안정된 ext4가 발표됨

39 파일시스템의 예 GFS(Google File System) 대규모의 클라우드 서비스를 제공을 위해 구글(Google)이 개발
클라이언트, 마스터, 여러 개의 청크(chunk)서버들로 구성 구글 파일 시스템 구조

40 파일시스템의 예 HDFS(Hadoop Distributed File System)
오픈 소스 소프트웨어 개발 프로젝트인 하둡에서 분산 컴퓨팅 프레임워크를 지원하기 위해 하둡 분산 파일시스템을 개발함 아마존, IBM, 야후 등 클라우드 컴퓨팅 플렛폼에 기반되는 분산 파일 시스템으로 가장 널리 사용됨 네임 노드 서버, 보조 네임 노드 서버와 다수의 데이터 노드 서버로 구성됨