-
Notifications
You must be signed in to change notification settings - Fork 34
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
软件:第13周额外作业 #46
Labels
Comments
TA大大,我百度了malloc定义二维数组,然后int **p; p [i];这里p是指向指针的指针,为什么p[i]就只是指针了呢@ghostbody |
p[i] == *(p + i),一次解引用,所以是指针。就像数组int arr[10]中arr是地址,arr[i] == *(arr + i)是int。【不知道对不对。。 |
感觉好像有点懂了 |
第4题第三问,深度递归没有声明局部变量的情况下不会栈溢出么?如果有局部变量,根据调用栈的原理,肯定是会溢出的啊= =@ghostbody |
@FuckingBoy 谁说的,不一定,最好的方法是做实验验证。 |
做了实验,没加局部变量也溢出了啊= =@ghostbody |
交到ftp的哪个文件夹下? |
@DengXj95 week13 deep thinking |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Dynamic Memory Allocation
1. Memory distribution map for a runtime program (very important for your 4-year study)
From Professor Wan Hai's courseWare
This is an overview for a program when it's loaded into the memory of the computer. There are totally 4 area for it, Code area, Static area, Heap and stack.
Code area: This area is used to store program codes(instructions for cpu to execute)
Static area: This area is for the ralatively ‘static’ variables. Global variables, static local variables, static global variables are allocated in the static storage area.
Heap: This area is management by the operating system and it's shared by other programs. You can get dynamic memory allocations in this area. This is the area we need to use in list
Stack: The stack is a area of memory that allocated by the compile. All variables declared in stack.
Notice that stack and heap in operating system are totally different in data structure
(注意:这里所说的堆和栈是操作系统的概念,跟数据结构中的堆和栈不同)
For example:
Notice that we have a operation before the program end.
free(b)
. Because we use the memory in the heap which means that these memory should be managed by the programmer. Even though the memory will be free by a mordern operating system, we should prevent memory lost (memory leak).For example:
The example above cause a memory leak problem because pointer point to another memory area and the previous memory area1 is lost.
2. Malloc() to get memory from the heap
The two examples above show how to get memory in heap. In fact, we it's a serial of functions.
C language with the memory of the functions are mainly calloc, alloca, malloc, free, realloc and so on.
<1> alloca is the application of the stack to the memory, so there is no need to release.
<2> malloc allocates memory is located in the heap, and there is no memory of the contents of the initial memory, so after the basic malloc, call the function memset to initialize this part of the memory space.
<3> calloc will initialize this part of the memory, set to 0
<4> realloc is the size of the memory of the malloc application.
<5> The heap needs to be released by the function free.
Notice that everytime you apply memory from heap, you should remember it and delete it(free) when your use of it is end.
Function Prototype
注意,对于一个函数,一定要看函数原型,函数原型里面包含了这个函数接口功能的很多信息。
这个函数的名称是malloc,动态分配内存
参数是unsigned int num_bytes,意思是分配的内存的字节数。
返回值是void 指针,理论是就是应该指向被分配的内存。
由于返回的指针是一种泛型编程思想中的无类型指针,所以应该强制转换为你需要的类型。
注意:在一次malloc函数调用中,返回的一段内存是连续的
3. Memory Leak
Consequences
A memory leak can diminish the performance of the computer by reducing the amount of available memory. Eventually, in the worst case, too much of the available memory may become allocated and all or part of the system or device stops working correctly, the application fails, or the system slows down vastly due to thrashing.
Memory leaks may not be serious or even detectable by normal means. In modern operating systems, normal memory used by an application is released when the application terminates. This means that a memory leak in a program that only runs for a short time may not be noticed and is rarely serious.
Much more serious leaks include those:
where the program runs for an extended time and consumes additional memory over time, such as background tasks on servers, but especially in embedded devices which may be left running for many years
where new memory is allocated frequently for one-time tasks, such as when rendering the frames of a computer game or animated video
where the program can request memory — such as shared memory — that is not released, even when the program terminates
where memory is very limited, such as in an embedded system or portable device
where the leak occurs within the operating system or memory manager
when a system device driver causes the leak
running on an operating system that does not automatically release memory on program termination. Often on such machines if memory is lost, it can only be reclaimed by a reboot, an example of such a system being AmigaOS.[citation neede
简单来讲,内存泄露就是动态分配的内存没有在使用完之后进行释放,导致内存垃圾堆积。
这样的危害有可能直接让你的操作系统崩溃掉(可以自己做下实验)
For example:
上述代码分配了100个int类型大小的连续内存单元,我们可以通过这个方式分配动态数组。上述代码分配的就是可以理解成100个int的数组。
运行上述程序,在运行到while(1)时候发生了内存泄露,因为原来动态分配的内存地址丢失了!你的程序无法再获得那100个在堆中申请的内存单元。可是这些内存单元仍然占据着内存,也就是内存垃圾。在编写动态分配的程序时,很容易出现这样的错误。正确做法是在这个指针不用的情况下,将其free。
有时候有些内存泄露是自己看不出来的,特别当函数变得复杂起来的时候。
下列程序为死亡程序,可以试试运行看看自己电脑的内存变化。
3. List(链表或线性表)
An introduction to List
From wikipedia
The operations about list are appending, deleting, modifying, querying.
we use this simple list again:
2.If append a node at the end of the list
3.Traversal
Deep Thinking(120pts, 20 for each)
1.Look at the following function:
(1) Which area in memory does the function store? And which dose the variable
int a
?function store : Code Area
variable 'int a': (function) stack
(2) What's the advantages of using static functions?
2. Look at the following program which is attempt to allocate a dynamic array.
Can we create an 2D array in the heap using this way? Give your explanations and give another way that can allocate a dynamic 2D array
No, the 2D dynamic array is discontinuous in 1D memory space which does not fit the accurate 2D array definition.
issues:
memset
or other memory operation on the whole block of memory, you can not get your expected result.Look at the following program:
Result:
This is the Problem.
One possible way:
3.Why use a list instead of an array? What's the advantages and disadvantages of them respectively?
Both store a sequence of elements, but using different techniques.
An array stores elements in successive order in memory, i.e. it looks like follows:
This means, elements are one after another consecutive in memory.
A ((doubly) linked) list, on the other hand, stores the items the following way: It creates an own "list item" for each element; this "list item" holds the actual element and a pointer/reference/hint/etc to the next "list item". If it is doubly linked, it also contains a pointer/reference/hint/etc to the previous "list item":
Both store a sequence of elements, but using different techniques.
An array stores elements in successive order in memory, i.e. it looks like follows:
This means, elements are one after another consecutive in memory.
A ((doubly) linked) list, on the other hand, stores the items the following way: It creates an own "list item" for each element; this "list item" holds the actual element and a pointer/reference/hint/etc to the next "list item". If it is doubly linked, it also contains a pointer/reference/hint/etc to the previous "list item":
This means, the elements can be spread all over the memory and are not stored at specific memory locations.
Now that we know this, we can compare some usual operations on sequences of elements:
1 | 2 | 3 | 4 | 5 | 6 | ... | 999 | 1000 | free | free
Now, we want to insert
4.5
between4
and5
: This means, we have to move all elements from5
to1000
one position right in order to make space for the4.5
:Moving all these elements, is a very expensive operation. So better don't do this too often.
Now we consider, how a list can perform this task: Let's say we have currently the following list:
Again, we want to insert
4.5
between4
and5
. This can be done very easily: We generate a new list item and update the pointers/references:We have simply created a new list element and generated sort of "bypass" to insert it - very cheap (as long as we have a pointer/reference to the list item the new element will be inserted after).
So, let's sum up: Linked lists are really nice when it comes to inserting at random positions (as long as you have a pointer to the adequate list item). If your operation involves adding lots of elements dynamically and traversing all elements anyway, a list might be a good choice.
An array is very good when it comes to index accesses. If your application needs to access elements at specific positions very often, you should rather use an array.
Notable things:
4.
(1)Why is it necessary to have a heap, i.e. why not use stack only?
The stack is the memory set aside as scratch space for a thread of execution. When a function is called, a block is reserved on the top of the stack for local variables and some bookkeeping data. When that function returns, the block becomes unused and can be used the next time a function is called. The stack is always reserved in a LIFO (last in first out) order; the most recently reserved block is always the next block to be freed. This makes it really simple to keep track of the stack; freeing a block from the stack is nothing more than adjusting one pointer.
The heap is memory set aside for dynamic allocation. Unlike the stack, there's no enforced pattern to the allocation and deallocation of blocks from the heap; you can allocate a block at any time and free it at any time. This makes it much more complex to keep track of which parts of the heap are allocated or free at any given time; there are many custom heap allocators available to tune heap performance for different usage patterns.
Each thread gets a stack, while there's typically only one heap for the application (although it isn't uncommon to have multiple heaps for different types of allocation).
To answer your questions directly:
The OS allocates the stack for each system-level thread when the thread is created. Typically the OS is called by the language runtime to allocate the heap for the application.
The stack is attached to a thread, so when the thread exits the stack is reclaimed. The heap is typically allocated at application startup by the runtime, and is reclaimed when the application (technically process) exits.
The size of the stack is set when a thread is created. The size of the heap is set on application startup, but can grow as space is needed (the allocator requests more memory from the operating system).
The stack is faster because the access pattern makes it trivial to allocate and deallocate memory from it (a pointer/integer is simply incremented or decremented), while the heap has much more complex bookkeeping involved in an allocation or free. Also, each byte in the stack tends to be reused very frequently which means it tends to be mapped to the processor's cache, making it very fast. Another performance hit for the heap is that the heap, being mostly a global resource, typically has to be multi-threading safe, i.e. each allocation and deallocation needs to be - typically - synchronized with "all" other heap accesses in the program.
(2)What's the max size of the stack or the heap for a c program in your computer? Can you revise it?
In linux,
revise stack example
max heap size is usually the virtual memory of your computer.
(3)Will deep recursive program really lead to stack overflow?Why? (The answer is no)
No, not really. The following program will cause stack overflow in normal mode compile.
But if we add compile parameter
gcc -O1 -foptimize-sibling-calls recursion.c
, there will not be stack overflow.Also we can calculate how large is it in one function stack, think about it.
5.(optional) How to use an array to create a list know as a static list in logic?
For example:
6. (optional) Think about that can we use an int_64 (long long) to create a list using the high 32 bits to store an int data and use the low 32 bits to store the next address pointer? If so, write a program to test. If not, write a program to explain your reasons.
Deadline and Submit
Dec 19th, 2015 18:00
Submit to ftp
Filename : 13331314_叶嘉祺_DMA.pdf
Questions
周一早上随机提问同学相关知识
The text was updated successfully, but these errors were encountered: