Modul 5 - Minneshantering

Question 1

How to use malloc()?

Answer 1

• malloc() is used to allocate memory dynamically (at runtime) on the heap.
• Needed when you don’t know how much memory will be used until the program runs.
• You pass it a size asking for some room on the heap:
  void *malloc(size_t size);

Return value:

• a pointer (variable that holds an address) to the beginning of the allocated memory
• or NULL if the memory can’t be allocated.

Question 2

How to use free()?

Answer 2

• free() deallocates the memory for a given pointer.
• Takes a pointer that was returnes from malloc() to find the memory.
• To know how much memory that is supposed to be freed, the memory block keeps the size in a header block that lies just before the actual memory.

Example:
int *x = malloc(10 * sizeof(int));
…
free(x);

Question 3

How does memory allocation work on Java (and other languages)?

Answer 3

They support automatic memory management. In such languages, while you call something like malloc()
to allocate memory (usually new or something similar to allocate a new object), you never have to call something to free space; rather, a garbage collector runs and figures out what memory you no longer have references to and frees it for you.

Question 4

What types of calls is malloc() and free()?

Answer 4

They are library calls. Thus the malloc library manages space within your virtual address space, but itself is built on top of some system calls which call into the OS to ask for more memory or release some back to the system.

Question 5

library calls vs system calls?

Answer 5

System calls and library calls are similar in that they are provided to application by the environment. The difference between the two is that system calls are implemented in kernel, whereas library calls are implemented in user space.

1. System calls (functions provided by the kernel)
2. Library calls (functions within program libraries)
   - Library is often just a wrapper for the system call - sometimes more complex.

Question 6

What does realloc() do?

Answer 6

realloc() makes a new larger region of memory, copies the old region into it, and returns the pointer to the new region.

Question 7

What does calloc() do?

Answer 7

calloc() allocates memory and also zeroes it before

returning; this prevents some errors where you assume that memory is zeroed and forget to initialize it yourself

Question 8

What does the system calls brk() and sbrk() do? (Kernel operations)

Answer 8

• brk() and sbrk() change the location of the program break, which defines the end of the process’s data segment.
• brk() sets the end of the data segment to the
  value specified by address
• sbrk() increments the program’s data space by
  increment bytes.
• Calling sbrk() with an increment of 0 can be
  used to find the current location of the program
  break.
• Calling sbrk() is costly i.e. better to do a few large allocations and then do several smaller malloc() operations.

Question 9

Free list strategies?

Answer 9

• Best fit: the block that minimize the left over.
• Worst fit: the block that maximize the left over.
• First fit: pick the first one.

Question 10

Buddy allocation pros and cons?

Answer 10

Pros:

• Easy to determine if two blocks can be merged together.
• Efficient allocation and deallocations of frames.
• Coalescing efficient, O(lg(n))
• Handles external fragmentation well.

Cons:
- Internal fragmentation - if we need a frame of 9 blocks we get 16! As only blocks of size 2^n can be given.

Question 11

Explain splitting a free list?

Answer 11

Split a memory block in the free list:

• Return the needed amount to the user
• The rest is kept on the free list

If a smaller chunk of memory is requested than what is available in the free list then the allocator performs splitting.

Question 12

What is a free list?

Answer 12

• Data structure used for dynamic memory allocation management.
• Contains blocks (references) of the available free space on the heap.
• This data structure must not be a list per se, but just some kind of data structure to track free space.

Question 13

Explain the mechanism known as coalescing of free space?

Answer 13

• Two blocks of free memory that lies next to each other are merged.
• The allocator coalesce free space when a chunk of memory is freed. That is merges newly freed space to the free spaces that are next to it, into a single larger free chunk.

The idea is simple: when returning a free chunk in memory, look carefully at the addresses of the chunk you are returning as well as the nearby chunks of free space; if the newly freed space sits right next to one (or two, as in this example) existing free chunks, merge them into a single larger free chunk.

Question 14

What is allocated in the header block?

Answer 14

• The header minimally contains the size of the allocated region, it may also contain additional pointers to speed up deallocation, a magic number to provide additional integrity checking, and other information.
• Allocators store this little bit of extra information
  in a header block which is kept in memory, usually just before the handed-out chunk of memory, so that we can free memory by giving a pointer to free(void *ptr) instead of giving a size parameter.

Question 15

How does best fit strategy work?

Answer 15

• The best fit strategy is quite simple: first, search through the free list and find chunks of free memory that are as big or bigger than the requested size. Then, return the one that is the smallest in that group of candidates; this is the so called best-fit chunk.
• Tries to reduce wasted space by returning a block that is close to what the user asked.
• But naive implementations pay a heavy performance penalty when performing an exhaustive search for the correct free block.

