플래그멘테이션(컴퓨팅)

Fragmentation (computing)
파일 시스템 조각화는 파일 시스템 조각화를 참조하십시오.

컴퓨터 스토리지에서 플래그멘테이션이란 스토리지 공간, 메인 스토리지 또는 세컨더리 스토리지가 비효율적으로 사용되어 용량이나 퍼포먼스가 저하되는 현상을 말합니다.플래그멘테이션의 정확한 결과는 사용 중인 스토리지 할당의 특정 시스템과 플래그멘테이션의 특정 형태에 따라 달라집니다.대부분의 경우 단편화로 인해 스토리지 공간이 "소모"되고, 이 경우 낭비되는 공간 자체를 의미하기도 합니다.

플래그멘테이션의 종류

플래그멘테이션에는 외부 플래그멘테이션, 내부 플래그멘테이션 및 데이터 플래그멘테이션의 3가지 형식이 있습니다.이러한 형식은 분리 또는 조합으로 존재할 수 있습니다.플래그멘테이션은 속도 또는 단순성을 향상시키는 대가로 받아들여지는 경우가 많습니다.프로세서등의 다른 자원에서도 같은 현상이 발생합니다.아래를 참조해 주세요.

기본원칙

컴퓨터 프로그램이 컴퓨터 시스템에 메모리 블록을 요청하면 블록은 청크로 할당됩니다.컴퓨터 프로그램이 청크로 완료되면 시스템에 다시 해방되어 나중에 다른 프로그램이나 같은 프로그램에 다시 할당할 수 있습니다.프로그램에 의해 청크가 유지되는 크기와 시간은 다양합니다.컴퓨터 프로그램은 수명 동안 많은 메모리 청크를 요청하고 해방시킬 수 있습니다.

프로그램이 시작되면 빈 메모리 영역은 길고 연속적입니다.시간이 지남에 따라 그리고 사용으로 인해 긴 인접 영역은 점점 더 작은 인접 영역으로 단편화됩니다.결국, 프로그램이 대용량의 연속 메모리 청크를 얻는 것이 불가능해질 수 있습니다.

종류들

내부 플래그멘테이션

메모리 페이징은 내부 플래그멘테이션을 생성합니다.이는 그만큼의 스토리지가 [1]필요한지 여부에 관계없이 페이지 프레임 전체가 할당되기 때문입니다.메모리 할당을 관리하는 규칙 때문에 필요한 것보다 더 많은 컴퓨터 메모리가 할당될 수 있습니다.예를 들어, 메모리는 청크(보통 4바이트의 배수)의 프로그램에만 제공할 수 있으며, 그 결과 프로그램이 29바이트를 요구하면 실제로는 32바이트의 청크를 얻을 수 있습니다.이 경우, 여분의 메모리는 낭비됩니다.이 시나리오에서는 사용할 수 없는 메모리가 할당된 영역 내에 포함되어 있습니다.고정 파티션이라고 불리는 이 배열은 비효율적인 메모리 사용으로 인해 어려움을 겪습니다. 즉, 아무리 작은 파티션이라도 모든 프로세스가 전체 파티션을 차지합니다.이러한 낭비를 내부 단편화라고 [2][3]합니다.

다른 유형의 플래그멘테이션과 달리 내부 플래그멘테이션은 재확보가 어렵습니다.보통 설계를 변경하는 것이 가장 좋습니다.예를 들어 동적 메모리 할당에서는 메모리 풀이 공간 오버헤드를 더 많은 개체로 분산시킴으로써 내부 플래그멘테이션을 대폭 줄입니다.

외부 플래그멘테이션

외부 플래그멘테이션은 빈 메모리가 작은 블록으로 분리되고 할당된 메모리에 의해 삽입될 때 발생합니다.특정 스토리지 할당 알고리즘이 프로그램에서 사용하는 메모리를 효율적으로 정렬하지 못할 때 발생하는 약점입니다.그 결과, 무료 스토리지는 사용 가능하지만, 애플리케이션의 요구를 만족시키기에는 개별적인 크기가 너무 작기 때문에 사실상 사용할 수 없게 됩니다."외부"라는 용어는 사용할 수 없는 스토리지가 할당된 영역 밖에 있다는 사실을 의미합니다.

