현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

버디 시스템과 외부단편화

익명 사용자의 이미지
글쓴이: 익명 사용자 / 작성시간: 목, 2002/09/26 - 3:14오전

버디시스템에서 외부단편화를 어떻게 해결했는지 알고자 합니다.

책에는 어떻게 메모리를 관리한다고만 나왔지 외부단편화를 해결하는 방법
은 나오지 않았습니다.

가르쳐 주세요..

Forums: 
프로그래밍 QnA
익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 목, 2002/09/26 - 9:40오전

buddy 할당 알고리즘에서 외부 단변화 현상을 보완한다는 것은
할당 단위가 고정적이기 때문입니다.

전에 제가 Buddy Algorithm의 예를 찾아서 정리해둔게 있으니
한번 보시길 바랍니다..

Buddy Algorithm의 예
http//www.ezdoum.com/stories.php?story=02/04/30/4581208

버디 알고리즘이 외부 단편화 현상을 해결했다고는 하나,
할당 단위가 2,4,8,16.. 이런식으로 될때
10을 할당을 요청했다면 16이 선택이 되어서 6이란 공간이
낭비가 되는 문제점이 있지요... (내부 단편화..)

그래서 요즘의 운영체제는 규격화된, 단위로 할당을 하고
그것을 그 할당받은 공간을
다시 서브 할당자를 두는 구조를 두고 있습니다.

리눅스 커널에서 슬랩 할당자가 그런것이겠죠..
또 malloc도 매번 커널로부터 할당을 요청하는게 아니라,
한번 통으로 받아놓고, 자체적인 힙관리를 하게됩니다.

슬랩 할당자 (Slab Allocator) An Object-Caching Kernel Memory Allocator
http//www.ezdoum.com/stories.php?story=02/04/12/3305082

메모리 할당자는 어느게 정답이란 것이 없고.
요청하는 메모리 패턴에 따라서 최적의 것을 선택하는 것이죠

hankyu의 이미지

글쓴이: hankyu / 작성시간: 화, 2020/04/14 - 11:58오후

Buddy System 알고리즘
사용하지 않는 모든 페이지 프레임을 그룹별로 묶어서 블록 리스트 10개에 넣는다.

각 리스트는 연속된 페이지 프레임 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024개로 구성된 그룹을 담는다. 블록의 첫 번째 페이지 프레임의 물리적인 주소는 그룹 크기의 배수다.

16-페이지 프레임의 시작 주소는 16*4K의 배수다(212 = 4096으로 정규 페이지 크기).

Buddy system 알고리즘 예
누군가 연속된 페이지 프레임 256개로 구성된 그룹(즉 1024KB)을 요청했다고 하자. 버디 시스템 알고리즘은 먼저 256-페이지-프레임 리스트에 여유 블록이 있는지 검사한다.

버디 시스템 알고리즘 - Struct ZONE 구조
[버디 시스템 알고리즘] Struct ZONE 구조

여유 블록이 없으면 다음으로 큰 블록, 즉 512-페이지 프레임 리스트에서 여유 블록을 찾는다.


여기서 여유 블록을 발견하면 페이지 프레임 512개 중에서 256개를 요청한 쪽으로 할당하고, 나머지 페이지 프레임 256개를 여유 256-페이지 프레임 블록 리스트에 추가한다. 이것이 버디 시스템 알고리즘 특징이다.

여유 512-페이지 블록이 없다면 다음으로 큰 블록, 즉 1024-페이지 프레임에서 블록을 찾는다. 여기서 블록을 찾으면 페이지 프레임 1024개 중 256개를 요청한 쪽으로 할당하고, 나머지 768개 중 처음 512개를 여유 512-페이지-프레임 블록 리스트에, 남은 페이지 프레임 256개를 여유 256-페이지 프레임 블록의 리스트에 넣는다.

출처: https://codingcoding.tistory.com/211 [코딩 기록]

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.