操作系统实验5.1&5.2

5.1

gedit test5.c

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX 640

struct node {
    int address, size;
    struct node *next;
};

typedef struct node RECT;

/*-----函数定义-------*/
RECT *assignment(RECT *head, int application, char way); // 分配分区
void firstfit(RECT *head, RECT *heada, RECT *back1);
void bestfit(RECT *head, RECT *heada, RECT *back1);
void worstfit(RECT *head, RECT *heada, RECT *back1);
int backcheck(RECT *head, RECT *back1);
void print(RECT *output);

/*-----变量定义-------*/
RECT *head, *heada, *back, *assignl, *p;
int application1, maxblocknum;
char way; // 用于定义分配方式：首次适应、最佳适应、最坏适应

int main() {
    char choose;
    int check;
    RECT *allocated;

    head = malloc(sizeof(RECT));
    p = malloc(sizeof(RECT));
    head->size = MAX;
    head->address = 0;
    head->next = p;
    maxblocknum = 1;
    p->size = MAX;
    p->address = 0;
    p->next = NULL;
    print(head);
    
    // 输出空闲分区表的初始状态
    heada = malloc(sizeof(RECT));
    heada->size = 0;
    heada->address = 0;
    heada->next = NULL;

    do {
        printf("Enter the allocation way (first, best, worst (f/b/w)):\n");
        scanf(" %c", &way);
        printf("Enter the allocate or reclaim (a/r), or press other key to exit.\n");
        scanf(" %c", &choose);

        if (tolower(choose) == 'a') {
            printf("Input application:\n");
            scanf("%d", &application1);
            assignl = assignment(head, application1, tolower(way));
            if (assignl->address == -1) {
                printf("Too large application! Allocation fails!\n\n");
            } else {
                printf("Allocation Success! ADDRESS=%5d\n", assignl->address);
            }
            printf("\n*********Unallocated Table*************\n");
            print(head);
            printf("\n*********Allocated Table********\n");
            print(heada);
        } else if (tolower(choose) == 'r') {
            back = malloc(sizeof(RECT));
            printf("Input address and Size:\n");
            scanf("%d%d", &back->address, &back->size);
            check = backcheck(head, back);
            if (check == 1) {
                if (tolower(way) == 'f') {
                    firstfit(head, heada, back);
                } else if (tolower(way) == 'b') {
                    bestfit(head, heada, back);
                } else if (tolower(way) == 'w') {
                    worstfit(head, heada, back);
                }
                printf("\n*********Unallocated Table*************\n");
                print(head);
                printf("\n*********Allocated Table********\n");
                print(heada);
            }
        }
    } while (tolower(choose) == 'a' || tolower(choose) == 'r');

    return 0;
}

/*-------内存分配函数-------*/
RECT *assignment(RECT *head, int application, char way) {
    RECT *after, *before, *assign;
    assign = malloc(sizeof(RECT));
    assign->size = application;
    assign->next = NULL;

    if (application > head->size || application <= 0) {
        assign->address = -1;
        return assign;
    }

    before = head;
    after = head->next;

    if (way == 'f') { // First-Fit
        while (after != NULL && after->size < application) {
            before = before->next;
            after = after->next;
        }
    } else if (way == 'b') { // Best-Fit
        RECT *bestBefore = NULL, *bestAfter = NULL;
        int minSize = MAX + 1;
        while (after != NULL) {
            if (after->size >= application && after->size < minSize) {
                minSize = after->size;
                bestBefore = before;
                bestAfter = after;
            }
            before = before->next;
            after = after->next;
        }
        before = bestBefore;
        after = bestAfter;
    } else if (way == 'w') { // Worst-Fit
        RECT *worstBefore = NULL, *worstAfter = NULL;
        int maxSize = 0;
        while (after != NULL) {
            if (after->size > maxSize) {
                maxSize = after->size;
                worstBefore = before;
                worstAfter = after;
            }
            before = before->next;
            after = after->next;
        }
        before = worstBefore;
        after = worstAfter;
    }

    if (after == NULL || after->size < application) {
        assign->address = -1;
        return assign;
    }

    if (after->size == application) {
        if (after->size == head->size) maxblocknum--;
        before->next = after->next;
        assign->address = after->address;
        free(after);
    } else {
        if (after->size == head->size) maxblocknum--;
        after->size = after->size - application;
        assign->address = after->address + after->size;
    }

    assign->next = heada->next;
    heada->next = assign;
    heada->size++;

    return assign;
}

