OSTEP的全称是Operating Systems: Three Easy Pieces,是一本很好的操作系统入门书,之所以再看这本书,是因为学习xv6碰到了不少困难,希望结合多个教材一起学习,后续会给出大部分章节的回顾,这里从第4章开始,本章介绍了抽象:进程。

书籍介绍:

学习资料:

第4 章 抽象:进程

内容回顾

关键概念

  • 进程:运行中的程序。
  • 虚拟化:
    • 需要低级机制和高级智能来支持;
    • 低级机制:称为机制,为系统的“如何(how)”问题提供答案;
    • 高级智能:称为策略,为系统的“哪个(which)”问题提供答案;
  • 时分共享(time sharing):允许资源由一个实体使用一小段时间,然后由另一个实体使用一小段时间。
  • 进程API:
    • 创建(create);
    • 销毁(destroy);
    • 等待(wait);
    • 其他控制(miscellaneous control);
    • 状态(statu);
  • 进程状态:
    • 运行(running);
    • 就绪(ready);
    • 阻塞(blocked);

作业

1

(base) λ python ./process-run.py -l 5:100,5:100
Produce a trace of what would happen when you run these processes:
Process 0
  cpu
  cpu
  cpu
  cpu
  cpu

Process 1
  cpu
  cpu
  cpu
  cpu
  cpu

Important behaviors:
  System will switch when the current process is FINISHED or ISSUES AN IO
  After IOs, the process issuing the IO will run LATER (when it is its turn)

CPU利用率是100%,因为5:100表示执行5个指令,CPU执行的机会为100%,验证这点:

(base) λ python ./process-run.py -l 5:100,5:100 -c
Time        PID: 0        PID: 1           CPU           IOs
  1        RUN:cpu         READY             1
  2        RUN:cpu         READY             1
  3        RUN:cpu         READY             1
  4        RUN:cpu         READY             1
  5        RUN:cpu         READY             1
  6           DONE       RUN:cpu             1
  7           DONE       RUN:cpu             1
  8           DONE       RUN:cpu             1
  9           DONE       RUN:cpu             1
 10           DONE       RUN:cpu             1

2

需要11个clock ticks,因为4:100需要4个clock ticks,此时使用CPU,无法进行IO;1:0需要进行IO,分别经历RUN:io,RUN:io_done以及WAITING状态,其中WAITING需要iolength个clock ticks,默认值为5,因此总共需要4 + 2 + 5 = 11个clock ticks。

验证:

λ python ./process-run.py -l 4:100,1:0 -c                      
Time        PID: 0        PID: 1           CPU           IOs   
  1        RUN:cpu         READY             1                 
  2        RUN:cpu         READY             1                 
  3        RUN:cpu         READY             1                 
  4        RUN:cpu         READY             1                 
  5           DONE        RUN:io             1                 
  6           DONE       WAITING                           1   
  7           DONE       WAITING                           1   
  8           DONE       WAITING                           1   
  9           DONE       WAITING                           1   
 10           DONE       WAITING                           1   
 11*          DONE   RUN:io_done             1                 

3

需要7个clock ticks,因为进程0先进入RUN:io状态,然后进入WAITING状态,需要5个clock ticks;此时系统切换到进程1,进程1进入RUN:cpu状态,需要4个clock ticks;最后进程0进入RUN:io_done状态,注意此时进程1进入DONE状态。

验证:

(base) λ python ./process-run.py -l 1:0,4:100 -c                                                 
Time        PID: 0        PID: 1           CPU           IOs
  1         RUN:io         READY             1
  2        WAITING       RUN:cpu             1             1
  3        WAITING       RUN:cpu             1             1
  4        WAITING       RUN:cpu             1             1
  5        WAITING       RUN:cpu             1             1
  6        WAITING          DONE                           1
  7*   RUN:io_done          DONE             1

4

因为进程在进行I/O时不会进行切换,所以此时和第2题的结果相同。

验证:

