カーネルに断片化されたメモリを圧縮させる方法

カーネルに断片化されたメモリを圧縮させる方法

私は走っていますFedora 26

これは私のアルゴリズム教授の非常に奇妙な課題です。宿題は次のように言います。

Cのメモリ断片化:
以下を実行するCプログラムを設計、実装、および実行します。3mサイズ800,000の配列の各シーケンスにメモリを割り当て、次にすべての偶数配列を明示的に解放し、mサイズ900,000の配列シーケンスの各配列シーケンスを割り当てます。プログラムが最初のシーケンスと2番目のシーケンスを配布するのにかかる時間を測定します。mプログラムで利用可能な主メモリをほぼすべて使用する場合に選択します。 」

これの全体的な目的は、メモリを断片化し、使用可能なメモリより少し隣接するメモリブロックを要求して、オペレーティングシステムにメモリを圧縮またはデフラグすることです。

授業の時に記憶は視覚的で実際に連続的ではないので、どうすればいいのかと尋ね、彼は「まあ、[仮想メモリ]をオフにしなければなりません。」と答えました。 「ガベージコレクション」に達すると、「ガベージコレクションにかかる時間のため、2番目の割り当て時間は最初の割り当て時間より大きくなければなりません」と言います。

数回検索した後、仮想メモリを無効にする最も近い方法はを使用することでしたswapoff -a。デスクトップ環境を無効にし、基本端末でプログラムをコンパイルして実行しました(特にデスクトップ環境などの重いプロセスなど、他のプロセスの干渉を避けるため)。 。私はこれを行い、m2番目の割り当てが最初の割り当てよりも時間がかかるポイントに達するまで、ますます速い速度でプログラムを実行しました。

速度を上げながらプログラムを実行してmみると、結局、2番目の割り当てが最初の割り当てよりも時間がかかることがわかりました。しかし、このプロセスでは、2番目の割り当て前にプロセスが終了するという問題が発生しました。確認してみると-killerによって殺されたdmesgことがわかりましたoom。 -killerに関するいくつかの記事を見つけて読んで、oomカーネルによるメモリの過剰割り当てを無効にできることがわかりました。

私はこれをして私のプログラムを再実行しますが、今回はm2番目の時間が最初の時間よりも高いものを見つけることができません。結局、mが大きくなると(過剰割り当てが有効な場合よりはるかに小さいですが)、mallocは失敗し、プログラムは終了します。

3つの質問がありますが、最初のものはそれほど重要ではありません。

  1. ガベージコレクションは正しい用語ですか?教授はそれがガベージコレクションであると非常にしっかりと述べましたが、私はガベージコレクションがプログラミング言語によって実行されると仮定しています。

  2. Linuxシステムで目的の圧縮を達成することは可能ですか?

  3. スワップを無効にしてもメモリオーバー割り当てを有効にしている場合、最初の割り当てよりも長い時間に2番目の割り当てに到達できるのはなぜですか?圧縮は実際に起こりますか?それでは、メモリオーバー割り当てを無効にしても圧縮が発生するポイントに到達できないのはなぜですか?

答え1

これまで調べていただきありがとうございます。これは本当に興味深い質問です。

ここでは一般的に考慮すべき重要な側面があります。メモリ割り当ては、部分的にはオペレーティングシステムの責任であり、部分的には実行中の各プロセスの責任です(メモリ保護と仮想アドレス空間を持たない古いシステムは無視されます)。オペレーティングシステムは、各プロセスに固有のアドレス空間を提供し、必要に応じてプロセスに物理メモリを割り当てる役割を果たします。各プロセスは、アドレス空間をある程度分割し、適切に使用できるようにする役割を果たします。ランタイム環境はほとんどのタスクを処理するため、プロセスの責任はプログラマーにとってほとんど見られません。

今あなたの質問に答えてみましょう...

  1. 私が見るには、ガベージコレクションがここで行うことから一歩離れたようです。私の考えでは、malloc()andを使ってCで書いているようですfree()ゴミ収集、プログラミング言語がサポートしている場合そしてランタイム環境は後者の部分を担当します。以前に割り当てられているが使用されなくなった(重要なことには再び使用できない)メモリブロックを識別して、アロケータに返します。質問がリンクされました存在するジェイドBP~のコメントいくつかの背景知識が提供されているが、人々ごとにガベージコレクション、さらにはガベージコレクションを構成する要素について非常に異なる見解を持っていることを示すので、最も興味深かった。

    私たちの関心の文脈では、「メモリ圧縮」を使用して問題のプロセスについて話しましょう。

  2. ユーザ空間プログラミングの観点から教授が要求するのは簡単な理由で、LinuxのCでは不可能です。我々は、物理メモリの断片化ではなく、アドレス空間の断片化に興味があります。 800,000バイトのブロックを多数割り当てると、各ブロックへのポインタの数が等しくなります。 Linuxでは、この時点でOS自体は多くの作業を実行せず、各割り当てをバックアップするための物理メモリは必ずしも必要ではありません(BTW、小規模な割り当ての場合、OSはまったく関与せず、Cライブラリのみに関与します)。アロケータただし、割り当てはCライブラリがそれを使用するのに十分な大きさであり、mmapこれはカーネルによって処理されます。奇数ブロックを解放すると、対応するアドレス空間ブロックを再取得することができますが、他のブロックへのポインタを変更することはできません。いつでもポインタを印刷すると、ポインタ間の差が900,000バイトブロックの割り当て要求(私のシステムでは802,816バイト)より大きくなく、2つのポインタの間にスペースがないことがわかります。 。プログラムには、より抽象的な値(他のコンテキストのハンドル)ではなく、各ブロックへの実際のポインタがあるため、ランタイム環境はこれについて何もできないため、使用可能なブロックを統合するためにメモリを圧縮することはできません。

    ポインタがプログラマに見える概念ではなく、プログラミング言語を使用している場合は、Linuxでメモリを圧縮できます。もう1つの可能性は、戻り値がポインタではなくメモリ割り当てAPIを使用することです。たとえば、Windowsのハンドルベースのヒープ割り当て関数を参照してください(ポインタは、ハンドルがロックされている場合にのみ有効です)。

  3. あなたが教える運動は、mmapフリーブロックウォーキングアルゴリズムを含むパフォーマンスを効果的に測定することです。まず3×を割り当てます。ブロックして半分を解除して割り当てを開始します。再びブロックを解放します。これらすべてのブロックを解放すると、カーネルアロケータに多くの利用可能なブロックがダンプされます。カーネルはそれを追跡する必要があります(呼び出しにかかる時間は、freeこの時点で最適化が発生しないことを示します)。各個々のブロックの割り当て時間を追跡すると、最初の900k割り当てに時間がかかることがわかります。たくさん他の割り当てより長く(私のシステムでは3倍)、2番目の割り当てははるかに高速でしたが、それでも時間がかかり(2倍)、3番目の割り当ては一般的なパフォーマンスレベルに戻りました。したがって、何かが起こっていますが、返されたポインタはそれがメモリ圧縮ではなく、少なくとも割り当てブロック圧縮(言及どおりに不可能)ではないことを示します。おそらく時間は、カーネルが追跡されたデータ構造を処理するために使用する時間に対応します。利用可能なアドレス空間プロセス(これを確認しており、後で更新する予定です)。これらの長い割り当ては、測定中の全体の割り当て順序を減らすことができます。つまり、900k の割り当ては 800k の割り当てより長くなります。

    悪用によって動作が変わる理由は、練習が純粋にアドレス空間を操作することから実際にメモリを割り当てることに変わり、遊び場のサイズが小さくなるためです。オーバーコミットできる場合、カーネルはプロセスアドレス空間によってのみ制限されるため、より多くのブロックを割り当て、アロケータにより多くの圧力を加えることができます。オーバーコミットを無効にすると、カーネルは使用可能なメモリによって制限されるため、アロケータm圧力が割り当て時間を超えるのに十分なレベルにない可能性がある値が減少します。

関連情報