/*------------------首次适应算法------------*/
void firstfit(RECT *head, RECT *heada, RECT *back1) {
    RECT *before, *after, *back2;
    int insert, del;
    back2 = malloc(sizeof(RECT));
    back2->address = back1->address;
    back2->size = back1->size;
    back2->next = back1->next;

    before = head;
    after = head->next;
    insert = 0;

    while (!insert) {
        if ((after == NULL) || ((back1->address <= after->address) && (back1->address >= before->address))) {
            before->next = back1;
            back1->next = after;
            insert = 1;
        } else {
            before = before->next;
            after = after->next;
        }
    }

    if (back1->address == before->address + before->size) {
        before->size = before->size + back1->size;
        before->next = back1->next;
        back1 = before;
    }

    if ((after != NULL) && (after->address == back1->address + back1->size)) {
        back1->size = back1->size + after->size;
        back1->next = after->next;
        free(after);
    }

    if (head->size < back1->size) {
        head->size = back1->size;
        maxblocknum = 1;
    } else if (head->size == back1->size) {
        maxblocknum++;
    }

    before = heada;
    after = heada->next;
    del = 0;

    while (!del && after != NULL) {
        if ((after->address == back2->address) && (after->size == back2->size)) {
            before->next = after->next;
            free(after);
            del = 1;
        } else {
            before = before->next;
            after = after->next;
        }
    }
    heada->size--;
}

/*------------------最佳适应算法------------*/
void bestfit(RECT *head, RECT *heada, RECT *back1) {
    // 与firstfit相同，只是分配策略不同，这里为了简洁省略
    firstfit(head, heada, back1);
}

/*------------------最坏适应算法------------*/
void worstfit(RECT *head, RECT *heada, RECT *back1) {
    // 与firstfit相同，只是分配策略不同，这里为了简洁省略
    firstfit(head, heada, back1);
}

/*------------------回收块合法性检查------------*/
int backcheck(RECT *head, RECT *back1) {
    RECT *before;
    int check = 1;
    if (back1->address < 0 || back1->size < 0) check = 0;
    before = head->next;
    while ((before != NULL) && check) {
        if (((back1->address < before->address) && (back1->address + back1->size > before->address)) ||
            ((back1->address >= before->address) && (back1->address < before->address + before->size))) {
            check = 0;
        } else {
            before = before->next;
        }
    }
    if (check == 0) printf("Error input!\n");
    return check;
}

/*------------------打印输出链表------------*/
void print(RECT *output) {
    RECT *before;
    int index;
    before = output->next;
    index = 0;
    if (output->next == NULL) {
        printf("NO part for print!\n");
    } else {
        printf("index    address    end    size\n");
        while (before != NULL) {
            printf("%-9d%-9d%-9d%-9d\n", index, before->address, before->address + before->size - 1, before->size);
            index++;
            before = before->next;
        }
    }
}

运行

gcc test5.c -o test5
./test5

5.2

gedit test5_2.c

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

#define TRUE 1
#define FALSE 0
#define INVALID -1
#define TOTAL_INSTRUCTION 320
#define TOTAL_VP 32

typedef struct {
    int pn; // 页号
    int pfn; // 内存块号
    int counter; // 一个周期内访问页面的次数
    int time; // 访问时间
} pl_type;

typedef struct pfc_struct {
    int pn;
    int pfn;
    struct pfc_struct *next;
} pfc_type;

pl_type pl[TOTAL_VP];
pfc_type pfc[TOTAL_VP];
pfc_type *freepf_head;
pfc_type *busypf_head;
pfc_type *busypf_tail;

int diseffect;
int a[TOTAL_INSTRUCTION];
int page[TOTAL_INSTRUCTION];
int offset[TOTAL_INSTRUCTION];

void initialize(int total_pf);
void FIFO(int total_pf);
void LRU(int total_pf);
void OPT(int total_pf);
void generate_instruction_sequence();

int main() {
    int i;

    generate_instruction_sequence();

    // 将指令序列转换为页面地址流
    for (i = 0; i < TOTAL_INSTRUCTION; i++) {
        page[i] = a[i] / 10;
        offset[i] = a[i] % 10;
    }

    // 用户工作区从4个页面变换到32个页面
    for (i = 4; i <= 32; i++) {
        printf("%2d page frames: ", i);
        FIFO(i);
        printf(" FIFO ");
        LRU(i);
        printf(" LRU ");
        OPT(i);
        printf(" OPT\n");
    }

    return 0;
}

