操作系统作业-20110421.doc

操作系统作业（2011-04-21）：

1、 假定某采用页式存储管理的系统中，主存容量为1MB，被分成256块，块号为0，1，2，……255。现有一个共4页（页号为0，1，2，3）的作业被依次装入到主存的第2，4，1，5块中。请回答：
（1）主存地址应该用多少位来表示？
（2）作业每一页的长度为多少字节？逻辑地址中的页内地址部分应占用多少位？
（3）画出页表并给出作业中每一页占用的主存块起始地址。
（4）若作业执行中要从第0页的第75单元和第3页的第548单元读信息，那么，实际应从主存的哪两个单元读信息？请把应访问的主存绝对地址用十六进制数表示。

[分析]由于主存容量为 1M，而 1M等于2的20次方，因而主存地址应用20位来表示。1M的主存空间被分成256块，因而每一块的长度为2的20次方／2的8次方＝2的12次方＝4096（字节）。在页式存储管理的系统中，作业信息分页的大小应该与主存分块的大小一致，故作业每一页的长度应为4096个字节。于是，逻辑地址中的页内地址部分应占12位。
因为主存块的大小为4096个字节（4K字节），块的编号从0开始，主存的绝对地址也是从0开始的，故每个主存块的起始地址为：
    块长*块号=4K*块号
现作业被分成四页（页号为0，1，2，3）且分别装入到第2，4，1，5块中。那么，这四页信息所在主存块起始地址应依次为：8K，16K，4K，20K。
作业执行时应把逻辑地址转换成绝对地址，地址转换的一般公式为：
    绝对地址=块号*块长+页内地址
利用二进制乘法的特性，只要把根据页号从页表中查得的块号作为高地址部分，把逻辑地址中的页内地址作为低地址部分，就能得到对应的绝对地址。根据本题的假设，主存地址共20位，页内地址占用了12位，因而，高地址部分占8位，低地址部分占12位。若作业执行中要从第0页第75单元读信息，则实际应从主存第2块的第兀单元去读信息。于是，高地址部分为块号2，用8位二进制码表示为：00000010；低地址部分为单元号（页内地址）75，用12位二进制码表示为000001001011；形成的20位绝对地址为：000000100000010010if。同样地，当要从第3页的第548单元读信息时，实际应从主存第5块的第548单元去读信息。于是，高地址部分应为块号5，低地址部分应为单元号548，用二进制码表示的20位绝对地址就应该为：00000101001000100100。题中要求把绝对地址用二进制编码的十六进制数来表示，即把每四位二进制码作为一个十六进制的数，其对应关系为：
    二进制编码   十六进制编码
    0000         0
    0001         1
    0010         2
    0011         3
    0100         4
    0101         5
    0110         6
    0111         7
    1000         8
    1001         9
    1010         A
    1011         B
    1100         C
    1101         D
    1110         E
    1111         F
因而，第0页第75单元的绝对地址可表示为：0204B
第3页第548单元的绝对地址可表示为：05224
［题解］（1）主存地址应该用20位来表示。
（2）作业每一页的长度应为2的12次方=4096个字节，逻辑地址中的页内地址部分应占用12位。
（3）作业中每一页占用主存块的起始地址为：
    页号  起始地址
    0     8K
    1     16K
    2     4K
    3     20K
（4）若作业执行中要从第0页的第75单元读信息，则实际应从主存的第2块第75单元读，应访问的主存绝对地址用二进制编码的十六进制数表示为对204B。若要从第3页的第548单元读信息，则实际应从主存的第5块第548单元读，应访问的主存绝对地址用二进制编码的十六进制数表示为：05224。

2、 兄弟俩共用一个账号，他们都可以用该账号到任何一家联网的银行自动存款或取款。假定银行的服务系统由“存款”和“取款”两个并发进程组成，且规定每次的存款额和取款额总是为100元。若进程结构如下：
begin
amount：integer；
amount：＝0；
cobegin
Process SAVE
m1： integer；
begin
m1：＝amount；
m1：＝m1+100；
amount：＝m1
end；
Process TAKE
m2：integer；
begin
m2：＝amount；
m2：＝m2-100；
amount：＝m2
end；
coend；
end；
请回答下列问题：
（1）请估计该系统工作时会出现怎样的错误？为什么？
（2）若哥哥先存了两次钱，但在第三次存钱时弟弟却正在取钱，则该账号上可能出现的余额为多少？正确的余额应该为多少？
（3）为保证系统的安全，若用PV操作来管理，应怎样定义信号量及其初值？解释信号量的作用。
（4）在程序的适当位置加上P操作和V操作，使其能正确工作。

