代写代考 NULL 32 32 32

Buddy System Strategy Assignment #3

Main memory and the registers built into each processing core are the only general-purpose storage that the CPU can access directly.

Registers are high-speed memories located within the Central Processing Unit (CPU). Because accessing the main memory to get an instruction or data word* takes much longer than executing an instruction, all CPUs contain some registers inside to hold key variables and temporary results.
Introduction
The CPU instruction set contains instructions that can load a data word of information from main memory into a register, and vice-versa
*an x86-64 processor architecture has a 64-bit word (equivalent to 8 bytes)
https://www.doc.ic.ac.uk/~eedwards/compsys/memory/index.html

Introduction
• Main memory (RAM)
o the most common form of Main Memory
o a repository of quickly accessible data shared by the CPU and I/O
o large array of bytes; each byte has its own address; shared by
CPU and I/O devices
• Data residing in disk must be transferred to main memory first, before CPU can process them.
• Instructions must be in memory for CPU to execute them.
https://math.hws.edu/javanotes/c1/s1.html

Memory Manager
• To improve both the utilization of the CPU and the computer’s response time to its users, general-purpose computers must keep several programs in memory, creating a need for memory management.
• The memory manager of an operating system is responsible for managing the computer’s primary memory (RAM):
o keeps track of which parts of memory are in use
o allocates memory to processes when they need it,
and deallocates it when they are done.
• The lowest level of cache memory is normally done by the hardware, so our focus will be on the programmer’s model of main memory and how it can be managed.

User space vs. Kernel space
Modern operating systems typically segregates virtual memory into user space and kernel space.
Physical memory space
User space
Mapping of physical memory space to logical address space:
• The separation serves to provide memory protection and hardware protection from malicious or errant software behaviour.
• Kernel space is strictly reserved for running a privileged operating system kernel, kernel extensions, and most device drivers.
• User space is the memory area where application software and some drivers execute.
Kernel space

Logical address space allotted to a process
Each process is allocated a portion of memory (user space) when run.
Logical address space
(also referred to as virtual address space)
Inside main memory (user space)
Mapping of physical memory space to logical address space:
an area of physical memory is mapped into a logical address space, and made available to a process.
Physical memory
(User space) logical address space virtual address space
May be organised in page frames, may not be contiguous
Made available to the user as contiguous
connections are only an abstraction (more complicated in practice).

Logical address space
(also referred to as virtual address space)
It is up to the memory management unit (MMU) to map logical pages to physical page frames in memory
Inside main memory (user space)
(User space) logical address space virtual address space
Physical memory
May be organised in page frames, may not be contiguous
Made available to the user as contiguous
Each process is allocated a portion of memory (user space) when run.

dynamic size
Layout of a Process in Memory
Each process is allocated a portion of memory (user space) when run.
fixed size
Inside main memory (user space) Layout of a process in memory:
connections are only an abstraction (more complicated in practice).
1. Text section—the executable code (in machine language)
2. Data section—global variables
3. Heap section—memory that is dynamically allocated during program
4. Stack section—temporary data storage when invoking functions (such
as function parameters, return addresses, and local variables)

Layout of a C program in Memory
Note: Modern OS add some randomness in the placement of the different program elements in memory, to prevent attackers from guessing the exact location of variables and content of heap allocations, and most importantly to prevent them from manipulating them. 9

Recall: Virtual Memory
Virtual Address Space of a Process in Memory Memory
The heap is allowed to grow upwards, as it is used for dynamic memory allocation The stack is allowed to grow downwards, as through successive function calls.
The hole between the heap and the stack is part of the virtual address space that is allowed to grow; it will require more physical pages only if the heap or stack grows.
Part of the
virtual address space that dynamically grows

Recall: Virtual Memory
Virtual Address Space of a Process in Memory Memory
The heap is allowed to grow upwards, as it is used for dynamic memory allocation The stack is allowed to grow downwards, as through successive function calls.
The hole between the heap and the stack is part of the virtual address space, but will require physical pages only if the heap or stack grows.
Part of the
virtual address space
The heap section can be dynamically managed using a combination of a memory paging system and the Buddy System algorithm that we will study next.

