1 00:00:03,560 --> 00:00:08,737 In this video, we are going to continue or discussion of run time organization by 2 00:00:08,737 --> 00:00:16,675 talking about how compilers handle global variables and heap data structures. Let's 3 00:00:16,675 --> 00:00:21,114 start by talking about global variables. The basic properties of the global 4 00:00:21,114 --> 00:00:26,085 variables that all the references point to the same object. That what it means to be 5 00:00:26,085 --> 00:00:31,116 global And for this reason, we can't store all the variables in the activation record 6 00:00:31,116 --> 00:00:35,378 because the activation record if, of course, is the allocated. When the 7 00:00:35,378 --> 00:00:40,117 activation completes and that would be the allocated global variable. So. The way 8 00:00:40,117 --> 00:00:45,134 that little variables are implemented is that all global are signed the fix address 9 00:00:45,134 --> 00:00:49,494 once And these variables with fixed addresses are said to be statically 10 00:00:49,494 --> 00:00:53,854 allocated because they're allocated essentially at compiled times. So the 11 00:00:53,854 --> 00:00:58,572 compiler decides where they going to live and then they will live there in all 12 00:00:58,572 --> 00:01:02,991 executions of the program And depending on the language, there may be other 13 00:01:02,991 --> 00:01:07,829 statically allocated values and we'll actually see some later on but they behave 14 00:01:07,829 --> 00:01:12,705 just the same as global variables. So I think global variables changes our run 15 00:01:12,705 --> 00:01:17,171 time organization picture a little bit. First we have the code as before, and 16 00:01:17,171 --> 00:01:21,696 then, immediately after the code is typically all of the static data. So these 17 00:01:21,696 --> 00:01:26,514 are the global variables and other static object, things that have fixed addresses 18 00:01:26,514 --> 00:01:31,215 for the duration of the execution of the program and then the stack comes after 19 00:01:31,215 --> 00:01:36,151 that. So the stack will start at the end of the static data area and grow towards 20 00:01:36,151 --> 00:01:42,390 the end of the program's allocated memory. Trying out to the heat, any value that, 21 00:01:42,390 --> 00:01:47,012 that outlives the procedure that creates it also cannot be stored in the activation 22 00:01:47,012 --> 00:01:51,468 record. Let's take a look at this example. So here we have a procedure [inaudible] 23 00:01:51,468 --> 00:01:56,097 and let's take a look at the activation record or frame for [inaudible]. Now let's 24 00:01:56,097 --> 00:02:01,641 say that a foo allocates a bar object and that we're going to store that object in 25 00:02:01,641 --> 00:02:06,984 foo activation And now when this method returns, of course the activation record 26 00:02:06,984 --> 00:02:12,527 would be de-allocated so the bar obj ect will also go away but that won't work here 27 00:02:12,527 --> 00:02:17,536 because notice that the dynamically allocated object [inaudible] allocated 28 00:02:17,536 --> 00:02:22,946 during an execution of foo is also the results of foo so this has to be, this has 29 00:02:22,946 --> 00:02:29,469 to be accessible to foo's caller. After [inaudible] exits And so what that means 30 00:02:29,469 --> 00:02:33,786 is that this borrow object and all dynamically allocated data has to be 31 00:02:33,786 --> 00:02:38,103 stored some place other than the activation record and language is what 32 00:02:38,103 --> 00:02:44,025 dynamically allocated data generally use a [inaudible] for that purpose. At this 33 00:02:44,025 --> 00:02:49,652 point, we can summarize the different kinds of data that the language of 34 00:02:49,652 --> 00:02:55,904 implementation has to deal with. First there is the code and in many languages, I 35 00:02:55,904 --> 00:03:01,945 shouldn't say most. In many languages. The code is fixed size and read only. I mean 36 00:03:01,945 --> 00:03:07,311 that the compiler creates all the code that will be used in the execution of the 37 00:03:07,311 --> 00:03:12,478 program and that could be allocated once. It should say that there are many 38 00:03:12,478 --> 00:03:17,778 languages also were this is not true and code can be dynamically created at one 39 00:03:17,778 --> 00:03:22,929 time. The static area. Would contain data with six addresses and this would be 40 00:03:22,929 --> 00:03:28,568 things like global variables and this is also typically fixed size and it was maybe 41 00:03:28,568 --> 00:03:34,140 readable and writable as opposed to the code which I generally don't want to be 42 00:03:34,140 --> 00:03:39,128 able to write. And then a stack is used to contain an activation record for each 43 00:03:39,128 --> 00:03:43,646 currently active procedure and the activation record is generally fixed size 44 00:03:43,646 --> 00:03:48,106 so each activation record for each particular kind of procedure has a fixed 45 00:03:48,106 --> 00:03:52,389 size and this will contain all the local information, the local variables 46 00:03:52,389 --> 00:03:56,966 contemporaries that needed to execute a particular activation. And finally, the 47 00:03:56,966 --> 00:04:01,777 heap is for everything else. So the heap is just for all the data that doesn't fit 48 00:04:01,777 --> 00:04:06,795 into other categories. This includes all of the dynamically allocated data And if 49 00:04:06,795 --> 00:04:14,423 you are familiar with C, then the heap and C is managed by the programmer using 50 00:04:14,423 --> 00:04:20,309 [inaudible] in Java, you have new. For dynamically allocating data and then 51 00:04:20,309 --> 00:04:26,169 garbage collection actually takes care of reclaiming data from the heap that is no 52 00:04:26,169 --> 00:04:32,125 longer used. Now many lang uage implementations use both the heap and the 53 00:04:32,125 --> 00:04:36,688 stack and there is a little bit of an issue here because both the heap and the 54 00:04:36,688 --> 00:04:41,425 stack grow. And so we have to take care that they don't grow into each and step on 55 00:04:41,425 --> 00:04:46,392 each other's data And there is a very nice and simple solution to this and as a start 56 00:04:46,392 --> 00:04:51,013 to heap and the stack at opposite ends of memory and let them grow towards each 57 00:04:51,013 --> 00:04:58,421 other. So, let's take another look at our Runtime Organization picture And just for 58 00:04:58,421 --> 00:05:04,330 review, first we have the code and then we have the static data. And then we have the 59 00:05:04,330 --> 00:05:09,780 stack which grows towards in this case the high address allocated to the program And, 60 00:05:09,780 --> 00:05:14,919 notice that the stack doesn't necessarily just grow as procedure three terms, stack 61 00:05:14,919 --> 00:05:19,874 will also shrink. So as the program runs the stack will get bigger or smaller 62 00:05:19,874 --> 00:05:24,989 depending on how many procedures are currently running. And the heap will start 63 00:05:24,989 --> 00:05:30,117 at the other end of memory and grow towards the lower address and so we 64 00:05:30,117 --> 00:05:36,029 allocate objects we'll be allocating from the back memory or the end of the memory 65 00:05:36,029 --> 00:05:41,629 allocated the program up towards the top of stack And If these two points have ever 66 00:05:41,629 --> 00:05:45,736 become equal and whether the two pointers. So, we have a stack allocation pointer 67 00:05:45,736 --> 00:05:50,052 which says where we are going to allocate the next stack frame. And we have a heap 68 00:05:50,052 --> 00:05:54,494 allocation point where it says where will allocate the next object if we have 69 00:05:54,494 --> 00:05:59,050 another dynamically allocated object. As long as one of these two pointers don't 70 00:05:59,050 --> 00:06:03,663 cross, as long as it never become equal then the program has memory to either add 71 00:06:03,663 --> 00:06:08,219 another stack frame or another dynamically allocated object and the program can 72 00:06:08,219 --> 00:06:12,661 continue away. If these programs ever become equal then the program is in fact 73 00:06:12,661 --> 00:06:17,502 out of memory and at that point the run time system will abort the program or try 74 00:06:17,502 --> 00:06:22,172 to get more memory from the operating or take some other course of action to deal 75 00:06:22,172 --> 00:06:26,852 with the fact. If there is no there is no more memory But as long as these two 76 00:06:26,852 --> 00:06:31,460 pointers don't cross, notice that this design Allows the heap and the stack to 77 00:06:31,460 --> 00:06:36,553 share this, this data area in whatever way suits the program best. So, this same 78 00:06:36,553 --> 00:06:41,404 design without any changes will work for programs that needed a lot of heap and 79 00:06:41,404 --> 00:06:46,557 only a little stack and for programs that need a lot of stack and only a little heap 80 00:06:46,557 --> 00:06:51,165 and things will have a rough balance between stack and heap as long as they 81 00:06:51,165 --> 00:06:54,500 don't exceed the total memory allocated to the program.