Time | Notes | ||
---|---|---|---|
1 | Running | Ready | Process |
2 | Running | Ready | |
3 | Running | Ready | |
4 | Running | Ready | |
5 | Running | ||
6 | Running | ||
7 | Running | ||
8 | Running | Process |
Time | Notes | ||
---|---|---|---|
1 | Running | Ready | |
2 | Running | Ready | |
3 | Running | Ready | Process |
4 | Blocked | Running | Process |
5 | Blocked | Running | so |
6 | Blocked | Running | |
7 | Ready | Running | I/O done |
8 | Ready | Running | Process |
9 | Running | ||
10 | Running | Process |
OS | Program |
---|---|
Create entry for process list | |
Allocate memory for program | |
Load program into memory | |
Set up stack with argc/argv | |
Clear registers | |
Execute call main() | |
Run main() | |
Execute return from main | |
Free memory of process | |
Remove from process list |
OS @ boot (kernel mode) | Hardware | |
---|---|---|
initialize trap table | remember address of... syscall handler | |
OS @ run (kernel mode) | Hardware | Program (user mode) |
Create entry for process list Allocate memory for program Load program into memory Setup user stack with argv Fill kernel stack with reg/PC return-from-trap | ||
restore regs (from kernel stack) move to user mode jump to main | ||
Run main() | ||
Call system call trap into OS | ||
save regs (to kernel stack) move to kernel mode jump to trap handler | ||
Handle trap Do work of syscall return-from-trap | ||
restore regs (from kernel stack) move to user mode jump to PC after trap | ||
Free memory of process | ||
Remove from process list | ||
Figure 6.2: Limited Direct Execution Protocol |
OS @ boot (kernel mode) | Hardware | |
---|---|---|
initialize trap table start interrupt timer | remember addresses of... syscall handler timer handler start timer interrupt CPU in X ms | |
OS @ run (kernel mode) | Hardware | Program (user mode) |
Process A | ||
timer interrupt save regs(A) | ||
Handle the trap Call switch () routine save regs(A) | ||
restore regs(B) | ||
Process B |
Pass(A) (stride=100) | Pass(B) (stride=200) | Pass(C) (stride=40) | Who Runs? |
---|---|---|---|
0 | 0 | 0 | A |
100 | 0 | 0 | B |
100 | 200 | 0 | C |
100 | 200 | 40 | C |
100 | 200 | 80 | C |
100 | 200 | 120 | A |
200 | 200 | 120 | C |
200 | 200 | 160 | C |
200 | 200 | 200 |
Virtual Address | Physical Address | |
---|---|---|
0 | 16 KB | |
1 KB | 17 KB | |
3000 | 19384 | |
4400 | Fault (out of bounds) |
Hardware Requirements | Notes |
---|---|
Privileged mode | Needed to prevent user-mode processes from executing privileged operations |
Base/bounds registers | Need pair of registers per CPU to support address translation and bounds checks |
Ability to translate virtual addresses and check if within bounds | Circuitry to do translations and check limits; in this case, quite simple |
Privileged instruction(s) to update base/bounds | OS must be able to set these values before letting a user program run |
Privileged instruction(s) to register exception handlers | OS must be able to tell hardware what code to run if exception occurs |
Ability to raise exceptions | When processes try to access privileged instructions or out-of-bounds memory |
OS Requirements | Notes |
---|---|
Memory management | Need to allocate memory for new processes; Reclaim memory from terminated processes; Generally manage memory via free list |
Base/bounds management | Must set base/bounds properly upon context switch |
Exception handling | Code to run when exceptions arise; likely action is to terminate offending process |
OS @ boot (kernel mode) | Hardware | (No Program Yet) |
---|---|---|
initialize trap table | ||
remember addresses of... | ||
system call handler | ||
timer handler | ||
illegal mem-access handler | ||
illegal instruction handler | ||
start interrupt timer | ||
start timer; interrupt after X ms | ||
initialize process table | ||
initialize free list |
OS @ run (kernel mode) | Hardware | Program (user mode) |
---|---|---|
To start process A: allocate entry in process table alloc memory for process set base/bound registers return-from-trap (into A) | ||
restore registers of A move to user mode jump to A’s (initial) PC | Process A runs Fetch instruction | |
translate virtual address perform fetch | ||
if explicit load/store: ensure address is legal translate virtual address perform load/store | Execute instruction | |
(A runs...) | ||
Timer interrupt move to kernel mode jump to handler | ||
Handle timer | ||
decide: stop A, run B call switch () routine save regs(A) to proc-struct(A) (including base/bounds) restore regs(B) from proc-struct(B) (including base/bounds) return-from-trap (into B) | ||
restore registers of B move to user mode jump to B’s PC | ||
Process B runs Execute bad load | ||
Load is out-of-bounds; move to kernel mode jump to trap handler | ||
Handle the trap decide to kill process B deallocate B’s memory free B's entry in process table |
Segment | Base | Size |
---|---|---|
Code | 32K | 2K |
Heap | 3K | |
Stack | 28K | 2K |
Segment | Base | Size (max 4K) | Grows Positive? |
---|---|---|---|
32K | 2K | 1 | |
3K | 1 | ||
28K | 2K | 0 |
Segment | Base | Size (max 4K) | Grows Positive? | Protection |
---|---|---|---|---|
32K | 2K | 1 | Read-Execute | |
34K | 3K | 1 | Read-Write | |
28K | 0 | Read-Write |
VPN | PFN | valid | prot |
---|---|---|---|
10 | 100 | 1 | rwx |
0 | |||
170 | 1 | ||
0 |
VPN | PFN | valid | prot | ASID |
---|---|---|---|---|
10 | 100 | 1 | rwx | 1 |
0 | ||||
10 | 170 | 1 | rwx | 2 |
l | 0 |
VPN | PFN | valid | prot | ASID |
---|---|---|---|---|
10 | 101 | 1 | 1 | |
0 | ||||
50 | 101 | 1 | 2 | |
0 | 1 |
VPN | G | ASID | |
---|---|---|---|
PFN | CDV |
PFN | valid | prot | present | dirty |
---|---|---|---|---|
10 | 1 | 1 | 0 | |
0 | - | - | ||
- | 0 | - | - | |
- | 0 | - | ||
23 | 1 | TW- | 1 | 1 |
- | 0 | - | - | |
0 | - | |||
- | 0 | - | - | |
- | 0 | - | - | |
0 | - | |||
- | 0 | - | ||
- | 0 | |||
- | 0 | - | - | |
0 | - | |||
28 | 1 | rw- | 1 | 1 |
4 | 1 | rw- | 1 | 1 |
0000 0000 | code |
0000 0001 | code |
0000 0010 | (free) |
0000 0011 | (free) |
0000 0100 | heap |
0000 0101 | heap |
0000 0110 | (free) |
0000 0111 | (free) |
PFN | valid? | PFN | valid | prot | PFN | valid | prot |
---|---|---|---|---|---|---|---|
100 | 1 | 10 | 1 | r-x | 0 | ||
0 | 23 | 1 | 0 | ||||
| | 0 | 0 | 0 | ||||
0 | 0 | 0 | 1 | ||||
0 | 80 | 1 | rw- | 0 | |||
0 | 59 | 1 | rw- | 0 | |||
0 | 0 | 0 | |||||
0 | 0 | 0 | |||||
0 | 0 | 0 | |||||
0 | 0 | 0 | |||||
0 | 0 | 0 | |||||
0 | 0 | 0 | |||||
0 | 0 | 0 | |||||
0 | 0 | 1 | 0 | ||||
0 | 0 | 55 | 1 | rw- | |||
101 | 1 | 0 | 45 | 1 | rw- |
Physical Memory | PFN 0 | PFN 1 | PFN 2 | PFN 3 |
---|---|---|---|---|
Proc 0 [VPN 0] | Proc 1 [VPN 2] | Proc 1 [VPN 3] | Proc 2 [VPN 0] |
Access | Hit/Miss? | Evict | Cache State |
---|---|---|---|
0 | Miss | 0 | |
1 | Miss | 0,1 | |
2 | Miss | ||
0 | Hit | ||
1 | Hit | ||
3 | Miss | 2 | |
0 | Hit | ||
3 | Hit | ||
1 | Hit | ||
2 | Miss | 3 | |
1 | Hit | ||
E: 2012年12月1日出版社区 |
Access | Hit/Miss? | Evict | Resulting Cache State |
---|---|---|---|
0 | Miss | First-in | |
1 | Miss | First-in | |
2 | Miss | First-in | |
0 | Hit | First-in | |
1 | Hit | First-in | |
3 | Miss | 0 | First-in |
0 | Miss | 1 | First-in |
3 | Hit | First-in | |
1 | Miss | 2 | First-in |
2 | Miss | 3 | First-in |
1 | Hit | First-in |
Access | Hit/Miss? | Evict | Resulting Cache State |
---|---|---|---|
0 | Miss | 0 | |
1 | Miss | 0, 1 | |
2 | Miss | 0, 1, 2 | |
0 | Hit | 0, 1, 2 | |
1 | Hit | 0, 1, 2 | |
3 | Miss | 0 | |
0 | Miss | 1 | |
3 | Hit | ||
1 | Miss | 3 | |
2 | Hit | ||
1 | Hit |
Access | Hit/Miss? | Evict | Resulting Cache State |
---|---|---|---|
0 | Miss | ||
1 | Miss | ||
2 | Miss | ||
0 | Hit | ||
1 | Hit | ||
3 | Miss | 2 | |
0 | Hit | ||
3 | Hit | ||
1 | Hit | ||
2 | Miss | 0 | |
1 | Hit |
main | Thread 1 | Thread2 |
---|---|---|
starts running | ||
prints "main: begin" | ||
creates Thread 1 | ||
creates Thread 2 | ||
waits for T1 | ||
runs prints "A" | ||
returns | ||
waits for T2 | ||
runs | ||
prints "B" returns | ||
prints "main: end" | ||
Figure 26.2: Thread Trees (1) |
OS | Thread 2 | (after instruction) | ||||
---|---|---|---|---|---|---|
Thread 1 | PC | eax | counter | |||
before critical section | 100 | 0 | 50 | |||
mov 8049a1c,&eax | 105 | 50 | 50 | |||
add $0x1, &eax | 108 | 51 | 50 | |||
interrupt | ||||||
save T1 | ||||||
restore T2 | 100 | 0 | 50 | |||
mov | 8049a1c, feax | 105 | 50 | 50 | ||
add | $0x1, feax | 108 | 51 | 50 | ||
mov | &eax, 8049a1c | 113 | 51 | 51 | ||
interrupt | ||||||
save T2 | ||||||
restore | 108 | 51 | 51 | |||
nov &eax,8049a1c | 113 | 51 | 51 |
Time | |||||
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 1 | 0 |
2 | 1 | 0 | 2 | 1 | 0 |
3 | 2 | 0 | 3 | 1 | 0 |
4 | 3 | 0 | 3 | 2 | 0 |
5 | 4 | 1 | 3 | 3 | 0 |
6 | 1 | 3 | 4 | 5 | |
7 | 0 | 2 | 4 |
State | State | State | SU | Comment | |||
---|---|---|---|---|---|---|---|
c1 | Run | Ready | Ready | 0 | Nothing to get | ||
c2 | Run | Ready | Ready | 0 | |||
c3 | Sleep | Ready | Ready | 0 | |||
Sleep | Ready | p1 | Run | 0 | |||
Sleep | Ready | p2 | Run | 0 | |||
Sleep | Ready | p4 | Run | 1 | Buffer now full | ||
Ready | Ready | p5 | Run | 1 | |||
Ready | Ready | p6 | Run | 1 | |||
Ready | Ready | p1 | Run | 1 | |||
Ready | Ready | p2 | Run | 1 | |||
Ready | Ready | p3 | Sleep | 1 | Buffer full; sleep | ||
Ready | c1 | Run | Sleep | 1 | |||
Ready | c2 | Run | Sleep | 1 | |||
Ready | c4 | Run | Sleep | 0 | ... and grabs data | ||
Ready | c5 | Run | Ready | 0 | |||
Ready | c6 | Run | Ready | 0 | |||
c4 | Run | Ready | Ready | 0 | Oh oh! No data |
State | State | State | SU | Comment | |||
---|---|---|---|---|---|---|---|
c1 | Run | Ready | Ready | 0 | Nothing to get | ||
c2 | Run | Ready | Ready | 0 | |||
c3 | Sleep | Ready | Ready | 0 | |||
Sleep | c1 | Run | Ready | 0 | |||
Sleep | c2 | Run | Ready | 0 | |||
Sleep | c3 | Sleep | Ready | 0 | Nothing to get | ||
Sleep | Sleep | p1 | Run | 0 | |||
Sleep | Sleep | p2 | Run | 0 | |||
Sleep | Sleep | p4 | Run | 1 | Buffer now full | ||
Ready | Sleep | p5 | Run | 1 | |||
Ready | Sleep | p6 | Run | 1 | |||
Ready | Sleep | p1 | Run | 1 | |||
Ready | Sleep | p2 | Run | 1 | |||
Ready | Sleep | p3 | Sleep | 1 | Must sleep (full) | ||
c2 | Run | Sleep | Sleep | 1 | Recheck condition | ||
c4 | Run | Sleep | Sleep | 0 | |||
c5 | Run | Ready | Sleep | 0 | Oops! Woke | ||
c6 | Run | Ready | Sleep | 0 | |||
c1 | Run | Ready | Sleep | 0 | |||
c2 | Run | Ready | Sleep | 0 | |||
c3 | Sleep | Ready | Sleep | 0 | Nothing to get | ||
Sleep | c2 | Run | Sleep | 0 | |||
Sleep | c3 | Sleep | Sleep | 0 | Everyone asleep... | ||
Value of Semaphore | Thread 0 | Thread 1 |
---|---|---|
1 | ||
1 | call sem_wait ( ) | |
0 | sem_wait () returns | |
0 | (crit sect) | |
0 | call sem_post ( ) | |
1 | sem_post () returns |
Val | Thread 0 | State | Thread 1 | State |
---|---|---|---|---|
1 | Run | Ready | ||
1 | call sem_wait ( ) | Run | Ready | |
0 | sem_wait () returns | Run | Ready | |
0 | (crit sect begin) | Run | Ready | |
0 | Interrupt; Switch | Ready | Run | |
0 | Ready | call sem_wait ( ) | Run | |
-1 | Ready | decr sem | Run | |
-1 | Ready | (sem<0) | Sleep | |
-1 | Run | Switch | Sleep | |
-1 | (crit sect end) | Run | Sleep | |
-1 | call sem_post ( ) | Run | Sleep | |
0 | incr sem | Run | Sleep | |
0 | wake ( T1 ) | Run | Ready | |
0 | sem_post ( ) returns | Run | Ready | |
0 | Interrupt; Switch | Ready | Run | |
0 | Ready | sem_wait ( ) returns | Run | |
0 | Ready | (crit sect) | Run | |
0 | Ready | call sem_post ( ) | Run | |
1 | Ready | sem_post () returns | Run |
Val | Parent | State | Child | State |
---|---|---|---|---|
0 | create(Child) | Run | (Child exists, can run) | Ready |
0 | call sem_wait ( ) | Run | Ready | |
-1 | decr sem | Run | Ready | |
-1 | (sem<0) | Sleep | Ready | |
-1 | Switch | Sleep | child runs | Run |
-1 | Sleep | call sem_post ( ) | Run | |
0 | Sleep | inc sem | Run | |
0 | Ready | wake (Parent) | Run | |
0 | Ready | sem_post () returns | Run | |
0 | Ready | Ready | ||
0 | sem_wait () returns | Run | Ready |
Val | Parent | State | Child | State |
---|---|---|---|---|
0 | create(Child) | Run | (Child exists; can run) | Ready |
0 | Ready | child runs | Run | |
0 | Ready | call sem_post ( ) | Run | |
1 | Ready | inc sem | Run | |
1 | Ready | wake (nobody) | Run | |
1 | Ready | sem_post ( ) returns | Run | |
1 | parent runs | Run | Readv | |
1 | call sem_wait ( ) | Run | Ready | |
0 | decrement sem | Run | Ready | |
0 | (sem≥0) | Run | Ready | |
0 | sem_wait () returns | Run | Ready |
Application | What it does | Non-Deadlock | Deadlock |
---|---|---|---|
MySQL | Database Server | 14 | 9 |
Apache | Web Server | 13 | 4 |
Mozilla | Web Browser | 41 | 16 |
OpenOffice | Office Suite | 6 | 2 |
Total | 74 | 31 |
T1 | T2 | T3 | T4 | |
L1 | yes | yes | no | no |
L2 | yes | yes | yes | no |
CPU 1 | T3 | T4 | |
---|---|---|---|
CPU 2 | T1 | T2 |
T1 | T2 | T3 | T4 | |
L1 | yes | yes | yes | no |
L2 | yes | yes | yes | no |
Cheetah 15K.5 | Barracuda | |
---|---|---|
Capacity | 300 GB | 1 TB |
RPM | 15,000 | 7,200 |
Average Seek | 9 ms | |
Max Transfer | 125 MB/s | 105 MB/s |
Platters | 4 | 4 |
Cache | 16 MB | 16/32 MB |
Connects via | SCSI | SATA |
Cheetah | Barracuda | |
---|---|---|
0.66 MB/s | 0.31 MB/s | |
125 MB/s | 105 MB/s |
Disk 0 | Disk 1 | Disk 2 | Disk 3 |
---|---|---|---|
0 | 1 | 2 | 3 |
4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 |
Disk 0 | Disk 1 | Disk 2 | Disk 3 | - |
---|---|---|---|---|
0 | 2 | 4 | 6 | chunk size: |
1 | 3 | 5 | 7 | 2 blocks |
8 | 10 | 12 | 14 | |
9 | 11 | 13 | 15 |
Disk 0 | Disk 1 | Disk 2 | Disk 3 |
---|---|---|---|
0 | 0 | 1 | 1 |
2 | 2 | 3 | 3 |
4 | 4 | 5 | 5 |
6 | 6 | 7 | 7 |
Disk 0 | Disk 1 | Disk 2 | Disk 3 | Disk 4 |
---|---|---|---|---|
0 | 1 | 2 | 3 | P0 |
4 | 5 | 6 | 7 | P1 |
8 | 9 | 10 | 11 | P2 |
12 | 13 | 14 | 15 | P3 |
C0 | C1 | C2 | C3 | P |
---|---|---|---|---|
0 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 |
Block0 | Block1 | Block2 | Block3 | Parity |
---|---|---|---|---|
00 | 10 | 11 | 10 | 11 |
10 | 01 | 00 | 01 | 10 |
Disk 0 | Disk 1 | Disk 2 | Disk 3 | Disk 4 |
---|---|---|---|---|
0 | 1 | 2 | 3 | P0 |
*4 | 5 | 6 | 7 | +P1 |
8 | 9 | 10 | 11 | P2 |
12 | *13 | 14 | 15 | +P3 |
Disk 0 | Disk 1 | Disk 2 | Disk 3 | Disk 4 |
---|---|---|---|---|
0 | 1 | 2 | 3 | P0 |
5 | 6 | 7 | P1 | 4 |
10 | 11 | P2 | 8 | 9 |
15 | P3 | 12 | 13 | 14 |
P4 | 16 | 17 | 18 | 19 |
RAID-0 | RAID-1 | RAID-4 | RAID-5 | |
---|---|---|---|---|
Capacity | ||||
Reliability | 0 | 1 (for sure) | 1 | 1 |
Throughput | ||||
Sequential Read | ||||
Sequential Write | ||||
Random Read | ||||
Random Write | ||||
Latency | ||||
Read | ||||
Write |