Kernel memory
Kernel, Kernel Memory
• Often allocated from a free-memory pool different from the list used to satisfy ordinary user-mode processes
• Many operating systems do not subject kernel code or data to the paging system (more on this later).
• The kernel requests memory for data structures of varying sizes, some of which are less than a page in size. Therefore, the kernel must use memory conservatively and must attempt to minimise waste due to fragmentation.
• The Buddy System is suited for managing free memory that is assigned to kernel processes. Interestingly, this algorithm has been successfully extended to become a scalable concurrent malloc (jemalloc).
https://github.com/jemalloc/jemalloc/wiki/Background

Memory Management Strategies
Memory Management
• Modern OS typically makes use of a paging algorithm to manage the virtual address space. Paging provide pages of memory to a process that needs memory. With the support of the processor, multiple page sizes can be mixed and matched (i.e. 4-KB, 2-MB, 1-GB pages). However, if a process needs only a few bytes, handing out an entire page is a waste of space. Therefore, to use memory more efficiently, another layer of memory management is used on top of paging. In Linux, the algorithm used is the Buddy system algorithm. It allows for the allocation of arbitrary-sized contiguous memory blocks.
• We will cover the Buddy System today, then we will cover the paging algorithm in the next lecture.

Dynamic Memory Allocation
The heap will grow as memory is dynamically allocated, and will shrink when memory is returned to the system.
#include
void *malloc(size_t size);
void free(void *ptr);
char *p1 = malloc(3);
char *p2 = malloc(1);
char *p3 = malloc(4);
char *p4 = malloc(6);
char *p5 = malloc(2);
0xffffffff

Dynamic Memory Allocation
#include
void *malloc(size_t size);
void free(void *ptr);
char *p1 = malloc(3);
char *p2 = malloc(1);
char *p3 = malloc(4);
char *p4 = malloc(6);
char *p5 = malloc(2);
0xffffffff

Dynamic Memory Allocation
A sequence of calls for malloc and free can cause the heap to be fragmented.
#include
void *malloc(size_t size);
void free(void *ptr);
char *p1 = malloc(3);
char *p2 = malloc(1);
char *p3 = malloc(4);
char *p4 = malloc(6);
char *p5 = malloc(2);
0xffffffff

Memory Management Strategy
Let us examine a strategy for managing free memory that is assigned to kernel processes.

Memory Allocation, Splitting a Memory Block

… and so on
9 29 512 8 28 256 7 27 128 6 26 64 5 25 32 4 24 16 3 23 8 2 22 4 1 21 2 0 20 1
The memory block size should be in the form of 2k.
The Buddy system
The Buddy System allocates memory from a fixed-size segment consisting of physically contiguous pages.
Memory is allocated in block sizes using a power-of-2 allocator, which satisfies requests in units sized as a power of 2 (e.g. 4KB, 8 KB, 16 KB, etc.)
Can we define a memory block of size 100Kb? 9.21

… and so on
9 29 512 8 28 256 7 27 128 6 26 64 5 25 32 4 24 16 3 23 8 2 22 4 1 21 2 0 20 1
The memory block size should be in the form of 2k. Can we define a memory block of size 100Kb? No.
The Buddy system
A request in units not appropriately sized is rounded up to the next highest power of 2.
But we can allocate 128 KB (27), as it is the smallest block that can satisfy a request for 100 KB.

2k Size … …
Maximum block size
… and so on
9 8 7 6 5 4 3 2 1 0
29 512 28 256 27 128 26 64 25 32 24 16 23 8 22 4 21 2 20 1
Minimum block size
The Buddy system
• The number of different block sizes that can be used depends on how much memory space is available and the minimum block size.
• For example, if there is 512KB of total free memory and the minimum block size is set to be 32KB, then we have the following block sizes:
e.g. Total memory available is 512 KB.

