武汉大学21级网安操作系统大作业 任务一
1. 问题介绍与思路摘要
1.1 问题介绍
在已有实验代码基础上，将1-8章节（可以包含第9章）进行功能综合，形成你自己的一个简易OS
功能要求：
? 可以考虑使用软盘或者硬盘，启动该mini-OS。
? 能够实现你在前面章节所实现的，内存分配与释放，
? 能够实现你在前面章节所实现的多进程管理与调度，
? 所有代码需用目录树结构管理，并添加完整的makefile编译，以及文档
1.2 思路摘要
根据老师点拨，法一决定在chapter10的基础上做，法二是在chapter6的基础上做的。
在本学期“内核雏形”一节的实验中，我们利用makefile初步形成了一个内核雏形，其中已经添加了在屏幕上画一个喜欢的ASCII图案、内存分配与释放、自己设计的键盘中断；在本学期“多进程与进程调度”一节的实验中，我们实现了多级反馈队列调度算法。
基于此，将之前完成的功能：启动代码，在引导过程中在屏幕上画一个喜欢的ASCII图案；内存分配与释放；自己设计的键盘中断；多级反馈队列调度算法等集成。
2. 具体思路及其实现（法一）
2.1 在屏幕上画一个喜欢的ASCII图案
在start.c中加入printself函数，内容自定义，如
PUBLIC void printDP() {
/* 通过打印空格的方式清空屏幕的前17行，并把 disp_pos 清零 */
int i;
disp_pos = 0;
for(i=0;i<80*17;i++){
disp_str(" ");
}
disp_pos = 0;
disp_str(
"Welcom to my test!
"
//自己可以自定义打印内容
);
}
然后，在kernel.asm引入并调用
效果如下
2.2 内存分配与释放
之前的实验中，将函数写在了一个文件中，即page.asm文件，直接复制到mm文件夹下，这是其中较为重要的几个函数。
DispTransfer: ; 保存现有的寄存器状态 xchg bx,bx pusha ; 打印base_address call DispReturn push szBASE call DispStr add esp, 4 ; 打印虚拟地址 mov eax, VirtualAddr push eax call DispInt add esp, 4 ; 打印PDE_base_address call DispReturn push szPDE call DispStr add esp, 4 ; 计算并打印页目录项 ; mov ax, SelectorFlatRW ; mov es, ax mov eax, VirtualAddr shr eax, 22 cmp eax, [PageTableNumber] ; jg .error mov ebx, 4 mul ebx mov edx, cr3 add eax, edx mov ecx, dword [es:eax] xor ecx, PG_P | PG_USU |PG_RWW and ecx, 0xfffffc00 push dword [es:eax] call DispInt add esp, 4 ; 打印PDE_base_address call DispReturn push szPTE call DispStr add esp, 4 ; 计算打印页表项 mov eax, VirtualAddr shr eax, 12 and eax, 0x3FF mov ebx, 4 mul ebx add eax, ecx mov ecx, dword [es:eax] xor ecx, PG_P | PG_USU | PG_RWW and ecx, 0xfffff000 push dword [es:eax] call DispInt add esp, 4 ; 打印Final_address call DispReturn push szFINAL call DispStr add esp, 4 ;计算打印最终地址 mov eax, VirtualAddr and eax, 0xFFF add eax, ecx push eax call DispInt add esp, 4 ; 恢复寄存器并返回 popa ret .error: ; 打印错误消息 push szAddressNotPresent call DispStr add esp, 4 ; 恢复寄存器并返回 popa
alloc_pages: ;save register ; push ds ; push es ; ;function implement ; mov bx, SelectorFlatRW ; mov ds,bx ; mov bx,SelectorData ; mov es,bx mov ecx,eax ;计算总共需要分配的物理内存大小，并将其存储在 ebx 寄存器中。 mov ebx,4096 ;page number * page size mul ebx mov ebx,[es:AvaLinearAddress] add [es:AvaLinearAddress],eax ;ebx存的是AvaLinearAddress 指定的线性地址对应的地址 push ebx mov eax,ebx mov ebx,cr3 and ebx,0xfffff000 and eax,0xffc00000 shr eax,20 add ebx,eax ;ebx中是PDE中的地址 mov edx,ebx ;edx->missing PDE address页目录项（PDE）的地址 mov ebx,[ebx] ;PTE 地址 ;test p flag 检查 PDE 中的 P 标志位 test ebx,0x0000_0001 jnz .pde_exist ;page table is not exist mov ebx,cr3 mov ebx,[ebx] ;first page table address and ebx,0xfffff000 shl eax,10 add ebx,eax ;这里会直接变为页表的位置 or ebx,0x0000_0007 mov [edx],ebx .pde_exist: mov eax,[esp] and ebx,0xfffff000 and eax,0x003ff000 shr eax,10 add ebx,eax .change_pte: call alloc_a_4k_page test eax,eax jz .allocation_failed ;分配失败 or eax,0x0000_0007 mov [ebx],eax add ebx,4 loop .change_pte .allocation_failed: pop ebx ; pop es ; pop ds ret alloc_a_4k_page: ;return eax: physical address ;保存寄存器的值 push ds push es ;function implement，设置合适的段寄存器的值，以确保访问正确的内存段 xor eax,eax ; mov ax,SelectorFlatRW ; mov es,ax ; mov ax,SelectorData ; mov ds,ax .search: bts [BitMap],eax jnc .find inc eax cmp eax,BitMapLen*8 jl .search ;no available physical space，执行 hlt 指令来暂停 CPU 的执行，表示没有可用的物理空间。 ;hlt;在分页分配中，使用 hlt 来表示分配失败并暂停 CPU 的执行是一种不常见的方式。 mov eax,0 ret .find: shl eax,12 pop es pop ds ret
free_pages: ; push ds ; push es push ebx ; save eax and ebx push eax ; mov bx, SelectorFlatRW ; mov ds, bx ; mov bx, SelectorData ; mov es, bx ; normal init ; find the pde and pte mov ebx, cr3 and ebx, 0xfffff000 and eax, 0xffc00000 shr eax, 20 ; 20 = 22 -2 add ebx, eax mov edx, [ebx] and edx, 0xfffffff8 mov [ebx], edx mov ebx, [ebx] mov eax, [esp] add esp, 4 and ebx,0xfffff000 and eax,0x003ff000 shr eax,10 add ebx, eax mov ecx, [esp] add esp,4 .free_pte: mov eax, [ebx] and eax, 0xfffffff8 mov edx, eax ; eax:映射的物理地址 shr edx, 12 ;edx:第edx个页面（由于物理地址开始为0x00000000） btr [BitMap], edx ;改变位图，设置为0，空闲 mov [ebx], eax add ebx,32 loop .free_pte ; pop es ; pop ds ret
然后在 kernel.asm中引入需要的函数
再添加 AllocAndFree函数并声明、调用
AllocAndFree: xchg bx,bx mov eax,4 call alloc_pages xchg bx,bx mov eax,ebx mov ebx,4 call free_pages xchg bx,bx ret
最后再在Makefile中 添加相关指令
代码效果如下图
这是DispTransfer（打马赛克的区域是个人信息，见谅）
这是alloc free
2.3 自己设计的键盘中断
在hwint01中添加自己设计的键盘中断代码，下面是示例代码
ALIGN 16 hwint01: ; Interrupt routine for irq 1 (keyboard) inc byte [gs:((80 * 17 + 50) * 2)] in al, 0x60 movzx ecx, al ;mov ecx, 8 cmp ecx,50 jg iretd_label lea ebx,[array+ecx] mov al,[ebx] mov ah,0ch mov [gs:((80 * 17 + 40)*2)],ax iretd_label: mov al,20h out 20h,al iretd
然后在一些代码地方添加能引发键盘中断的指令，运行后即可得到下图
2.4 多级反馈队列调度算法（仅展示关键代码）
首先，在sys/proc.h中定义多级反馈队列的三个队列
在kernel/global.c中初始化多级反馈队列
然后，在include/sys/global.h中声明，作为全局可用，这样在任何地方都有queue指向第一个队列
然后，在include/sys/proc.h中为每个进程添加参数inqueue（是否在队列中）、runtime（当前剩余时间）、queuenum（所在队列号）等参数。
再在kernel/proc.c中将入队和出队封装成两个函数inqueue和outqueue
int inqueue(struct proc* p) { // 把p进队
QUEUE* tempqueue;
tempqueue = queue + p->queuenum; // 将当前程序放到队尾
tempqueue->taskqueue[tempqueue->rear] = p;
tempqueue->rear = (tempqueue->rear + 1) % QUEUE_LEN;
p->inqueue = 1;
tempqueue->len += 1;
void outqueue(struct proc* p) { // 把p所在队的队首出队
QUEUE* tempqueue;
// __asm__ __volatile__("xchg %bx,%bx");
tempqueue = queue + p->queuenum;
tempqueue->front = (tempqueue->front + 1) % QUEUE_LEN;
p->inqueue = 0;
tempqueue->len -= 1; // 队首就绪, 出队
}
接下来是重头戏，即多级队列调度算法
首先仿造原schedule中的方法, 判断是否有新进程入队, 若一个进程当前为可执行状态, 并且不在队中, 则将其入队. 因为每次执行进程都会使进程出队, 所以在最开始初始化保证了每次调用该函数都能拿到进程。
struct proc* get_one_proc() { // 每次能拿到一个进程 , 且不可能拿不到
struct proc* p;
QUEUE* tempqueue;
int now_queue_num = 0;
for (p = &FIRST_PROC; p <= &LAST_PROC; p++) {
if (p->p_flags == 0 && p->inqueue == 0 &&
(p != p_proc_ready || queue->len == 0)) {
// __asm__ __volatile__("xchg %bx, %bx");makei e
p->ticks = queue->timep; // 进队进行初始化
p->queuenum = 0;
p->runtime = 100;
inqueue(p);
// disp_int(p - &FIRST_PROC);
}
}
now_queue_num = 0;
while (now_queue_num <= 2) { // 在三个队列中找能运行的程序
tempqueue = queue + now_queue_num;
int length = 0;
int point = tempqueue->front;
while (tempqueue->taskqueue[point]->p_flags != 0 &&
length < tempqueue->len) {
outqueue(tempqueue->taskqueue[point]);
inqueue(tempqueue->taskqueue[point]);
// 如果是阻塞的则先出队再入队
length += 1;
point = (point + 1) % QUEUE_LEN;
}
if (length < tempqueue->len) { // 找到一个
return tempqueue->taskqueue[point];
}
now_queue_num++;
}
}
然后编写调度函数, 需要考虑, 是否发生抢占? 若没发生, 当前时间片是否用完, 当前程序运行时间是否结束? 基于以上分支, 编写调度函数如下所示
void myschedule() {
struct proc *p, *next;
next = get_one_proc();
if (p_proc_ready->ticks && p_proc_ready->runtime &&
next->queuenum >= p_proc_ready->queuenum) { //当前进程有时间片和运行时间，且没有优先级更高的，继续
return;
}
if (p_proc_ready->runtime == 0) { // 运行时间用完，换下一个
p_proc_ready = next;
outqueue(next);
return;
}
if (p_proc_ready->ticks == 0) { // 当前时间片用完, 进队,且选下一个
if (p_proc_ready->queuenum < 2) {
p_proc_ready->queuenum += 1; // 进到下一队列
}
p_proc_ready->ticks = (queue + p_proc_ready->queuenum)->timep;
inqueue(p_proc_ready);
p_proc_ready = next;
outqueue(next);
return;
}
if (next->queuenum < p_proc_ready->queuenum) { // 抢占 有更高的优先级
inqueue(p_proc_ready);
p_proc_ready = next;
outqueue(next);
return;
}
}
然后，在include/sys/proto.h声明myschdule，因为后面别的文件要调用。
此处还存在一个地方对进程的调度存在控制, 因为此处存储在进程的阻塞, 而程序阻塞后需要选出下一个执行的程序, 否则就会发生死锁, 所以需要在下面的block函数中也进行相应的修改。
PRIVATE void block(struct proc* p) {
assert(p->p_flags);
inqueue(p);
struct proc* next = get_one_proc();
p_proc_ready = next;
outqueue(next);
// disp_int(p_proc_ready - &FIRST_PROC);
}
最后，修改clock.c中的clock_handler函数让当前进程的时间片和运行时间减少。
PUBLIC void clock_handler(int irq) {
if (++ticks >= MAX_TICKS)
ticks = 0;
if (key_pressed)
inform_int(TASK_TTY);
if (k_reenter != 0) {
return;
}
// if (p_proc_ready->ticks > 0) {
// return;
// }
if (p_proc_ready->ticks)
p_proc_ready->ticks--;
if (p_proc_ready->runtime)
p_proc_ready->runtime--;
myschedule();
__asm__ __volatile__("xchg %bx,%bx");
switch ((p_proc_ready - &FIRST_PROC))
{
case 0x6:
disp_str("A,");
break;
case 0x7:
disp_str("B,");
break;
case 0x8:
disp_str("C,");
break;
default:
break;
}
disp_str("");
}
编译运行后，效果如下图
但是，可以看到，存在问题
不知道为啥，这里一开始少了一个A。另外，达到5个之后，队列以C、A、B的顺序从5到8到9才到10。
2.5 Makefile集成
在目录下执行tree指令，得到如下目录树。Makefile中的修改不多，只有在内存与分配中修改了一小部分，详细可看对应小节，此处略去。
.
├── 80m.img
├── a.img
├── bochsrc
├── boot
│ ├── boot.asm
│ ├── boot.bin
│ ├── include
│ │ ├── fat12hdr.inc
│ │ ├── load.inc
│ │ └── pm.inc
│ ├── loader.asm
│ └── loader.bin
├── command
│ ├── echo.c
│ ├── Makefile
│ ├── pwd.c
│ └── start.asm
├── fs
│ ├── disklog.c
│ ├── link.c
│ ├── main.c
│ ├── misc.c
│ ├── open.c
│ └── read_write.c
├── include
│ ├── stdio.h
│ ├── string.h
│ ├── sys
│ │ ├── config.h
│ │ ├── console.h
│ │ ├── const.h
│ │ ├── fs.h
│ │ ├── global.h
│ │ ├── hd.h
│ │ ├── keyboard.h
│ │ ├── keymap.h
│ │ ├── proc.h
│ │ ├── protect.h
│ │ ├── proto.h
│ │ ├── sconst.inc
│ │ └── tty.h
│ └── type.h
├── kernel
│ ├── clock.c
│ ├── console.c
│ ├── global.c
│ ├── hd.c
│ ├── i8259.c
│ ├── kernel.asm
│ ├── keyboard.c
│ ├── kliba.asm
│ ├── klib.c
│ ├── main.c
│ ├── proc.c
│ ├── protect.c
│ ├── start.c
│ ├── systask.c
│ └── tty.c
├── kernel.bin
├── krnl.map
├── lib
│ ├── close.c
│ ├── exec.c
│ ├── exit.c
│ ├── fork.c
│ ├── getpid.c
│ ├── misc.c
│ ├── open.c
│ ├── orangescrt.a
│ ├── printf.c
│ ├── read.c
│ ├── stat.c
│ ├── string.asm
│ ├── syscall.asm
│ ├── syslog.c
│ ├── unlink.c
│ ├── vsprintf.c
│ ├── wait.c
│ └── write.c
├── Makefile
├── mm
│ ├── exec.c
│ ├── forkexit.c
│ ├── main.c
│ └── page.asm
└── scripts
├── genlog
└── splitgraphs
10 directories, 78 files
至此，任务一第一种方法完成。
3. 具体思路及其实现（法二）
在第六章代码基础上完成，前面的流程与法一都一样，只有多级队列调度部分的代码不一样。（仅展示重要函数）
先是在main.c中修改kernel_main函数
PUBLIC int kernel_main()
{
disp_str("-----"kernel_main" begins-----
");
int j;
disp_pos = 0;
for(j=0;j<80*25;j++){
disp_str(" ");
}
disp_pos = 0;
TASK* p_task = task_table;
PROCESS* p_proc = proc_table;
char* p_task_stack = task_stack + STACK_SIZE_TOTAL;
u16 selector_ldt = SELECTOR_LDT_FIRST;
int i;
for (i = 0; i < NR_TASKS; i++) {
strcpy(p_proc->p_name, p_task->name); // name of the process
p_proc->pid = i; // pid
p_proc->ldt_sel = selector_ldt;
memcpy(&p_proc->ldts[0], &gdt[SELECTOR_KERNEL_CS >> 3],
sizeof(DESCRIPTOR));
p_proc->ldts[0].attr1 = DA_C | PRIVILEGE_TASK << 5;
memcpy(&p_proc->ldts[1], &gdt[SELECTOR_KERNEL_DS >> 3],
sizeof(DESCRIPTOR));
p_proc->ldts[1].attr1 = DA_DRW | PRIVILEGE_TASK << 5;
p_proc->regs.cs = ((8 * 0) & SA_RPL_MASK & SA_TI_MASK)
| SA_TIL | RPL_TASK;
p_proc->regs.ds = ((8 * 1) & SA_RPL_MASK & SA_TI_MASK)
| SA_TIL | RPL_TASK;
p_proc->regs.es = ((8 * 1) & SA_RPL_MASK & SA_TI_MASK)
| SA_TIL | RPL_TASK;
p_proc->regs.fs = ((8 * 1) & SA_RPL_MASK & SA_TI_MASK)
| SA_TIL | RPL_TASK;
p_proc->regs.ss = ((8 * 1) & SA_RPL_MASK & SA_TI_MASK)
| SA_TIL | RPL_TASK;
p_proc->regs.gs = (SELECTOR_KERNEL_GS & SA_RPL_MASK)
| RPL_TASK;
p_proc->regs.eip = (u32)p_task->initial_eip;
p_proc->regs.esp = (u32)p_task_stack;
p_proc->regs.eflags = 0x1202; /* IF=1, IOPL=1 */
p_task_stack -= p_task->stacksize;
p_proc++;
p_task++;
selector_ldt += 1 << 3;
}
time_slice = 5;//初始化
process_num = 0;
// for ( i = 0; i < NR_TASKS; i++)
// {
// proc_table[i].priority = 1;
// proc_table[i].ticks = time_slice;
// }
proc_table[0].ticks = 4;
proc_table[0].priority = 1;
proc_table[1].ticks = 8;
proc_table[1].priority = 2;
proc_table[2].ticks = 16;
proc_table[2].priority = 3;
k_reenter = 0;
ticks = 0;
p_proc_ready = proc_table;
/* 初始化 8253 PIT */
out_byte(TIMER_MODE, RATE_GENERATOR);
out_byte(TIMER0, (u8) (TIMER_FREQ/HZ) );
out_byte(TIMER0, (u8) ((TIMER_FREQ/HZ) >> 8));
put_irq_handler(CLOCK_IRQ, clock_handler); /* 设定时钟中断处理程序 */
enable_irq(CLOCK_IRQ); /* 让8259A可以接收时钟中断 */
restart();
while(1){}
}
然后修改clock.c中的clock_handler函数
PUBLIC void clock_handler(int irq)
{
ticks++;
p_proc_ready->ticks--;
PROCESS* p;
//disp_int(p_proc_ready->pid);
//if (k_reenter != 0) {
// return;
//}
if(p_proc_ready->priority == 1)
{
if(p_proc_ready->ticks == 0)
{
p_proc_ready->priority = 2;
p_proc_ready->ticks = time_slice * 2;
schedule();
}
}else if(p_proc_ready->priority == 2){
if(p_proc_ready->ticks != 0)
{
for(p = proc_table; p < proc_table + NR_TASKS; p++)
{
if (p->priority == 1)
{
p_proc_ready = p;
return;
}
}
for(p = proc_table; p < proc_table + NR_TASKS; p++)
{
if (p->priority == 2)
{
p_proc_ready = p;
return;
}
}
}else{
p_proc_ready->priority = 3;
p_proc_ready->ticks = time_slice * 3;
schedule();
}
}else if(p_proc_ready->priority == 3){
if(p_proc_ready->ticks != 0)
{
for(p = proc_table; p < proc_table + NR_TASKS; p++)
{
if (p->priority == 1)
{
p_proc_ready = p;
return;
}
}
for(p = proc_table; p < proc_table + NR_TASKS; p++)
{
if (p->priority == 2)
{
p_proc_ready = p;
return;
}
}
}else{
p_proc_ready->ticks = time_slice * 3;
schedule();
if(p_proc_ready->priority == 3)
{
while(1){
process_num = (process_num + 1) % NR_TASKS;
p_proc_ready = proc_table + process_num;
if(p_proc_ready->priority == 3) break;
}
}
}
}
return;
//if (p_proc_ready->ticks > 0) {
// return;
//}
//schedule();
}
还有schedule函数
PUBLIC void schedule()
{
PROCESS* p;
int inf = 0xfffffff;
int greatest_priority = 0xfffffff;
while (greatest_priority == inf) {
for (p = proc_table; p < proc_table+NR_TASKS; p++) {
if (p->priority < greatest_priority) {
greatest_priority = p->priority;
p_proc_ready = p;
}
}
// if (!greatest_ticks) {
// for (p = proc_table; p < proc_table+NR_TASKS; p++) {
// p->ticks = p->priority;
// }
// }
}
}
编译运行后，结果如下
可以看到，显示根据时间片和优先级输出，最后优先级一致后，则进行轮询，故实验成功。