The Abstraction: Address Spaces

1 13 The Abstraction: Address SpacesIn the early days, building computer systems was easy. Why, youask?Because users didn t expect much. It is those darned users withtheirexpectations of ease of use , high performance , reliability , etc., thatreally have led to all these headaches. Next time you meet one of thosecomputer users, thank them for all the problems they have Early SystemsFrom the perspective of memory, early machines didn t provide muchof an abstraction to users. Basically, the physical memory of themachinelooked something like what you see in Figure (page 2).

2 The OS was a set of routines (a library, really) that sat in memory(start-ing at physical Address 0 in this example), and there would be one run-ning program (a process) that currently sat in physical memory (startingat physical Address 64k in this example) and used the rest of were few illusions here, and the user didn t expect much from theOS. Life was sure easy for OS developers in those days, wasn t it? Multiprogramming and Time SharingAfter a time, because machines were expensive, people began to sharemachines more effectively. Thus the era ofmultiprogrammingwas born[DV66], in which multiple processes were ready to run at a given time,and the OS would switch between them, for example when one decidedto perform an I/O.

3 Doing so increased the effectiveutilizationof theCPU. Such increases inefficiencywere particularly important in thosedays where each machine cost hundreds of thousands or even millions ofdollars (and you thought your Mac was expensive!).Soon enough, however, people began demanding more of machines,and the era oftime sharingwas born [S59, L60, M62, M83]. Specifically,many realized the limitations of batch computing, particularly on pro-grammers themselves [CV65], who were tired of long (and hence ineffec-12 THEABSTRACTION: ADDRESSSPACESmax64KB0 KBCurrent Program(code, data, etc.))

4 Operating System(code, data, etc.)Figure :Operating Systems: The Early Daystive) program-debug cycles. The notion ofinteractivitybecame impor-tant, as many users might be concurrently using a machine, each waitingfor (or hoping for) a timely response from their currently-executing way to implement time sharing would be to run one process for ashort while, giving it full access to all memory (Figure ),then stop it,save all of its state to some kind of disk (including all of physical mem-ory), load some other process s state, run it for a while, and thus imple-ment some kind of crude sharing of the machine [M+63].

5 Unfortunately, this approach has a big problem: it is way too slow,particularly as memory grows. While saving and restoring register-levelstate (the PC, general-purpose registers, etc.) is relatively fast, saving theentire contents of memory to disk is brutally non-performant. Thus, whatwe d rather do is leave processes in memory while switching betweenthem, allowing the OS to implement time sharing efficiently (as shown inFigure , page 3).In the diagram, there are three processes (A, B, and C) and eachofthem have a small part of the 512KB physical memory carved out forthem.

6 Assuming a single CPU, the OS chooses to run one of the processes(say A), while the others (B and C) sit in the ready queue waiting to time sharing became more popular, you can probably guess thatnew demands were placed on the operating system. In particular, allow-ing multiple programs to reside concurrently in memory makesprotec-tionan important issue; you don t want a process to be able to read, orworse, write some other process s [ ] : ADDRESSSPACES3512KB448KB384KB320KB256KB1 92KB128KB64KB0KB(free)(free)(free)(free) Operating System(code, data, etc.)Process A(code, data, etc.)

7 Process B(code, data, etc.)Process C(code, data, etc.)Figure :Three Processes: Sharing The Address SpaceHowever, we have to keep those pesky users in mind, and doing sorequires the OS to create aneasy to useabstraction of physical call this abstraction theaddress space, and it is the running program sview of memory in the system. Understanding this fundamental OS ab-straction of memory is key to understanding how memory is Address space of a process contains all of the memory state of therunning program. For example, thecodeof the program (the instruc-tions) have to live in memory somewhere, and thus they are in the ad-dress space.

8 The program, while it is running, uses astackto keep trackof where it is in the function call chain as well as to allocate local variablesand pass parameters and return values to and from routines. Finally, theheapis used for dynamically-allocated, user-managed memory, suchasthat you might receive from a call tomalloc()in C ornewin an object-oriented language such as C++ or Java. Of course, there are other thingsin there too ( , statically-initialized variables), butfor now let us justassume those three components: code, stack, and the example in Figure (page 4), we have a tiny Address space(only 16KB)1.

9 The program code lives at the top of the Address space1We will often use small examples like this because (a) it is a pain to represent a 32-bitaddress space and (b) the math is harder. We like simple math. 2008 20, ARPACI-DUSSEAUTHREEEASYPIECES4 THEABSTRACTION: ADDRESSSPACES16KB15KB2KB1KB0 KBStack(free)HeapProgram Codethe code segment:where instructions livethe heap segment:contains malloc d datadynamic data structures(it grows positively)(it grows negatively)the stack segment:contains local variablesarguments to routines, return values, :An Example Address Space(starting at 0 in this example, and is packed into the first 1K ofthe ad-dress space).

10 Code is static (and thus easy to place in memory),so we canplace it at the top of the Address space and know that it won t need anymore space as the program , we have the two regions of the Address space that may grow(and shrink) while the program runs. Those are the heap (at the top) andthe stack (at the bottom). We place them like this because each wishes tobe able to grow, and by putting them at opposite ends of the addressspace, we can allow such growth: they just have to grow in oppositedirections. The heap thus starts just after the code (at 1KB) and growsdownward (say when a user requests more memory viamalloc()); thestack starts at 16KB and grows upward (say when a user makes a proce-dure call).