4. The Abstraction: The Process
process: it is a running program.
HOW TO PROVIDE THE ILLUSION OF MANY CPUS?
by virtualizing the CPU. By running one process, then stopping it and running another, and so forth.
mechanisms: low-level methods or protocols that implement a needed piece of functionality. For example, context switch. time-sharing mechanism.
Policies are algorithms for making some kind of decision within the OS.
scheduling policy decidion which programs to run on a CPU.
4.1 The Abstraction: A Process
machine state: what a program can read or update when it is running.
machine state component: memory, registers(program counter, PC; instruction pointer, IP; stack pointer; frame pointer)
4.2 Process API
- Create: create new processes.
- Destroy: destroy processes forcefully.
- Wait: wait for a process to stop running.
- Miscellaneous Control: e.g. suspend a process and then resume it.
- Status: get some status information about a process.
4.3 Process Creation: A Little More Detail
how programs are transformed into processes?
load its code and any static data (e.g., initialized variables) into memory, into the address space of the process. Programs initially reside on disk in some kind of executable format;
Some memory must be allocated for the program’s run-time stack (or just stack).The OS may also allocate some memory for the program’s heap.
The OS will also do some other initialization tasks, particularly as re- lated to input/output (I/O).
to start the program running at the entry point, namely main().
4.4 Process States
In a simplified view, a process can be in one of three states
- Running
- Ready
- Blocked
scheduled
Running ----> Ready
| <---- ^
| descheduled |
I/O: initiate I/O: done
| |
----> Blocked -----4.5 Data Structures
The OS is a program, it has some key data struc- tures that track various relevant pieces of information. the OS likely will keep some kind of process list for all processes.
// the registers xv6 will save and restore
// to stop and subsequently restart a process
struct context {
int eip;
int esp;
int ebx;
int ecx;
int edx;
int esi;
int edi;
int ebp;
};
// the different states a process can be in
enum proc_state { UNUSED, EMBRYO, SLEEPING,
RUNNABLE, RUNNING, ZOMBIE };
// the information xv6 tracks about each process
// including its register context and state
struct proc {
char *mem;
uint sz;
char *kstack;
enum proc_state state;
int pid;
struct proc *parent;
void *chan;
// Start of process memory
// Size of process memory
// Bottom of kernel stack
// for this process
// Process state
// Process ID
// Parent process
// If non-zero, sleeping on chan
// If non-zero, have been killed
int killed;
struct file *ofile[NOFILE]; // Open files
struct inode *cwd;
struct context context;
struct trapframe *tf;
// Current directory
// Switch here to run process
// Trap frame for the
// current interrupt
};Homework
https://zhanghuimeng.github.io/post/ostep-ch-04-homework-simulation-process-run-py/
进程有四种不同的状态： RUNNING、READY、WAITING、DONE
每个进程由多个指令组成。每个指令只会做两件事，使用 CPU 或进行 IO
通过命令 -l PROCESS_LIST 指定进程列表，列表格式是 X1:Y1,X2:Y2 ，X 表示指令的数，Y 表示指令是使用 CPU 的概率(0-100) 如果是100则全部是使用CPU 如果是0则全部是 IO 操作。 -L IO_LENGTH 指定 I/0 需要的时间。
-
./process-run.py -l 5:100,5:100有两个进程 各需要五个时间片的 CPU 操作
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结果，很明显需要 5+5=10 个时间片。CPU 占用率是 100%。
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
Stats: Total Time 10
Stats: CPU Busy 10 (100.00%)
Stats: IO Busy 0 (0.00%)-
./process-run.py -l 4:100,1:0两个进程 一个需要 4 个时间片的 CPU 一个需要 一个 IO 请求并等待结束。I/O 操作默认需要 5 个时间片。（README里没看到。代码里看到的…）
Produce a trace of what would happen when you run these processes:
Process 0
cpu
cpu
cpu
cpu
Process 1
io结果
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 DONE
Stats: Total Time 10
Stats: CPU Busy 5 (50.00%)
Stats: IO Busy 4 (40.00%)P0 先执行四个时间片，P1 再执行一个 IO 操作，然后等待 5 个时间片，并在第 5 个时间片结束。
所以 P0 的 CPU 使用率 5/10, IO 使用率 5/10
-
./process-run.py -l 1:0,4:100将第二题的两个进程倒过来。看到下面 Important behaviors 有说，当一个进程结束或者发起I/O操作后，会进行进程的切换。
Produce a trace of what would happen when you run these processes:
Process 0
io
Process 1
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)结果 ./process-run.py -l 1:0,4:100 -c -p
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* DONE DONE
Stats: Total Time 6
Stats: CPU Busy 5 (83.33%)
Stats: IO Busy 4 (66.67%)因为在等待 IO 的时候 另一个进程在占用 CPU 进行计算，所以提高了 CPU 和 IO 的使用率
-
./process-run.py -l 1:0,4:100 -S SWITCH_ON_END-S有两个选项，SWITCH_ON_IO,SWITCH_ON_END代表进程切换的时机。SWITCH_ON_END表示一个进程结束才切换。默认是SWITCH_ON_IO。
Process 0
io
Process 1
cpu
cpu
cpu
cpu结果 ./process-run.py -l 1:0,4:100 -c -p -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* DONE RUN:cpu 1
7 DONE RUN:cpu 1
8 DONE RUN:cpu 1
9 DONE RUN:cpu 1
Stats: Total Time 9
Stats: CPU Busy 5 (55.56%)
Stats: IO Busy 4 (44.44%)此时在 P0 发起 IO 操作之后 不会切换进程而是会一直等到 P0 结束。所以耗时会更加。注意 IO 结束的最后一个时间片是不占用 CPU 和 IO 的。
./process-run.py -l 1:0,4:100 -c -p -S SWITCH_ON_IO此时其实和题 3 相同 因为SWITCH_ON_IO是默认选项。-
./process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_LATER-I有两个选项，IO_RUN_LATER表 IO 结束之后，等待正在运行的进程结束之后，再进行发起 IO请求的进程。为默认值。IO_RUN_IMMEDIATE表示 IO 结束之后，立刻切换到发起 IO 的进程。
Process 0
io
io
io
Process 1
cpu
cpu
cpu
cpu
cpu
Process 2
cpu
cpu
cpu
cpu
cpu
Process 3
cpu
cpu
cpu
cpu
cpu结果 ./process-run.py -l 3:0,5:100,5:100,5:100 -c -p -S SWITCH_ON_IO -I IO_RUN_LATER
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* READY RUN:cpu READY READY 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 1
18 WAITING DONE DONE DONE 1
19 WAITING DONE DONE DONE 1
20 WAITING DONE DONE DONE 1
21 WAITING DONE DONE DONE 1
22* RUN:io DONE DONE DONE 1
23 WAITING DONE DONE DONE 1
24 WAITING DONE DONE DONE 1
25 WAITING DONE DONE DONE 1
26 WAITING DONE DONE DONE 1
27* DONE DONE DONE DONE
Stats: Total Time 27
Stats: CPU Busy 18 (66.67%)
Stats: IO Busy 12 (44.44%)每次当前进程结束，会回到 IO 发起的进程，也就是 P0。最后当 P1 P2 P3 都结束的时候，还在等待 IO 。所以猜想每次 IO 结束都立刻返回发起 IO 的进程，是不是可以提高 CPU 使用率。
- 情况和 6 一样。查看结果
./process-run.py -l 3:0,5:100,5:100,5:100 -c -p -S SWITCH_ON_IO -I IO_RUN_IMMEDIATE可以发现上面猜想的正确性。
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* RUN:io READY READY READY 1
7 WAITING RUN:cpu READY READY 1 1
8 WAITING DONE RUN:cpu READY 1 1
9 WAITING DONE RUN:cpu READY 1 1
10 WAITING DONE RUN:cpu READY 1 1
11* RUN:io DONE READY READY 1
12 WAITING DONE RUN:cpu READY 1 1
13 WAITING DONE RUN:cpu READY 1 1
14 WAITING DONE DONE RUN:cpu 1 1
15 WAITING DONE DONE RUN:cpu 1 1
16* DONE DONE DONE RUN:cpu 1
17 DONE DONE DONE RUN:cpu 1
18 DONE DONE DONE RUN:cpu 1
Stats: Total Time 18
Stats: CPU Busy 18 (100.00%)
Stats: IO Busy 12 (66.67%)