예를 들어, 프로그램이 3개의 연속된 메모리 블록을 할당한 후 중간 블록을 해제하는 상황을 가정해 보겠습니다.메모리 할당자는 이 빈 메모리 블록을 향후 할당에 사용할 수 있습니다.그러나 할당할 메모리가 이 빈 블록보다 크면 이 블록을 사용할 수 없습니다.

크기가 다른 파일이 많이 생성되고 크기가 변경되며 삭제되기 때문에 파일 시스템에서도 외부 플래그멘테이션이 발생합니다.여러 개의 작은 조각으로 분할된 파일을 삭제하면 마찬가지로 작은 빈 영역이 남기 때문에 그 효과는 더욱 심각해집니다.

0x0000 0x1000 0x2000 0x3000 0x4000 0x5000 평.
스토리지에 사용할 수 있는 모든 메모리부터 시작합니다.
A B C 크기가 0x1000인 3개의 블록 A, B 및 C가 할당되었습니다.
A C 해제된 블록 B.B가 사용한 메모리는 B의 크기보다 큰 블록에는 포함할 수 없습니다.
A C 블록 C가 블록 B의 빈 슬롯으로 이동했기 때문에 나머지 공간은 크기가 0x4000인 더 큰 블록에 사용할 수 있습니다.

데이터 플래그멘테이션

데이터 플래그멘테이션은 메모리 내의 데이터 컬렉션이 서로 가깝지 않은 여러 조각으로 분할될 때 발생합니다.일반적으로 이미 외부 조각화가 발생한 스토리지에 큰 개체를 삽입하려고 시도한 결과입니다.예를 들어 파일 시스템의 파일은 일반적으로 블록 또는 클러스터라는 단위로 관리됩니다.파일 시스템이 생성되면 파일 블록을 동시에 저장할 수 있는 여유 공간이 생깁니다.이것에 의해, 파일의 신속한 판독과 기입이 가능하게 됩니다.다만, 파일의 추가, 삭제, 사이즈의 변경에 수반해, 빈 공간은 외부적으로 단편화해, 새로운 데이터를 격납하는 작은 구멍만이 남습니다.새 파일이 작성되거나 기존 파일이 확장되면 운영체제는 사용 가능한 구멍에 맞도록 새 데이터를 연속되지 않은 새 데이터 블록에 넣습니다.새로운 데이터 블록은 필연적으로 분산되어 있어 읽기/쓰기 헤드의 시크 시간과 회전 대기 시간으로 인해 액세스가 느려지고 추가 위치를 관리하기 위한 추가 오버헤드가 발생합니다.이를 파일 시스템 플래그멘테이션이라고 합니다.

이미 알려진 크기의 새 파일을 쓸 때 해당 파일보다 큰 빈 구멍이 있는 경우 운영 체제는 파일을 이러한 구멍 중 하나에 넣는 것으로 데이터 조각화를 방지할 수 있습니다.이러한 잠재적인 구멍 중 어느 것을 넣을지를 선택하는 알고리즘은 다양합니다.각각은 빈 패킹 문제에 대한 휴리스틱 근사 솔루션입니다."best fit" 알고리즘은 충분히 큰 가장 작은 구멍을 선택합니다."최악 적합" 알고리즘은 가장 큰 구멍을 선택합니다."퍼스트 핏 알고리즘"은 충분히 큰 첫 번째 구멍을 선택합니다.「next fit」알고리즘은, 각 파일의 기입 장소를 추적합니다."next fit" 알고리즘은 "first fit"보다 빠릅니다. "first fit" 알고리즘은 "worst fit"[4]과 같은 속도인 "best fit"보다 빠릅니다.

압축으로 외부 단편화를 제거할 수 있는 것처럼 데이터 스토리지를 재배치하여 관련 단편화를 제거할 수 있습니다.예를 들어, 조각 모음 도구의 주요 작업은 각 파일의 블록이 연속되도록 Disk의 블록을 재배치하는 것입니다.대부분의 조각 모음 유틸리티는 빈 공간 조각화를 줄이거나 제거하려고 시도합니다.자동 메모리 관리를 실행하는 유틸리티인 일부 이동 가비지 컬렉터는 캐시 성능을 향상시키기 위해 관련 개체를 서로 가깝게 이동하기도 합니다(이를 압축이라고 합니다).

