操作系统第二章作业

2.1 比较程序的顺序执行和并发执行

程序顺序执行	程序并发执行
顺序性：处理机的操作严格按照程序所规定的顺序执行	间断性：共享系统资源，程序之间形成了相互制约的关系
封闭性：程序一旦开始执行，执行结果不受外界因素影响	失去封闭性：多个程序共享系统中的各种资源，这些资源的状态将由多个程序来改变，致使程序失去封闭性。
可再现性：只要程序执行时的环境和初始条件相同，都将获得相同的结果。	不可再现性：程序失去封闭性，计算结果与并发程序执行速度有关。程序经过多次执行后，虽然他们执行时的环境和初始条件相同，但是结果却不相同。

2.2 比较程序和进程

1）进程是一个动态的概念，而程序则是一个静态的概念。程序是指令的有序集合，没有任何执行含义，而进程则强调执行过程，它动态地被创建，并被调度执行后消亡。

2）进程具有并行特征，而程序没有。进程具有并行特征的两个方面，即独立性和异步性。也就是说，在不考虑资源共享的情况下，各进程的执行是独立的，它们之间不存在逻辑上的制约关系，各进程的是异步的。由于程序不反映执行过程，所以不具有并行特征。

3）进程是系统中独立存在的实体，是竞争资源的基本单位。进程对应特殊的描述结构

并有申请、使用、释放资源的资格。由于系统中存在多个进程，系统资源的有限性必然导致多个进程对资源的共享和竞争，从而使进程的并行性受到系统的制约。

4）进程的存在必然需要程序的存在，但进程和程序不是一一对应的。由于进程是程序

的执行过程，所以程序是进程的一个组成部分。处于静止状态的程序并不对应于任何进程。

当程序被处理机执行时，它一定属于某一个或者多个进程。属于进程的程序可以是一个，也可以是多个。不同的进程可以包含同一个程序，只要该程序所对应的数据集不同。

2.3 试对进程的状态及状态转换进行总结，注意状态转换的物理含义及转化条件。

处于就绪状态的进程 ，在调度程序为之分配了处理机之后，该进程便可执行，相应地，它就由就绪状态转变为运行状态。正在执行的进程也称为当前进程，如果分配给它的时间片已完而被暂停执行时，该进程便由执行状态又回复到就绪状态；如果因发生某事件而使进程的执行受阻，使之无法继续执行，该进程将由执行状态转变为阻塞状态。引入挂起状态后，又增加了从挂起状态到非挂起状态之间的转换，当进程处于未被挂起的就绪状态时，用挂起原语Suspend将该进程挂起后，该进程便转变成为静止就绪状态，此时进程不再被调度执行。当进程处于未被挂起的阻塞状态时，用Suspend原语将它挂起后，进程便转变为静止阻塞状态，处于该状态的进程在其所期待的事件出现后，将从静止阻塞状态变成静止就绪。处于活动就绪状态的进程，若用**原语Active**后，该进程将转变为挂起就绪状态。处于活动阻塞状态的进程，若用**原语Active**后，将转变为阻塞挂起状态。

2.4 试举例说明引起进程创建、撤消、阻塞或被唤醒的主要事件分别有哪些

引起进程创建，如用户登录；作业调度；提供服务；应用请求。

进程撤销，当一个进程到达了自然结束点，或时出现了无法克服的错误，或是被操作系统所中介，或是被其他有终止权的进程所终结，都会引起进程撤销。

进程阻塞，请求系统服务,不能立即满足;启动某种操作,且必须在该操作完成之后才能继续执行;新数据尚未到达,相互合作进程的一方需首先获得另一进程数据才能继续;无新工作可做,特定功能系统进程当完成任务且暂无任务。

进程被唤醒，系统服务满足;操作完成;数据到达;新任务出现。

2.5 试根据你自己的理解，采用类C语言设计和描述操作系统关于进程控制块的数据结构、组织方式及管理机制。在此基础上，给出进程的创建、终止、阻塞、唤醒、挂起与**等函数原型及函数代码。注意，对于过于复杂的功能或你无法解决的细节可采用指定功能的函数模块如处理机调度scheduler()来替代。

进程控制块的数据结构：

Struct
task_struct {

long state; /*任务的运行状态（-1 不可运行，0 可运行(就绪)，>0 已停止）*/

long counter;/*运行时间片计数器(递减)*/

long priority;/*优先级*/

long
signal;/*信号*/

struct 
sigaction sigaction[32];/*信号执行属性结构，对应信号将要执行的操作和标志信息*/

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 * filp[NR_OPEN];/*进程使用的文件表结构*/

/*
ldt for this task 0 - zero 1 - cs 2 - ds&ss */

struct 
desc_struct ldt[3];/*本任务的局部描述符表。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 && j<i)  { p = p->next;  ++j;  }

   
// 顺指针向后查找，直到 p 指向第 i 个元素或 p 为空

if( !p || j>i )

   
return ERROR;      //  第 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)

begin

i:=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进程的父进程j       

i.progeny:=null;       //i的家庭指针为空

j.progeny:=i;          //把i填入其父进程pcb中的家庭指针处

i.state:=RQ;           //i所在状态队列首指针

Insert(RQ,i);          //把i进程插入RQ队尾

continue;

end

终止：

Procedure destroy(n)

Begin

Sched:=false;

i:=getinternal
name(n);//获取n进程的内部名

kill(i);

if sched then scheduler else continue;//假如Schde为真，则转调度程序，否则继续

end

procedure kill(i)

begin

if i.stata(i)=”executing” then

begin stop(i);

sched:=true 
end;

remove (i.stata,i);              
//将被撤消进程从i.state所指示的队列中除去

for all S∈i.progeny do kill(s);

for all r∈(i.main store ∪i.resources) do

if 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的进程号i

Begin

i:=EP;     
//从执行进程EP获得调用者内部标识符

Stop(i);

i.status:=”blockda”;
i.stata=WQ(r);//填写阻塞队列指针

insert(WQ(r),i);
//把i插入WQ队尾

scheduler       
//转调度程序

}

唤醒：

Procedure wakeup(n)

Begin

i :=getinternal name(n);

remove
(WQ(r),i);    //把i进程从等待r而受阻塞队列中摘除

i.status:=”ready”;
//置i进程为“就绪”状态

i.sdata:=RQ;        
//把i进程插入到就绪队列

insert(RQ,i);

continue

end

挂起：

Procedure suspend(n,a)

Begin

i:=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)

Begin
i:=getinternal name(n)

i.status:=if i.status=”readys” then “readya” else blockeda;

if i.status=”readys” then scheduler;//当**后的进程处于“readys”状态针，将引起重新调度

else
continue

end