2014年华电计算机专业考研专业课复习2
1、܌进程的基本概念
为了提高计算机系统中各种资源的利用率，现代操作系统广泛采用多道程序技术（multi-programming），使多个程序同时在系统中存在并运行。描述进程的数据结构——进程控制块（PCB）
一个进程应该包括：
程序的代码；
程序的数据；
PC中的值，用来指示下一条将运行的指令；
一组通用的寄存器的当前值，堆、栈；
一组系统资源（如打开的文件）
程序是文本，是语句的描述（静态）
进程是运行中的程序，含有上下文信息（动态）
结构特征：程序段、相关的数据段、PCB构成了进程实体
动态性：进程是进程实体的一次执行，进程的状态总是在变化，PCB的内容总是在变化
并发性：多个进程实体，同存于内存中，能在一段时间内同时运行（宏观上）
独立性：独立运行和资源调度的基本单位。每个进程都有“自己”的PC和内部状态，运行时独立于其他的进程（逻辑PC和物理PC）
异步性：以各自独立的、不可预知的速度向前推进
2、܌进程的控制
Running运行 Blocked阻塞 Ready就绪
进程的三种基本状态
1) 就绪(Ready)状态：进程一旦获得CPU就可以投入运行的状态
2) 执行状态：进程获得CPU正在运行的状态
3) 阻塞状态：进程由于等待资源或某个事件的发生而暂停执行的状态
运行à阻塞
等待I/O的结果
等待某一进程提供输入
运行à就绪
运行进程用完了时间片
运行进程被中断，因为一高优先级进程处于就绪状态
就绪 à 运行
调度程序选择一个新的进程运行
阻塞 à就绪
当所等待的事件发生时
3、܌进程同步
两个进程使用相同的一个共享一个资源（如共享文件，打印机等）引出进程同步问题。
进程在运行过程中所做的工作分为两类：
内部计算（不会导致竞争条件）
对共享内存或共享文件的访问（可能导致竞争条件）
我们把完成第二类工作的程序称为“临界区”，把需要互斥访问的共享资源称为“临界资源”。如果我们能设计出某种方法，使得任何两个进程都不会同时出现在临界区中，就可以避免竞争条件的出现。
由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。
wait(S): while S≤0 do no-op S:=S-1;
signal(S): S:=S+1;
4、܌经典的进程同步互斥问题
4.1有3个客户在某天的日常生活中使用了某个 ATM 自动取款机。假设他们对 ATM 的使用顺序是 a 到来，a 进入， b 到来， c 到来， a 离开，b 进入， b 离开， c 进入， c 离开。
4.2某阅览室，最多可容纳100名读者同时阅览，当阅览室中少于100名读者时，阅览室外等候的读者可以立即进入，否则需要在外面等待。每个读者可看成一个进程。
semaphore seats；
seats.value=100;
while(阅览时间)
{
wait(seats);
进入阅览室；
阅读；
离开阅览室；
signal(seats);
}
4.3司机与售票员
while(上班时间)
{
发动汽车；
正常运行；
到站停车；
}
while(上班时间)
{
关闭车门；
售票；
打开车门；
}
4.4两个并发进程的读写
设有一个缓冲区buffer，大小为一个字节（如图）。Compute进程不断产生字符，送buffer，Print进程从buffer中取出字符打印。如不加控制，会出现多种打印结果，这取决于这两个进程运行的相对速度。在这众多的打印结果中，只有Compute和Print进程的运行刚好匹配的一种是正确的，其它均为错误。
semaphore S_Empty； // 缓冲区是否为空，初值为1
semaphore S_Full; // 是否有数据写入，初值为0
while(计算未完成)
{ P(S_Empty);
Write_Data( )；
V(S_Full);
}
Compute
while(打印未完成)
{
P(S_Full)； Print_Data( )； V(S_Empty);
}
4.5有一个仓库，可以存放A和B 两种产品。要求：1)每次只能存入一种产品(A或B)；2)-N<A产品数量-B产品数量<M。试用PV操作描述产品A与产品B的入库过程。
semaphore mutex；// 初始化为1
semaphore sa; // 初始化为m-1
semaphore sb; // 初始化为n-1
while(……)
{ P(Sa);
P(mutex);
将产品入库；
V(mutex);
V(Sb);
}
while(……)
{ P(Sb);
P(mutex);
将产品入库；
V(mutex);
V(Sa);
}
4.6生产者-消费者问题描述
两个进程（生产者和消费者）共享一个公有的、固定大小的缓冲区，生产者不断地制造产品，并把它放入缓冲区，而消费者不断地把产品取出来，并且使用它。要求两个进程都能正确地工作。
对于生产者进程：制造一个产品，当要送入缓冲区时，要检查缓冲区是否已满，若未满，才可将产品送入缓冲区，并在必要时通知消费者；否则等待；对于消费者进程：当它去取产品时，先要检查缓冲区中是否有产品可取，若有，则取走一个，并在必要时通知生产者；否则等待。
这种相互等待，并互通信息就是典型的进程同步。
同时，缓冲区是个临界资源，因此，各个进程在使用缓冲区的时候，还有一个互斥的问题。
semaphore S_Buffer_Num; // 空闲的缓冲区个数，初值为N
semaphore S_Product_Num; // 缓冲区当中的产品个数，初值为0
semaphore S_Mutex; // 用于互斥访问的信号量，初值为1
void producer(void) { int item;
while(TRUE)
{ item = produce_item( ); // 制造一个产品 P(S_Buffer_Num); // 是否有空闲缓冲区 P(S_Mutex); // 进入临界区 insert_item(item); // 产品放入缓冲区 V(S_Mutex); // 离开临界区 V(S_Product_Num); // 新增了一个产品 }
}
void consumer(void) { int item;
while(TRUE)
{ P(S_Product_Num); // 缓冲区中有无产品 P(S_Mutex); // 进入临界区 item = remove_item( ) // 从缓冲区取产品 V(S_Mutex); // 离开临界区 V(S_Buffer_Num); // 新增一个空闲缓冲区 consume_item(item); // 使用该产品 }
}
4.7哲学家就餐问题、读者写者问题、南开天大之路问题、和尚喝水问题（略）
5、܌进程通信
低级通信：只能传递状态和整数值（控制信息），包括用来实现进程同步和互斥的信号量和管程机制。优点是速度快。缺点是：
传送信息量小：每次通信传递的信息量固定，若需要传递较多信息，就得进行多次通信。
编程复杂：用户需要直接去实现通信的细节，编程复杂，容易出错。
高级通信：能够传送任意数量的数据，包括三类：共享内存、管道、消息。
6、܌线程定义及实现
进程当中的一条执行流程叫线程。
进程是资源分配单位，线程是CPU调度单位；
进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；
线程同样具有就绪、阻塞和执行三种基本状态，同样具有状态之间的转换关系；
线程 ＝ 轻量级进程（lightweight process）
用户线程：在用户空间实现，时间片分配给进程；
内核线程：在内核中实现，时间片分配给线程；