INTRODUCTION TO COMPUTER SYSTEMS
INTRODUCTION TO COMPUTER SYSTEMS COMP 221
Popular in Course
Popular in ComputerScienence
This 53 page Class Notes was uploaded by Cleora Stiedemann on Monday October 19, 2015. The Class Notes belongs to COMP 221 at Rice University taught by Scott Rixner in Fall. Since its upload, it has received 11 views. For similar materials see /class/224948/comp-221-rice-university in ComputerScienence at Rice University.
Reviews for INTRODUCTION TO COMPUTER SYSTEMS
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: 10/19/15
Memory Allocation Scott Rixner rixnerriceedu Big Picture C gives you access to underlying data representations amp layout Needed for systems programming o Inconvenient for application programming Necessary to understand Memory is a finite sequence of fixedsize storage cells o Most machines view storage cells as bytes 0 byteaddresses 0 Individual bits are not addressable o May also view storage cells as words Scott Rixner Memory Allocation Process Memory OxFFFFFFFF Kernel Virtual Memory Invisible to user code User Stack Created at runtime Shared Libraries Shared among processes Created at runtime Heap L39J ReadNVrite Data Loaded from the executable Readonly Code and Data Scott Rixner Memory Allocation Allocation For all data memory must be allocated Allocated memory space reserved Two questions o When do we know the size to allocate o When do we allocate Two possible answers for each o Compiletime static o Runtime dynamic Scott Rixner Memory Allocation How much memory to allocate Sometimes obvious One byte quot char c int array10 lt 10 sizeofint 40 usually Sometimes not Is this going to point to one char c character or a string int arrayh How big will this array be o How will these be used 0 Will they point to already allocated memory what we ve seen so far 0 Wil new memory need to be allocated we haven39t seen this yet Scott Rixner Memory Allocation malloc Won39t continually remind you of this include ltmallo chgt int array int mallocnumitems sizeofint Allocate memory dynamically Pass a size number of bytes to allocate o Finds unused memory that is large enough to hold the specified number of bytes and reserves it o Returns a void that points to the allocated memory 0 Must typecast the returned pointer appropriately Essentially equivalent to new in Java and C Scott Rixner Memory Allocation 6 Using malloc int i Statically allocates space for 2 pointers Vi int array i int mallocsizeofint array int mallocnumitems sizeofint i 3 array3 5 Dynamically allocates space for data i and array are interchangeable o Arrays z pointers to the initial 0th array element i could point to an array as well May change over the course of the program Allocated memory is not initialized calloc zeros allocated memory otherwise same as malloc Scott Rixner Memory Allocation Using malloc Always check the return value of system calls like malloc for errors int a int mallocnumitems sizeofint if a NULL fprintfstderr 0ut of memoryn exit1 o For brevity won t in class Textbook uses capitalization convention o Capitalized version of functions are wrappers that check for errors and exit if they occur ie Malloc 0 May not be appropriate to always exit on a malloc error though as you may be able to recover memory Scott Rixner Memory Allocation When to Allocate Static time Dynamic time 39 Typically global Typically local variables varlables int f int value int value int main int main o Only one copy ever exists so can allocate at compiletime 0 One copy exists for each call may be unbounded of calls so can t allocate at compiletime Scott Rixner Memory Allocation 9 When to Allocate Static time Some local variables One copy exists for all calls allocated at compiletime int f static int value I39 int main Scott Rixner Memory Allocation Confusingly local static has nothing to do with global static 10 Allocation in Process Memory OXFFFFFFFF OxFFBECOOO User Stack Static size dynamic allocation Local variables 0xFF3DC000 Shared Libraries Programmer controlled variablesized objects Heap Dynamic size dynamic allocation ReadNVrite Data Static size static allocation Readonly Code and Data GIOba39 variables 0x00010000 and static local variables 0x00000000 Scott Rixner Memory Allocation 11 Deallocation Space allocated via declaration entering scope is deallocated when exiting scope f int y int array10 Can t refer to y or array outside of f 0 so their space is deallocated upon return Scott Rixner Memory Allocation 12 Deallocation malloc allocates memory explicitly Must also deallocate it explicitly using free Not automatically deallocated garbage collected as in Scheme amp Java Forgetting to deallocate leads to memory leaks amp running out of memory int a int mallocnumitems sizeofint free a a int malloc2 numitems sizeofint Must not use a freed pointer unless reassigned or reallocated Scott Rixner Memory Allocation 13 Deallocation Space allocated by malloc is freed when the program terminates If data structure is used until program termination don t need to free o Entire process memory is deallocated Assumes virtual memory implementation is bugfree Bad assumption Scott Rixner Memory Allocation 14 Back to createdate Date Date createdate3int month createdate3int month int day int day int year int year Date d Date d d gtmonth month d Date mallocsizeofDate d gtday day d gtyear year d gtmonth month d gtday day return d d gtyear year return d Scott Rixner Memory Allocation 15 Pitfall void foo Potential problem memory allocation is performed in know its implementation today createdate39 l 2005 use today return Memory is still allocated for today Will never be deallocated calling function doesn t even know about it Scott Rixner Memory Allocation 16 Possible Solutions void foo Date today void foo Date today today createdate3 today createdate3 use today use today freetoday destroydatetoday return return l Explicitly deallocate memory Complete the abstraction create specification of createdate3 has a corresponding destroy must tell you to do this Scott Rixner Memory Allocation 17 What s Wrong With This Code int f int makearray int i int array10 return ampi return array Consider j f Leads to referencing deallocated memory o Never return a pointer to a local variable Behavior depends on allocation pattern 0 Space not reallocated unlikely works 0 Space reallocated very unpredictable Scott Rixner Memory Allocation 19 One Solution int f int makearray int iptr int array int mallocsizeof int int malloclO sizeof int return iptr return array Allocate with malloc and return its pointer Upon return space for local pointer variable is deallocated But the malloced space isn t deallocated until it is freed o Potential memory leak if caller is not careful as with createdate3 Scott Rixner Memory Allocation 20 What s Wrong With This Code return y Ax int matvecint A int x int y int mallocN sizeofint Initialization int i j loop fory i0 j0 malloced amp declared space is not initialized o i j yi initially contain unknown data garbage Often has zero value leading to seemingly correct results Scott Rixner Memory Allocation 21 What s Wrong With This Code char p int i Allocate space for MN matrix prmallocM sizeof Char for i0 iltM i1 pi mallocN sizeofchar char Allocates wrong amount of memory Leads to writing unallocated memory Scott Rixner Memory Allocation 22 What s Wrong With This Code char p int i Allocate space for MN matrix lt p char mallocM sizeofchar for i0 i1 pi char mallocN sizeofchar Offby 1 error Uses interval OM instead of 0M 1 Leads to writing unallocated memory Be careful with loop bounds Scott Rixner Memory Allocation 23 What s Wrong With This Code char s 1234567 char t7 strcpyt s t doesn t have space for string terminator Leads to writing unallocated memory One way to avoid char s 1234567 char t char mallocstrlens1 sizeofchar strcpyt s Scott Rixner Memory Allocation 24 What s Wrong With This Code int binheapdeleteint binheapltint size int packet packet binheap0 binheao 0 binheapsize 1 heapifybinheap returnpacket size 51ze 1 Changes a pointer instead of its contents o Writes unallocated memory o Pointer arithmetic not intended here but still dangerous Scott Rixner Memory Allocation Using const const int size Pointer to a constant integer Cannot write to size int const size Constant pointer to an integer Cannot modify the pointer size Can write to size Scott Rixner Memory Allocation 26 What s Wrong With This Code Search memory for a value Assume value is present int searchint p int value while p gt 0 ampamp value re turn p Misused pointer arithmetic Search skips some data can read unallocated memory and might not ever see value Should never add sizeof to a pointer o Could consider rewriting this function amp its uses to use array notation instead Scott Rixner Memory Allocation 27 What s Wrong With This Code x int mallocN sizeofint y int mallocM sizeofint for i0 iltM i1 Premature free Reads and writes deallocated memory Behavior depends on allocation pattern Space not reallocated gt works Space reallocated gt very unpredictable Scott Rixner Memory Allocation 28 What s Wrong With This Code free x gt void foo int x int mallocN sizeofint return Memory leak doesn t free malloced space Data still allocated but inaccessible since can t refer to x Slows future memory performance Scott Rixner Memory Allocation What s Wrong With This Code struct ACons int first A peek at one way struct ACons rest tode neHsE typedef struct ACons List void foo List list cons1cons2cons3NULL return Memory leak frees only beginning of data structure o Remainder of data structure is still allocated but inaccessible 0 Need to write deallocation destructor routines for each data structure Scott Rixner Memory Allocation 30 Next Time Lists and Trees Scott Rixner Memory Allocation 31 Arrays and Pointers in C Scott Rixner rixnerriceedu Arrays in C All elements of same type homogenous Array size in declaration must be constant A 4 lnt arraylo Compare C int arraylO int b Java int10 array First element index 0 array 0 i Last element index size 1 array9 4 array 10 5 arra 1 6 v No bounds checking Allowed usually causes no error array10 may overwrite D Scott Rixner Arrays and Pointers 2 Array Representation Homogeneous gt Each element same size 5 bytes o An array of m data values is a sequence of mxs bytes o Indexing 0th value at byte SxO 1st value at byte Sx1 m and s are not part of representation o Unlike in some other languages 0 5 known by compiler usually irrelevant to programmer o m often known by compiler if not must be saved by programmer 0X1008 0X1004 0X1000 Scott Rixner Arrays and Pointers Array Representation char c1 int a3 char c2 int i 0X1014 0x1010 OXIOOC Could be optimized by 32J33i31 ESSEnquot 0x1004 by default not 0x1000 Array aligned by size of elements Scott Rixner Arrays and Pointers Array Sizes int array10 What is array3 returns the size of an object in bytes sizeof array Scott Rixner Arrays and Pointers 4O MultiDimensional Arrays 0X1014 0x1010 int matrix23 0x100C matrix10 17 0x1008 0X1004 0X1000 Recall no bounds checking What happens when you write matrixO 3 42 Scott Rixner Arrays and Pointers 6 VariableLength Arrays int n m int arrayn New C99 feature but not fully supported by gcc We ll ignore Scott Rixner Arrays and Pointers Addresses Arrays o Elements in contiguous addresses viewed as element offsets from base of array Size of storage cells typically viewed as bytes Usually smallest addressable unit of memory 0 Few machines can directly access bits individually Addresses also known as byteaddresses Sometimes viewed as words Most common size of addressable unit of memory o When applicable use wordaddresses o Wordaddress m byteaddress m x bytesword Scott Rixner Arrays and Pointers Memory Addresses Pointers Special case of boundedsize natural numbers o Maximum memory limited by processor wordsize o 232 bytes 4GB 264 bytes 16 exabytes A pointer is just another kind of value 5th basic type in C Scott Rixner Arrays and Pointers Pointer Operations in C Creation amp variable Returns variable s memory address Dereference pointer Returns contents stored at address Indirect assignment pointer val Stores value at address Of course still have Assignment pointer ptr Stores pointer in another variable Scott Rixner Arrays and Pointers 10 Using Pointers int i1 int i2 int Ptrli 0x1014 int ptr2 0x1010 i1 1 0X100C 12 2quot 0x1008 ptrl ampi1 ptr2 ptrl 0x1000 ptrl 3 12 ptr2 Scott Rixner Arrays and Pointers Using Pointers cont intl int2 int int intptrl intptrl int intptrl int intptr2 1036 8 int ptr2 int2 ampintl ampint2 some data to point to get addresses of data What happens Type check warning intptr2 is not an int intl becomes 8 Scott Rixner Arrays and Pointers 12 Using Pointers cont int intl 1036 some data to point to int int2 8 int intptrl ampintl get addresses of data int intptr2 ampint2 int ptrl intptr2 intptr1 intptr2 What happens Type check warning intptr2 is not an int Changes intptrl doesn t change intl Scott Rixner Arrays and Pointers 13 Pointer Arithmetic pointer number pointer number Eg pointer 1 adds 1 something to a pointer char p int p char a 1nt a char b int b p a p ampa p 1 lt In each p now points to b gtp 1 Assuming compiler doesn39t reorder variables in memory Adds 1sizeofchar to Adds 1sizeofint to the memory address the memory address Pointer arithmetic is usually confusing and bad style Scott Rixner Arrays and Pointers 14 The Simplest Pointer in C Special constant pointer NULL o Points to no data o Dereferencing illegal causes segmentation fault To define include ltstdlibhgt or ltstdiohgt Scott Rixner Arrays and Pointers 15 Generic Pointers void a pointer to anything type cast tells the compiler to void p change an object39s type for type int i checking purposes does not modify char 39 the object in any way p void ampi P void ampCr39 Dangerous Sometimes necessary Lose all information about what type of thing is pointed to Reduces effectiveness of typechecking Can t use pointer arithmetic Useful in limited circumstances o Might find useful in last project Scott Rixner Arrays and Pointers 16 Passby Reference void setxandyint x int y x 1001 y 1002 void f int a 1 int b 2 setxandyampaampb Scott Rixner Arrays and Pointers 17 Arrays and Pointers Dirty secret Passmg arrays Array z pointer to the initial Arrays don t Incom lete e 0th array element p wp know0W S39Ze 1nt f 39 t ai E ai oo1n Iarray I un51gned 1nt Slze This is one reason why arrays arraylsizel don t know their own size 0 They are just pointers int main Usually bad style to Interchange arrays and pointers int a10 M5 o Avoid pointer arithmetic fooa10 foob5 Scott Rixner Arrays and Pointers 18 Arrays and Pointers int int i arraylO for i 0 i lt 10 i arrayi int p int arraylO m Scott Rixner Arrays and Pointers 19 Strings In C strings are just an array of characters o Terminated with 0 character o Arrays for boundedlength strings Pointer for constant strings or unknown length char str115 char str2 C terminator 39 039 Scott Rixner Arrays and Pointers 20 Hello worldn Hello worldn String length Must calculate length t can pass an in array or pointer strlen array access to pointer terminator while 1en What is the size of the array return len int len Check for Provided by standard C library include ltstringhgt Scott Rixner Arrays and Pointers 21 Next Time Structures and Unions Scott Rixner Arrays and Pointers 22
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'