데이터 조각화가 발생하지 않는 4가지 종류의 시스템이 있습니다. 즉, 항상 모든 파일을 연속적으로 저장합니다.적어도 일부 일시적인 데이터 플래그멘테이션을 허용하는 시스템에 비해 4가지 유형 모두 중대한 단점이 있습니다.

  1. 각 파일을 연속해서 작성하기만 하면 됩니다.파일을 저장할 수 있는 연속된 여유 공간이 아직 충분하지 않은 경우 삭제된 파일에서 파일을 저장할 수 있는 여유 공간이 많더라도 시스템은 즉시 파일 저장에 실패합니다.
  2. 파일을 저장할 수 있는 충분한 연속 빈 공간이 없는 경우 복사 수집기를 사용하여 많은 빈 공간을 파일을 저장할 수 있을 만큼 큰 연속 빈 영역으로 변환합니다.이것은 파일을 fragment로 분할하여 사용 가능한 빈 공간에 넣는 것보다 훨씬 더 많은 시간이 걸립니다.
  3. 고정 크기의 블록 스토리지를 통해 파일을 빈 블록에 쓸 수 있습니다.프로그래머가 너무 작은 고정 블록 크기를 선택하면 파일을 저장할 수 있을 만큼 많은 빈 블록이 있더라도 시스템은 즉시 일부 파일(블록 크기보다 큰 파일)을 저장하지 못합니다.프로그래머가 블록 크기를 너무 크게 선택하면 내부 단편화에 많은 공간이 낭비됩니다.
  4. 일부 시스템에서는 동적 할당을 완전히 피하고 필요할 수 있는 모든 파일을 미리 저장(연속)하는 공간을 확보합니다. 예를 들어, MultiFinder는 애플리케이션 프로그래머가 필요로 하는 RAM의 양에 따라 RAM의 한 덩어리를 각 애플리케이션에 미리 할당합니다.

개요

외부 플래그멘테이션에 비해 오버헤드 및 내부 플래그멘테이션은 메모리 낭비와 성능 저하를 거의 고려하지 않습니다.다음과 같이 정의됩니다.

0%의 fragment화는 모든 빈 메모리가 하나의 큰 블록에 있음을 의미합니다.예를 들어 100MB의 빈 메모리가 존재하지만 저장용 메모리의 최대 빈 블록은 10MB에 불과할 경우 fragmentation은 90%입니다.

외부 플래그멘테이션은 프라이머리 메모리(RAM) 스토리지 시스템보다 파일 시스템에서 문제가 적은 경향이 있습니다.이는 보통 프로그램은 RAM 스토리지 요구를 연속된 블록으로 이행해야 하지만 파일 시스템은 일반적으로 사용 가능한 블록(프래그먼트)의 모든 컬렉션을 사용하여 논리적으로 파일을 조립할 수 있도록 설계되어 있기 때문입니다.alli는 연속적으로 표시됩니다.따라서 고도로 fragment화된 파일 또는 다수의 작은 파일을 풀볼륨에서 삭제한 후 새로 해방된 공간과 동일한 크기의 새 파일이 생성된 경우 새 파일은 삭제로 해방된 것과 동일한 fragment를 단순히 재사용합니다.삭제된 파일이 1개의 파일일 경우 새 파일은 이전 파일과 마찬가지로 fragment화되지만, 어떤 경우에도 모든 (높은 fragment화) 빈 공간을 사용하여 새 파일을 생성해도 문제가 없습니다.반면 RAM에서는 사용되는 스토리지 시스템은 종종 작은 비연속 빈 블록의 요청을 충족하기 위해 큰 블록을 조립할 수 없기 때문에 요청을 이행할 수 없으며 프로그램에서는 메모리를 필요로 하는 모든 작업을 계속할 수 없습니다(단, 여러 개의 작은 개별 요청으로 요청을 재발행할 수 있는 경우가 있습니다).

문제

스토리지 장애

플래그멘테이션으로 인해 발생하는 가장 심각한 문제는 자원 고갈로 인해 프로세스 또는 시스템에 장애가 발생하는 것입니다.연속적인 블록을 저장할 필요가 있어 저장할 수 없는 경우 장애가 발생합니다.플래그멘테이션에 의해 리소스가 충분하지만 연속되는 양이 아니더라도 이 문제가 발생합니다.예를 들어 컴퓨터에 4GiB의 메모리와 2GiB의 빈 메모리가 있는데 메모리가 1MiB의 빈 메모리, 1MiB의 빈 메모리 순서로 fragment화 되어 있는 경우, 합계 2GiB의 빈 메모리라도 연속되는 1GiB의 요구를 만족시킬 수 없습니다.

이를 피하기 위해 할당자는 실패하는 대신 디플래그(또는 메모리 압축 사이클) 또는 주요 가비지 수집 사이클 등의 기타 자원 재확보를 트리거하여 요구를 충족시킬 수 있을 것으로 기대할 수 있습니다.이를 통해 프로세스를 계속할 수 있지만 성능에 심각한 영향을 미칠 수 있습니다.

성능 저하

플래그멘테이션은 여러 가지 이유로 퍼포먼스를 저하시킵니다.기본적으로 플래그멘테이션은 리소스 할당 및 액세스에 필요한 작업을 증가시킵니다.예를 들어 하드 드라이브나 테이프 드라이브에서는 시퀀셜 데이터 읽기는 매우 빠르지만 다른 주소를 찾는 것은 느리기 때문에 단편화된 파일을 읽거나 쓰려면 수많은 검색이 필요하며 따라서 장치의 마모가 더 심해질 수 있습니다.또, 자원을 fragment화하지 않는 경우는, 빈 영역의 개시로부터 1개의 블록을 되돌리는 것으로, 간단하게 할당 요구를 만족시킬 수 있다.단, 이 요구는 fragment화되어 있기 때문에 충분한 빈 블록을 검색해야 합니다.이러한 요구는 시간이 오래 걸릴 수 있습니다.또는 몇 개의 작은 블록에 의해 요구를 충족시켜야 합니다(가능한 경우).그 결과, 이 할당은 fragment화 되어, 복수의 부분을 관리하기 위해서 추가의 오버헤드가 필요합니다.

하위 문제는 단편화가 개별 데이터가 아닌 캐시 보유 블록으로 인해 캐시를 너무 빨리 소진하여 스레싱을 발생시킬 수 있다는 것입니다.예를 들어 프로그램이 256KiB의 작업 세트를 가지고 있고 256KiB 캐시(L2 명령+데이터 캐시 등)를 가진 컴퓨터에서 실행 중이기 때문에 전체 작업 세트가 캐시에 적합하므로 적어도 캐시 적중률 측면에서 빠르게 실행된다고 가정합니다.게다가 64개의 Translation Lookaside Buffer(TLB; 변환 룩사이드버퍼) 엔트리가 각각4 KiB 페이지용으로 설정되어 있다고 합니다.각 메모리액세스에는 가상에서 물리로의 변환이 필요합니다.이 변환은 페이지가 캐시(여기서는 TLB)에 있는 경우 고속입니다.작업 세트가 fragment화 되어 있지 않은 경우는, 64 페이지(페이지 작업 세트가 64 페이지)에 들어가, 모든 메모리 룩업을 캐시로부터 처리할 수 있습니다.다만, 작업 세트가 fragment화되어 있는 경우는, 64 페이지에 들어가지 않고, 스레싱에 의해서 실행이 늦어집니다.작업 중에 페이지는 TLB 에 추가 및 삭제가 반복됩니다.따라서 시스템 설계의 캐시 사이징에는 플래그멘테이션을 고려할 수 있는 마진을 포함해야 합니다.

메모리 플래그멘테이션은 시스템 [citation needed]매니저가 직면한 가장 심각한 문제 중 하나입니다.시간이 지남에 따라 시스템 성능 저하로 이어집니다.최종적으로 메모리 플래그멘테이션으로 인해 (애플리케이션에서 사용 가능한) 빈 메모리가 완전히 손실될 수 있습니다.

메모리 플래그멘테이션은 커널 프로그래밍 수준의 문제입니다.애플리케이션의 리얼타임 컴퓨팅에서는, 플래그멘테이션 레벨이 99%에 달해, 시스템 크래시나 그 외의 [citation needed]불안정성의 원인이 되는 일이 있습니다.메모리 플래그멘테이션의 중대 수준 상승을 예상하는 것은 불가능하기 때문에 이러한 유형의 시스템 크래시를 피하기 어려울 수 있습니다.단, 메모리 플래그멘테이션이 과도한 경우 시스템에서 일부 프로그램을 계속 실행하는 것은 불가능할 수 있지만, 시스템 자체에서 사용되는 메모리 블록을 이동하여 사용 가능한 메모리를 보다 적은 수의 대용량 bl로 통합할 수 있도록 함으로써 적절하게 설계된 시스템은 중대한 플래그멘테이션 상태에서 회복할 수 있어야 합니다.ok, 또는 최악의 경우 일부 프로그램을 종료하고 메모리를 해방한 후 결과적으로 사용 가능한 메모리의 합계를 조각 모음합니다.이것에 의해, 적어도 시스템 장해의 의미에서의 진정한 크래시는 회피할 수 있어 일부의 프로그램을 계속 실행하거나 프로그램 데이터를 보존하거나 할 수 있습니다.또한 플래그멘테이션은 시스템소프트웨어 설계의 현상입니다.소프트웨어에 따라서는 플래그멘테이션의 영향을 받기 쉬우며 메모리 플래그멘테이션의 결과로 프로세스를 강제로 셧다운하거나 정지하지 않는 시스템을 설계할 수도 있습니다.

유사 현상

플래그멘테이션은 메모리 할당의 문제로 가장 잘 알려져 있지만, 다른 자원,[5] 특히 프로세서에 대해서도 유사한 현상이 발생합니다.예를 들어 프리엠프티브멀티태스킹에 타임셰어링을 사용하지만 프로세스가 차단되었는지 여부를 체크하지 않는 시스템에서는 타임슬라이스의 일부분은 실행되지만 타임슬라이스의 나머지 부분은 블록되어 처리되지 않는 프로세스가 타임슬라이스의 내부 플래그멘테이션으로 인해 시간을 낭비합니다.보다 근본적으로는, 시분할 자체는, 1회의 중단 없는 실행이 아니고, 단편화된 타임 슬라이스로 실행되기 때문에, 프로세스의 외부 fragment화를 일으킵니다.프로세스 스위칭 비용 및 동일한 캐시를 사용하는 여러 프로세스로 인한 캐시 압력 증가로 인해 성능이 저하될 수 있습니다.

동시 시스템(특히 분산형 시스템)에서 프로세스를 진행하기 위해 프로세스 그룹이 상호 작용해야 하는 경우, 프로세스가 다른 시간 또는 다른 머신(시간 또는 머신에 걸쳐 단편화됨)에 스케줄링되어 있는 경우, 서로 대기하거나 서로 통신하는 데 소요되는 시간이 성능을 크게 저하시킬 수 있습니다.대신 퍼포먼스 시스템에서는 그룹의 [5]동시 스케줄링이 필요합니다.

일부 플래시 파일 시스템에는 "데드 공간" 및 "암흑 공간"[6]과 같은 여러 가지 종류의 내부 조각화가 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Null, Linda; Lobur, Julia (2006). The Essentials of Computer Organization and Architecture. Jones and Bartlett Publishers. p. 315. ISBN 9780763737696. Retrieved Jul 15, 2021.
  2. ^ "Partitioning, Partition Sizes and Drive Lettering". The PC Guide. April 17, 2001. Retrieved 2012-01-20.
  3. ^ "Switches: Sector copy". Symantec. 2001-01-14. Retrieved 2012-01-20.
  4. ^ D. Samanta."클래식 데이터 구조" 2004. 페이지 76
  5. ^ a b Ousterhout, J. K. (1982). "Scheduling Techniques for Concurrent Systems" (PDF). Proceedings of Third International Conference on Distributed Computing Systems. pp. 22–30.
  6. ^ 아드리안 헌터."UBIFS 설계 개요" . 2008 . etc . 8 .

원천