(base) λ python ./process-run.py -l 1:0,4:100 -c -S SWITCH_ON_END                                 
Time        PID: 0        PID: 1           CPU           IOs
  1         RUN:io         READY             1
  2        WAITING         READY                           1
  3        WAITING         READY                           1
  4        WAITING         READY                           1
  5        WAITING         READY                           1
  6        WAITING         READY                           1
  7*   RUN:io_done         READY             1
  8           DONE       RUN:cpu             1
  9           DONE       RUN:cpu             1
 10           DONE       RUN:cpu             1
 11           DONE       RUN:cpu             1

5

因为进程在进行I/O时会进行切换,所以此时和第3题的结果相同。

验证:

(base) λ python ./process-run.py -l 1:0,4:100 -c -S SWITCH_ON_IO
Time        PID: 0        PID: 1           CPU           IOs
  1         RUN:io         READY             1
  2        WAITING       RUN:cpu             1             1
  3        WAITING       RUN:cpu             1             1
  4        WAITING       RUN:cpu             1             1
  5        WAITING       RUN:cpu             1             1
  6        WAITING          DONE                           1
  7*   RUN:io_done          DONE             1

6

当第一次I/O完成时,发出的进程没有马上进入RUN:io_done状态,只有等到其他CPU任务完成时,才会进入RUN:io_done状态,然后才能执行后续I/O。这样效率较低,因为可以在I/O的同时执行CPU任务:

(base) λ python ./process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_LATER -c -p
Time        PID: 0        PID: 1        PID: 2        PID: 3           CPU           IOs
  1         RUN:io         READY         READY         READY             1
  2        WAITING       RUN:cpu         READY         READY             1             1
  3        WAITING       RUN:cpu         READY         READY             1             1
  4        WAITING       RUN:cpu         READY         READY             1             1
  5        WAITING       RUN:cpu         READY         READY             1             1
  6        WAITING       RUN:cpu         READY         READY             1             1
  7*         READY          DONE       RUN:cpu         READY             1
  8          READY          DONE       RUN:cpu         READY             1
  9          READY          DONE       RUN:cpu         READY             1
 10          READY          DONE       RUN:cpu         READY             1
 11          READY          DONE       RUN:cpu         READY             1
 12          READY          DONE          DONE       RUN:cpu             1
 13          READY          DONE          DONE       RUN:cpu             1
 14          READY          DONE          DONE       RUN:cpu             1
 15          READY          DONE          DONE       RUN:cpu             1
 16          READY          DONE          DONE       RUN:cpu             1
 17    RUN:io_done          DONE          DONE          DONE             1
 18         RUN:io          DONE          DONE          DONE             1
 19        WAITING          DONE          DONE          DONE                           1
 20        WAITING          DONE          DONE          DONE                           1
 21        WAITING          DONE          DONE          DONE                           1
 22        WAITING          DONE          DONE          DONE                           1
 23        WAITING          DONE          DONE          DONE                           1
 24*   RUN:io_done          DONE          DONE          DONE             1
 25         RUN:io          DONE          DONE          DONE             1
 26        WAITING          DONE          DONE          DONE                           1
 27        WAITING          DONE          DONE          DONE                           1
 28        WAITING          DONE          DONE          DONE                           1
 29        WAITING          DONE          DONE          DONE                           1
 30        WAITING          DONE          DONE          DONE                           1
 31*   RUN:io_done          DONE          DONE          DONE             1

Stats: Total Time 31
Stats: CPU Busy 21 (67.74%)
Stats: IO Busy  15 (48.39%)

7

当第一次I/O完成时,发出的进程马上进入RUN:io_done,然后可以立即进入RUN:io状态,随后进入WAITING状态,与此同时其他CPU任务可以运行,从而提高CPU利用率:

