第一次自测
结合文件I/O内核数据结构，说明系统调用函数open的执行过程。
答：当程序中执行open函数打开时文件时，系统首先检查该文件的v_node是否存在，若不存在，则先为其创建其v_node，将文件的属性从外存读入v-node；接着，创建其文件表(file table)表项，设置读写方式、读写位置、v-node指针，访问计数器置为1；然后，在进程的描述符表中找到索引号最小的空闲表项，在其中填入文件表表项的指针，返回描述符表项的索引号
第二次自测
若盘块大小为 2KB ，块地址用4字节表示，文件系统采用索引组织，索引项0至索引项9为直接索引，索引项10为一级间接索引，索引项11为二级间接索引，索引项12为三级间接索引，若文件索引节点已在内存，
（1）该系统支持的最大文件大小是多少？
（2）请计算从以下文件位置620 0000处读出10K字节数据，需要读写多少个磁盘块？
解：
（1）最大文件大小为：
（10+512+5122+5123）×2KB
=20KB+1MB+512MB+256GB
（2）从位置620 0000处读出10K字节数据，其首字节位置为620 0000，末字节位置为6210239，对应的相对块号分别为：
620 0000/2048=3027.34
621 0239/2048=3032.34
由于直接索引、一级间接索引、二级间接索引下登记的磁盘块数分别为10、512、5122而522<3027、3032<5122 这些数据块的磁盘块号都登记在二级间接指针之下；
同时(3027-522)/512=4.89，(3032-512)/ 512=4.90，这些数据块的磁盘块号都登记在4号索引块中。因此需要读取的磁盘块数为2+3032-3027+1=8个。
读出10KB数据需要读写8个磁盘块。
- 要编写一个多进程应用程序，各进程之间关系如图所示，要求各个进程输出其方框中的进程名。
答：
int main() {
int pid;
printf(“p1\n”);
pid=fork();
if(pid==0) {
printf(“p11\n”)
exit(0);
}
pid=fork();
if(pid==0) {
printf(“p12\n”)
exit(0);
}
pid=fork();
if(pid==0) {
printf(“p13\n”)
pid=fork();
if(pid==0) printf(“p131\n”)
}
给出导致进程状态转换的事件：
（1）运行就绪状态转换，1种；
（2）创建就绪，1种；
（3）运行阻塞，2种；
（4）运行终止，2种。
答：
（1）时间片用完
（2）fork
（3）scanf、read
（4）exit、被0除
第三次自测
阅读下面程序代码，请分析从理论上有哪几种可能的输出结果。
int x=y=1;
void * thread1(void *arg) { x=y*5;}
void * thread2(void *arg) { y=x*10;}
int main()
{ pthread_t t1,t2,t3;
pthread_create(&t1,NULL,thread1,NULL);
pthread_create(&t2,NULL,thread2,NULL);
pthread_join(t1,NULL);
pthread_join(t2,NULL);
printf("x=%d y=%d\n",x,y);
}
答：
（1）x=5 y=10 //同时
（2）x=5 y=50
（3）x=50 y=10
生产者/消费者程序代码
#define N 10
int buf[N], outpos=0, inpos=0;
void produce() {
while (1){
item=produce();
sbuf_insert(item,buf); //insert
}
}
void consumer() {
while (1){
item=sbuf_remove(buf); //remove
consume(item);
}
}
void sbuf_insert(item,buf) {
buf[inpos]=item;
inpos=(inpos+1) mod N;
}
intsbuf_remove(buf) {
item=buf[outpos];
outpos=(outpos+1) mod N;
return item;
}
int main() {
int k, m, i,; pthread_t tid;
scanf("%d%d”, &k,&m);
for(i=0; i<m; i++)
pthread_create(&tid, NULL, produce, NULL);
for(i=0; i<p; i++)
pthread_create(&tid, NULL, consumer, NULL);
}
消费者与生产者竞争缓冲区avail = 0, ready = 0
消费者之间竞争主导权mutex = 1
#define N 20
int buf[N]; int outpos=0; int inpos=0;
semaphore avail=N, ready=0;
semaphore mutex1=mutex2 =1;
void Thread_Pi() //生产者线程，有k个
{
while (1) {
item=produce(); //产生数据
wait(avail); wait(mutex1);
sbuf_insert(item,buf); //向缓冲区投放数据
signal(mutex1); signal(ready);
}
}
void Thread_Ci() //消费者线程，有m个
{
while (1) {
wait(ready); wait(mutex2);
item=sbuf_remove(buf); //从缓冲区去数据
signal(mutex2); signal(avail);
consume(item); //消费或处理数据
}
}
void sbuf_insert(item, buf) //数据写入函数
{ buf[inpos]=item;
inpos=(inpos+1)mod N;
}
int sbuf_remove(buf) //数据读出函数
{ item=buf[outpos];
outpos=(outpos+1) mod N;
return item;
}
- 某超级市场，可容纳100个人同时购物，入口处备有篮子，每个购物者可持一个篮子入内购物。出口处结账，并归还篮子,出、入口仅容纳一人通过。请用P、V操作完成购物同步算法。
解：
semaphore mutex1=mutex2=1, baskets=N;
semaphore sem=100;
互斥量mutex1是入门, mutex2是出门
信号量Baskets:篮子的个数, Sem:可容纳的人数
Customer() {
Wait(sem);//
Wait(baskets); //取购物篮
Wait(mutex1); //得到入门
Signal(mutex1);//入门
Wait(mutex2);//得到出门
Signal(mutex2);//出门
Signal(baskets);//返还篮子
Signal(sem);//
}
7. 试用信号量实现这6个代码段的同步
Semaphore s12=s13=s24=s25=s46=s56=s36=0;
s1只生产信号量不需要得到信号量
其他的线程都需要得到上一步的信号量
- 今有三个并发进程R，M，P，它们共享了一个可循环使用的缓冲区B，缓冲区B共有N个单元。
进程R负责从输入设备读信息，每读一个字符后，把它存放在缓冲区B的一个单元中；
进程M负责处理读入的字符，若发现读入的字符中有空格符，则把它改成“，”；
进程P负责把处理后的字符取出并打印输出。当缓冲区单元中的字符被进程P取出后，则又可用来存放下一次读入的字符。
请用PV操作为同步机制写出它们能正确并发执行的程序。
解：
Semaphore avail=N, ready1=0,ready2=0;//
char B[N];//缓冲区
int pos1=pos2=pos3=0;//下标
R() {
while(1) {
<<从设备读取一个字符ch>>
wait(avail);//获得一个空闲空间-1
B[pos1]=ch;
pos1=(pos1+1) mod N;
signal(ready1);//增加一个字符,生产+1
}
}
M() {
while(1) {
wait(ready1);//得到一个产品 -1
ch=B[pos2];
if(ch==’ ‘) ch=’,’;
B[pos2]=ch;
pos2=(pos2+1) mod N;
signal(ready2);//加工一个新产品 + 1
}
}
P() {
while(1) {
wait(ready2);//得到一个新产品 - 1
B[pos3]=ch;
pos3=(pos3+1) mod N;
signal(avail);//释放一个空闲空间+1
}
}
-
有一座桥如图所示，车流如图中箭头所示。桥上不允许两车交会，但允许同方向多辆车依次通行（即桥上可以有多个同方向的车）。用信号量和P、V操作实现交通管理,写出描述代码，以防止桥上堵塞。
重点题型
分析:
两个线程函数EasttoWest, WesttoEaset
每个方向上的车辆都要对当前通行的车辆做统计,以确保自己是否要和敌方争夺通道的使用权,为防止多个同方向的线程同时对count进行操作,需要互斥量mutex1, mutex2.另外还需要一个争夺通道权的互斥量wmutex
semaphore mutex1=mutex2=wmutex=1;
int count1=count2=0;
EasttoWest() {
wait(mutex1);
count1++;
if(count1==1) wait(wmutex);
signal(mutex1);
汽车走过单行道
wait(mutex1);
count1--;
if(count1==0) signal(wmutex);
signal(mutex1);
}
WesttoEaset() {
wait(mutex2);
count2++;
if(count2==1) wait(wmutex);
signal(mutex2);
汽车走过单行道
wait(mutex2);
count2--;
if(count2==0) signal(wmutex);
signal(mutex2);
}