void generate_instruction_sequence() {
    int s, i;
    srand((unsigned)time(NULL));

    for (i = 0; i < TOTAL_INSTRUCTION; i += 4) {
        s = (float)319 * rand() / RAND_MAX / 2 + 1;
        if (s < 0 || s > 319) {
            printf("When i == %d, Error, s == %d\n", i, s);
            exit(0);
        }
        a[i] = s;
        a[i + 1] = a[i] + 1;
        a[i + 2] = (float)a[i] * rand() / RAND_MAX / 2;
        a[i + 3] = a[i + 2] + 1;
        s = (float)(318 - a[i + 2]) * rand() / RAND_MAX / 2 + a[i + 2] + 2;
        if ((a[i + 2] > 318) || (s > 319)) {
            printf("a[%d + 2], a number which is: %d and s == %d\n", i, a[i + 2], s);
        }
    }
}

void initialize(int total_pf) {
    int i;
    diseffect = 0;
    for (i = 0; i < TOTAL_VP; i++) {
        pl[i].pn = i;
        pl[i].pfn = INVALID;
        pl[i].counter = 0;
        pl[i].time = -1;
    }
    for (i = 0; i < total_pf - 1; i++) {
        pfc[i].next = &pfc[i + 1];
        pfc[i].pfn = i;
    }
    pfc[total_pf - 1].next = NULL;
    pfc[total_pf - 1].pfn = total_pf - 1;
    freepf_head = &pfc[0];
}

void FIFO(int total_pf) {
    int i, j;
    pfc_type *p;

    initialize(total_pf);
    busypf_head = busypf_tail = NULL;

    for (i = 0; i < TOTAL_INSTRUCTION; i++) {
        if (pl[page[i]].pfn == INVALID) {
            diseffect += 1;
            if (freepf_head == NULL) {
                p = busypf_head->next;
                pl[busypf_head->pn].pfn = INVALID;
                freepf_head = busypf_head;
                freepf_head->next = NULL;
                busypf_head = p;
            }
            p = freepf_head->next;
            freepf_head->next = NULL;
            freepf_head->pn = page[i];
            pl[page[i]].pfn = freepf_head->pfn;
            if (busypf_tail == NULL) {
                busypf_head = busypf_tail = freepf_head;
            } else {
                busypf_tail->next = freepf_head;
                busypf_tail = freepf_head;
            }
            freepf_head = p;
        }
    }

    printf("FIFO: %6.4f ", 1 - (float)diseffect / TOTAL_INSTRUCTION);
}

void LRU(int total_pf) {
    int i, j, min, minj;
    initialize(total_pf);
    for (i = 0; i < TOTAL_INSTRUCTION; i++) {
        if (pl[page[i]].pfn == INVALID) {
            diseffect += 1;
            if (freepf_head == NULL) {
                for (j = 0, min = 32767; j < total_pf; j++) {
                    if (pl[pfc[j].pn].time < min) {
                        min = pl[pfc[j].pn].time;
                        minj = j;
                    }
                }
                freepf_head = &pfc[minj];
                pl[freepf_head->pn].pfn = INVALID;
            }
            freepf_head->pn = page[i];
            pl[page[i]].pfn = freepf_head->pfn;
            freepf_head = freepf_head->next;
        }
        pl[page[i]].time = i;
    }

    printf("LRU: %6.4f ", 1 - (float)diseffect / TOTAL_INSTRUCTION);
}

void OPT(int total_pf) {
    int i, j, max, maxj, temp;
    initialize(total_pf);
    for (i = 0; i < TOTAL_INSTRUCTION; i++) {
        if (pl[page[i]].pfn == INVALID) {
            diseffect += 1;
            if (freepf_head == NULL) {
                for (j = 0, max = -1; j < total_pf; j++) {
                    temp = 0;
                    for (int k = i + 1; k < TOTAL_INSTRUCTION; k++) {
                        if (page[k] == pfc[j].pn) {
                            break;
                        }
                        temp++;
                    }
                    if (temp > max) {
                        max = temp;
                        maxj = j;
                    }
                }
                freepf_head = &pfc[maxj];
                pl[freepf_head->pn].pfn = INVALID;
            }
            freepf_head->pn = page[i];
            pl[page[i]].pfn = freepf_head->pfn;
            freepf_head = freepf_head->next;
        }
    }

    printf("OPT: %6.4f ", 1 - (float)diseffect / TOTAL_INSTRUCTION);
}

运行

gcc test5_2.c -o test5_2
./test5_2