移転（コンピューティング）

ソフトウェア開発において、再配置とは、プログラムの位置依存コードとデータにロードアドレスを割り当て、割り当てられたアドレスを反映するようにコードとデータを調整するプロセスです。 ^{[ 1 ] [ 2 ]}

リンカは通常、シンボル解決と連携して再配置を実行します。シンボル解決とは、プログラムを実行する前に、ファイルやライブラリを検索して、シンボル参照やライブラリ名をメモリ内の実際に使用可能なアドレスに置き換えるプロセスです。

再配置は通常、リンカによってリンク時に行われますが、再配置ローダによってロード時に行われる場合や、実行時に実行中のプログラム自体によって行われる場合もあります。

オブジェクトファイルは通常、さまざまなメモリセグメントまたはセクションタイプに分割されます。セグメントタイプの例としては、コードセグメント（.text）、初期化済みデータセグメント（.data）、未初期化データセグメント（.bss）などがあり、その他にもプログラマによって共通セグメントや名前付き静的セグメントなど、さまざまなタイプが存在します。

再配置テーブルは、コンパイラまたはアセンブラによって作成され、オブジェクトファイルまたは実行可能ファイルに格納されるアドレスのリストです。テーブルの各エントリは、オブジェクトコード内の絶対アドレスを参照しており、ローダがプログラムを再配置する際に、正しい場所を参照するように変更する必要があります。再配置テーブルのエントリはフィックスアップと呼ばれ、プログラムを完全な単位として再配置するように設計されています。場合によっては、テーブル内の各フィックスアップ自体がベースアドレス0に対する相対アドレスであるため、ローダがテーブルを移動するにつれてフィックスアップ自体を変更する必要があります。^{[ 2 ]}

一部のアーキテクチャでは、特定の境界（セグメント境界など）を越える修正や、ワード境界に整列していない修正は不正であり、リンカーによってエラーとしてフラグ付けされます。^{[ 3 ]}

リンカはオブジェクトファイル内のセグメント情報と再配置テーブルを読み込み、以下の手順で再配置を実行します。

• 共通タイプのすべてのセグメントを、そのタイプの単一のセグメントにマージする
• 各セグメントおよび各シンボルに重複しない実行時アドレスを割り当て、すべてのコード（関数）およびデータ（グローバル変数）に一意の実行時アドレスを割り当てる。
• 再配置テーブルを参照して、データコードおよびオブジェクトコード内のシンボル参照を修正し、割り当てられた実行時アドレスを指すようにします。

以下の例では、ドナルド・クヌースのMIXアーキテクチャとMIXALアセンブリ言語を使用しています。基本的な原理はどのアーキテクチャでも同じですが、詳細は異なります。

• （A）プログラムSUBRはコンパイルされてオブジェクトファイル（B）が生成されます。（B）は機械語とアセンブリ言語の両方で示されています。コンパイラは、コンパイルされたコードの開始位置を任意の場所（多くの場合、図に示すように位置1）に指定できます。位置13には、位置5にあるステートメントSTへのジャンプ命令の機械語が含まれています。
• （C）SUBRが後で他のコードとリンクされる場合、1以外の場所に格納される可能性があります。この例では、リンカはSUBRを120の位置に配置します。ジャンプ命令のアドレスは現在133の位置にありますが、ステートメントSTのコードの新しい位置（現在は125）を指すように再配置する必要があります。[命令に示されている1 61は、125のMIXマシンコード表現です]。
• （D）プログラムがメモリにロードされて実行される際、リンカによって割り当てられた場所とは異なる場所にロードされる場合があります。この例では、SUBR が現在位置 300 にあることを示しています。ジャンプ命令のアドレスは現在 313 にありますが、 STの更新された位置 305 を指すように再度再配置する必要があります。[4 49 は 305 の MIX マシン表現です]。

アーキテクチャによっては、アドレス割り当てを実行時まで延期することで再配置を完全に回避するものもあります。例えば、ゼロアドレス演算を行うスタックマシンや、コンパイル単位ごとに個別のセグメントにロードされるセグメント化されたアーキテクチャなどが挙げられます。

• ゴミ収集
• ポインタススウィズリングとは、ポインタ変更の遅延的な形式である。
• 事前バインディング
• リベース
• 再配置可能なオブジェクトモジュール形式
• 静的ライブラリ

