操作系统分析及实践实验指导书..docx

操作系统分析及实践实验指导书郭玲玲高俊涛佟喜峰苏冬娜目录实验1：LINUX的FORK、EXEC、WAIT代码的分析.1实验2：进程管理.16实验3：进程调度.21实验4：银行家算法.28实验5：虚拟存储器管理.33实验6：设备管理.38实验7：SPOOLING技术.43实验8：文件系统.47实验9：操作系统接口.68附录1：如何在C语言中读写数据文件.74附录2：如何在VISUALSTUDIO6.0环境下创建和调试C+程序.78实验1：Linux的fork、exec、wait代码的分析实验目的通过对Linux的fork、exec、wait代码的分析,了解一个操作系统进程的创建、执行、等待、退出的过程,锻炼学生分析大型软件代码的能力。实验要求1认真阅读实验指导书中源代码；2提高对操作系统中功能函数的认识。实验内容认真阅读Linux的fork、exec、wait代码，分析操作系统对进程创建、执行和等待的实现过程。实验准备1.fork：系统调用是UNIX中产生进程的唯一途径。通过复制父进程的虚拟内存来产生新的进程。2.exec：本函数调用一个新进程来覆盖掉当前进程映像。当一个程序想要调用另一个程序时，它通常先调用fork产生一个新进程，然后这个新进程再调用exec来运行新的程序(即通常由子进程来调用exec),然后父进程通过调用一个wait函数等待子进程退出。3.wait：父进程通过调用一个wait函数等待子进程退出。具体代码内容以及相关说明一、数据结构1structtask_struct进程的内核数据结构是task_struct结构，它使用两个指针next_task和prev_task将各个进程连成一个循环双链表，相应的指针p_opptr、p_pptr、p_cptr、p_ysptr和p_osptr来表示进程之间的家族关系。structtask_struct/进程描述符。longstate;/任务的运行状态（-1不可运行，0可运行(就绪)，0已停止）。longcounter;/任务运行时间计数(递减)（滴答数），运行时间片。longpriority;/运行优先数。任务开始运行时counter=priority，越大运行越1长。longsignal;/信号是位图，每个比特位代表一种信号，信号值=位偏移值+1。structsigactionsigaction32;/信号执行属性结构，对应信号将要执行的操作和标志信息。longblocked;/进程信号屏蔽码（对应信号位图）。intexit_code;/任务执行停止的退出码，其父进程会取。unsignedlongstart_code;/代码段地址。unsignedlongend_code;/代码长度（字节数）。unsignedlongend_data;/代码长度+数据长度（字节数）。unsignedlongbrk;/总长度（字节数）。unsignedlongstart_stack;/堆栈段地址。longpid;/进程标识号(进程号)。longfather;/父进程号。longpgrp;/父进程组号。longsession;/会话号。longleader;/会话首领。unsignedshortuid;/用户标识号（用户id）。unsignedshorteuid;/有效用户id。unsignedshortsuid;/保存的用户id。unsignedshortgid;/组标识号（组id）。unsignedshortegid;/有效组id。unsignedshortsgid;/保存的组id。longalarm;/报警定时值（滴答数）。longutime;/用户态运行时间（滴答数）。longstime;/系统态运行时间（滴答数）。longcutime;/子进程用户态运行时间。longcstime;/子进程系统态运行时间。longstart_time;/进程开始运行时刻。unsignedshortused_math;/标志：是否使用了协处理器。inttty;/进程使用tty的子设备号。-1表示没有使用。unsignedshortumask;/文件创建属性屏蔽位。structm_inode*pwd;/当前工作目录i节点结构。structm_inode*root;/根目录i节点结构。structm_inode*executable;/执行文件i节点结构。unsignedlongclose_on_exec;/执行时关闭文件句柄位图标志。（参见include/fcntl.h）structfile*filpNR_OPEN;/进程使用的文件表结构。structdesc_structldt3;/本任务的局部表描述符。0-空，1-代码段cs，2-数据和堆栈段ds&ss。structtss_structtss;/本进程的任务状态段信息结构。2;2tasktask定义为指向structtask_struct结构的指针数组，这个数组的每个项代表系统中的一个任务。数组的大小是NR_TASKS，它规定了系统中同时可以运行的任务的数量。externstructtask_struct*taskNR_TASKS;3tarray_freelist自由时间片列表tarray_freelist拥有一个说明task数组中自由位置的列表，即当前没有被使用的空位置。structtask_struct*tarray_freelist;4struct-linux_binprm内核中为可执行程序的装入定义了一个数据结构linux_binprm，以便将运行一个可执行文件时所需的信息组织在一起。/usr/src/linux/include/linux/binfmts.hstructlinux_binprmcharbufBINPRM_BUF_SIZE;structpage*pageMAX_ARG_PAGES;structmm_struct*mm;unsignedlongp;/*currenttopofmem*/intsh_bang;structfile*file;inte_uid,e_gid;kernel_cap_tcap_inheritable,cap_permitted,cap_effective;void*security;intargc,envc;char*filename;/*Nameofbinaryasseenbyprocps*/char*interp;/*Nameofthebinaryreallyexecuted.Mostofthetimesameasfilename,butcouldbedifferentforbinfmt_misc,script*/unsignedinterp_flags;unsignedinterp_data;unsignedlongloader,exec;#ifdef_KERNEL_#defineMAX_ARG_PAGES32linux_binprm-page每个参数的最大长度为一个物理页面，所以linux_binprm中有个页面指针数组，数组的大小为允许的最大参数个数MAX_ARG_PAGES，目前这个常数定义为32。5进程状态TASK_RUNNING：运行状态；TASK_INTERRUPTIBLE：等待状态可以让其他进程唤醒；TASK_UNINTERRUPTIBLE：等待状态但不让其他进程唤醒；TASK_ZOMBIE：进程已经结束执行但尚未消亡；TASK_STOPPED：进程暂停用其他进程的信号才能唤醒；3TASK_SWAPPING：被换出的进程。二、常量和出错信息的意义#defineNR_TASKS64/系统中同时最多任务（进程）数。#defineHZ100/定义系统时钟滴答频率(1百赫兹，每个滴答10ms)#defineFIRST_TASKtask0/任务0比较特殊，所以特意给它单独定义一个符号。#defineLAST_TASKtaskNR_TASKS-1/任务数组中的最后一项任务。#defineTASK_RUNNING0/进程正在运行或已准备就绪。#defineTASK_INTERRUPTIBLE1/进程处于可中断等待状态。#defineTASK_UNINTERRUPTIBLE2/进程处于不可中断等待状态，主要用于I/O操作等待。#defineTASK_ZOMBIE3/进程处于僵死状态，已经停止运行，但父进程还没发信号。#defineTASK_STOPPED4/进程已停止。三、各模块/函数的功能及详细框图1do_fork模块当进程调用fork时，该进程从概念上被分成两部分祖先和子孙可以自由选择不同的路径。在fork之后，祖先进程和其子进程几乎是等同的，它们所有的变量都有相同的值，它们打开的文件都相同，等等。但是如果祖先进程改变了一个变量的值，子进程看不到这个变化，反之亦然，子进程是祖先进程的一个拷贝，但它们并不共享内存内容。linux保留了传统的fork并增加了一个更加通用的函数_clone。鉴于fork创建一个新进程的子孙进程后。子孙进程虽然是祖先进程的拷贝，但是它们并不共享内容，_clone允许你定义祖先进程和子进程所应该共享的内容，如果你没有给_clone提供它所能识别的五个标志，子孙进程和祖先进程就不会共享任何内容，这就和传统fork类似。如果你提供了全部的五个标志，子孙进程就可以和祖先进程共享任何内容，这就和传统的线程类似，其他标记的不同组合可以使你完成介于两者之间的功能。分配新的进程控制块并给新的进程控制块赋值给新进程一个PID设置进程之间的家族信息把新进程放到Pidhash表中把进程设置为TASK_RUNNING状态4图1do_fork函数流程图longdo_fork(unsignedlongclone_flags,unsignedlongstack_start,structpt_regs*regs,unsignedlongstack_size,int_user*parent_tidptr,int_user*child_tidptr)structtask_struct*p;inttrace=0;longnr;if(unlikely(clone_flags&CLONE_STOPPED)staticint_read_mostlycount=100;/*如果在clone_flags中设置了CLONE_PID标志，就返回一个错误(EPERM)。*因为CLONE_PID有特殊的作用，当这个标志为1时，父，子进程(线程)共用一个进程号*即子进程虽然有自己的task_struct结构，却使用父进程的pid.*但是只有0号进程(即系统中的空线程)才允许使用这个标志。*/if(count0&printk_ratelimit()charcommTASK_COMM_LEN;count-;printk(KERN_INFOfork():process%suseddeprecatedcloneflags0x%lxn,get_task_comm(comm,current),clone_flags&CLONE_STOPPED);/*Whencalledfromkernel_thread,dontdousertracingstuff.*/if(likely(user_mode(regs)trace=tracehook_prepare_clone(clone_flags);p=copy_process(clone_flags,stack_start,regs,stack_size,child_tidptr,NULL,trace);/*copy_process()函数申请PCB空间，并赋值*/if(!IS_ERR(p)structcompletionvfork;nr=task_pid_vnr(p);if(clone_flags&CLONE_PARENT_SETTID)put_user(nr,parent_tidptr);5if(clone_flags&CLONE_VFORK)p-vfork_done=&vfork;init_completion(&vfork);tracehook_report_clone(trace,regs,clone_flags,nr,p);/*根据该文件中别处定义的辅助函数，根据所提供的clone_flags参数的值为子孙进程建立祖先进程的数据结构中子孙进程部分的拷贝。如果clone_flags指明相关的部分应该是共享而不是拷贝，这是辅助函数就简单地增加引用计数接着返回；否则，它就创建新进程所独有的新拷贝。*/p-flags&=PF_STARTING;if(unlikely(clone_flags&CLONE_STOPPED)/*WellstartupwithanimmediateSIGSTOP.*/sigaddset(&p-pending.signal,SIGSTOP);set_tsk_thread_flag(p,TIF_SIGPENDING);_set_task_state(p,TASK_STOPPED);elsewake_up_new_task(p,clone_flags);tracehook_report_clone_complete(trace,regs,clone_flags,nr,p);if(clone_flags&CLONE_VFORK)freezer_do_not_count();wait_for_completion(&vfork);freezer_count();tracehook_report_vfork_done(p,nr);elsenr=PTR_ERR(p);returnnr;2get_pid模块PID是使用get_pid函数生成的，该函数能够返回一个没有使用的PID。它从last_pid开始这是最近分配的PID。内核中使用的get_pid的版本是内核复杂性和速度频繁折中的一个例子：这里速度更为重要一些。get_Pid经过了高度优化它比直接向前的实现方法要复杂得多，但是速度也要快得多。最直接的实现方法将遍历执行整个任务列表典型的情况可能有几十项，有时候也可能成百上千项对每一个可能的PID进程检测并找出适当的值。但是在人多数情况下都可以跳过。如果所需要的只是要为每一个运行进程都快速计算一个各不相同的整数，那么这里已经有现实可用的方法：只要取在task数组中进程的索引就可以了。这肯6定要比现在的get_Pid速度要快。毕竟，这无须遍历任务列表。但是，很多现存的应用程序都假定在一个PID可以再重用之前都需要等待一段时间。这种假定在任何情况下都是不安全的，但是，如果为了这些程序的问题而将内核牵涉进去可能仍然是不好的。现存的PID分配策略速度仍然很快，并且它偶尔还有可以暴露这些应用程序中的潜在的缺陷。staticintget_pid(unsignedlongflags)staticintnext_safe=PID_MAX;/静态next_safe,初始时让它等于最大的pid值。/*next_safe变量是一个为加快系统运行速度而设定的变量；它保持记录了可能保留的次最低的候选PID。当last_pid递增并超过这个范围时，系统应该检测整个任务列表来保证这个候选PID是否仍在被保留若（原来保留这个PID的进程现在可能已经运行完了）。由于遍历这个任务列表可能会很慢，所以只要可能就应该避免执行这样的操作。因此，在执行这个遍历的过程中，get_Pid要重新计算next_safe如果有些进程已经死掉了，这个数字可能现在更大了，因此get_pid可以避免一些将来对任务列表的遍历(next_safe是静态的，因此其值在下次get_Pid需要分配PID时就会保留下来）。如果新的进程要和其祖先共享PID，就返回祖先进程的PID。*/structtask_struct*p;intpid;if(flags&CLONE_PID)returncurrent-pid;spin_lock(&lastpid_lock);/*开始搜寻候选PID寻找未使用的值。位与运算只是通过测试低15位是否置位来简单测试last_pid的新值是否超过了32767（最大允许的PID）。*/if(+last_pid)&0xffff8000)last_pid=300;/*Skipdaemonsetc.*/gotoinside;/显然，大于了8000，就不需要判断last_pid=next_safe了。if(last_pid=next_safe)/当准备分配的last_pid大于了next_safe，那么这个值就unsafe了。inside:next_safe=PID_MAX;/先把next_safe拉到最后，然后再一步一步的寻找最佳位置。read_lock(&tasklist_lock);repeat:for_each_task(p)if(p-pid=last_pid|p-pgrp=last_pid|p-tgid=last_pid|p-session=last_pid)if(+last_pid=next_safe)if(last_pid&0xffff8000)/next_safe值不总是PID_MAX7last_pid=300;next_safe=PID_MAX;gotorepeat;if(p-pidlast_pid&next_safep-pid)next_safe=p-pid;if(p-pgrplast_pid&next_safep-pgrp)next_safe=p-pgrp;if(p-sessionlast_pid&next_safep-session)next_safe=p-session;/这是为了找到last_pid,到next_safe的最好空间。read_unlock(&tasklist_lock);pid=last_pid;spin_unlock(&lastpid_lock);returnpid;3do_execve模块图2do_execve函数流程图如果能够进行的所有工作只是fork（或者_clone)，那么就一次次建立同一个进程的拷贝就可以了这样Linux系统就只能运行在系统中第一个创建的用户进程init了。init是很有用的，但是功能还没有如此强大；还需要处理其他事情。在创建新的进程以后，它通过调用exec就能够变成独立于其他进程的进程了。因此创建一个“真正”的新进程与其祖先不同的程序运行镜像任务分为两步，一步是fork，另一步是exec。do_execve处理三种工作：8（1）把一些定义信息从文件读入内存。（2）准备新的参数和环境这是C应用程序将它作为argc、argv和cnvp使用的内容。（3）装载可以解析可执行文件的二进制处理程序，并让它处理剩余的修改内核数据的工作。intdo_execve(/准备新的参数和环境char*filename,char_user*_user*argv,char_user*_user*envp,structpt_regs*regs)structlinux_binprm*bprm;/建立structlinux_binprmstructfile*file;structfiles_struct*displaced;intretval;retval=unshare_files(&displaced);if(retval)gotoout_ret;retval=-ENOMEM;bprm=kzalloc(sizeof(*bprm),GFP_KERNEL);if(!bprm)gotoout_files;file=open_exec(filename);retval=PTR_ERR(file);if(IS_ERR(file)/判断可执行文件是否存在gotoout_kfree;sched_exec();bprm-file=file;bprm-filename=filename;bprm-interp=filename;retval=bprm_mm_init(bprm);if(retval)gotoout_file;bprm-argc=count(argv,MAX_ARG_STRINGS);if(retval=bprm-argc)envc=count(envp,MAX_ARG_STRINGS);if(retval=bprm-envc)0)gotoout_mm;retval=security_bprm_alloc(bprm);9if(retval)gotoout;retval=prepare_binprm(bprm);if(retvalfilename,bprm);/用copy_strings来把参数和环境变量拷贝到次年进程if(retvalexec=bprm-p;retval=copy_strings(bprm-envc,envp,bprm);if(retvalargc,argv,bprm);if(retvalflags&=PF_KTHREAD;retval=search_binary_handler(bprm,regs);/用search_binary_hander来找到要执行的二进制处理程序if(retval=0)/*execvesuccess*/security_bprm_free(bprm);acct_update_integrals(current);free_bprm(bprm);if(displaced)put_files_struct(displaced);returnretval;out:if(bprm-security)/判断bprm是否安全security_bprm_free(bprm);/如果安全则释放它out_mm:if(bprm-mm)mmput(bprm-mm);out_file:if(bprm-file)allow_write_access(bprm-file);/如果该文件有写权限则访问fput(bprm-file);10out_kfree:free_bprm(bprm);out_files:if(displaced)reset_files_struct(displaced);out_ret:returnretval;4do_exit模块exit用来让进程结束它在内核中是通过sys_exit实际是采用do_exit实现的当进程退出的时候内和会释放所有相关资源内存文件等等并停止给它CPU的机会但是这个时候进程并没有结束需要保留进程的task_struct结构等待它的父进程调用wait来查询子孙进程的退出状态所以内和必须保留子孙进程的PID直到wait发生为止这个时候的进程是僵进程。图3do_exit函数流程图NORET_TYPEvoiddo_exit(longcode)/设置退出代码函数的参数structtask_struct*tsk=current;intgroup_dead;profile_task_exit(tsk);WARN_ON(atomic_read(&tsk-fs_excl);if(unlikely(in_interrupt()panic(Aiee,killinginterrupthandler!);if(unlikely(!tsk-pid)panic(Attemptedtokilltheidletask!);tracehook_report_exit(&code);/让进程进入TASK_ZOMBIE状态，并记录它11的退出代码if(unlikely(tsk-flags&PF_EXITING)printk(KERN_ALERTFixingrecursivefaultbutrebootisneeded!n);tsk-flags|=PF_EXITPIDONE;if(tsk-io_context)exit_io_context();set_current_state(TASK_UNINTERRUPTIBLE);schedule();exit_signals(tsk);/设置PF_EXITINGsmp_mb();spin_unlock_wait(&tsk-pi_lock);if(unlikely(in_atomic()printk(KERN_INFOnote:%s%dexitedwithpreempt_count%dn,current-comm,task_pid_nr(current),preempt_count();acct_update_integrals(tsk);if(tsk-mm)update_hiwater_rss(tsk-mm);update_hiwater_vm(tsk-mm);group_dead=atomic_dec_and_test(&tsk-signal-live);if(group_dead)hrtimer_cancel(&tsk-signal-real_timer);exit_itimers(tsk-signal);acct_collect(code,group_dead);#ifdefCONFIG_FUTEX/定义CONFIG_FUTEXif(unlikely(tsk-robust_list)exit_robust_list(tsk);#ifdefCONFIG_COMPAT/定义CONFIG_COMPATif(unlikely(tsk-compat_robust_list)compat_exit_robust_list(tsk);#endif#endifif(group_dead)tty_audit_exit();if(unlikely(tsk-audit_context)audit_free(tsk);tsk-exit_code=code;taskstats_exit(tsk,group_dead);exit_mm(tsk);12if(group_dead)acct_process();exit_sem(tsk);exit_files(tsk);/结束文件任务exit_fs(tsk);check_stack_usage();/检查堆栈使用情况exit_thread();cgroup_exit(tsk,1);exit_keys(tsk);if(group_dead&tsk-signal-leader)disassociate_ctty(1);module_put(task_thread_info(tsk)-exec_domain-module);if(tsk-binfmt)module_put(tsk-binfmt-module);proc_exit_connector(tsk);exit_notify(tsk,group_dead);/调用exit_notify告知它的祖先进程这个进程已经退出#ifdefCONFIG_NUMAmpol_put(tsk-mempolicy);tsk-mempolicy=NULL;#endif#ifdefCONFIG_FUTEXif(unlikely(!list_empty(&tsk-pi_state_list)exit_pi_state_list(tsk);if(unlikely(current-pi_state_cache)kfree(current-pi_state_cache);#endifdebug_check_no_locks_held(tsk);tsk-flags|=PF_EXITPIDONE;if(tsk-io_context)exit_io_context();if(tsk-splice_pipe)_free_pipe_info(tsk-splice_pipe);preempt_disable();/*causesfinalput_task_structinfinish_task_switch().*/tsk-state=TASK_DEAD;schedule();/调用Shedule释放CPUBUG();/*Avoidnoreturnfunctiondoesreturn.*/for(;)cpu_relax();/*ForwhenBUGisnull*/5sys_wait4模块和exec一样，wait是一组函数，而不是一个函数。wait家族中的其他函数最终都是使用一个系统调用sys_wait4实现的，这个系统调用的名字反映出它实现了wait家族中最通用的函数wait4。标准c库libc的实现必须重新组织对于其他wait13函数调用的参数，并调用sys_waitpid。除了处理一些其他内容，sys_wait4也只有sys_wait4最终把僵进程消除。然而从应用程序的观点来看，wait和相关函数要检测子孙进程的状态，检测是否有进程死亡了，如果有，到底是哪一个进程，这个进程是怎么死亡的。图4sys_wait4函数流程图asmlinkagelongsys_wait4(pid_tupid,int_user*stat_addr,intoptions,structrusage_user*ru)/设置参数，结构变量structpid*pid=NULL;enumpid_typetype;longret;if(options&(WNOHANG|WUNTRACED|WCONTINUED|_WNOTHREAD|_WCLONE|_WALL)return-EINVAL;/检查wait4的参数是否有效，无效则包错，有效继续执行if(upid=-1)type=PIDTYPE_MAX;/找到直接子进程，找到参数与PID相匹配的进程并更新子孙进程使用的时间和系统信息elseif(upid0*/type=PIDTYPE_PID;pid=find_get_pid(upid);ret=do_wait(type,pid,options|WEXITED,NULL,stat_addr,ru);14put_pid(pid);/*avoidREGPARMbreakageonx86:*/asmlinkage_protect(4,ret,upid,stat_addr,options,ru);returnret;/释放子孙进程PCB实验报告要求1.阐述实验目的和实验内容；2.提交模块化的实验程序源代码；3.简述程序的测试过程，提交实录的输入、输出界面；4.鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。思考与练习如果可以的话，尽量多找一些其他操作系统函数源代码或者是不同版本相同函数的源代码进行阅读并理解。15实验2：进程管理实验目的1.理解进程的概念，明确进程和程序的区别。2.理解并发执行的实质。3.掌握进程的创建、睡眠、撤销等进程控制方法。实验要求1认真阅读实验指导书，设计出进程管理涉及到的相应算法；2根据设计的算法写出程序；3在运行环境中测试程序，并保证顺利执行。实验内容用C语言编写程序，模拟实现创建新的进程；查看运行进程；换出某个进程；杀死运行进程等功能。实验准备1.进程的概念2.进程的状态3.进程状态之间的转换4.进程控制块5.进程的创建与撤销6.进程的阻塞与唤醒算法演示#include#include#includestructjincheng_typeintpid;intyouxian;intdaxiao;intzhuangtai;/标志进程状态，0为不在内存，1为在内存，3为挂起charinfo10;structjincheng_typeneicun20;16intshumu=0,guaqi=0,pid,flag=0;voidcreate()if(shumu=20)printf(n内存已满，请先换出或杀死进程n);elsefor(inti=0;i20;i+)/定位，找到可以还未创建的进程if(neicuni.zhuangtai=0)break;printf(n请输入新进程pidn);scanf(%d,&(neicuni.pid);for(intj=0;ji;j+)if(neicuni.pid=neicunj.pid)printf(n该进程已存在n);return;printf(n请输入新进程优先级n);scanf(%d,&(neicuni.youxian);printf(n请输入新进程大小n);scanf(%d,&(neicuni.daxiao);p