StorageParts of a computerIt’s all bitsStorage is storageSelf-modifying programsPreparation for next exampleProcedure callsProblems with the previous codeThe end of an eraAn aside—compilers and loadersStatic and dynamic storageStacksHeapsStacks vs. heapsImplementing a heapAnatomy of a blockThe heap, IThe heap, IIThe heap, IIIThe heap, IVThe heap, VThe heap, VIThe heap, VIIThe heap, VIIIPointersAdvantages/disadvantagesDeallocationDisciplineGarbage collectionGarbage collection algorithmsReference countingProblems with reference countingMark and sweepProblems with mark and sweepGarbage collection in JavaNo garbage collection in C or C++The EndJan 14, 2019Storage2Parts of a computerFor purposes of this talk, we will assume three main parts to a computerMain memory, once upon a time called core, but these days called RAM (Random Access Memory)RAM consists of a very long sequence of bits, organized into bytes (8-bit units) or words (longer units)Peripheral memory, these days called disks (even when they aren’t) or drivesPeripheral memory consists of a very, very long sequence of bits, organized into pages of words or bytesPeripheral memory is thousands of times slower than RAMThe CPU (Central Processing Unit), which manipulates these bits, and moves them back and forth between main memory and peripheral memory3It’s all bitsEverything in a computer is represented by a sequence of bits—integers, floating point numbers, characters, and, most importantly, instructionsBits are the ultimate flexible representation—at least until we have working quantum computers, which use qubits (quantum bits)Modern languages use strong typing to prevent you from accidentally treating a floating point number as a boolean, or a string as an integerA weakly typed language provides some protection, but there are ways around itBut it wasn’t always this way...4Storage is storageAt one time, words representing machine instructions and words representing data could be intermixedStrong typing was a thing of the futureIt was the programmer’s responsibility to avoid executing data, or doing arithmetic on instructionsBoth of these things could be done, either accidentally or deliberatelyMachine instructions are just a sequence of bitsThey can be manipulated like any other sequence of bitsHence, programmers could change any instruction into any other instruction (of the same size), or rewrite whole blocks of instructionsA self-modifying program is one that changes its own instructions5Self-modifying programsOnce upon a time, self-modifying programs were thought of as a good thingJust think of how flexible your programs could be!...yes, and smoking was once considered good for your healthThe usual way to step through an array was by adding one to the address part of a load or store instructionYou could write some really clever self-modifying programsBut, as the poet Piet Hein says:Here’s a good rule of thumb:Too clever is dumb.6Preparation for next exampleIn the next example, we will talk about how a higher-level language might be translated into assembly languagesHere are some of the assembly instructions we will use:The load instruction copies a value from a memory location into a special register called the accumulatorExample: load 53 gets whatever is in location 53 and puts it into the accumulatorThe enter instruction puts a given value into the accumulatorExample: enter 53 puts 53 itself into the accumulatorAll arithmetic is done in the accumulatorExample: add 53 adds the contents of location 53 to the accumulatorThe store instruction copies a value from the accumulator into memoryExample: store 53 puts whatever is in the accumulator into location 537Procedure callsConsider the following:a = add(b, c);...function add(x, y) { return x + y;}Here’s how it might have been translated to assembly language in the old days (red values are filled in as the program runs):42 [ 0] // a43 [ 10] // b44 [ 15] // c20 [load from 43] // addr of b21 [store in 71]22 [load from 44] // addr of c23 [store in 72]24 [enter 27] // the return addr25 [store in addr part of 70]26 [jump to 73]27 [store in 42] // addr of a70 [jump to 27] // gets return addr71 [ 10] // will receive b72 [ 15] // will receive c73 [load value at addr 71]74 [add value at addr 72]75 [jump to 70]8Problems with the previous codeIn this example, storage was static—you always knew where everything was (and it didn’t move around)If you called a function, you told it where to return to, by storing the return address in the function itselfHence, you could call the function from (almost) anywhere, and it would find its way backYou stored the parameter values in the function itselfThis worked fine until recursion was inventedRecursion requires:Multiple return addressesMultiple copies of parameters and local variablesIn other words, recursion requires dynamic storage9The end of an eraWhat really killed off self-modifying programs was the advent of timesharing computersMultiple users, or at least multiple programs, could share the computer, taking turnsBut there isn’t always enough main memory to satisfy everybodyWhen one program is running, another program (or parts of it) may need to be copied to disk, and brought back in again laterThis is really, really slowIf only the data changed, not the program, we wouldn’t have to save the program (which is often the largest part) over and over and over...Besides, with the new emphasis on understandable programs, self-modifying programs were turning out to be a Really Bad IdeaBesides, think about what a security nightmare self-modifying programs could be!10An aside—compilers and loadersAlthough self-modifying code is a bad idea, it is still necessary for computers to be able to create and modify machine instructionsThis is what a compiler does—it creates machine instructionsA loader takes a compiled program and puts it somewhere in a computer memoryIt can’t always put it in the same place, so it has to be able to modify the addresses in the instructionsStill, compilers and loaders don’t modify themselves11Static and dynamic storageIn the beginning, storage was static—you declared your variables at the beginning of the program, and that was all you gotA procedure or function with, say, three
View Full Document