`
`
`
`Patent Owner Finjan, Inc. — Ex. 2008, p. 2
`
`
`
`Chapter 9
`
`MEMORY
`
`MANAGEMENT
`
`In Chapter 6, we showed how the CPU can be shared by a set of processes. As
`a result of CPU sched uling, we can improve both the utilization of the CPU and
`the speed of the computer's response to its users. To realize this increase in
`performance, however, we must keep several processes in memory; that is, we
`must shzzre memory.
`In this chapter, we discuss various ways to manage memory. The memory-
`management algorithms vary from a primitive bare-machine approach to pag-
`ing and segmentation strategies. Each approach has its own advantages and
`disadvantages. Selection of a memory—management method for a specific sys-
`tem depends on many factors, especially on the hardware design of the system.
`As we shall see, many algorithms require hardware support, although recent
`designs have closely integrated the hardware and operating system.
`
`9.1 I Background
`
`As we saw in Chapter 1, memory is central to the operation of a modern
`computer system. Memory consists of a large array of words or bytes, each
`with its own address. The CPU fetches instructions from memory according
`to the value of the program counter. These instructions may cause additional
`loading from and storing to specific memory addresses.
`A typical instruction-execution cycle, for example, first fetches an instruc-
`tion from memory. The instruction is then decoded and may cause operands
`to be fetched from memory. After the instruction has been executed on the
`
`
`
`274
`
`Chapter 9 Memory Management
`
`operands, results may be stored back in memory. The memory unit sees only a
`stream of memory addresses; it does not know how they are generated (by the
`instruction counter, indexing, indirection, literal addresses, and so on) or What
`they are for (instructions or data). Accordingly, we can ignore how a memory
`address is generated by a program. We are interested in only the sequence of
`memory ad dresses generated by the running program.
`
`9.1.1 Address Binding
`
`Usually, a program resides on a disk as a binary executable file. The program
`must be brought into memory and placed within a process for it to be executed.
`Depending on the memory management in use, the process may be moved
`between disk and memory during its execution. The collection of processes
`on the disk that is waiting to be brought into memory for execution forms the
`input queue.
`The normal procedure is to select one of the processes in the input queue
`and to load that process into memory. As the process is executed, it accesses
`instructions and data from memory. Eventually, the process terminates, and its
`memory space is declared available.
`Most systems allow a user process to reside in any part of the physical mem-
`ory. Thus, although the address space of the computer starts at 00000, the first
`address of the user process does not need to be 00000. This arrangement affects
`the addresses that the user program can use.
`In most cases, a user program
`will go through several steps—some of which may be optional——before being
`executed (Figure 9.1). Addresses may be represented in different ways during
`these steps. Addresses in the source program are generally symbolic (such as
`Count). A compiler will typically bind these symbolic addresses to relocatable.
`addresses (such as “14 bytes from the beginning of this module”). The link-
`age editor or loader will in turn bind these relocatable addresses to absolute
`addresses (such as 74014). Each binding is a mapping from one address space
`to another.
`
`Classically, the binding of instructions and data to memory ad dresses can
`be done at any step along the way:
`
`0 Compile time: If you know at compile time where the process will reside
`in memory, then absolute code can be generated. For example, if you know
`a priori that a user process resides starting at location R, then the generated
`compiler code will start at that location and extend up from there.
`If, at
`some later time, the starting location changes, then it will be necessary to
`recompile this code. The MS—DOS COM-format programs are absolute code
`bound at compile time.
`
`Load time: If it is not known at compile time where the process will reside
`in memory, then the compiler must generate relocatable code. in this case,
`
`
`
`ogrann
`-cuted.
`\ oved
`ncesses
`nnsthe
`
`queue
`cesses
`
`and its
`
`I mem-
`l e first
`affects
`
`ogram
`being
`during
`uch as
`
`atable ‘
`e link-
`: solute
`. space
`
`ES can
`
`9.1 Background
`
`275
`
`source
`program
`
`compiler or
`assembler
`
`other
`object
`
` al|y
`loaded
`system .
`library
`
`_
`
`in-memory
`binary
`memory
`image
`
`p
`
`execution
`time (run
`time)
`
`Figure 9.1 Multistep processing of a user program.
`
`final binding is delayed until load time. If the starting address changes, we
`need only to reload the user code to incorporate this changed Value.
`
`If the process can be moved during its execution from
`Execution time:
`one memory segment to another, then binding must be delayed until run
`time. Special hardware must be available for this scheme to work, as will
`be discussed in Section 9.1.2. Most general-purpose operating systems use
`this method.
`
`
`
`Patent Owner Finjan, Inc. — Ex. 2008, p. 6
`
`
`
`Patent Owner Finjan, Inc. — Ex. 2008, p. 7