2k Size … …
… and so on
Maximum block size
9 8 7 6 5 4 3 2 1 0
29 512 28 256 27 128 26 64 25 32 24 16 23 8 22 4 21 2 20 1
Minimum block size: 32KB
The Buddy system
We need to define a minimum block size as the memory management strategy needs to keep track of some necessary header information associated with each block. This header also occupies some memory space.
The minimum block size should be set greater than the size of the header to accommodate some useful data.
9.24 e.g. 32KB=16KBheader+16KBdata.

The Buddy system: Free List
• The system starts off with a single free block of max. size (e.g. 512).
empty empty
k=9 k=8 k=7
To make it easier to find free blocks of memory, we can maintain a Free List.

Over time, the number of blocks per row may grow or shrink, depending on the sequence of memory allocation/deallocation requests.
The Buddy system: Free List
This will make searching for a free block of a certain size straightforward.
NULL 32 32 32

Memory Allocation Strategy
The Buddy system
Pseudocode: Memory Allocation, Splitting a block
1. Initially, the memory space available is treated as a single memory block
2. To allocate a block of memory, the system must work out which order of
block to allocate. If a memory request of size n is made, such that 𝒌􏰂𝟏 𝒌, then the entire block is allocated.
3. Otherwise, the memory block is split into two equal buddies
4. The process continues until the smallest block greater than or equal to n
is generated.

The Buddy system
Given a request for memory allocation, find a suitable block
Example: Given an initial single memory block of size 26=64KB, and a memory allocation request of size n=40KB, compute for the suitable memory block that could be allocated to satisfy the request. Assume that the header size is negligible.
 If a memory request of size n is made, such that 𝟐𝒌􏰂𝟏 􏰃 𝒏 􏰄 𝟐𝒌, then the entire block is allocated
 Otherwise, the memory block is split into two equal buddies
Here, 𝑘 􏰀 6; 26 = 64 2􏰅􏰂􏰆= 32
2􏰅 = 64 2􏰅􏰂􏰆 􏰃𝒏􏰄2􏰅
contiguous memory block
32 􏰃 40 􏰄 64
The whole 64KB block is allocated to satisfy the request.

Memory Deallocation, Coalescing Free Blocks

Coalescing memory
• When a block is freed, the system does not just add it to the Free List for that block size – first, it should check whether the block can be combined with other existing free blocks, to form a larger free block.

Coalescing memory
• This is where the Buddy System gets its name from. A free block of memory is not just combined with any of the neighbouring free block, it has a particular buddy of the same size and can only be combined with that specific buddy block.

Coalescing memory
• In the tree view of the buddy system, the buddy of a block is the other child node that has the same parent.

Coalescing memory
• If a block of memory is freed, the system should check whether the buddy is also free and then combine them together into a single free block.
• The buddy of this newly combined block may also be free, so the system needs to check this buddy as well and combine them together as well (and so on).
Block to be freed

Coalesce blocks
Coalescing memory
• When block is freed, it can be combined with its buddy.

Coalesce blocks
Coalescing memory
• This new free block can also be combined with its buddy.

Coalescing memory
• This time the buddy is not free so the process stops (remember to check the size of the buddy to make sure it hasn’t be split up into smaller blocks).
Cannot coalesce blocks anymore

Coalescing memory
The blocks of memory are not actually stored as a tree, so how to find the buddy block?
If the block has a start address of address and a size of size, then the address of the buddy block can be calculated from:
buddy = start + (address – start) ^ size Where:
^ is the xor operation;
start is the start address of the whole memory available to the process.

start = 0 address = 48K size = 8K
Coalescing memory
Calculate the address of the buddy of this block to be freed.
Free To be freed Free
0 8K 16K 32K 48K 56K 64K
buddy = start + (address – start) ^ size buddy = 0 + (48K – 0) ^ 8K = 56K
We can see that the buddy block is free, so we should coalesce the two blocks. 9.38

Buddy System Strategy
Let us further examine how the Buddy System Strategy works by considering a train of memory allocation and deallocation requests.

The Buddy system
Initially, a process is given one contiguous memory block for which it could operate on, to satisfy a series of memory allocation and deallocation requests.
e.g. initial memory = 64 kBytes //this is a single contiguous free // memory block
k 2k Size 9 29 512 8 28 256 7 27 128 6 26 64
26 = 64 kBytes
5 25 32 4 24 16 3 23 8 2 22 4 1 21 2 0 20 1
contiguous memory block

