模拟实现最佳适应算法最坏适应算法首次适应算法循环首次适应算法四种动态分区分配算法
时间: 2023-12-14 16:33:44 浏览: 113
以下是四种动态分区分配算法的模拟实现:
1. 首次适应算法(First Fit Algorithm)
首次适应算法是最简单的动态分区分配算法之一。它从内存的低地址开始查找,找到第一个能够满足请求的空闲分区,并将其分配给请求进程。
```c
void firstFit(int requestSize) {
int i;
for (i = 0; i < numOfBlocks; i++) {
if (freeList[i].size >= requestSize) {
freeList[i].size -= requestSize;
printf("Allocated block of size %d at address %d\n", requestSize, freeList[i].startAddr);
if (freeList[i].size == 0) {
numOfBlocks--;
for (; i < numOfBlocks; i++) {
freeList[i] = freeList[i + 1];
}
}
return;
}
}
printf("No block of sufficient size available\n");
}
```
2. 循环首次适应算法(Next Fit Algorithm)
循环首次适应算法是首次适应算法的改进版。它从上一次分配的位置开始查找,找到第一个能够满足请求的空闲分区,并将其分配给请求进程。
```c
void nextFit(int requestSize) {
int i;
for (i = lastBlock; i < numOfBlocks; i++) {
if (freeList[i].size >= requestSize) {
freeList[i].size -= requestSize;
printf("Allocated block of size %d at address %d\n", requestSize, freeList[i].startAddr);
if (freeList[i].size == 0) {
numOfBlocks--;
for (; i < numOfBlocks; i++) {
freeList[i] = freeList[i + 1];
}
}
lastBlock = i;
return;
}
}
for (i = 0; i < lastBlock; i++) {
if (freeList[i].size >= requestSize) {
freeList[i].size -= requestSize;
printf("Allocated block of size %d at address %d\n", requestSize, freeList[i].startAddr);
if (freeList[i].size == 0) {
numOfBlocks--;
for (; i < numOfBlocks; i++) {
freeList[i] = freeList[i + 1];
}
}
lastBlock = i;
return;
}
}
printf("No block of sufficient size available\n");
}
```
3. 最佳适应算法(Best Fit Algorithm)
最佳适应算法是一种更为复杂的动态分区分配算法。它从所有空闲分区中找到最小的能够满足请求的分区,并将其分配给请求进程。
```c
void bestFit(int requestSize) {
int i, bestBlock = -1, bestSize = INT_MAX;
for (i = 0; i < numOfBlocks; i++) {
if (freeList[i].size >= requestSize && freeList[i].size < bestSize) {
bestBlock = i;
bestSize = freeList[i].size;
}
}
if (bestBlock != -1) {
freeList[bestBlock].size -= requestSize;
printf("Allocated block of size %d at address %d\n", requestSize, freeList[bestBlock].startAddr);
if (freeList[bestBlock].size == 0) {
numOfBlocks--;
for (; bestBlock < numOfBlocks; bestBlock++) {
freeList[bestBlock] = freeList[bestBlock + 1];
}
}
} else {
printf("No block of sufficient size available\n");
}
}
```
4. 最坏适应算法(Worst Fit Algorithm)
最坏适应算法是一种更为复杂的动态分区分配算法。它从所有空闲分区中找到最大的能够满足请求的分区,并将其分配给请求进程。
```c
void worstFit(int requestSize) {
int i, worstBlock = -1, worstSize = INT_MIN;
for (i = 0; i < numOfBlocks; i++) {
if (freeList[i].size >= requestSize && freeList[i].size > worstSize) {
worstBlock = i;
worstSize = freeList[i].size;
}
}
if (worstBlock != -1) {
freeList[worstBlock].size -= requestSize;
printf("Allocated block of size %d at address %d\n", requestSize, freeList[worstBlock].startAddr);
if (freeList[worstBlock].size == 0) {
numOfBlocks--;
for (; worstBlock < numOfBlocks; worstBlock++) {
freeList[worstBlock] = freeList[worstBlock + 1];
}
}
} else {
printf("No block of sufficient size available\n");
}
}
```
阅读全文