Chapter 7: Run-Time? Environments
the compiler creates and manages a run-time environment in which it assumes its? target programs are being executed.編譯器創(chuàng)建并管理一個(gè)運(yùn)行時(shí)環(huán)境，并在這個(gè)環(huán)境中模擬目標(biāo)程序的執(zhí)行。
Run-time environment deals with a? variety of issues such as? the? layout and allocation? of? storage locations? for the objects? named in? the source program, the mechanisms used by the target? pro-gram to access variables, the linkages? between procedures, the mechanisms for passing parameters ,? and? the? interfaces? to? the? operating system,? input / output devices ,? and other programs.運(yùn)行時(shí)環(huán)境負(fù)責(zé)處理源程序中的對(duì)象的存儲(chǔ)位置的分布以及分配、目標(biāo)程序存取變量的機(jī)制、過程之間的鏈接、傳遞參數(shù)的機(jī)制、跟操作系統(tǒng)、IO設(shè)備和其他程序交互的接口。
The two themes in this chapter are the allocation of storage locations and access to variables and data. We shall discuss memory management in some detail, including stack allocation, heap management, and garbage collection.這一章的2個(gè)主題是存儲(chǔ)位置的分配和存取變量和數(shù)據(jù)。將會(huì)詳細(xì)地討論內(nèi)存管理中的棧分配、堆管理和垃圾回收。
7.1? Storage? Organization
The? run-time? representation? of? an? object? program? in? the? logical? address space consists of? data and program areas.在邏輯地址空間下，程序的運(yùn)行時(shí)環(huán)境包括數(shù)據(jù)區(qū)和代碼區(qū)
On? many? machines,? instructions? to? add integers may? expect integers to? be aligned,? that is ,? placed at an address divisible by 4.四字節(jié)對(duì)齊問題
The? size? of the? generated target code? is? fixed? at? compile? time,? so the? compiler can place the executable target? code in a statically? determined area? Code, usually? in? the? low? end of? memory.? Similarly,? the size? of? some? program? data objects,? such? as? global? constants, and? data generated by? the? compiler,? such? as information to support garbage collection,? may be known at? compile time ,? and these? data? objects? can? be? placed? in? another? statically determined? area? called Static.可執(zhí)行的目標(biāo)代碼放在Code區(qū)，像全局常量這樣的程序數(shù)據(jù)對(duì)象和由編譯器產(chǎn)生的比如為了支持垃圾回收的一些信息等數(shù)據(jù)放在Static區(qū)。
To maximize the utilization of? space at run time ,? the other two areas,? Stack and Heap,? are at the opposite ends of? the? remainder? of? the address space.
The stack is? used? to? store? data structures called activation records that? get generated during procedure calls.棧用來保存因過程調(diào)用而產(chǎn)生的activation records。
In? practice,? the? stack? grows? towards? lower? addresses,? the? heap? towards higher.實(shí)際的操作系統(tǒng)中，棧向低地址生長(zhǎng)，堆向高地址生長(zhǎng)。
an? activation record? is? used? to? store information? about the? status? of? the machine, such as the value of? the program counter? and? machine? registers ,? when? a? procedure? call? occurs.activation record用來保存過程調(diào)用發(fā)生時(shí)機(jī)器狀態(tài)的信息，比如程序計(jì)數(shù)器和機(jī)器寄存器的值。
When control returns from the call, the activation of the calling procedure can be restarted after restoring the values of relevant registers and setting the program counter to the point immediately after the call. 調(diào)用一個(gè)函數(shù)返回后，相關(guān)寄存器的值會(huì)被重置，程序計(jì)數(shù)器會(huì)指向函數(shù)的下一行，主程序的activation可以被重新開始。
Data objects whose lifetimes are con-tained in that of an activation can be allocated on the stack along with other information associated with the activation.局部數(shù)據(jù)對(duì)象和其他與activation關(guān)聯(lián)的信息是在stack上分配的。
Many programming languages allow the programmer to allocate and deal-locate data? under program control. For example, C has the functions malloc and free that can be used to obtain and give back arbitrary chunks of stor-age. The heap is used to manage this kind of long-lived data.programmer申請(qǐng)的內(nèi)存是在堆上分配的。
7.1.1 Static Versus Dynamic Storage Allocation
We say? that? a storage-allocation decision is? static, if? it can? be made by? the? compiler? looking? only? at? the? text? of the? program,? not at what? the program? does? when it? executes. Conversely,? a? decision is? dynamic? if it? can be decided only while the? program is running.內(nèi)存分配有static和dynamic之后
Many compilers use some combination of? the following two strategies? for? dynamic storage allocation:
Stack storage: Names local to a procedure are allocated space on a stack.
Heap storage: Data that? may outlive the call to? the? procedure that? cre-ated it? is? usually? allocated? on a? "heap"? of reusable storage.
To support heap management, "garbage? collection" enables? the? run-time system to detect useless data? elements and reuse their storage, even if? the pro-grammer does? not? return? their space explicitly.運(yùn)行時(shí)環(huán)境可以檢測(cè)不再使用的數(shù)據(jù)元素，并且在即使pro-grammer沒有顯式地釋放它們的情況下重用它們的存儲(chǔ)空間。
7. 2 Stack Allocation of Space
Almost all compilers? for? languages that use procedures, functions,? or methods as units of user-defined actions manage at least part of? their run-time memory as a? stack. 使用過程、函數(shù)或者方法作為用戶定義的操作的單元的語言的編譯器把它們運(yùn)行時(shí)內(nèi)存的一部分組織成一個(gè)棧。
Each? time? a? procedure is? called,? space? for? its? local? variables? is pushed onto a stack,? and when the procedure terminates ,? that space is popped off the? stack.每次過程被調(diào)用時(shí)，它的局部變量的空間被加入到一個(gè)棧上，過程結(jié)束時(shí)，那段空間被彈出棧。
7. 2.1 Activation Trees
Stack allocation would not be feasible? if? procedure calls, or? activations of pro-cedures,? did? not? nest? in? time.時(shí)間上要嵌套
We therefore can? represent the activations of? procedures during? the? running of? an entire program by a tree,? called an? activation tree.激活樹？
Each node corresponds to one? activation,? and the? root? is? the? activation? of? the? "main"? procedure that initiates execution of? the program.每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)activation，根是main過程的activation，main過程初始化程序的執(zhí)行。
At a node for? an? activation of procedure? p, the? children? correspond? to activations? of? the? procedures? called? by this activation of? p.過程p的activation對(duì)應(yīng)的節(jié)點(diǎn)，它的子節(jié)點(diǎn)對(duì)應(yīng)過程p調(diào)用的過程的activations。
Notice? that? one? child? must? finish? before? the activation? to? its? right? can begin.左節(jié)點(diǎn)必須在右節(jié)點(diǎn)的開始之前結(jié)束。
The use of? a? run-time stack? is? enabled? by several? useful relationships? between the? activation tree and the behavior of? the program:
1. The sequence of? procedure calls corresponds to a preorder traversal of the activation tree.
2. The sequence of returns? corresponds to a postorder traversal? of the acti-vation tree.
3. The order in which these activations were called is the order in which they appear along the path to N, starting at the root, and they will return in the reverse of that order.
7.2.2 Activation Records
Procedure calls and returns are usually managed by a run-time stack called the control stack. 控制棧
Each live activation? has? an? activation? record ( sometimes called? a frame)? on the? control? stack,? with the root? of the? activation tree? at? the? bottom , and the entire? sequence of activation? records on the stack corresponding to the path? in? the? activation? tree? to? the? activation? where? control? currently? resides.在控制棧上，每一個(gè)live的activation有一個(gè)activation? record，activation tree的根在底部?？刂茥Ｉ蟖ctivation records的完整序列對(duì)應(yīng)activation tree上到控制當(dāng)前停留的activation的路徑。
The latter activation has its record at the top of the stack.后來的activation的record在棧頂。
We shall conventionally draw control stacks with the bottom of the stack higher than the top, so the elements in an activation record that appear lowest on the page are actually? closest to the top of the stack.控制棧底部在下，activation tree中出現(xiàn)在越下的activation record的元素，事實(shí)上越靠近棧頂。
Here is a list of the kinds of data that might appear in an activation record:
1. Temporary values比如計(jì)算表達(dá)式產(chǎn)生的且不能夠放在寄存器中的值
2. Local data
3. A saved machine status: This information? typically includes the? return? address and? the? contents of registers that were used? by the calling procedure and that? must be restored when the? return occurs.包括返回地址和寄存器的內(nèi)容
4. An "access link"
5. A control link: pointing to? the? activation record of the caller
6. Space for the return value: if called procedures return a value ,? we may prefer to place that value in? a? register? for? efficiency.
7. The actual parameters: Commonly,? these values are? not placed? in? the? activation record? but rather? in registers, when possible,? for? greater efficiency.通常，實(shí)際參數(shù)不放在activation record中，為了更好的效率，而是放在寄存器中。
the top of stack is? at? the? bottom of diagrams.棧頂在圖示的下方
when a procedure is recursive,? it is normal to have several of its activation records on the stack at the same time.遞歸函數(shù)可以在棧中同時(shí)有多個(gè)它的activation records。
7.2.3 Calling Sequences
Procedure calls are? implemented by what are? known as calling? sequences, which consists? of? code? that? allocates? an? activation? record? on? the? stack? and? enters information into its fields.過程調(diào)用由calling sequences實(shí)現(xiàn)，calling sequences由在棧上分配activation? record并把信息寫入到activation? record的域中的代碼構(gòu)成。
The? code in? a? calling? se-quence? is? often? divided? between? the? calling? procedure? ( the? "caller" )? and? the procedure? it? calls? (the? "callee" ).
1. Values communicated between caller? and callee are? generally placed at the beginning of? the callee's activation record, so? they? are? as close? as possible to? the? caller 's? activation? record.
2. Fixed-length? items? are generally? placed? in? the? middle.
3. Items whose size? may? not? be? known? early? enough? are? placed? at? the? end of the? activation? record.
4. We must locate the top-of-stack pointer judiciously.
A? register top_sp points? to? the? end? of the? machine- status field? in? the? current top? activation record.? This position within the? callee's activation record is? known to the? caller,? so the caller? can? be made responsible for? setting? top_sp? before? control? is? passed? to? the? callee.寄存器top_sp指向當(dāng)前最頂activation record的機(jī)器狀態(tài)域之后。
The calling sequence and its? division between? caller and? callee is? as? follows:
1.? The caller evaluates? the actual parameters.調(diào)用者計(jì)算實(shí)際參數(shù)
2.? The? caller? stores? a? return? address? and? the? old? value? of? top_sp? into? the callee's? activation? record.? The? caller then? increments? top_sp? to? the po-sition shown in? Fig. 7.7.? That is,? top_sp? is moved past? the? caller's local data and temporaries and the? callee's? parameters and status fields.調(diào)用者把返回地址和top_sp的舊值保存到被調(diào)用者的activation? record。然后移動(dòng)top_sp的指向，越過調(diào)用者的局部數(shù)據(jù)以及臨時(shí)變量和被調(diào)用者的參數(shù)以及狀態(tài)域。
3. The callee saves the register values and other status information.保存寄存器的值和其他狀態(tài)信息
4.? The callee initializes its local data and begins execution.初始化局部數(shù)據(jù)并開始執(zhí)行
A suitable, corresponding return sequence is:
1. The callee places the? return value? next? to? the? parameters.被調(diào)用者把返回值放在臨近參數(shù)的內(nèi)存空間。
2. Using? information? in the machine-status? field,? the callee? restores? top_sp and? other? registers,? and? then? branches? to? the return? address? that? the caller? placed in the status? field.被調(diào)用者重置top_sp和其他寄存器，跳到調(diào)用者指定的返回地址處。
3. Although top_sp has been decremented, the caller knows where the return value is, relative to the current value of top-sp; the caller therefore may use that value.調(diào)用者取用返回值。
7.2.4? Variable-Length? Data on? the? Stack
In modern languages, objects whose size cannot be determined at compile time are allocated space in the heap. However, it is also possible to allocate objects, arrays, or other structures of unknown size on the stack.編譯期不能確定大小的對(duì)象，可以在堆上分配，也可以在棧上分配。
the stack? can? be used? only? for? an object if? it is local to? a procedure and? becomes inaccessible when the? procedure returns.只有局部對(duì)象的內(nèi)存空間才可以從棧上分配。
Access to the data on the stack is through two pointers, top? and? top_sp. Here, top? marks the actual top of stack; it points to the position at which the next activation? record will begin. The second, top_sp? is used to find local, fixed-length fields of the? top activation record.top指針標(biāo)識(shí)棧的真正的棧頂，指向下一個(gè)activation? record的開始；top_sp用來尋找棧頂activation record的局部的定長(zhǎng)的域。
7.3? Access? to? Nonlocal? Data? on? the? Stack
Access becomes? more? complicated in? languages? where procedures? can? be declared inside? other? procedures.當(dāng)可以在一個(gè)過程中聲明另一個(gè)過程時(shí)，存取數(shù)據(jù)變得更加復(fù)雜。
7.3.1? Data Access? Without? Nested? Procedures
For languages? that do? not allow nested procedure declarations, allocation of storage for variables? and access to those variables is? simple:
1.? Global variables are allocated static? storage.? The locations of these vari-ables? remain? fixed? and? are? known? at? compile? time .? So? to? access? any variable? that is not? local to the? currently executing procedure, we simply use the statically determined address.
2. Any other name must? be local? to the? activation? at? the top? of the? stack. We may access these variables through the top_sp pointer of the stack.
7.3.2? Issues? With? Nested? Procedures
Finding the declaration that? applies to a nonlocal name x? in? a nested pro-cedure? p? is? a static? decision;? it can? be done by? an extension of? the? static-scope rule? for? blocks.
Suppose? x? is? declared in? the? enclosing procedure? q.? Finding the relevant? activation of q? from? an? activation of? p? is a dynamic decision; it? re-quires? additional? run-time? information? about activations.? One possible solution to this problem is to use? "access links".
7.3.3? A? Language? With Nested Procedure? Declarations
介紹了一種叫做ML語言，function definitions? can be nested函數(shù)定義可以嵌套。
ML is? a functional? language,? meaning? that? variables , once? declared? and initialized,? are not changed.? There are? only a few exceptions , such as? the array, whose elements can be changed? by special function calls.變量一旦聲明并初始化之后，不可以改變；例外是數(shù)組。
val? (name)? =? (expression)
fun? (name)? ( (arguments) )? =? (body)
et? (list of? definitions)? in? (statements)? end
7.3.4? Nesting? Depth
nesting depth 1: procedures that are not nested within any other procedure
if a procedure p is defined immediately within a procedure at nesting depth i, then give p the nesting depth i+1.如果過程p是在nesting depth為i的過程中直接被定義的，則過程p的nesting depth為i+1。
7.3.5? Access? Links
A direct implementation of the normal static scope rule for nested functions is obtained by adding a pointer called the access link to each activation record.為每一個(gè)activation record添加一個(gè)稱為access link的指針，來實(shí)現(xiàn)嵌套函數(shù)的正常的靜態(tài)范圍規(guī)則。
Access links form a chain from the activation record at the top of the stack to a? sequence of activations at progressively lower nesting depths.access links形成了一條從棧頂?shù)腶ctivation record到低嵌套深度的一系列activations的鏈。
7.3.6? Manipulating? Access? Links
what should happen when a procedure q? calls procedure p,? explicitly？? There are three? cases:
1.? Procedure? p? is at? a higher nesting depth than? q
2.? The call? is? recursive, that? is, p? =? q
3.? The? nesting? depth? np of p? is? less than the nesting depth? nq of? q
7.3.7? Access? Links? for? Procedure? Parameters函數(shù)作為參數(shù)
when procedures are used as parameters, the caller? needs to? pass,? along? with the? name of? the? procedure-parameter, the? proper access link for? that? parameter.
7.3.8? Displays
One? problem with? the? access-link? approach? to? nonlocal? data? is? that? if? the? nesting depth? gets? large,? we? may have to follow? long? chains? of links? to reach the? data we need.? A more efficient? implementation? uses an auxiliary array d,? called? the display,? which consists? of one pointer for each nesting depth.當(dāng)嵌套深度很大時(shí)，access link方法不再適用，于是引入了display方法。
We arrange that, at? all? times, d[i] is a pointer to the highest activation record on the stack for any procedure at nesting depth i.d[i]指向當(dāng)前棧上嵌套深度為i的最高的activation record。
The? advantage? of? using? a? display? is that? if? procedure p? is executing,? and it? needs to access? element? x? belonging? to? some? procedure? q,? we? need? to? look only in? d[i] ,? where i? is the nesting depth of q;? we follow? the pointer d[i]? to the activation? record? for? q,? wherein? x? is? found? at? a? known? offset.優(yōu)點(diǎn)是不用沿著長(zhǎng)長(zhǎng)的鏈表去查詢對(duì)應(yīng)的activation? record記錄。
In order to maintain the display correctly,? we need to save previous values of display entries in new activation records.在新的activation record中，保存display enties的舊值。
7.4 Heap Management
The heap is the portion of the store that is used for data that lives indefinitely, or until the program explicitly deletes it.長(zhǎng)時(shí)間使用的或者需要程序顯式刪除的數(shù)據(jù)保存在堆上。
the memory manager ,? the? subsystem? that? allo-cates? and? deallocates? space within the? heap;? it? serves? as an? interface? between application? programs and the? operating? system.
7. 4.1? The? Memory? Manager
The memory manager keeps track of all the free space in heap storage at all times. memory manager追蹤檢測(cè)所有堆存儲(chǔ)上的空閑空間。
It? performs two basic functions: Allocation and Deallocation.
data elements? of? different sizes are allocated, and there? is no? good way to predict the lifetimes of all allocated objects.數(shù)據(jù)元素的大小不固定，而且沒有好的方式來預(yù)測(cè)所有被分配的對(duì)象的生命周期。
7.4.2 The Memory Hierarchy of a Computer
A memory hierarchy consists of a series of storage elements, with the smaller faster ones "closer" to the processor, and the larger slower ones further away.離CPU越近，存儲(chǔ)介質(zhì)越快。
7.4.3? Locality? in? Programs
a? program has temporal locality if the memory locations it accesses are likely to be accessed again within a short period of time.如果一塊內(nèi)存被訪問了，那么在將來一段短的時(shí)間內(nèi)，它很大可能還會(huì)被訪問。（時(shí)間局部性）
a program has spatial locality if memory locations close to the location accessed are likely also to be accessed within a short period of time.（空間局部性）
Optimization Using? the? Memory Hierarchy
One effective technique to improve the spatial lo-cality of instructions is to have the compiler place basic blocks (sequences of instructions that are always executed sequentially) that are likely to follow each other contiguously - on the? same page, or even the same cache line, if possi-ble.盡可能地，把基本塊放在同一page甚至同一cache line上。
We can also improve the? temporal? and? spatial? locality? of data? accesses? in a program? by? changing? the? data? layout or the order of the computation.改變計(jì)算的數(shù)據(jù)流或者順序
7.4.4? Reducing? Fragmentation
At the beginning of? program execution, the heap is one contiguous unit of free space. As the program allocates and deallocates memory, this space is broken up into free and used chunks of memory, and the free? chunks need not reside in a contiguous area of the heap.隨著程序分配和回收內(nèi)存，堆空間出現(xiàn)了碎片。
Best-Fit? and? Next-Fit? Object? Placement
best-fit algorithm tends to spare the large holes to satisfy subsequent, larger? requests. An alternative, called first-fit, where an object is placed in the first? (lowest-address) hole in which it fits, takes less time to place objects, but has? been found inferior to best-fit in overall performance.best-fit算法是找到差不多最合適的Hole，first-fit是找到第一個(gè)合適的Hole，效率比best-fit要差。
next-fit strategy, trying to allocate the object in the chunk that has last been? split, whenever enough space for the new object remains in that chunk. Next-fit also tends to improve the speed of the allocation operation.
Managing and? Coalescing Free? Space
7.4.5? Manual? Deallocation? Requests
Ideally, any storage that? will no longer? be accessed should? be? deleted.? Conversely,? any storage? that? may be referenced must not be deleted.不再使用的空間應(yīng)該被回收，正在被引用的空間一定不能被刪除。
Problems? with Manual Deallocation
The common mistakes take two forms: failing ever to delete data that cannot? be referenced is called a memory- leak error, and referencing deleted data is a? dangling-pointer-dereference error.
Programming? Conventions? and? Tools
Object ownership: associate? an? owner with? each? object? at? all times, The owner? is responsible for either? deleting? the? object? or for? passing the? object? to? another? owner.
Reference? counting: associate? a? count? with each? dynamically allocated object, Whenever a reference to the object is? created, we incre-ment the reference? count ;? whenever a? reference is removed,? we decrement the? reference count.? When the count goes? to? zero , the object can no? longer be? referenced and can therefore be deleted.
Region- based allocation: When objects? are? created to be used only within some step of a? computation,? we can? allocate all such objects? in? the? same? region.? We? then? delete? the? entire? region? once? that computation? step completes.