(base) λ python ./process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_IMMEDIATE -c -p
Time        PID: 0        PID: 1        PID: 2        PID: 3           CPU           IOs
  1         RUN:io         READY         READY         READY             1
  2        WAITING       RUN:cpu         READY         READY             1             1
  3        WAITING       RUN:cpu         READY         READY             1             1
  4        WAITING       RUN:cpu         READY         READY             1             1
  5        WAITING       RUN:cpu         READY         READY             1             1
  6        WAITING       RUN:cpu         READY         READY             1             1
  7*   RUN:io_done          DONE         READY         READY             1
  8         RUN:io          DONE         READY         READY             1
  9        WAITING          DONE       RUN:cpu         READY             1             1
 10        WAITING          DONE       RUN:cpu         READY             1             1
 11        WAITING          DONE       RUN:cpu         READY             1             1
 12        WAITING          DONE       RUN:cpu         READY             1             1
 13        WAITING          DONE       RUN:cpu         READY             1             1
 14*   RUN:io_done          DONE          DONE         READY             1
 15         RUN:io          DONE          DONE         READY             1
 16        WAITING          DONE          DONE       RUN:cpu             1             1
 17        WAITING          DONE          DONE       RUN:cpu             1             1
 18        WAITING          DONE          DONE       RUN:cpu             1             1
 19        WAITING          DONE          DONE       RUN:cpu             1             1
 20        WAITING          DONE          DONE       RUN:cpu             1             1
 21*   RUN:io_done          DONE          DONE          DONE             1

Stats: Total Time 21
Stats: CPU Busy 21 (100.00%)
Stats: IO Busy  15 (71.43%)

8

seed=1

(base) λ python ./process-run.py -s 1 -l 3:50,3:50
Produce a trace of what would happen when you run these processes:
Process 0
  cpu    
  io
  io_done
  io
  io_done

Process 1
  cpu
  cpu
  cpu

-I IO_RUN_IMMEDIATE参数:

(base) λ python ./process-run.py -s 1 -l 3:50,3:50 -I IO_RUN_IMMEDIATE -c -p                     
Time        PID: 0        PID: 1           CPU           IOs
  1        RUN:cpu         READY             1
  2         RUN:io         READY             1
  3        WAITING       RUN:cpu             1             1
  4        WAITING       RUN:cpu             1             1
  5        WAITING       RUN:cpu             1             1
  6        WAITING          DONE                           1
  7        WAITING          DONE                           1
  8*   RUN:io_done          DONE             1
  9         RUN:io          DONE             1
 10        WAITING          DONE                           1
 11        WAITING          DONE                           1
 12        WAITING          DONE                           1
 13        WAITING          DONE                           1
 14        WAITING          DONE                           1
 15*   RUN:io_done          DONE             1

Stats: Total Time 15
Stats: CPU Busy 8 (53.33%)
Stats: IO Busy  10 (66.67%)

-I IO_RUN_LATER参数,注意CPU任务只需要3个clock ticks(< IO时间),所以和之前情形相同:

(base) λ python ./process-run.py -s 1 -l 3:50,3:50 -I IO_RUN_LATER -c -p                         
Time        PID: 0        PID: 1           CPU           IOs
  1        RUN:cpu         READY             1
  2         RUN:io         READY             1
  3        WAITING       RUN:cpu             1             1
  4        WAITING       RUN:cpu             1             1
  5        WAITING       RUN:cpu             1             1
  6        WAITING          DONE                           1
  7        WAITING          DONE                           1
  8*   RUN:io_done          DONE             1
  9         RUN:io          DONE             1
 10        WAITING          DONE                           1
 11        WAITING          DONE                           1
 12        WAITING          DONE                           1
 13        WAITING          DONE                           1
 14        WAITING          DONE                           1
 15*   RUN:io_done          DONE             1

Stats: Total Time 15
Stats: CPU Busy 8 (53.33%)
Stats: IO Busy  10 (66.67%)

-S SWITCH_ON_IO参数:

