8

と について混乱heapしてfree listいます。いくつか質問がありますが、C で malloc がどのように機能するかについては理解しています。間違っている場合は修正してください。

  • ヒープ メモリは、データ ブロックのリンクされたリスト (フリー リスト) として構成されていますか?
  • ヒープメモリとフリーリストに違いはありますか?

ストレージ割り当てに関する私の理解 (改善の余地あり) :- malloc を呼び出すと、ヒープにメモリが割り当てられ、適切なサイズのデータ​​ ブロックを から選択することによって行われfree listます。

malloc によって特定のメモリ ブロックが返されると、そのブロックはフリー リストから削除され、そのメモリ ブロックの物理アドレスがページ テーブルで更新されます。

を使用してメモリが解放されるfree()と、データ ブロックがフリー リストに挿入され、断片化を減らすために、隣接するブロックと結合さpresentれ、ページ テーブル エントリのビットがクリアされます。

したがって、ヒープ全体はフリーリスト（フリーブロックのリンクリスト）+割り当てられたデータブロックです。

それはストレージ割り当ての全体像ですか?

編集：Linuxカーネル開発（Robert Love）の章からメモリ管理、スラブ割り当て

「空きリストには、使用可能な、既に割り当てられているデータ構造のブロックが含まれています。コードがデータ構造の新しいインスタンスを必要とする場合、十分な量のメモリを割り当てて設定するのではなく、空きリストから構造の 1 つを取得できます。後でデータ構造が不要になると、割り当てを解除するのではなく、フリー リストに戻します。この意味で、フリー リストはオブジェクト キャッシュとして機能し、頻繁に使用されるタイプのオブジェクトをキャッシュします。

フリーリストは、「利用可能な、割り当てられたデータ構造のブロック」として言及されています。

  • フリーリストにある場合、どのように割り当てられますか?
  • そして、メモリのブロックを解放リストに返すことは、そのブロックの割り当てを解除することと同じではありませんか?
  • スラブの割り当てとストレージの割り当ての違い
4

3 に答える 3

8

malloc()ページテーブルとは実際には関係ありません。仮想アドレスを割り当て、カーネルはページが実際に物理 RAM またはディスク上のどこに格納されているかを追跡します。

malloc()システムコールを介してカーネルと対話します。brk()システムコールは、カーネルにプロセスにより多くのページを割り当てるように要求するか、ページを解放してカーネルに戻します。したがって、実際には 2 つのレベルのメモリ割り当てがあります。

  • カーネルはページをプロセスに割り当て、それらのページを他のプロセスが使用できないようにします。カーネルの観点からは、ページはどこにでも配置でき、その場所はページ テーブルによって追跡されますが、プロセスの観点からは、連続した仮想アドレス空間です。操作する「プログラムブレーク」brk()は、カーネルがアクセスできるアドレス (割り当てられたページに対応するため) と、アクセスしようとするとセグメンテーション違反を引き起こすアドレスとの間の境界です。
  • malloc()プログラムで使用するために、プログラムのデータ セグメントの可変サイズ部分を割り当てます。データ セグメントの現在のサイズ内に十分な空き領域がない場合brk()、カーネルからより多くのページを取得するために使用され、データ セグメントが大きくなります。データ セグメントの末尾に未使用のスペースがあることが判明すると、使用brk()されていないページをカーネルに戻して、データ セグメントを小さくします。

そのプロセスで実行されているプログラムが実際にはページを何にも使用していない場合でも、ページを (カーネルによって) プロセスに割り当てることができることに注意してください。free()メモリのブロックがデータ セグメントの中央にある場合、より高いアドレスに割り当てられた他のブロックがまだあるため、 の実装を使用してデータ セグメントを縮小することはできませfree()ん。brk()そのため、ページはカーネルの観点からは「空き領域」であっても、プログラムに割り当てられたままになりますmalloc()。

フリーリストがどのように機能するかについてのあなたの説明は私には正しいように思えますが、私はメモリアロケータがどのように実装されているかについての専門家ではありません. しかし、Robert Love から投稿された引用は、Linux カーネル内のメモリ割り当てについて話しているように聞こえます。これはmalloc()、ユーザー空間プロセス内のメモリ割り当てとは無関係です。その種の空きリストは、おそらく動作が異なります。