• ジョンソン、グレン (1975-12-21) [1975-11-13]。11 /34 メモリ管理基本ロジックテスト。デジタル機器株式会社(DEC)。MAINDEC-11-DFKTA-AD。2017-08-19に取得。
• Formaniak, Peter G.; Leitch, David (1977年7月) 「マイクロプロセッサソフトウェア標準案」 BYTE -小型システムジャーナル技術フォーラム第 2巻第 7号、米国ニューハンプシャー州ピーターバラ：Byte Publications, Inc.  34、62–63ページ。ark :/13960/t32245485。2021年12月6日取得。（3ページ）（注：Mostekによる再配置可能な16進フォーマットについて説明しています。）
• Ogdin, Carol Anne; Colvin, Neil; Pittman, Tom; Tubb, Philip (1977年11月) 「再配置可能なオブジェクトコード形式」 BYTE -小型システムジャーナル技術フォーラム第 2巻第 11号、米国ニューハンプシャー州ピーターバラ：Byte Publications, Inc. pp. 198–205。ark :/13960/t59c88b4h、ark:/13960/t3kw76j24。2021年12月6日取得。 （8ページ）（注：TDLによる再配置可能な16進フォーマットについて説明しています。）
• キルダル、ゲイリー・アーレン（1978年2月）[1976] 「絶対マシンコードの静的再配置のための簡単な手法」『ドクター・ドッブズ・ジャーナル・オブ・コンピュータ・カリステニクス＆オーソドンティア』3（2）。ピープルズ・コンピュータ・カンパニー：10–13（66–69）。ISBN 0-8104-5490-4. #22 ark:/13960/t8hf1g21p . 2017-08-19に取得.^{[リンク削除]}。元々は以下で発表されました: Kildall, Gary Arlen (1977) [1976年11月22日～24日]。「絶対マシンコードの静的再配置のための簡単な手法」。米国カリフォルニア州モントレーの海軍大学院で執筆。Titus, Harold A. (編)。会議記録: 第10回アシロマ回路、システム、コンピュータ会議: 1976年11月22日～24日に発表された論文。信号、システム、コンピュータに関するアシロマ会議。米国カリフォルニア州パシフィックグローブ、アシロマホテルおよび会議場: Western Periodicals Company。pp. 420–424。ISSN 1058-6393 。 2021年12月6日取得。  （609ページ）。（この「サイズ変更」方法は、ページ境界再配置と呼ばれ、プログラムの実行に必要なTPAを最大化するために、 MOVCPMを使用してCP/M-80ディスクイメージに静的に適用することができました。また、CP/Mデバッガのダイナミックデバッグツール（DDT）が自身をより高いメモリ領域に再配置するために動的に利用されました。同じアプローチは、IMS AssociatesのBruce H. Van Nattaによって再配置可能なPL/Mコードを生成するために独自に開発されました。段落境界再配置として、この方法の別のバリアントは、後にDR DOS 6.0以降でKEYB、SHARE、NLSFUNCなどの動的HMA自己再配置TSRによって利用されました。やや類似したアプローチに基づく、より洗練されたバイトレベルのきめ細かい方法は、Matthias R. PaulとAxel C. Frinkeによって独自に考案され、常駐ドライバやTSR（FreeKEYBなど）の実行時フットプリントを動的に最小化するための動的デッドコード除去に使用されました。）
• Mossip, Richard H. (1980 年 9 月～10 月)。米国ニュージャージー州ブルーミングデールにて執筆。「再配置可能なコード」(PDF)。S -100 Microsystems。第 1 巻、第 5 号。米国ニュージャージー州マウンテンサイドおよびスプリングフィールド: Libes, Inc. pp . 54–55。ISSN 0199-7955。ark :/13960/s2cfgkmxcwg。ark:/13960/s2qdm1t01nr。2023年 11 月 27 日にオリジナルからアーカイブ(PDF) 。2023年 11 月 27 日に取得。  （2ページ）（注：ページ境界の再配置とアセンブラの再配置について説明します。）
• Huitt, Robert; Eubanks, Gordon ; Rolander, Thomas "Tom" Alan ; Laws, David; Michel, Howard E.; Halla, Brian; Wharton, John Harrison ; Berg, Brian; Su, Weilian; Kildall, Scott ; Kampe, Bill (2014-04-25). Laws, David (編). "Legacy of Gary Kildall: The CP/M IEEE Milestone Dedication" (PDF) (ビデオの書き起こし). Pacific Grove, California, USA: Computer History Museum . CHM 参照番号: X7170.2014. 2014-12-27のオリジナルからアーカイブ(PDF) 。2020-01-19 に取得。[…] Laws: […] OS の「動的再配置」について説明していただけますか? […]ユーバンクス: […]ゲイリーがやったことは […] 驚くべきことでした。 […] 学校で彼が研究室に飛び込んできて、「再配置する方法がわかった」と言った日のことを覚えています。彼は、唯一のバイトが常に最上位バイトになるという事実を利用しました。そして、ビットマップを作成しました。 […] コンピュータのメモリ容量がどれだけあっても、オペレーティングシステムは常に最上位メモリに移動できました。したがって、これを […] メモリ容量の異なるマシンで商用化することができました。 […] 64K CP/Mと 47K CP/M を販売することはできません。アドレスでハードコンパイルするのはばかげています。ゲイリーはある夜、おそらく真夜中にコーディングのことを考えているときにこれを発見し、これが CP/M の商用化を可能にしました。私は、この再配置がなければ、非常に難しい問題だったと思います。人々がそれを購入するには、複雑に思えるでしょうし、メモリを追加する場合は別のオペレーティングシステムを入手しなければなりません。 […] Intel […]は、メモリ アドレスのバイトを逆にしていました。しかし、それらは常に同じ場所にあったので、正確には256 バイト境界で再配置できました。したがって、それらの場所のビットマップだけで常に再配置できました […] 法則: 動的再配置について私がこれまで聞いた中で最も雄弁な説明です […]（33ページ）
• Guzis, Charles "Chuck" P. (2015-07-29). "Re: MOVCPM.COM はどのように動作するのですか？." . Vintage Computer Forum . ジャンル: CP/M および MP/M. 2020-02-01のオリジナルからアーカイブ済み。2020-02-01 に取得。[…] MOVCPM は初期のタイプの PRL フォーマットを使用します。基本的に、CP/Mは 2 回アセンブルされます。2 回目は 100H バイトのオフセットです。2 つのバイナリが比較され、ビットマップが構築されます。ビットがセットされているということは、アドレスの最上位バイトが調整されることを意味します。アドレスの下位バイトは影響を受けません。そのため、「ページ再配置可能ファイル」となります。ビットマップの各バイトは、バイナリデータの 8 バイトに対応します。 […] したがって、MOVCPM で移動するすべてのものは、イメージとその再配置ビットマップの一部です。 […]
• Guzis, Charles "Chuck" P. (2016-11-08). "Re: CP/M アセンブリ プログラムで RST 28h を使用するのは安全ですか? . " Vintage Computer Forum . ジャンル: CP/M および MP/M. 2020-02-01のオリジナルからアーカイブ済み。2020-02-01 に取得。 […] PRL ファイルと、それが元々 MOVCPMで始まった経緯、そしてMP/MおよびCP/M 3.0の不可欠な部分になった経緯について言及しました。しかし、PRL ファイルはビット マップを使用し、各ビットがメモリ位置に対応します。1 ビットは、対応するメモリ位置にページ再配置オフセットを追加する必要があることを示します。絶対メモリ参照 (相対参照とは対照的に) が非常に少ない場合は、ビット マップではなくポインタ リスト (参照ごとに 2 バイト) を使用したい場合があります。これは、相対ジャンプのない8080コードでは考えにくいですが、 Z80コードでは考慮する必要があるかもしれません。これを素早く見つけるコツは、プログラムを2回アセンブルすることです。2回目は100Hオフセットしてアセンブルし、2つのバイナリを比較します。実行時再配置の利点は、再配置の問題を回避しようとするコードに対してペナルティを負う必要がないことです。つまり、「トリック」は不要で、ストレートなコードを書けばよいのです。[…]
• ロス、リチャード・L.（1978年2月）[1977] 「移転は単にプログラムを移動させることではない」『ドクター・ドッブズ・ジャーナル・オブ・コンピュータ・カリステニクス＆オーソドンティア』3（2）。米国カリフォルニア州リッジフィールド：ピープルズ・コンピュータ・カンパニー：14–20（70–76）。ISBN 0-8104-5490-4. #22. 2019年4月20日にオリジナルからアーカイブされました。2019年4月19日に取得。
• カリンガート、ピーター（1979）[1978年11月5日]。「8.2.2 再配置ローダー」。ノースカロライナ大学チャペルヒル校にて執筆。Horowitz 、Ellis（編）『アセンブラ、コンパイラ、およびプログラム変換』コンピュータソフトウェアエンジニアリングシリーズ（初版、第1 刷）。米国メリーランド州ポトマック：Computer Science Press, Inc.、 pp . 237–241。ISBN  0-914894-23-4ISSN 0888-2088 LCCN 78-21905 2020年3月20日取得  （2+xiv+270+6ページ）
• Microsoft OBJ ファイル形式。Microsoft、製品サポートサービス。アプリケーションノート SS0288。2017年8 月 21 日取得。{{cite book}}: CS1メンテナンス: アーカイブサービスは非推奨になりました (リンク)
• Tanenbaum, Andrew Stuart ; Bos, Herbert (2015).現代オペレーティングシステム（第4 版）. Pearson Education Inc. ISBN 978-0-13359162-0。
• Elliott, John C. (2012-06-05) [2000-01-02]. "Microsoft REL形式" . seasip.info . 2020-01-26 のオリジナルからアーカイブ済み. 2020-01-26に取得. […] REL形式は、MicrosoftのM80とDigital ResearchのRMACによって生成されます。 […]
• Brothers, Hardin (1983 年 4 月) 「再配置可能なコードの理解」 . 80 Micro . The Next Step (39). 1001001, Inc. : 38 , 40, 42, 45. ISSN 0744-7868 . 2020 年 2 月 6 日取得。 
• Brothers, Hardin (1985 年 4 月) 「再配置可能なプログラム: マイクロコンピューティングの放浪者」80 Micro . The Next Step (63)。CW Communications/Peterborough, Inc .: 98、100、102–103。ISSN 0744-7868。2020年2月6日取得。 
• Ganssle, Jack (1992年2月) 「再配置可能なコードの記述 - 一部の組み込みコードは複数のアドレスで実行する必要がある」。組み込みシステムプログラミング。The Ganssle Group - Perfecting the Art of Building Embedded Systems / TGG。2019年7月18日のオリジナルからアーカイブ。 2020年2月20日取得。