(base) λ python ./process-run.py -s 1 -l 3:50,3:50 -S SWITCH_ON_IO -c -p
Time        PID: 0        PID: 1           CPU           IOs
  1        RUN:cpu         READY             1
  2         RUN:io         READY             1
  3        WAITING       RUN:cpu             1             1
  4        WAITING       RUN:cpu             1             1
  5        WAITING       RUN:cpu             1             1
  6        WAITING          DONE                           1
  7        WAITING          DONE                           1
  8*   RUN:io_done          DONE             1
  9         RUN:io          DONE             1
 10        WAITING          DONE                           1
 11        WAITING          DONE                           1
 12        WAITING          DONE                           1
 13        WAITING          DONE                           1
 14        WAITING          DONE                           1
 15*   RUN:io_done          DONE             1

Stats: Total Time 15
Stats: CPU Busy 8 (53.33%)
Stats: IO Busy  10 (66.67%)

-S SWITCH_ON_END参数,在I/O完成时才会切换进程:

(base) λ python ./process-run.py -s 1 -l 3:50,3:50 -S SWITCH_ON_END -c -p
Time        PID: 0        PID: 1           CPU           IOs
  1        RUN:cpu         READY             1
  2         RUN:io         READY             1
  3        WAITING         READY                           1
  4        WAITING         READY                           1
  5        WAITING         READY                           1
  6        WAITING         READY                           1
  7        WAITING         READY                           1
  8*   RUN:io_done         READY             1
  9         RUN:io         READY             1
 10        WAITING         READY                           1
 11        WAITING         READY                           1
 12        WAITING         READY                           1
 13        WAITING         READY                           1
 14        WAITING         READY                           1
 15*   RUN:io_done         READY             1
 16           DONE       RUN:cpu             1
 17           DONE       RUN:cpu             1
 18           DONE       RUN:cpu             1

Stats: Total Time 18
Stats: CPU Busy 8 (44.44%)
Stats: IO Busy  10 (55.56%)

seed=2

(base) λ python ./process-run.py -s 2 -l 3:50,3:50
Produce a trace of what would happen when you run these processes:
Process 0
  io
  io_done
  io
  io_done
  cpu

Process 1
  cpu
  io
  io_done
  io
  io_done

Important behaviors:
  System will switch when the current process is FINISHED or ISSUES AN IO
  After IOs, the process issuing the IO will run LATER (when it is its turn)

-I IO_RUN_IMMEDIATE参数:

(base) λ python ./process-run.py -s 2 -l 3:50,3:50 -I IO_RUN_IMMEDIATE -c -p
Time        PID: 0        PID: 1           CPU           IOs
  1         RUN:io         READY             1
  2        WAITING       RUN:cpu             1             1
  3        WAITING        RUN:io             1             1
  4        WAITING       WAITING                           2
  5        WAITING       WAITING                           2
  6        WAITING       WAITING                           2
  7*   RUN:io_done       WAITING             1             1
  8         RUN:io       WAITING             1             1
  9*       WAITING   RUN:io_done             1             1
 10        WAITING        RUN:io             1             1
 11        WAITING       WAITING                           2
 12        WAITING       WAITING                           2
 13        WAITING       WAITING                           2
 14*   RUN:io_done       WAITING             1             1
 15        RUN:cpu       WAITING             1             1
 16*          DONE   RUN:io_done             1

Stats: Total Time 16
Stats: CPU Busy 10 (62.50%)
Stats: IO Busy  14 (87.50%)

-I IO_RUN_LATER参数:

(base) λ python ./process-run.py -s 2 -l 3:50,3:50 -I IO_RUN_LATER -c -p
Time        PID: 0        PID: 1           CPU           IOs
  1         RUN:io         READY             1
  2        WAITING       RUN:cpu             1             1
  3        WAITING        RUN:io             1             1
  4        WAITING       WAITING                           2
  5        WAITING       WAITING                           2
  6        WAITING       WAITING                           2
  7*   RUN:io_done       WAITING             1             1
  8         RUN:io       WAITING             1             1
  9*       WAITING   RUN:io_done             1             1
 10        WAITING        RUN:io             1             1
 11        WAITING       WAITING                           2
 12        WAITING       WAITING                           2
 13        WAITING       WAITING                           2
 14*   RUN:io_done       WAITING             1             1
 15        RUN:cpu       WAITING             1             1
 16*          DONE   RUN:io_done             1

