清华大学第二版算法分析与设计课件第一章pdf

计算机操作系统作业汇总清华大学出版社

思考与练习题（第一章） 1.什么是操作系统？它的主要功能是什么？ 答：操作系统是控制和管理计算机的软、硬件资源，合理地组织计算机的工作流程，以方便用户使用的程序集合。其主要功能包括进程管理功能、存储管理功能、设备管理功能和文件管理功能。 2.什么是多道程序设计技术？多道程序设计技术的主要特点是什么？ 答：把多个独立的程序同时放入内存，使它们共享系统中的资源。??????? （1）多道，即计算机内存中同时放多道相互独立的程序。? （2）宏观上并行，是指同时进入系统的多道程序都处于运行过程中。? （3）微观上串行，是指在单道处理机环境下，内存中的多道程序轮流占用CPU，交替执行。 3.批处理操作系统是怎样的一种操作系统？它的特点是什么？ 答：批处理操作系统是一种基本的操作系统类型。在该系统中，用户的作业（包括程序、数据及程序的处理步骤）被成批地输入到计算机中，然后在操作系统的控制下，用户的作业自动的执行。? 特点：单道：（1）自动性。（2）顺序性。（3）单道性。 多道：（1）多道性。（2）无序性。（3）调度性。

4.什么是分时操作系统？什么是实时操作系统？试从交互性、及时性、独立性、多路性和 可靠性几个方面比较分时操作系统和实时操作系统。 答：分时操作系统：计算机能够同时为多个终端用户服务，而且能在很短的时间内响应用户的要求。实时操作系统：对外部输入的信息，实时系统能够在规定的时间内处理完毕并做出反应。 （1）多路性：分时系统是为多个终端用户提供服务，实时系统的多路性主要表现在经常对多路的现场信息进行采集以及多个对象或多个执行机构进行控制。 （2）独立性：每个终端向实时系统提出服务请求时，是彼此独立的工作、互不干扰。 （3）及时性：实时信息处理系统与分时系统对及时性的要求类似，都以人们能够接受的等待时间来确定。实时控制系统对一时性的要求更高，是以控制对象所要求的开始截止时间或完成截止时间来确定的。 5.实时操作系统分为哪两种类型？ 答：（1）实时控制系统?（2）实时信息处理系统。 6.操作系统的主要特征是什么？ 答：（1）并发性?（2）共享性?（3）虚拟性?（4）不确定性。 7.操作系统与用户的接口有几种？它们各自用在什么场合？ 答：两种，命令接口和程序接口。

清华大学操作系统lab2及slub实现实验报告

练习0：把实验1的代码填入本实验中代码有lab1的注释相应的部分。 用understand中的merge工具将实验1中填写代码部分复制到实验2中，如图1。 图1 练习1：实现firstfit连续物理内存分配算法。 对于lab2代码首先对其make，之后在虚拟机中运行查看其错误所在位置如图2。 可以发现其错误出现在default_check(void)这个函数之中，该函数为检查firstfit算法的函数。继续分析错误出现的原因: struct Page *p0 = alloc_pages(5), *p1, *p2; assert(p0 != NULL); assert(!PageProperty(p0)); list_entry_t free_list_store = free_list; list_init(&free_list); assert(list_empty(&free_list)); assert(alloc_page() == NULL); unsigned int nr_free_store = nr_free; nr_free = 0;

free_pages(p0 + 2, 3); assert(alloc_pages(4) == NULL); assert(PageProperty(p0 + 2) && p0[2].property == 3); assert((p1 = alloc_pages(3)) != NULL); assert(alloc_page() == NULL); assert(p0 + 2 == p1); p2 = p0 + 1; free_page(p0); free_pages(p1, 3); assert(PageProperty(p0) && p0->property == 1); assert(PageProperty(p1) && p1->property == 3); assert((p0 = alloc_page()) == p2 - 1); //错误出现的位置 分析源码后可知，在其对内存进行一些列分配释放操作后，再次申请一页内存后出现错误，可知其在最后一次p0 = alloc_page()申请中得到内存页的位置与算法规则不相符，回到default_alloc_pages(size_t n)、default_free_pages(struct Page *base, size_t n)函数中可以分析得到，在分配函数和释放函数中都出现错误： list_add(&free_list, &(p->page_link)); 分配函数中若分得的块大小大于申请页数，则需要将多余的页形成一个块，按照从低地址到高地址的顺序挂回free_list中，而不是直接挂到free_list的后面。 list_add(&free_list, &(base->page_link)); 将释放页与空闲页合并操作之后，只是将新的空闲区域挂到了free_list的后面，并没有按照从低地址到高地址的顺序将其挂到free_list之中，导致后面check 函数中出现错误。对源代码做如下修改（红色为修改部分）： static struct Page * default_alloc_pages(size_t n) { assert(n > 0); //出错判断 if (n > nr_free) { //申请页大小与现有空闲页比较 return NULL; } struct Page *page = NULL; list_entry_t *le = &free_list; while ((le = list_next(le)) != &free_list) { //从free_list的头开始寻找符合条件的空闲块 struct Page *p = le2page(le, page_link); if (p->property >= n) { page = p; break; } } if (page != NULL) {

清华大学操作系统lab3实验报告

实验3：虚拟内存管理 练习1：给未被映射的地址映射上物理页 ptep=get_pet(mm->dir,addr,1); if(ptep == NULL){ //页表项不存在 cprintf("get_pte in do_pgfault failed\n"); goto failed; } if (*ptep == 0) { //物理页不在内存之中 //判断是否可以分配新页 if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) { cprintf("pgdir_alloc_page in do_pgfault failed\n"); goto failed; } } else{ if(swap_init_ok) { struct Page *page=NULL; ret = swap_in(mm, addr, &page); if(ret != 0){ //判断页面可否换入 cprintf("swap_in in do_pgfault failed\n"); goto failed; } //建立映射 page_insert(mm->pgdir, page, addr, perm); swap_map_swappable(mm, addr, page, 1); } else { cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep); goto failed; } } ret = 0; failed: return ret; } 练习2：补充完成基于FIFO算法 _fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in){ list_entry_t *head=(list_entry_t*) mm->sm_priv; list_entry_t *entry=&(page->pra_page_link); assert(entry != NULL && head!=NULL);