Contiguous memory block
The Buddy system
Example (continuation): Given: 64 kBytes of free contiguous memory Next, let us consider the following memory allocation request:
 Request: allocate 7 kBytes
We need to find an appropriately sized free memory block to satisfy this request. So far, we only have one memory block of size 64 kbytes that we could use, but is this the right size?

Contiguous memory block
32 􏰃 7 􏰄 64
The Buddy system
Example (continuation): Given: 64 kBytes of free contiguous memory  Request: allocate 7 kBytes
Examining the initial block, here, 𝒌 􏰀 𝟔; 26 = 64 kBytes Request: n = 7 kBytes
2􏰅􏰂􏰆 􏰃𝒏􏰄2􏰅 2􏰅􏰂􏰆= 32
This evaluates to false; therefore, we need to split the memory block. (Go to Step#3)

The Buddy system
Example (continuation): Given: 64 kBytes of free contiguous memory  Request: allocate 7 kBytes
Applying Step#3, we split the block into two equal buddies of size 32 kBytes each.
We then examine if the block size satisfies the request. Here, 𝒌 􏰀 𝟓; 25 = 32 kBytes
Request: n = 7 kBytes

The Buddy system
Example (continuation): Given: 64 kBytes of free contiguous memory  Request: allocate 7 kBytes
Applying Step#3, we split the block into two equal buddies of size 32 kBytes each.
We then examine if the block size satisfies the request.
Here, 𝒌 􏰀 𝟓; 25 = 32 kBytes Request: n = 7 kBytes
split the memory block again. (Go to Step#3)
This evaluates to false; therefore, we need to

The Buddy system
Example (continuation): Given: 64 kBytes of free contiguous memory  Request: allocate 7 kBytes
Applying Step#3, we split the first 32-kByte block into two equal buddies, of size 16 kBytes each.
We then examine if the block size satisfies the request. Here, 𝒌 􏰀 𝟒; 24 = 16 kBytes
Request: n = 7 kBytes

The Buddy system
Example (continuation): Given: 64 kBytes of free contiguous memory  Request: allocate 7 kBytes
Applying Step#3, we split the first 32-kByte block into two equal buddies, of size 16 kBytes each.
We then examine if the block size satisfies the request.
Here, 𝒌 􏰀 𝟒; 24 = 16 kBytes Request: n = 7 kBytes
This evaluates to false; therefore, we need to split the memory block
again. (Go to Step#3)

The Buddy system
Example (continuation): Given: 64 kBytes of free contiguous memory  Request: allocate 7 kBytes
Applying Step#3, we split the first 16-kByte block into two equal buddies, of size 8 kBytes each.
We then examine if the block size satisfies the request. Here, 𝒌 􏰀 𝟑; 23 = 8 kBytes
Request: n = 7 kBytes

The Buddy system
Example (continuation): Given: 64 kBytes of free contiguous memory  Request: allocate 7 kBytes
We then examine if the block size satisfies the request. Here, 𝒌 􏰀 𝟑; 23 = 8 kBytes
Request: n = 7 kBytes
Finally, this evaluates to true; therefore, we have found the right block that satisfies the memory allocation request of 7 kBytes.

The Buddy system
Example (continuation): Given: 64 kBytes of free contiguous memory  Request: allocate 7 kBytes
Free Blocks
Allocated Block

The Buddy system
In order to respond quickly to future memory allocation and deallocation requests, it is useful to keep track of the free memory blocks using a data structure that is suited to the task. One possibility is to make use of an array of doubly linked lists.
Note that this is a 2D data structure. We can call this the Free List.
Free Blocks
Allocated Block
24 NULL 16 previous

Free Blocks
Total of 64 kBytes
The Buddy system
It is important to note that the Free List is 2D as the number of blocks per row may grow or shrink, depending on the sequence of memory allocation and deallocation requests.
As an example, the Free List may contain 1 block of size

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts