清华初试912os习题12013midexam

1、本科生 试题 纸课程：操作系统（ A 卷） 时间：2013 年 04 月 10 日上午 9:5011:50系别： 班级： 学号：答卷注意事项:1.在开始答题前，请在试题纸和答卷本上写明系别、班级、学号和。2.在答卷本上答题时, 要写明题号, 不必抄题。3.答题时, 要书写清楚和整洁。4.请注意回答所有试题。本试卷有 7 个题目，共 16 页。5.完毕, 必须将试题纸和答卷本一起交回。一、（12 分）1）试说明硬中断（hardware的相同点和不同点。errupt）、异常（exception）和系统调用（system call）2）下面代码完成在进入 trap()函数前的准备工作。其中 push

2、al 完成包括 esp 在内的 CPU 寄存器压栈。试说明“pushl %esp”的作用是什么？=trntry.S (kerntrap)=#include # vectors.S sends all traps here.text.globl alltraps alltraps:# push registers to build a trap frame# therefore make the stack look like a struct trapframe pushl %dspushl %es pushl %fs pushl %gspushal# load GD_KDATAo %ds a

3、nd %es to set up data segments for kernelmovl $GD_KDATA, %eax movw %ax, %dsmovw %ax, %es pushl %esp call trap# pop the pushed stack popopl %esper# return falls through to trapret.globl trapret第 1 页/共 16 页 trapret:# restore registers from stack popal# restore %ds, %es, %fs and %gs popl %gspopl %fspop

4、l %es popl %ds# get rid of the trap number and error code addl $0 x8, %espiret=Trap.c (kerntrap)=/* * trap - handles or dispatches an exception/errupt. if and when trap() returns,* the code in kern/trap/trntry.S restores the old CPU se savedhe* trapframe and then uses the iret instruction to return

5、from the exception.* */ voidtrap(struct trapframe *tf) / dispatch based on what type of trap occurred trap_dispatch(tf);二、（13 分）1）系统调用的参数传递有几种方式？各特点？2）sys_exec 是一个加载和执行指定可执行文件的系统调用。请说明在下面的 ucore 实现中，它的三个参数分别是以什么方式传递的。=Proc.c (kernpros)=/ do_execve - call exit_mmap(mm)&pug_pgdir(mm) to reclaim memory

6、 space of current pros/- call load_icode to setup new memory space accroding binary prog.do_execve(const char *name,argc, const char *argv) sic_assert(EXEC_MAX_ARG_LEN = FS_MAX_FPATH_LEN);struct mm_struct *mm = current-mm;if (!(argc = 1 & argc = EXEC_MAX_ARG_NUM) return -E_INVAL;char local_namePROC_

7、NAME_LEN + 1;memset(local_name, 0, sizeof(local_name);第 2 页/共 16 页char *kargvEXEC_MAX_ARG_NUM;const char *path;ret = -E_INVAL;lock_mm(mm);if (name = NULL) snprf(local_name, sizeof(local_name), %d, current-);else if (!copy_string(mm, local_name, name, sizeof(local_name) unlock_mm(mm);return ret;if (r

8、et = copy_kargv(mm, argc, kargv, argv) != 0) unlock_mm(mm);return ret;path = argv0; unlock_mm(mm);files_closeall(current-filesp);/* sysfile_open will check the argv0 may be incorrect */fd;argument path, thus we have to use a user-space poer, andif (ret = fd = sysfile_open(path, O_RDONLY) mm = NULL;r

9、et= -E_NO_MEM;if (ret = load_icode(fd, argc, kargv) != 0) goto execve_exit;put_kargv(argc, kargv); set_proc_name(current, local_name); return 0;第 3 页/共 16 页execve_exit: put_kargv(argc, kargv); do_exit(ret);panic(already exit: %e.n, ret);=Syscall.c (kernsyscall)=sicsys_exec(u32_t arg) const char *nam

10、e = (const char *)arg0;argc = ()arg1;const char *argv = (const char *)arg2;return do_execve(name, argc, argv);sic(*syscalls)(u32_t arg) = SYS_exit SYS_fork SYS_wait SYS_exec SYS_yield SYS_killSYS_getsys_exit, sys_fork, sys_wait, sys_exec, sys_yield, sys_kill,sys_get,SYS_psys_p,SYS_pgdirsys_pgdir,;#d

11、efine NUM_SYSCALLS(sizeof(syscalls) / (sizeof(syscalls0)void syscall(void) struct trapframe *tf = current-tf; u32_t arg5;num = tf-tf_regs.reg_eax;if (num = 0 & num tf_regs.reg_edx; arg1 = tf-tf_regs.reg_ecx; arg2 = tf-tf_regs.reg_ebx; arg3 = tf-tf_regs.reg_edi; arg4 = tf-tf_regs.reg_esi;tf-tf_regs.r

12、eg_eax = syscallsnum(arg); return ;第 4 页/共 16 页pr_trapframe(tf);panic(undefined syscall %d,= %d, name = %s.n,num, current-, current-name);=libs-user-ucore/syscall.c=sys_exec(const char *filename, const char *argv, const char *envp)return syscall(SYS_exec, filename, argv, envp);=libs-user-ucore/arch/

13、i386/syscall.c=u32_t syscall(num, .)va_list ap;va_start(ap, num);u32_t aMAX_ARGS;i;for (i = 0; i MAX_ARGS; i+) ai = va_arg(ap, u32_t);va_end(ap);u32_t ret;asm volatile (%1;:=a (ret):i(T_SYSCALL),a(num),d(a0), c(a1), b(a2), D(a3), S(a4):cc, memory); return ret;三、（15 分）1）描述伙伴系统（Buddy System）中对物理内存的分配和

14、回收过程。2）假定一个操作系统内核中由伙伴系统管理的物理内存有 1MB，试描述按下面顺序进行物理内存分配和回收过程中，每次分配完成后的分配区域的首地址和大小，或每次回收完成后的空闲区域队列（要求说明，每个空闲块的首地址和大小）。建议给出分配和回收的中间过程。a)b)c)d)进程 A 申请50KB；进程 B 申请100KB；进程 C 申请40KB；进程 D 申请70KB；第 5 页/共 16 页$ % & ( ) :h &$ _hM;H fQK / &$ 0$,.4$ /2$ m; / &$ 0$,.4$ /2$ mfF;c *$0- , /, L / &$ 0$,.4$ /2$ m; / &$

15、 0$,.4$ /2$ mf=Pmm . h ( k e r n mm) =#define alloc_page() alloc_pages(1)#define free_page(page) free_pages(page, 1)sic inline struct Page *pte2page(pte_t pte) if (!(pte & PTE_P) panic(pte2page called with invalid pte);return pa2page(PTE_ADDR(pte);sic inlinepage_ref_inc(struct Page *page) ref += 1;r

16、eturn ref;sic inlinepage_ref_dec(struct Page *page) ref -= 1;return ref; 6 /e 16 =Pmm.c (kernmm)=/page_remove_pte - free an Page sturct which is related linear address la/- and clean(invalidate) pte which is related linear address la/note: PT is changed, so the TLB need to be invalidatesic inline vo

17、idpage_remove_pte(pde_t *pgdir, uptr_t la, pte_t *ptep) /* LAB2 EXERCISE 3: YOUR CODE* free.* being*Please check if pts valid, and tlb must be manually updated if mapis updatedMaybe you want help comment, BELOW comments can help you finish the codeSome Useful MACROs and DEFINEs, you can use them in

18、below implemenion. MACROs or Functions:struct Page *page pte2page(*ptep): get the according page from the value of a ptep free_page : free a pagepage_ref_dec(page) : decrease ref. NOTICE: ff ref = 0 , then this page should betlb_invalidate(pde_t *pgdir, uptr_t la) : InvalidateB entry, but only if th

19、e page tablesedited are the ones currently in use by the prosor.DEFINEs:PTE_P0 x001/ page table/directory entry flags bit : Present*/#if 0if (0) /(1) check if page directory is presentstruct Page *page = NULL; /(2) find corresponding page to pte/(3) decrease page reference/(4) and free this page whe

20、n page reference reachs 0/(5) clear second page table entry/(6) flush tlb#endif=Your code 1=/ invalidateB entry, but only if the page tables being/ edited are the ones currently in use by the provoidsor.tlb_invalidate(pde_t *pgdir, u if (rcr3() = PADDR(pgdir) invlpg(void *)la);ptr_t la) sic void第 7

21、页/共 16 页check_alloc_page(void) pmm_manager-check();cprf(check_alloc_page() succeeded!n);=Mmu.h (kernmm)=/* page #define #define #define #define #define #define #define #define #define#definetable/directory entry flags */PTE_P PTE_W PTE_U PTE_PWT PTE_PCD PTE_A PTE_D PTE_PS PTE_MBZPTE_AVAIL0 x0010 x00

22、20 x0040 x0080 x0100 x0200 x0400 x0800 x1800 xE00/ Present/ Writeable/ User/ Write-Through/ Cache-Disable/ Acsed/ Dirty/ Page Size/ Bits must be zero/ Available for software use/ The PTE_AVAIL bits arent used by the kernel orretedby the/ hardware, so usroses are allowed to set themarbitrarily.#defin

23、e PTE_USER(PTE_U | PTE_W |PTE_P)五、（20 分）1）试用图示描述 32 位 X86 系统在采用 4KB 页面大小时的虚拟地址结构和地址置换过程。2）在采用 4KB 页面大小的 32 位 X86 的 ucore 虚拟确定。系统中，进程页面的起始地址由宏 VPT0 x0D000000#define VPT请计算：2a)试给出页目录中自和页表项的虚拟地址。页表项的虚拟地址；2b)虚拟地址 0X87654321 对应的页目录项六、（15 分）试描述 FIFO 页面替换算法的基本原理，并 swap_fifo.c 中未完成 FIFA 页面替换算法实验函数 map_swapp

24、able()和 swap_out_vistim() 。=Defs.h (libs)=/* * to_struct - get the struct from a ptr* ptr:a struct poer of member* type:the type of the struct this is embedded in* member: the name of the member with* */#define to_struct(ptr, type, member)he struct(type *)(char *)(ptr) - offsetof(type, member)第 8 页/

25、共 16 页=Memlayout.h (kernmm)=/ convert list entry to page#define le2page(le, member)to_struct(le), struct Page, member)=List.h (libs)=#ifndef LIBS_LIST_H #define LIBS_LIST_H #ifndef ASSEMBLER #include /* * Simple doubly linked list implemenion.* Some of theernal functions ( ) are useful when manipula

26、ting* whole lists rathern single entries, as sometimes we already know* the next/prev entries and we can generate better code by using them* directly rather* */n using teric single-entry routines.struct list_entry struct list_entry *prev, *next;typedef struct list_entry list_entry_t;ss sic inline vo

27、id list_init(list_entry_t *elm) attribute (always_inline);ic inline void list_add(list_entry_t *lism, list_entry_t *elm) attribute (always_inline);ic inline void list_add_before(list_entry_t *lism, list_entry_t *elm) attribute (always_inline);sic inline void list_add_after(list_entry_t *lism, list_e

28、ntry_t *elm) attribute (always_inline);s s s ssic inline void list_del(list_entry_t *lism) attribute (always_inline);ic inline void list_del_init(list_entry_t *lism) attribute (always_inline);ic inline bool list_empty(list_entry_t *list) attribute (always_inline);ic inline list_entry_t *list_next(li

29、st_entry_t *lisic inline list_entry_t *list_prev(list_entry_t *lism) attribute (always_inline);m) attribute (always_inline);sic inline void list_add(list_entry_t *elm, list_entry_t *prev, list_entry_t *next) attribute (always_inline);sic inline void list_del(list_entry_t *prev, list_entry_t *next) a

30、ttribute (always_inline);/* * list_init - initialize a new entry第 9 页/共 16 页* elm:* */new entry to be initializedsic inline voidlist_init(list_entry_t *elm) elm-prev = elm-next = elm;/* *list_add - add a new entrylism:list head to add after* elm:*new entry to be added* Insert the new element elm *af

31、ter* the element lism which* is already* */he list.sic inline voidlist_add(list_entry_t *lism, list_entry_t *elm) list_add_after(lism, elm);/* *list_add_before - add a new entrylism:list head to add before* elm:*new entry to be added* Insert the new element elm *before* the element lism which* is al

32、ready* */he list.sic inline voidlist_add_before(list_entry_t *lism, list_entry_t *elm) list_add(elm, lism-prev, lism);/* *list_add_after - add a new entrylism:list head to add after* elm:*new entry to be added* Insert the new element elm *after* the element lism which* is already* */he list.sic inli

33、ne voidlist_add_after(list_entry_t *lism, list_entry_t *elm) list_add(elm, lism, lism-next);第 10 页/共 16 页/* * list_del - deletes entry from list* lism:*the element tete from the listNote: list_empty() on lisin an undefined se.* */m does not return true after this, the entry issic inline voidlist_del

34、(list_entry_t *lism) list_del(lism-prev, lism-next);/* * list_del_init - deletes entry from list and reinitialize it.* lism:*the element tete from the list.* Note: list_empty() on lis* */m returns true after this.sic inline voidlist_del_init(list_entry_t *lislist_del(lism);m) list_init(lism);/* * li

35、st_empty - tests whether a list is empty* list:* */the list to test.sic inline boollist_empty(list_entry_t *list) return list-next = list;/* * list_next - get the next entry* lis*/m:the list headsic inline list_entry_t *list_next(list_entry_t *lism) return lism-next;/* * list_prev - get the previous

36、 entry* lis*/m:the list head第 11 页/共 16 页sic inline list_entry_t *list_prev(list_entry_t *lis return lism-prev;m) /* * Insert a new entry bet*n two known consecutive entries.* This is only forernal list manipulation where we know* the prev/next entries already!* */sic inline void list_add(list_entry

37、_t *elm, list_entry_t *prev, list_entry_t *next) prev-next = next-prev = elm;elm-next = next; elm-prev = prev;/* * Delete a list entry by making the prev/next entries po*to each other.* This is only forernal list manipulation where we know* the prev/next entries already!* */sic inline void list_del(

38、list_entry_t *prev, list_entry_t *next) prev-next = next;next-prev = prev;#endif /* ! ASSEMBLER */#endif /* ! LIBS_LIST_H */= Swap_fifo.c (kernmm)=#include #include #include #include #include #include #include /* wikipediaThe simplest Page Replacement Algorithm(PRA) is a FIFO algorithm.第 12 页/共 16 页

39、* (1) Prepare: In order to implement FIFO PRA, we should manage all swappable pages, so we can*/link these pageso pra_list_head according the time order. Atyou shouldbe familiar to the struct list in list.h. struct list is a simple doubly linked listimplemenion. You should know howto USE: list_init,

40、 list_add(list_add_after),list_add_before, list_del, list_next, list_prev. Another tricky method is to transforma general list struct to a spel struct (such as struct page). You can find some MACRO:le2page (emlayout.h), (in future labs: le2vma (in vmm.h), le2proc (in proc.h),etc.list_entry_t/*pra_li

41、st_head;* (2) _fifo_init_mm: init pra_list_head and let mm-sm_priv poto the addr of pra_list_head.*/ sNow, From the memory control struct mm_struct, we can acs FIFO PRAic_fifo_init_mm(struct mm_struct *mm)list_init(&pra_list_head); mm-sm_priv = &pra_list_head;/cprf( mm-sm_priv %x in fifo_init_mmn,mm

42、-sm_priv); return 0;/* (3)_fifo_map_swappable: According FIFO PRA, we should link the most recent arrival page at the back of pra_list_head qeueue*/sic_fifo_map_swappable(struct mm_struct *mm, uptr_t addr, struct Page *page,swap_in)list_entry_t *head=(list_entry_t*) mm-sm_priv;list_entry_t *entry=&(

43、pra_page_link);assert(entry != NULL & head != NULL);/record the page acs situlation/*LAB3 EXERCISE 2: YOUR CODE*/(1)link the most recent arrival page at the back of the pra_list_head qeueue.=Your code 2=return 0;/* (4)_fifo_swap_out_victim: According FIFO PRA, we should unlink the ear of pra_list_he

44、ad qeueue,st arrival page in front*/ sthen set the addr of addr of this page to ptr_page.ic_fifo_swap_out_victim(struct mm_struct *mm, struct Page * ptr_page,in_tick)第 13 页/共 16 页list_entry_t *head=(list_entry_t*) mm-sm_priv; assert(head != NULL);assert(in_tick=0);/* Select the victim */*LAB3 EXERCI

45、SE 2: YOUR CODE*/(1) unlink the earst arrival page in front of pra_list_head qeueue/(2) set the addr of addr of this page to ptr_page/* Select the tail */=Your code 3=return 0;sic_fifo_check_swap(void) cprf(write Virt Pagec=in fifo_check_swapn);0 x0c;*(unsigned char *)0 x3000assert(pgfault_num=4);cp

46、rf(write Virt Pagea=in fifo_check_swapn);0 x0a;*(unsigned char *)0 x1000assert(pgfault_num=4);cprf(write Virt Paged=in fifo_check_swapn);0 x0d;*(unsigned char *)0 x4000assert(pgfault_num=4);cprf(write Virt Pageb=in fifo_check_swapn);0 x0b;*(unsigned char *)0 x2000assert(pgfault_num=4);cprf(write Virt Pagee=in fifo_check_swapn);0 x0e;*(unsigne