于 2012-04-12T01:40:25.990 に答える
3

最初にやりたいことは、カーネルとプログラムの割り当てを区別することです。@Wyzardが言ったように、mallocはbrk（sbrk、場合によってはmmap）を使用して、カーネルからより多くのページを取得します。私のmallocの理解は非常に良いものではありませんが、それはあなたがアリーナと呼ぶかもしれないものを追跡します。メモリへのアクセスを仲介し、必要に応じてメモリを割り当てるために適切なシステムコールを行います。

フリーリストは、メモリを管理する1つの方法です。カーネルからより多くのメモリが必要になるたびにmmapまたはbrkを呼び出すのは遅く、非効率的です。これらは両方とも、カーネルモードへのコンテキストスイッチを必要とし、どのプロセスがメモリを所有しているかを追跡するためにデータ構造を割り当てます。ユーザーレベルの空きリストは、メモリを常に要求してカーネルに返すことのないように最適化されています。ユーザープログラムの目標は、カーネルがその作業を行うのを待つのではなく、その作業を行うことです。

今あなたの他の質問に答えるために：

  • フリーリストにある場合、どのように割り当てられますか？

フリーリストを考える別の方法は、キャッシュとしてです。プログラムはリクエストを作成し、カーネルはそれらを一度にすべてではなくオンデマンドで実行しようとします。ただし、プログラムがメモリの一部で実行される場合、高速パスはこれをカーネルに返すのではなく、安全な場所に置いて再度割り当てることです。特に、フリーリストはアロケータがプルできるメモリ領域を追跡できますが、ユーザーコードがそれを採用してすべてを上書きし始めることができないような方法で（メモリ保護を使用して）追跡できます。 。

  • そして、メモリのブロックをフリーリストに戻すことは、そのブロックの割り当てを解除することと同じではありませんか？

ブロックの割り当てを本当に解除するには、これをカーネルに返して内部ページテーブルを更新する必要があると仮定すると、違いは実際には、基になる物理ページ（またはフレーム）を制御できるものにあります。実際にメモリの割り当てを解除してカーネルに戻すと、カーネルはこれらのページからプルできるようになりますが、ユーザーレベルのフリーリストに戻すと、プログラムの一部が引き続きそのメモリを制御することになります。

  • スラブの割り当てはストレージの割り当てとどのように異なりますか？

これは、いくつかの異なる領域を取得し始めています（私はあまりよく知らない）。スラブアロケータは、カーネルがメモリ割り当てを管理する1つの方法です。私が見たところ、スラブは割り当てをさまざまなサイズにグループ化しようとし、それらの要求を満たすためのページのプールを持っています。一般的なx86アーキテクチャでは、16バイトから4 MBまでの2の累乗で、連続した物理メモリを割り当てることができると思います（64ビットマシンを使用していますが）。このレベルのフリーリストの概念と、さまざまなシステムニーズに対応するために割り当てサイズを効率的にアップグレードまたはダウングレードする方法があると思います。

一方、ストレージの割り当ては、ハードディスクに空き容量があることを確認するように聞こえます。私は実際にその用語を聞いたことがないので、推測することしかできません。

于 2012-04-12T02:25:49.130 に答える
1

ここでは、2 つの異なるアロケーターを参照しています。

  1. Zone にページを割り当てるために使用されるバディ システム アロケータは、free_list を使用して空きページを保存し、解放した後にそれらを割り当てます。
  2. keme_cache,kmalloc 呼び出しなど、既に割り当てられているデータ構造で動作するスラブ アロケーター。

ヒープについては、C プログラミングのヒープ メモリを参照してください。

ユーザー空間の ac プログラムの場合、malloc が行われる call_stack にヒープ メモリがあります。これは、より多くのメモリが必要な場合に sbrk() によって進められる _break によってマークされます。

Linux カーネルでは、各プロセスに task_struct があり、独自のスタックと、プロセスが使用するページのリストへのポインターがあります。

于 2016-10-04T07:34:17.743 に答える