首页 北航操作系统

# Lab 3-1 Exam

题目大意是 Linux 系统在管理进程时，维护了一个软件 ASID，由硬件 ASID 和版本号组成，要求编写程序模拟使用软件 ASID 的情形下，进程建立时 ASID 的分配过程

考察点有

  • 读懂一段资料的能力
  • 根据流程图改写代码的能力（因为题目直接给出了一个详尽的流程图）
  • 进程的创建过程，进程结构体中的内容
  • ASID 的概念和作用

首先按照题意，定义两个宏，从 env_asid 中获取硬件 ASID 和版本号，然后再 Env 结构体中增加 env_asid 字段

#define HARDWARE_ASID(env_asid) ((env_asid) & 0x3f)
#define VERSION_ASID(env_asid) ((env_asid) >> 6)

然后再按照题目要求，修改下面的代码

u_int mkenvid(struct Env * e) {
    /*Hint: lower bits of envid hold e's position in the envs array. */
    u_int idx = (u_int)e - (u_int)envs;
    idx /= sizeof(struct Env);
    /*Hint: avoid envid being zero. */
    return (1 << (LOG2NENV)) | idx;  //LOG2NENV=10
}

然后根据需要添加或修改下面的代码，下面简要解释

  • 原本的 asid_alloc 当无法分配时，会发出一个 panic ，而现在我们肯定不想让它这样，因此我们改为返回一个错误的值 65
  • 然后根据 asid_alloc 函数，自己写一个 check_asid_free ，检查 ASID 是否空闲
  • exam_env_run 就是根据流程图改写代码了，注意先后顺序，首先需要检查 ASID 是否有效（版本号是否相同），如果有效就什么都不用做了，无效的话，检查当前版本号下的 ASID 是否耗尽，没耗尽就直接再分配一个就行了，如果耗尽了，那么就需要让版本号加 1，然后把 ASID 位图全部置为 0，然后重新分配 ASID 即可
static u_int asid_alloc() {
    int i, index, inner;
    for (i = 0; i < 64; ++i) {
        index = i >> 5;
        inner = i & 31;
        if ((asid_bitmap[index] & (1 << inner)) == 0) {
            asid_bitmap[index] |= 1 << inner;
            return i;
        }
    }
    return 65;
}
static u_int check_asid_free(int id) {
    u_int index = id >> 5;
    u_int inner = id & 31;
    if ((asid_bitmap[index] & (1 << inner)) == 0) return 1;
    return 0;
}
// Lab 3-1 Exam
static u_int system_version = 0x4;
u_int exam_env_run(struct Env * e) {
    if (VERSION_ASID(e->env_asid) == system_version) return 0;
    int proc_asid = HARDWARE_ASID(e->env_asid);
    if (check_asid_free(proc_asid) == 1) {
        e->env_asid = (system_version << 6) | proc_asid;
        asid_bitmap[(proc_asid >> 5)] |= 1 << (proc_asid & 31);
        return 0;
    } else {
        proc_asid = asid_alloc();
        if (proc_asid != 65) {
            e->env_asid = (system_version << 6) | proc_asid;
            return 0;
        } else {
            //printf("%d\n", HARDWARE_ASID(e->env_id));
            system_version += 1;
            asid_bitmap[0] = asid_bitmap[1] = 0;
            proc_asid = asid_alloc();
            e->env_asid = (system_version << 6) | proc_asid;
            return 1;
        }
    }
}
void exam_env_free(struct Env * e) {
    if (VERSION_ASID(e->env_asid) == system_version) {
        asid_free(HARDWARE_ASID(e->env_asid));
    }
}
# Lab 3-1 Extra
模拟操作系统中的 PV 操作，具体题目见链接
考察要点为
  • 链表宏的使用
  • 记录型信号量的实现方法（因此理论课需要认真听）
一些坑点
  • 题目要求 struct Env 结构体的大小不超过 256 字节，因此你只能添加不多与 3 个 u_int 类型的变量
  • 如果你了解记录型信号量，就很容易意识到一个进程可以多次进行 P 操作
  • 题目有特殊规定，可能有进程没有进行 P 操作就进行了 V 操作，这时候我们需要凭空创造出一个资源给这个进程
对于下面代码的一些解释：
  • 首先定义 Signal 结构体，维护一个信号量 num ，和在这个信号量上的等待队列
  • S_init 按照题目写，然后自己写一个 is_in_waitqueue 判断某个进程是否位于某个等待队列中
  • Add 和 Sub 是对应的信号量的值进行操作
  • P 和 V 是对应信号量的操作，按照题意模拟，考虑上述特殊情况即可
  • my_env_create 复制 env_run 中的必要内容，否则可能会出现奇怪的问题
// Lab 3-1 Extra
struct Signal {
    u_int num;
    struct Env_list wait_queue;
};
static struct Signal S[3];
void S_init(int s, int num) {
    S[s].num = num;
    LIST_INIT(&(S[s].wait_queue));
}
int is_in_waitqueue(struct Env* e, int s) {
    struct Env *i; 
    LIST_FOREACH(i, &(S[s].wait_queue), env_link) {
        if (i == e) return 1;
    }   
    return 0;
}
void Add(struct Env *e, int s) {
    if (s == 1) ++e->have1;
    else if(s == 2) ++e->have2;
}
void Sub(struct Env *e, int s) {
    if (s == 1 && e->have1 > 0) --e->have1;
    else if (s == 2 && e->have2 > 0) --e->have2;
}
int P(struct Env* e, int s) {    
    if (is_in_waitqueue(e, 1) || is_in_waitqueue(e, 2)) return -1;
    if (S[s].num > 0) {
        Add(e, s);
        S[s].num--;
        return 0;
    } else {
        LIST_INSERT_TAIL(&(S[s].wait_queue), e, env_link);
        return 0;
    }
}
int V(struct Env* e, int s) {
    if (is_in_waitqueue(e, 1) || is_in_waitqueue(e, 2)) return -1;
    else {
        S[s].num++;
        Sub(e, s);
        if (S[s].num > 0) {
            if (!LIST_EMPTY(&(S[s].wait_queue))) {
                struct Env * new_env = LIST_FIRST(&(S[s].wait_queue));
                LIST_REMOVE(new_env, env_link);
                Add(new_env, s);
                S[s].num--;
            }
        }
    }
    return 0;
}
int get_status(struct Env* e) {
    if (is_in_waitqueue(e, 1) || is_in_waitqueue(e, 2)) return 1;
    if (e->have1 == 0 && e->have2 == 0) return 3;
    else return 2;
}
int my_env_create() {
    struct Env *e;
    if (LIST_EMPTY(&env_free_list)) {
        return -1;
    }
    e = LIST_FIRST(&env_free_list);
    e->env_id = mkenvid(e);
    e->env_status = ENV_RUNNABLE;
    
    e->env_tf.cp0_status = 0x10001004;
    e->env_tf.regs[29] = USTACKTOP;
    LIST_REMOVE(e, env_link);
    e->have2 = e->have1 = 0;
    return e->env_id;
}