Class Note for CS 403 at UA-Programming Languages (12)
Class Note for CS 403 at UA-Programming Languages (12)
Popular in Course
Popular in Department
This 5 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Alabama - Tuscaloosa taught by a professor in Fall. Since its upload, it has received 23 views.
Reviews for Class Note for CS 403 at UA-Programming Languages (12)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Lecture 9 Thursday 2603 Today A little more on Java and pointers Memory Leaks Reading Assignments For Next Class pp 189191 38894 Assignments Assignment 2 clue tonight Exam 1 Tuesday February 11 Open book open notes Sprung 2mm cs 403 class Nam Pa 21 Pointer A reference to an object Normally implemented as an address Some languages restrict reference to be only heap objects Ada 83 Pascal Other languages allow pointers to nonheap objects C int x int y x ampy Sprung 2mm cs 403 class Nam Pa 2 2 Pointer Design Issues Dereferencing alternatives Implicit Explicit Deallocation alternatives Explicit deallocation operator in the language Automatic storage reclamation Garbage collection Some combination of both garbage collection and explicit deallocation 5mm 2mm cs 403 class Nam Pa Fundamental Pointer Operations Memory allocation mm x new int Int x x new misc Stack 5 5 new Stack Dereferences Explicit Implicit smznnz cs 403 class Nam P e A Implicit vs Explicit Dereferencing Explicit C intx y x new int Implicit A reference to a pointervariable is an automatic dereference y x would function as y x smznnz cs 403 class Nam P e 5 A More Realistic Example C EXQIiCil DSfeI39enCe I Ada Implicit dereffor recs class Node type Node is record public x integer intx next access Node Node next end Node I n access Node Node n n new Node nnewNode nx3 nx3 ngtx3 2mm cs 403 class Nam P References in C Normally used for parameters Hold addresses Two rules lnitialized to an address lmplicitly dereferenced in every noninitialization use void fooint ampx inty 0 X Y y X Sprung 2mm cs 403 Class Notes P e 7 Java and Objects Declaration Stack s Implementation Record array integer Java Puts a pointer in the activation record C Puts the whole stack in the activation record Must allocate space forthe object in Java S new Stack rather than s gt push All objects in Java are allocated on the heap Dereferencing in Java is then implicit spush Spring 2mm cs 403 Class Notes Pointer Arithmetic The following is valid in CC int n inta int b10 a b n a3 n a 3 n b3 n b 3 Sprung 2mm cs 403 Class Notes P e 2 p 21D Problems With Pomters 1 Dangling reference already covered Pointer refers to an object that is no longer valid space has been reclaimed Dangerous 2 Memory leaks Space on the heap has no pointers pointing to it Wastes space A long running program might run out of space smznnzcsmzchssmms p 211 Arrays Stack vs Heap Allocation o Cj int a50 Allocates the array on the stack int a or a Allocates a pointer on the stack The second declaration must be followed with a new a new in x 5mm 2mm cs 403 Class Notes P Memory Leaks Simplest version void mainvoid int x y x newint y newint 5 2mm cs 403 Class Notes Memory Leaks Can be very insidious Delete a node from a linked list without freeing the memory Sprung 2on3 cs 403 Class Natzs P 213 Memory Leaks Big longrunning programs may run out of memory this way Approaches Tell programmerto be careful to always use the deletefreedeallocate operator May overuse tnis operator creating dangling references Use delete 39ee carefully and also automatically free up memory pointed to directly when local pointer variables go away Doesn t nandle llrlllted llsts where nodes in tne heap rnav contain additional pointers Sprung 2on3 cs 403 Class Natzs P 214 Example of 2nd Approach void roovoidl int x x new ll lt50 vlslmls l Automatically free memory pointed to by x when foo nishes Useful in this case programmer failed to use delete at the end of this function as they should have 5mm 2mm cs 403 Class Natzs P l But in this case same approach creates dangling reference void footlnt XK mm a x lrreemg memory pointed to by a is wrong here Void malnivoldK x x3 fy570 smznnz cs AUZChSSNatzs P 216 And it doesn t scratch the surface here void roovoidl Node head rnal39lufactul39e llrlllted list pointed to ov nead l Freeing up the node pointed to by head only cleans up one node In this case programmer should have iterated through the list and freed every node at the end of foo smznnz cs AUZChSSNatzs P 217 Garbage Collection Another Approach Idea Don t provide deallocation operator in the language Simply clean up after the programmer at the appropriate time Advantage No dangling references Disadvantage Performance 2on3 cs 403 Class Natzs P l What Garbage Collection Will Do void foovoid Node head llmanufacture linked list pointed to by quothead In this example garbage collection will walk through the entire list and free up every node once head is dead No explicit list traversal to free up memory is needed Java supports this approach and provides automatic garbage collection it does not provide a delete operator SpnngZUUZCS AUZClassNatzs Pa 219 Reference Counts May have to be modified When a function nishes and its variables die Any time a pointer variable appears on the lefthandside of an assignment statement Any time the garbage collection routine reclaims a chunk of heap space containing a pointer Reference counts don t work on circular lists Why not Spun muzcs AUZClassNatzs Pa 22 Approaches to Garbage Collection Reference counts Don t always work well Mark and sweep Works better than reference counts but much more complicated Typical approaches are periodic At some frequency the garbage collection routine runs resulting in periodic performance costs muzcs AUZClassNatzs P n Reference Counts Slack 5 page stooces m 5 2mm cs 403 Class Notes P Reference Counts For every heap object Keep a counter ofthe number of pointers pointing to that object Modrythe reference counts every time a pointer changes either up or down as appropriate When a reference count reaches 0 reclaim that object Requirements Language must keep track of pointers that change or die eg local variables when a function returns Language must also keep track of pointers within the heap itselfwhen such pointers are either changed or their space is reclaimed s muzcs AUZClassNatzs P l Mark and Sweep Better than reference counts Simplest form 3 steps Collector walks through heap marks each block tentatively as useless Beginning with each pointer outside the heap collector recursively explores all linked data structures in the program marking each newly discovered block as useful Collector again walks through the heap again returning every useless block to free space 5 2mm cs 403 Class Notes P A Basic Idea Mark and Sweep mmcsbmcmm h Problems with this Version Non xedsize blocks Every block must start with An indicatlun er us SlZE An indicatlun er Whether ur nut n is currently free Collector must be able to nd pointers embedded within each block Some information at the beginning oflhe block regarding where the internally embedded pointers are mmcsbmcmm hm Exam 1 Review Tuesday upenrbuuk upenrnutes Tuplcs e Cumpllalmnvs mlevpvelalmn 7 ENE syntaxspecmcalmn e Sluvage mudels allc ack heap e Slall and s1acllt s1uvage uvgamzalmn e Pumlevdeslgn issues 7 Danglingpumlevsmemuvyleaks 7 Garbage eeueenen Quesuen types 7 Shunanwev e Wylieevaluate segmenls ulcude e Truelalse Wllmusllllcallun e LuukaluldexamsunlheWeb mmcsbmcmm hm
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'