Stats: Total Time 16
Stats: CPU Busy 10 (62.50%)
Stats: IO Busy  14 (87.50%)

-S SWITCH_ON_IO参数:

(base) λ python ./process-run.py -s 2 -l 3:50,3:50 -S SWITCH_ON_IO -c -p
Time        PID: 0        PID: 1           CPU           IOs
  1         RUN:io         READY             1
  2        WAITING       RUN:cpu             1             1
  3        WAITING        RUN:io             1             1
  4        WAITING       WAITING                           2
  5        WAITING       WAITING                           2
  6        WAITING       WAITING                           2
  7*   RUN:io_done       WAITING             1             1
  8         RUN:io       WAITING             1             1
  9*       WAITING   RUN:io_done             1             1
 10        WAITING        RUN:io             1             1
 11        WAITING       WAITING                           2
 12        WAITING       WAITING                           2
 13        WAITING       WAITING                           2
 14*   RUN:io_done       WAITING             1             1
 15        RUN:cpu       WAITING             1             1
 16*          DONE   RUN:io_done             1

Stats: Total Time 16
Stats: CPU Busy 10 (62.50%)
Stats: IO Busy  14 (87.50%)

-S SWITCH_ON_END参数,在I/O完成时才会切换进程:

(base) λ python ./process-run.py -s 2 -l 3:50,3:50 -S SWITCH_ON_END -c -p
Time        PID: 0        PID: 1           CPU           IOs
  1         RUN:io         READY             1
  2        WAITING         READY                           1
  3        WAITING         READY                           1
  4        WAITING         READY                           1
  5        WAITING         READY                           1
  6        WAITING         READY                           1
  7*   RUN:io_done         READY             1
  8         RUN:io         READY             1
  9        WAITING         READY                           1
 10        WAITING         READY                           1
 11        WAITING         READY                           1
 12        WAITING         READY                           1
 13        WAITING         READY                           1
 14*   RUN:io_done         READY             1
 15        RUN:cpu         READY             1
 16           DONE       RUN:cpu             1
 17           DONE        RUN:io             1
 18           DONE       WAITING                           1
 19           DONE       WAITING                           1
 20           DONE       WAITING                           1
 21           DONE       WAITING                           1
 22           DONE       WAITING                           1
 23*          DONE   RUN:io_done             1
 24           DONE        RUN:io             1
 25           DONE       WAITING                           1
 26           DONE       WAITING                           1
 27           DONE       WAITING                           1
 28           DONE       WAITING                           1
 29           DONE       WAITING                           1
 30*          DONE   RUN:io_done             1

Stats: Total Time 30
Stats: CPU Busy 10 (33.33%)
Stats: IO Busy  20 (66.67%)

seed=3

(base) λ python ./process-run.py -s 3 -l 3:50,3:50
Produce a trace of what would happen when you run these processes:
Process 0
  cpu
  io
  io_done
  cpu

Process 1
  io
  io_done
  io
  io_done
  cpu

Important behaviors:
  System will switch when the current process is FINISHED or ISSUES AN IO
  After IOs, the process issuing the IO will run LATER (when it is its turn)

-I IO_RUN_IMMEDIATE参数:

(base) λ python ./process-run.py -s 3 -l 3:50,3:50 -I IO_RUN_IMMEDIATE -c -p       
Time        PID: 0        PID: 1           CPU           IOs
  1        RUN:cpu         READY             1
  2         RUN:io         READY             1
  3        WAITING        RUN:io             1             1
  4        WAITING       WAITING                           2
  5        WAITING       WAITING                           2
  6        WAITING       WAITING                           2
  7        WAITING       WAITING                           2
  8*   RUN:io_done       WAITING             1             1
  9*         READY   RUN:io_done             1
 10          READY        RUN:io             1
 11        RUN:cpu       WAITING             1             1
 12           DONE       WAITING                           1
 13           DONE       WAITING                           1
 14           DONE       WAITING                           1
 15           DONE       WAITING                           1
 16*          DONE   RUN:io_done             1
 17           DONE       RUN:cpu             1

