DOC PREVIEW
Penn CIT 594 - Storage Lecture

This preview shows page 1-2-17-18-19-36-37 out of 37 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 computerFor purposes of this talk, we will assume three main parts to a computerMain 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 drivesPeripheral memory consists of a very, very long sequence of bits, organized into pages of words or bytesPeripheral memory is thousands of times slower than RAMThe CPU (Central Processing Unit), which manipulates these bits, and moves them back and forth between main memory and peripheral memory3It’s all bitsEverything in a computer is represented by a sequence of bits—integers, floating point numbers, characters, and, most importantly, instructionsBits 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 integerA weakly typed language provides some protection, but there are ways around itBut it wasn’t always this way...4Storage is storageAt one time, words representing machine instructions and words representing data could be intermixedStrong typing was a thing of the futureIt was the programmer’s responsibility to avoid executing data, or doing arithmetic on instructionsBoth of these things could be done, either accidentally or deliberatelyMachine instructions are just a sequence of bitsThey can be manipulated like any other sequence of bitsHence, programmers could change any instruction into any other instruction (of the same size), or rewrite whole blocks of instructionsA self-modifying program is one that changes its own instructions5Self-modifying programsOnce upon a time, self-modifying programs were thought of as a good thingJust think of how flexible your programs could be!...yes, and smoking was once considered good for your healthThe usual way to step through an array was by adding one to the address part of a load or store instructionYou could write some really clever self-modifying programsBut, as the poet Piet Hein says:Here’s a good rule of thumb:Too clever is dumb.6Preparation for next exampleIn the next example, we will talk about how a higher-level language might be translated into assembly languagesHere 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 accumulatorExample: load 53 gets whatever is in location 53 and puts it into the accumulatorThe enter instruction puts a given value into the accumulatorExample: enter 53 puts 53 itself into the accumulatorAll arithmetic is done in the accumulatorExample: add 53 adds the contents of location 53 to the accumulatorThe store instruction copies a value from the accumulator into memoryExample: store 53 puts whatever is in the accumulator into location 537Procedure callsConsider 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] // c20 [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 a70 [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 codeIn 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 itselfHence, you could call the function from (almost) anywhere, and it would find its way backYou stored the parameter values in the function itselfThis worked fine until recursion was inventedRecursion requires:Multiple return addressesMultiple copies of parameters and local variablesIn other words, recursion requires dynamic storage9The end of an eraWhat really killed off self-modifying programs was the advent of timesharing computersMultiple users, or at least multiple programs, could share the computer, taking turnsBut there isn’t always enough main memory to satisfy everybodyWhen one program is running, another program (or parts of it) may need to be copied to disk, and brought back in again laterThis is really, really slowIf 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 IdeaBesides, think about what a security nightmare self-modifying programs could be!10An aside—compilers and loadersAlthough self-modifying code is a bad idea, it is still necessary for computers to be able to create and modify machine instructionsThis is what a compiler does—it creates machine instructionsA loader takes a compiled program and puts it somewhere in a computer memoryIt can’t always put it in the same place, so it has to be able to modify the addresses in the instructionsStill, compilers and loaders don’t modify themselves11Static and dynamic storageIn the beginning, storage was static—you declared your variables at the beginning of the program, and that was all you gotA procedure or function with, say, three


View Full Document

Penn CIT 594 - Storage Lecture

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Pruning

Pruning

11 pages

Arrays

Arrays

17 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Recursion

Recursion

25 pages

Quicksort

Quicksort

21 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
Download Storage Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Storage Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Storage Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?