第三次作业参考答案.docx

q 2.1 比较程序的顺序执行和并发执行。答：程序顺序执行程序并发执行顺序性：处理机的操作严格按照程序所规定的顺序执行间断性：共享系统资源，程序之间形成了相互制约的关系封闭性：程序一旦开始执行，执行结果不受外界因素影响失去封闭性：多个程序共享系统中的各种资源，这些资源的状态将由多个程序来改变，致使程序失去封闭性。可再现性：只要程序执行时的环境和初始条件相同，都将获得相同的结果。不可再现性：程序失去封闭性，计算结果与并发程序执行速度有关。程序经过多次执行后，虽然他们执行时的环境和初始条件相同，但是结果却不相同。 2.2 比较程序和进程。答：1）进程是一个动态的概念，而程序则是一个静态的概念。程序是指令的有序集合，没有任何执行含义，而进程则强调执行过程，它动态地被创建，并被调度执行后消亡。2）进程具有并行特征，而程序没有。进程具有并行特征的两个方面，即独立性和异步性。也就是说，在不考虑资源共享的情况下，各进程的执行是独立的，它们之间不存在逻辑上的制约关系，各进程的是异步的。由于程序不反映执行过程，所以不具有并行特征。3）进程是系统中独立存在的实体，是竞争资源的基本单位。进程对应特殊的描述结构并有申请、使用、释放资源的资格。由于系统中存在多个进程，系统资源的有限性必然导致多个进程对资源的共享和竞争，从而使进程的并行性受到系统的制约。4）进程的存在必然需要程序的存在，但进程和程序不是一一对应的。由于进程是程序的执行过程，所以程序是进程的一个组成部分。处于静止状态的程序并不对应于任何进程。当程序被处理机执行时，它一定属于某一个或者多个进程。属于进程的程序可以是一个，也可以是多个。不同的进程可以包含同一个程序，只要该程序所对应的数据集不同。q 2.3 试对进程的状态及状态转换进行总结，注意状态转换的物理含义及转化条件。答：处于就绪状态的进程 ，在调度程序为之分配了处理机之后，该进程便可执行，相应地，它就由就绪状态转变为运行状态。正在执行的进程也称为当前进程，如果分配给它的时间片已完而被暂停执行时，该进程便由执行状态又回复到就绪状态；如果因发生某事件而使进程的执行受阻，使之无法继续执行，该进程将由执行状态转变为阻塞状态。引入挂起状态后，又增加了从挂起状态到非挂起状态之间的转换，当进程处于未被挂起的就绪状态时，用挂起原语Suspend将该进程挂起后，该进程便转变成为静止就绪状态，此时进程不再被调度执行。当进程处于未被挂起的阻塞状态时，用Suspend原语将它挂起后，进程便转变为静止阻塞状态，处于该状态的进程在其所期待的事件出现后，将从静止阻塞状态变成静止就绪。处于活动就绪状态的进程，若用激活原语Active激活后，该进程将转变为挂起就绪状态。处于活动阻塞状态的进程，若用激活原语Active激活后，将转变为阻塞挂起状态。q 2.4 试举例说明引起进程创建、撤消、阻塞或被唤醒的主要事件分别有哪些？答：引起进程创建，如用户登录；作业调度；提供服务；应用请求。进程撤销，当一个进程到达了自然结束点，或时出现了无法克服的错误，或是被操作系统所中介，或是被其他有终止权的进程所终结，都会引起进程撤销。进程阻塞，请求系统服务,不能立即满足;启动某种操作,且必须在该操作完成之后才能继续执行;新数据尚未到达,相互合作进程的一方需首先获得另一进程数据才能继续;无新工作可做,特定功能系统进程当完成任务且暂无任务。进程被唤醒，系统服务满足;操作完成;数据到达;新任务出现。q 2.5 试根据你自己的理解，采用类C语言设计和描述操作系统关于进程控制块的数据结构、组织方式及管理机制。在此基础上，给出进程的创建、终止、阻塞、唤醒、挂起与激活等函数原型及函数代码。注意，对于过于复杂的功能或你无法解决的细节可采用指定功能的函数模块如处理机调度scheduler()来替代。答：进程控制块的数据结构：Struct task_struct long state; /*任务的运行状态（-1 不可运行，0 可运行(就绪)，0 已停止）*/long counter;/*运行时间片计数器(递减)*/long priority;/*优先级*/long signal;/*信号*/struct sigaction sigaction32;/*信号执行属性结构，对应信号将要执行的操作和标志信息*/long blocked; /* bitmap of masked signals */* various fields */int exit_code;/*任务执行停止的退出码*/unsigned long start_code,end_code,end_data,brk,start_stack; /*代码段地址 代码长度（字节数）代码长度 + 数据长度（字节数）总长度 堆栈段地址*/long pid,father,pgrp,session,leader;/*进程标识号(进程号) 父进程号 父进程组号 会话号 会话首领*/unsigned short uid,euid,suid;/*用户标识号（用户id） 有效用户id 保存的用户id*/unsigned short gid,egid,sgid; /*组标识号（组id） 有效组id 保存的组id*/long alarm;/*报警定时值*/long utime,stime,cutime,cstime,start_time;/*用户态运行时间 内核态运行时间 子进程用户态运行时间子进程内核态运行时间 进程开始运行时刻*/unsigned short used_math;/*标志：是否使用协处理器*/* file system info */int tty; /* -1 if no tty, so it must be signed */unsigned short umask;/*文件创建属性屏蔽位*/struct m_inode * pwd;/*当前工作目录i 节点结构*/struct m_inode * root;/*根目录i节点结构*/struct m_inode * executable;/*执行文件i节点结构*/unsigned long close_on_exec;/*执行时关闭文件句柄位图标志*/struct file * filpNR_OPEN;/*进程使用的文件表结构*/* ldt for this task 0 - zero 1 - cs 2 - ds&ss */struct desc_struct ldt3;/*本任务的局部描述符表。0-空，1-代码段cs，2-数据和堆栈段ds&ss*/* tss for this task */Struct tss_struct tss;/*本进程的任务状态段信息结构*/;组织方式：Typedef struct LNode ElemType data;/存储pcb块的数据信息struct Lnode *next; / 指针域LNode, * LinkList; （结构指针）链表查找方式：Status GetElem_L(LinkList L, int i, ElemType &e) /L是带头结点的链表的头指针，以 e 返回第 i 个元素p = L-next; j = 1; / p指向第一个结点，j为计数器while (p & jnext; +j; /顺指针向后查找，直到 p 指向第 i 个元素或 p 为空if ( !p | ji ) returnERROR; / 第 i 个元素不存在e = p-data; / 取得第 i 个元素return OK; / GetElem_L 算法复杂度为：O(ListLength(L)系统建立几张索引表。每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址。当指针查找索引表，找出PCB的地址，再通过指针找对应该地址的PCB块。平均查找长度：=(n/s+ s)/2+1 n为表的长度 s 为表中的记录个数进程管理机制：用户使用应用程序，应用程序要访问系统调用接口，产生中断，而系统调用接口需要查询中断向量表，cpu根据 中断向量号跳转到所需的服务中，即系统调用服务程序。系统服务程序会调用内核函数（create,terminate,block,wakeup,suspend,active）进程的创建与终止：创建：Bool fret=Bool CreateProcess(LPCTSTR lpApplivationName, /全部或部分地指明包括可执行代码的EXE文件的文件名LPCTSTR lpApplivationName, /向可执行文件发送的参数LPCTSTR lpApplivationName, / 返回进程句柄的安全属性.主要指明这一句柄是否应该由其他子进程所继承LPSECURIITY_ATTRIBUTES lpThreadAttributes, /返回进程的主线程的句柄的安全属性BOOL bInheritHandle, /一种标志，告诉系统允许新进程继承创建者进程的句柄DWORD dwCreationFlage, /特殊的创建标志 (如CREATE_SUSPENDED) 的位标记LPVOID lpEnvironment, / 向新进程发送的一套环境变量；如为null值则发送调用者环境LPCTSTR lpCurrentDirectory, /新进程的启动目录STARTUPINFO lpStartupInfo, /STARTUPINFO结构，包括新进程的输入和输出配置的详情LPPROCESS_INFORMATION lpProcessInformation / 调用的结果块；发送新应用程序的进程和主线程的句柄和ID);终止： If (m_hPro) /如果句柄合法 if(!TerminateProcess(m_hPro,0) /根据句柄，终止刚才创建的进程 AfxMessageBox(“关闭进程出现错误！”); Exit（0） else AfxMessageBox(TerminateProcess成功); 原语：被创建进程的外部标识符n、初始CPU状态S0，进程优先数K0、初始内存M0以及所需资源的清单R0等、某进程运行的中间结果acc。创建：从PCB集合种索取一个空白PCB，并获得该PCB的内部标识符i ;然后，把调用者提供的参数，以及从执行过程EP中获得的调用者内部标识j ，填入该PCB，设置记帐数据，置新进程为“静止就绪”状态；最后，把此PCB分别插入就绪队列RQ和进程家族中。Procedure Create(n,S0,k0,M0,R0,acc)begini:=get Internal Name(n);/获得内部名i.id:=n; /填外部名i.Priority:=k0; /填优先表i.cpu state:=S0; /填cpu初始状态i.mainstore:=M0; /填写主存区域i.resource:=R0; /填写资源清单i.status:=Readys; /填写进程状态j:=EP; /获取调用者内部标识i.Parent:=j; /填入i进程的父进程geny:=null; /i的家庭指针为空geny:=i; /把i填入其父进程pcb中的家庭指针处i.state:=RQ; /i所在状态队列首指针Insert(RQ,i); /把i进程插入RQ队尾continue;end终止：Procedure destroy(n)BeginSched:=false;i:=getinternal name(n);/获取n进程的内部名kill(i);if sched then scheduler else continue;/假如Schde为真，则转调度程序，否则继续endprocedure kill(i)beginif i.stata(i)=”executing” thenbegin stop(i);sched:=true end;remove (i.stata,i); /将被撤消进程从i.state所指示的队列中除去for all Sgeny do kill(s);for all r(i.main store i.resources) doif owned(r) then insert (r.semaphore,r.date);/属于父进程的资源归还且插入父进程资源清单for all created resources(i) do remove descriptor (R);/撤消自己的资源清单归还系统remove process control block (i);end阻塞：Procedure block /阻塞执行进程中的某个进程EP的进程号iBegini:=EP; /从执行进程EP获得调用者内部标识符Stop(i);i.status:=”blockda”; i.stata=WQ(r);/填写阻塞队列指针insert(WQ(r),i); /把i插入WQ队尾scheduler /转调度程序唤醒：Procedure wakeup(n)Begini :=getinternal name(n);remove (WQ(r),i); /把i进程从等待r而受阻塞队列中摘除i.status:=”ready”; /置i进程为“就绪”状态i.sdata:=RQ; /把i进程插入到就绪队列insert(RQ,i);continueend挂起：Procedure suspend(n,a)Begini:=getinternal name(n);s:=i.status;if s=”executing” then stop(i);a:=copy PCB(i);i.status:=if s=”blockeda” then “blockeds” else readys;if s=”executing” then scheduler else continue;end激活：Procedure active(n)Begini:=getinternal name(n)i.status:=if i.status=”readys” then “readya” else blockeda;if i.status=”readys” then scheduler;/当激活后的进程处于“readys”状态针，将引起重新调度else continueend2.1 什么是临界区？引入临界区目的是什么？答：临界区：每个进程中访问临界资源的那段代码称为临界区。目的：如果共享该临界资源的每个进程能互斥的进入自己的临界区，就能保证对临界资源的互斥访问。q 2.2 记录型信号量的物理意义。答：记录型信号量的初值表示系统中某类资源的数目，因而又被称为资源信号量。当值为正(n)时，表示当前n个临界资源可用，或者最多还可允许n进程进入该资源对应的临界区；当值为0时表示临界资源已经全部被占用；当值为负(-n)时其绝对值表示等待使用该资源的进程数。q 2.3 信号量（整型和记录型）不用原语能否实现进程互斥？各举一反例说明。答：整型：不能。S=1process1: begin单独执行每个程序都是正确的，因为每个程序都能实现一个进程进入临界区。但是，当程序并发执行的时候P1: while s=0 do no_op s=1没进入循环P2: while s=0 do no_op s=1 没进入循环P1: s=s-1 s=0 进入临界区 P2: s=s-1 s=-1 进入临界区两个进程可能同时进入临界区 repeat while s=0 do no_op s=s-1 N=N-1;/访问临界资源 s=s+1 until false;endprocess2:begin repeat while s=0 do no_op s=s-1 N=N+1; s=s+1 until false;endP1:s=1-1=0P2:s