Question 16

How does worst fit strategy work?

Answer 16

• The worst fit approach is the opposite of best fit; find the largest chunk and return the requested amount; keep the remaining (large) chunk on the free list.
• Worst fit tries to thus leave big chunks free instead of lots of small chunks that can arise from a best-fit approach.
• However, a full search of free space is required, and thus this approach can be costly.
• Studies show that it performs badly, leading to excess
  fragmentation while still having high overheads.

Question 17

How does first fit strategy work?

Answer 17

• The first fit method simply finds the first block that is big enough and returns the requested amount to the user.
• First fit has the advantage of speed — no exhaustive search of all the free spaces are necessary.
• But sometimes pollutes the beginning of the
  free list with small objects. Thus, how the allocator manages the free list’s order becomes an issue.
• One approach is to use address-based ordering; by keeping the list ordered by the address of the free space, coalescing becomes easier, and fragmentation tends to be reduced.

Question 18

How does next fit strategy work?

Answer 18

Instead of always beginning the first-fit search at the beginning of the list, the next fit algorithm keeps an extra pointer to the location within the list where one was looking last.

• The idea is to spread the searches for
  free space throughout the list more uniformly, thus avoiding splintering of the beginning of the list.
• The performance of such an approach is quite similar to first fit, as an exhaustive search is once again avoided.

Question 19

What is the basic idea of segregated lists?

Answer 19

The basic idea is simple: if a particular application
has one (or a few) popular-sized request that it makes, keep a separate list just to manage objects of that size; all other requests are forwarded to a more general memory allocator.

Question 20

Benefits and complications of segregated lists?

Answer 20

• The benefits of such an approach are obvious. By having a chunk of memory dedicated for one particular size of requests, fragmentation is much less of a concern; moreover, allocation and free requests can be
  served quite quickly when they are of the right size, as no complicated search of a list is required.
• One complication for example is, how much memory should one dedicate to the pool of memory that serves specialized requests of a given size, as opposed to the general pool?

Question 21

What is the slab allocator?

Answer 21

• The slab allocator tries to resolve the complication of segregated lists.
• When the kernel boots up, it allocates a number of object caches for kernel objects that are likely to be requested frequently (e.g. locks, file-system inodes etc)
• The object caches thus are each segregated free lists of a given size and serve memory allocation and free requests quickly
• When a given cache is running low on free space, it requests some slabs of memory from a more general memory allocator
• The general memory allocator can in turn request memory from the specialized source (the segregated list) if it is not used much, thus reclaim space.
• The slab allocator also initializes free objects on the list beforehand, making the process even faster

Question 22

How does the buddy allocation work?

Answer 22

• It’s a allocator designed to make coalescing simple (merging free blocks)
• In such a system, free memory is first conceptually thought of as one big space of size 2^N.
• When a request for memory is made, the search for
  free space recursively divides free space by two until a block that is big enough to accommodate the request is found.
• This scheme can suffer from internal fragmentation, as you are only allowed to give out power-of-two-sized blocks.
• The beauty of buddy allocation is found in what happens when that block is freed. When returning the 8KB block to the free list, the allocator checks whether the “buddy” 8KB is free; if so, it coalesces the two blocks into a 16KB block. The allocator then checks if the buddy of the 16KB block is still free; if so, it coalesces those two blocks. This recursive coalescing
  process continues up the tree, either restoring the entire free space or stopping when a buddy is found to be in use.

Question 23

How does the system call mmap() work?

Answer 23

• mmap() creates a new mapping in the virtual
  address space of the calling process.
• The length argument specifies the length of the
  mapping.
• If addr is NULL, then the kernel chooses the
  address at which to create the mapping.
• The prot argument describes the desired memory
  protection of the mapping.
• flags, fd and offset for mapping of file in memory

void * mmap ( void *addr , size_t length , int prot , int flags , int fd , off_t offset );

Question 24

sbrk() vs mmap()?

Answer 24

brk() and sbrk():

• Easy to extend the process heap
• Not easy to hand back allocated memory
• Only one “heap”
  ´- Not part of POSIX

mmap():

• POSIX standard
• Easy to allocate several large areas
• Easy to hand back allocated memory
• Ability to map a file in memory

Question 25

What does sbrk(size) do? (system call)

Answer 25

• Ask for more memory on the heap by using program break
• The program break points to the end of the heap
• Increments the program break by the defined size in bytes

Return value:

• The previous program break
• or -1 on error.
• sbrk(0) returns the current location of the program break.

Question 26

What does brk(address) do? (system call)

Answer 26

• Similar to sbrk() but takes an address instead.
• Sets the program break to the specified address

Returns value:

• 0 on success
• or -1 on error.