调度算法

进程和作业调度算法

1. 先来先服务（FCFS）
2. 短作业优先（SJF）
3. 高响应比优先（HRRN）
4. 轮转调度算法（RR）

页面置换算法

1. 最佳页面置换算法（OPT）
2. 先进先出页面置换算法（FIFO）
3. 最近最久未使用置换算法（LRU）
4. 最少使用页面置换算法（LFU）

磁盘调度算法

1. FCFS
2. SSTF
3. SCAN
4. CSCAN

二级页表

某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下:

10位	10位	12位
页目录号	页表索引	页内偏移量

 

请回答下列问题：
(1)页和页框的大小各为多少字节？进程的虚拟地址空间大小为多少页？
(2)假定页目录项和页表项均占4B,则进程的页目录和页表共占多少页？要求写出计算过程。
(3)若在某指令周期内访问的虚拟地址为01000000H和01112048H，则进行地址转换时共应访问多少个二级页表？要求说明理由。

银行家算法

PV操作

排队叫号问题

某银行有1个服务窗口和10个供顾客等待的座位。顾客到达银行时，如果有空座位，就可以到取号机上领取一个号，等待叫号。取号机每次只允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：

cobegin {
    process 顾客i {
        从取号机上取一个号码;
        等待叫号;
        获得服务;
    }

    process 营业员 {
        while(TRUE) {
            叫号;
            为顾客服务;
        }
    }
} coend

要求用信号量机制实现这三步与互斥活动，并说明所定义的信号量的含义（要求用伪代码描述）。

semaphore mutex = 1;
int seat = 10, count = 0;

void 顾客i {
    wait(seat);
    wait(mutex);
    取号;
    signal(mutex);
    signal(count);
    等待叫号;
    signal(seat);
}

process 营业员：
while(1) {
    wait(count);
    叫号;
    为顾客服务;
}

信号量实现进程同步

假设P1和P2中有两段代码C1和C2.如果要强制C1先于C2执行，可以写如下代码：

 semaphore S = 0;

P1:
while(TRUE) {
    C1;
    signal(S);
    ....
}   

P2:
while(TRUE) {
    wait(S);
    C2;
    ....
}

经典的进程同步问题

生产者-消费者问题

某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题。

（1）用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。

（2）根据所定义的信号量，利用PV操作写出能正确并发执行的进程。

(1) 定义一个信号量为S，初始值为20。含义如下：
S > 0 表示售票厅可以继续进入
S = 0 表示售票厅满
S < 0 表示需要在外面等待
(2) PV操作如下：
process n (n = 1, 2, 3 ...)
while(TRUE) {
    wait(S);
    购票;
    signal(S);
}

有两个生产者a、b不断向仓库存放产品，由销售者c取走仓库中产品（仓库初态为空，仓库容量为无限大）。请写出通过P、V操作实现3个进程间的同步和互斥的框图或伪程序，并写出信号量的初值和意义。

(1) mutex = 1：互斥信号量给a和b和c
production = 0：表示仓库内的产品
(2) PV操作如下：
process a/b:
while(TRUE) {
    wait(mutex);
    放入产品;
    signal(production);
    signal(mutex);
}
process c:
while(TRUE) {
    wait(production);
    wait(mutex);
    取走产品;
    signal(mutex);
}

有三个并发进程R、W1和W2，共享两个各可存放一个数的缓冲区B1、B2。进程R每次从输入设备读入一个数，若读入的是奇数，则将它存入B1中，若读入的是偶数，将它存入B2中；当B1中有数，由进程W1将其打印输出；当B2中有数，进程W2将其打印输出。试编写保证三者正确工作的程序。

struct semaphone B1_Empty, B1_Full, B2_Empty, B2_Full;
B1_Empty.value=1;
B1_Full.value=0;
B2_Empty.value=1;
B2_Full.value=0;
void R( ) {	
    int a;
    While(1) {
	read a number a;
	if(a%2==1) {	
            wait(B1_Empty);
            put a in B1;
            signal(B1_Full);
        } else {	
            wait(B2_Empty);
            put a in B2;
            signal(B2_Full);
	}
    }
}
void W1( ) {	
    while(1) {	
        wait(B1_Full);
	print a number from B1;
	signal(B1_Empty);
    }
}
void W2( ) {	
    while(1) {	
        wait(B2_Full);
        print a number from B2;
	signal(B2_Empty);
    }
}
void main( ) {
    R( );
    W1( );
    W2( );
}
 

读者-写者问题