Stats: Total Time 17
Stats: CPU Busy 9 (52.94%)
Stats: IO Busy  11 (64.71%)

-I IO_RUN_LATER参数:

(base) λ python ./process-run.py -s 3 -l 3:50,3:50 -I IO_RUN_LATER -c -p 
Time        PID: 0        PID: 1           CPU           IOs
  1        RUN:cpu         READY             1
  2         RUN:io         READY             1
  3        WAITING        RUN:io             1             1
  4        WAITING       WAITING                           2
  5        WAITING       WAITING                           2
  6        WAITING       WAITING                           2
  7        WAITING       WAITING                           2
  8*   RUN:io_done       WAITING             1             1
  9*       RUN:cpu         READY             1
 10           DONE   RUN:io_done             1
 11           DONE        RUN:io             1
 12           DONE       WAITING                           1
 13           DONE       WAITING                           1
 14           DONE       WAITING                           1
 15           DONE       WAITING                           1
 16           DONE       WAITING                           1
 17*          DONE   RUN:io_done             1
 18           DONE       RUN:cpu             1

Stats: Total Time 18
Stats: CPU Busy 9 (50.00%)
Stats: IO Busy  11 (61.11%)

-S SWITCH_ON_IO参数:

(base) λ python ./process-run.py -s 3 -l 3:50,3:50 -S SWITCH_ON_IO -c -p
Time        PID: 0        PID: 1           CPU           IOs
  1        RUN:cpu         READY             1
  2         RUN:io         READY             1
  3        WAITING        RUN:io             1             1
  4        WAITING       WAITING                           2
  5        WAITING       WAITING                           2
  6        WAITING       WAITING                           2
  7        WAITING       WAITING                           2
  8*   RUN:io_done       WAITING             1             1
  9*       RUN:cpu         READY             1
 10           DONE   RUN:io_done             1
 11           DONE        RUN:io             1
 12           DONE       WAITING                           1
 13           DONE       WAITING                           1
 14           DONE       WAITING                           1
 15           DONE       WAITING                           1
 16           DONE       WAITING                           1
 17*          DONE   RUN:io_done             1
 18           DONE       RUN:cpu             1

Stats: Total Time 18
Stats: CPU Busy 9 (50.00%)
Stats: IO Busy  11 (61.11%)

-S SWITCH_ON_END参数,在I/O完成时才会切换进程:

(base) λ python ./process-run.py -s 3 -l 3:50,3:50 -S SWITCH_ON_END -c -p
Time        PID: 0        PID: 1           CPU           IOs
  1        RUN:cpu         READY             1
  2         RUN:io         READY             1
  3        WAITING         READY                           1
  4        WAITING         READY                           1
  5        WAITING         READY                           1
  6        WAITING         READY                           1
  7        WAITING         READY                           1
  8*   RUN:io_done         READY             1
  9        RUN:cpu         READY             1
 10           DONE        RUN:io             1
 11           DONE       WAITING                           1
 12           DONE       WAITING                           1
 13           DONE       WAITING                           1
 14           DONE       WAITING                           1
 15           DONE       WAITING                           1
 16*          DONE   RUN:io_done             1
 17           DONE        RUN:io             1
 18           DONE       WAITING                           1
 19           DONE       WAITING                           1
 20           DONE       WAITING                           1
 21           DONE       WAITING                           1
 22           DONE       WAITING                           1
 23*          DONE   RUN:io_done             1
 24           DONE       RUN:cpu             1

Stats: Total Time 24
Stats: CPU Busy 9 (37.50%)
Stats: IO Busy  15 (62.50%)