［分析]由于“存款”和“取款”两个并发进程使用了共享变量amount，在进程中没有对共享变量的使用加以限制，因而当两个进程交叉访问共享变量时可能会出现与时间有关的错误。
因amount的初值为“0”，故当哥哥先存了两次钱后，amount的值应该为200（每次存人 100元）。之后，哥哥和弟弟各自调用SAVE和TAKE进行存款和取款，使两个进程同时执行。它们并发执行时可能有如下两种情况：
（1）进程在临界区执行没有被打断。此时若哥哥先执行了 m1:=amount；m1:= m1＋100；amount:=m1；则 amount的值为 300。然后，由弟弟执行 m2:= amount； m2:=m2-100；amount:= m2；则弟弟从 300元中取走了 100元使 amount的值保持为 200。如果弟弟先执行，则弟弟将从已有的200元存款中取出 100元使amount的值成为 100。然后，哥哥再执行存人 100元的工作而使amount的值仍为200。可见，无论是哥哥先执行存款还是弟弟先执行取款，只要各自在临界区的工作没有间断，则均使amount保持正确值。
（2）两个进程在临界区交替执行。此时可能哥哥先执行了 m1:=amount，但还没有执行后继操作时弟弟调用的 TAKE进程占用处理器执行了 m2:=amount，那么，m1和 m2都取到了相同的值 200。同样地，若两个进程先后执行了 m2:= amount和 m1:= amount，则 m1和 m2也都取到相同的值200。随后，两个进程并发执行时将使m1=300，m2=100。如果SAVE进程先执行amount:= m1，TAKE进程后执行 amount:= m2，则 amount的终值为 100。如果 TAKE进程先执行 amount:= m2，SAVE进程后执行 amount:= m1，则 amount的终值为 300。
可见，进程并发执行时该账号上可能出现的余额为100元，200元，300元，正确的余额数应该为200元。之所以会出现错误是由于没有限制进程互斥地进入相关临界区执行，为保证系统的安全，可用 PV操作实现互斥。用 PV操作管理时只需定义一个互斥信号量，其初值为“ 1”，用以限制每次只有一个进程可以进入临界区执行。
[题解]（1）系统工作时会出现与时间有关的错误，这是因为并发进程中没有对共享变量amount的使用加以限制，进程交叉访问amount时就会出错。
（2）账号上可能出现的余额为100元或200元或300元，正确的余额应该为200元。
（3）用PV操作管理时可定义一个信号量S,S的初值为1，信号量S用于限制进程互斥地进入相关临界区执行。
（4）使用PV操作管理后能保证正确并发执行的进程结构如下：
begin
    amount:integer;
    s:semaphore;
    amount:=0; s:=1;
cobegin
    Process SAVE
        m1:integer;
    begin
        P(S);
        m1:=amount;
        m1:=m1+100;
        amount:=m1;
        V(S)
    end;
    Process TAKE
        m2:integer;
    begin
        P(S);
        m2:=amount;
        m2:=m2-100;
        amount:=m2;
        V(S)
    end;
    coend:
    end;

3、 有一仓库，可存放A和B两种产品，每次入库时只能存入A或B一种产品，每次出库时只能取出A或B一种产品。现要求：
（1） -30<A产品数量-B产品数量<40
（2） A产品数量+B产品数量<200
试用P、V操作描述产品的入库过程和出库过程。

main()
{
Semaphore empty=199;   //A+B<200
Semaphore full=0;
Semaphore mutex=1;
Semaphore AB=39;      //A-B<40
Semaphore BA=29;      //B-A<30
Cobegin
   InLib();
 OutLib();
Coend
}
入库过程 InLib()      出库过程OutLib()
while(有产品入库)        while(有产品须出库)
{                       {
  if(产品为A)            if(产品为A)
{  P(empty);             {  P(full)
   P(AB)                    P(BA)
   P(mutex)                 P(mutex)
   A产品入库                 A产品出库
   V(mutex)                 V(mutex)
   V(BA)                    V(AB)
   V(full);                 V(empty)
}else{                      }else{
   P(empty);                P(full)
   P(BA)                    P(AB)
   P(mutex)                 P(mutex)
   B产品入库                 B产品出库
   V(mutex)                 V(mutex)
   V(AB)                    V(BA)
   V(full);                 V(empty)
  }                           }
}                           }

5