a、b两点之间是一段东西向的单行道，现要设计一个自动管理系统，管理规则如下：当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一个方向的车必须在ab段外等待；当ab之间无车辆在行驶时，到达a点（b点）的车辆可以进入ab段，但不能从a点和b点同时驶入，当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用信号量为工具，对ab段实现正确的管理以保证行驶安全。

semaphore S1 = 1, S2 = 1, Sab = 1;
int ab = ba = 0;

void Pab() {
    while(1) {
        wait(S1);
        if(ab == 0) wait(Sab);
        ab = ab + 1;
        signal(S1);
        从a开往b;
        wait(S1);
        ab = ab - 1;
        if(ab == 0) signal(Sab);
        signal(S1);
    }
}

void Pab() {
    while(1) {
        wait(S2);
        if(ba == 0) wait(Sba);
        ba = ba + 1;
        signal(S2);
        从b开往a;
        wait(S2);
        ba = ba - 1;
        if(ba == 0) signal(Sba);
        signal(S2);
    }
}

其他问题

有3个并发执行的进程A，B，C，它们在执行时都要读共享文件F。限定：进程A和进程B可同时读文件F，进程B和进程C也可同时读文件F，但不允许进程A和进程C同时读文件F。请回答下列问题：

（1）用PV操作实现管理时应怎样定义信号量及其初值？

（2）写出用PV操作管理3个进程的程序。

semaphore mutex = 1;

process A:
while(1) {
    wait(mutex);
    读文件;
    signal(mutex);
}

process B:
while(1) {
    读文件;
}

process C:
while(1) {
    wait(mutex);
    读文件;
    signal(mutex);
}

设公共汽车上，司机和售票员的活动分别是：司机活动：启动车辆、正常行车、到站停车；售票员活动：关车门、售票、开车门。

要求：当发车时间到，售票员关好车门后，司机才能启动车辆，售票员开始售票；当到站后，司机停车后，售票员才能打开车门，乘客下车，站牌乘客上车。

在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现他们的同步。

 semaphore doorMutex = 0, stopMutex = 0;

process driver:
while(1) {
    wait(doorMutex);
    启动车辆;
    正常行驶;
    到站停车;
    signal(stopMutex);
}
    


process waiter:
while(1) {
    关门;
    signal(doorMutex);
    售票;
    wait(stopMutex);
    开车门;
    乘客上下车;
}

公路上有一座桥，该桥一次只允许一辆汽车在桥上行驶。当桥上有汽车时，其它汽车不能上桥。试问：

（1）这是一个同步问题还是互斥问题？

（2）用信号量和P、V操作描述并发过程的活动。

(1) 是一个互斥问题
(2) PV操作如下:
semaphore mutex = 1;
process car_n: (n = 1, 2, 3, ...)
while(1) {
    wait(mutex);
    上桥;
    下桥;
    signal(mutex);
}

在一个盒子里混装了数量相等的围棋白子和黑子,现在要用自动分拣系统把白子和黑子分开，设分拣系统有两个进程P1和P2,其中P1捡白子、P2捡黑子，规定每个进程每次只捡一子，当一个进程正在捡子时不允许另一个进去，当一个进程捡完一子时必须让另一个进程去捡，试写出这两个并发进程能够正确执行的程序。

semaphore white = 1, black = 0;

process A:
while(1) {
    wait(white);
    捡白子;
    signal(black);
}

process B:
while(1) {
    wait(black);
    捡黑子;
    signal(white);
}

假设有一个路口，通行交通规则如下：只要没有机动车在通行，路口行人就可以通过，只有没有行人在通过路口且没有其他机动车在通过路口时该机动车才能通过。请用P、V操作描述行人和机动车通过路口的同步互斥过程。

semaphore road = 1, rmutex = 1;
int count = 0;

process Person:
while(1) {
    wait(rmutex);
    count++;
    if(count == 1) wait(road);
    signal(rmutex);
    通过路口;
    wait(rmutex);
    count--;
    if(count == 0) signal(road);
    sinal(rmutex);
}

process Car:
while(1) {
   wait(road);
   通过路口;
   signal(road);
}

问答

内核和用户态

进程通信

逻辑地址转换物理地址

与设备无关的I/O软件

设备分配中的数据结构

1. 设备控制表（DCT）
2. 通道控制表（CHCT）
3. 系统设备表（SDT）
4. 控制器控制表（COCT）

设备分配时应该考虑的因素

1. 设备的固有属性：共享设备、独占设备、虚拟设备
2. 设备的分配算法：（1）FCFS、（2）最高优先级优先算法：优先级高的排在前面，优先级相同的按FCFS排列。
3. 设备分配的安全性：安全分配方式（破坏请求和保持）、不安全分配方式（银行家算法）。

外存组织方式