나는 달리고 있다 Fedora 26.
이것은 내 알고리즘 교수의 매우 이상한 과제입니다. 숙제는 다음과 같이 말합니다.
C의 메모리 조각화:
다음을 수행하는 C 프로그램을 설계, 구현 및 실행합니다.3m크기가 800,000인 배열의 각 시퀀스에 대해 메모리를 할당한 다음 모든 짝수 배열을 명시적으로 해제하고m크기가 900,000인 배열 시퀀스의 각 배열 시퀀스를 할당합니다. 프로그램이 첫 번째 시퀀스와 두 번째 시퀀스를 배포하는 데 걸리는 시간을 측정합니다.m프로그램에서 사용할 수 있는 주 메모리를 거의 모두 사용 하려면 선택합니다 . "
이것의 전반적인 목표는 메모리를 조각화한 다음 사용 가능한 것보다 약간 더 인접한 메모리 블록을 요청하여 운영 체제가 메모리를 압축하거나 조각 모음하도록 하는 것입니다.
수업 시간에 기억은 시각적이고 실제로 연속적이지 않기 때문에 어떻게 해야 하느냐고 물었고, 그는 "글쎄, [가상 메모리]를 꺼야 해요."라고 대답했습니다. "가비지 수집"에 도달하면 "가비지 수집에 걸리는 시간 때문에 두 번째 할당 시간은 첫 번째 할당 시간보다 커야 합니다."라고 말합니다.
몇 번 검색한 후 가상 메모리를 비활성화하는 가장 가까운 방법은 를 사용하는 것이었습니다 swapoff -a. 데스크탑 환경을 비활성화하고 기본 터미널에서 프로그램을 컴파일하고 실행했습니다(특히 데스크탑 환경과 같은 무거운 프로세스와 같은 다른 프로세스의 간섭을 피하기 위해). . 나는 이렇게 하고 m두 번째 할당이 첫 번째 할당보다 오래 걸리는 지점에 도달할 때까지 점점 더 빠른 속도로 프로그램을 실행했습니다 .
속도를 높이면서 프로그램을 실행 m해 보니 결국 두 번째 할당이 첫 번째 할당보다 시간이 더 오래 걸리는 것을 발견했습니다. 그런데 이 과정에서 두 번째 할당 전에 프로세스가 종료되는 문제가 발생했습니다. 확인해 보니 -killer에 의해 살해된 dmesg것으로 나타났습니다 oom. -killer에 대한 여러 기사를 찾아서 읽었으며 oom커널에 의한 메모리 과잉 할당을 비활성화할 수 있다는 것을 알았습니다.
나는 이것을 하고 내 프로그램을 다시 실행하는데, 이번에는 m두 번째 시간이 첫 번째 시간보다 더 높은 것을 찾을 수 없습니다. 결국 m이 커지면(과잉 할당이 활성화된 경우보다 훨씬 작지만) malloc이 실패하고 프로그램이 종료됩니다.
세 가지 질문이 있는데 첫 번째는 그다지 중요하지 않습니다.
가비지 수집이 올바른 용어인가요? 교수님은 그것이 가비지 수집이라고 매우 단호하게 말씀하셨지만, 나는 가비지 수집이 프로그래밍 언어에 의해 수행된다고 가정하고 있으며 이것이 더 조각 모음으로 간주될 것입니다.
Linux 시스템에서 원하는 압축을 달성하는 것이 가능합니까?
스왑을 비활성화했지만 여전히 메모리 초과 할당을 활성화한 경우 첫 번째 할당보다 더 긴 시간에 두 번째 할당에 도달할 수 있는 이유는 무엇입니까? 압축이 실제로 발생합니까? 그렇다면 메모리 초과 할당을 비활성화한 후에도 압축이 발생하는 지점에 도달할 수 없는 이유는 무엇입니까?
답변1
지금까지 조사해 주셔서 감사합니다. 이것은 참으로 흥미로운 질문입니다.
여기서 일반적으로 고려해야 할 중요한 측면이 있습니다. 메모리 할당은 부분적으로는 운영 체제의 책임이고 부분적으로는 실행 중인 각 프로세스의 책임입니다(메모리 보호 및 가상 주소 공간이 없는 이전 시스템은 무시). 운영 체제는 각 프로세스에 고유한 주소 공간을 제공하고 필요한 경우 프로세스에 실제 메모리를 할당하는 역할을 합니다. 각 프로세스는 주소 공간을 어느 정도 분할하고 적절하게 사용되도록 하는 역할을 담당합니다. 런타임 환경이 대부분의 작업을 처리하기 때문에 프로세스의 책임은 프로그래머에게 거의 보이지 않습니다.
이제 귀하의 질문에 답변해 드리자면...
내가 보기에는 가비지 수집이 여기서 수행하는 작업에서 한 발짝 떨어진 것 같습니다. 내 생각에는
malloc()and를 사용하여 C로 작성하고 있는 것 같습니다free().쓰레기 수거, 프로그래밍 언어가 지원하는 경우그리고런타임 환경은 후자 부분을 담당합니다. 이전에 할당되었지만 더 이상 사용되지 않는(중요하게 다시는 사용할 수 없는) 메모리 블록을 식별하여 할당자에게 반환합니다.질문이 연결됨존재하다제이드 BP~의논평몇 가지 배경 지식이 제공되었지만, 사람들마다 가비지 수집, 심지어 가비지 수집을 구성하는 요소에 대해 매우 다른 견해를 갖고 있음을 보여주기 때문에 가장 흥미로웠습니다.우리의 관심의 맥락에서 "메모리 압축"을 사용하여 문제의 프로세스에 대해 이야기하겠습니다.
사용자 공간 프로그래밍 관점에서 교수가 요구하는 것은 간단한 이유 때문에 Linux의 C에서는 불가능합니다. 우리는 물리적 메모리 조각화가 아니라 주소 공간 조각화에 관심이 있습니다. 800,000바이트 블록을 많이 할당하면 각 블록에 대한 포인터 수가 동일해집니다. Linux에서는 이 시점에서 OS 자체가 많은 작업을 수행하지 않으며 각 할당을 백업할 물리적 메모리가 반드시 필요한 것은 아닙니다(BTW, 소규모 할당의 경우 OS는 전혀 관여하지 않고 C 라이브러리만 관여합니다). 할당자; 그러나 여기서 할당은 C 라이브러리가 이를 사용할 만큼 충분히 크며
mmap이는 커널에 의해 처리됩니다. 홀수 블록을 해제하면 해당 주소 공간 블록을 다시 얻을 수 있지만 다른 블록에 대한 포인터를 변경할 수는 없습니다. 언제든지 포인터를 인쇄해 보면 포인터 간의 차이가 900,000바이트 블록에 대한 할당 요청(내 시스템에서는 802,816바이트)보다 크지 않고 두 포인터 사이에 공간이 없다는 것을 알 수 있습니다. . 프로그램에는 좀 더 추상적인 값(다른 컨텍스트의 핸들)이 아닌 각 블록에 대한 실제 포인터가 있기 때문에 런타임 환경은 이에 대해 아무 것도 할 수 없으므로 사용 가능한 블록을 통합하기 위해 메모리를 압축할 수 없습니다.포인터가 프로그래머에게 보이는 개념이 아닌 프로그래밍 언어를 사용하는 경우 Linux에서 메모리 압축이 가능합니다. 또 다른 가능성은 반환 값이 포인터가 아닌 메모리 할당 API를 사용하는 것입니다. 예를 들어 Windows에서 핸들 기반 힙 할당 함수를 참조하세요(포인터는 핸들이 잠겨 있을 때만 유효함).
귀하가 가르치는 운동은
mmap자유 블록 걷기 알고리즘을 포함하여 성과를 효과적으로 측정하는 것입니다. 먼저 3 ×를 할당합니다.쌀차단하고 절반을 해제한 다음 할당을 시작합니다.쌀다시 블록을 해제합니다. 이러한 모든 블록을 해제하면 커널 할당자에 많은 사용 가능한 블록이 덤프됩니다. 커널은 이를 추적해야 합니다(호출하는 데 걸리는 시간은free이 시점에서 최적화가 발생하지 않음을 나타냅니다). 각 개별 블록의 할당 시간을 추적해 보면 첫 번째 900k 할당에 많은 시간이 소요되는 것을 알 수 있으며,많은다른 할당보다 길었고(내 시스템에서는 3배), 두 번째 할당은 훨씬 빨랐지만 여전히 더 오래 걸렸고(2배), 세 번째 할당은 일반적인 성능 수준으로 돌아왔습니다. 따라서 어떤 일이 일어나고 있지만 반환된 포인터는 그것이 메모리 압축이 아니며 적어도 할당 블록 압축(언급한 대로 불가능함)이 아님을 나타냅니다. 아마도 시간은 커널이 추적된 데이터 구조를 처리하는 데 사용하는 시간에 해당합니다. 사용 가능한 주소 공간 프로세스(이 내용을 확인 중이며 나중에 업데이트할 예정입니다). 이러한 긴 할당은 측정 중인 전체 할당 순서를 왜소하게 만들 수 있습니다. 즉, 900k 할당은 800k 할당보다 오래 걸립니다.남용으로 인해 동작이 바뀌는 이유는 연습이 순전히 주소 공간을 조작하는 것에서 실제로 메모리를 할당하는 것으로 바뀌어 놀이터의 크기가 줄어들기 때문입니다. 오버커밋할 수 있으면 커널은 프로세스 주소 공간에 의해서만 제한되므로 더 많은 블록을 할당하고 할당자에 더 많은 압력을 가할 수 있습니다. 오버커밋을 비활성화하면 커널은 사용 가능한 메모리에 의해 제한되므로
m할당자 압력이 할당 시간을 초과할 정도로 충분하지 않은 수준으로 가질 수 있는 값이 줄어듭니다.