操作系统：原理与设计

.2 os prerequisites 50–125
2.1 important software resources to be managed by os 50
2.2 interaction with os in mainframe systems (interrupts in general) 55
2.2.1 the program status word 55
2.2.2 different fields of psw 55
2.2.3 controlling i/o 57
2.2.4 the interrupt concept 60
2.2.5 interrupt priority 65
2.2.6 what other manufacturers (other than ibm) do? 66
2.2.7 interrupt cycle 67
2.2.8 differences between subroutine call and interrupt scheme 68
2.3 example from pc environment and related discussion 69
2.3.1 different ways to control pc hardware 69
2.3.2 accessing the bios and dos 71
2.4 current ‘state-of-the-art’ scenario in os design 75
2.5 fundamental concepts related to ipc 100
2.5.1 message queues 102
2.5.2 semaphores 111
2.5.3 shared memory 120
summary 124
exercises 124
3 concurrent processing126–194
3.1 introduction to concurrent processing 126
3.2 process concept 127
3.3 introduction to process control block 128
3.4 interaction of user’s process with the system 139
3.4.1 exec sys 140
3.5 introduction to concurrent program 144
3.6 distinction between a procedure call and a process creation 145
3.7 introduction to process environment 148
3.7.1 introduction to process id 148
3.7.2 shells or command interpreter 154
3.8 process state transitions 155
3.9 difference between user, daemon and kernel processes 160
3.10 interprocess communication 161
3.1.01 file and record locking 161
3.10.2 simple pipes and named pipes 188
3.10.3 pipes and sockets 188
3.11 hierarchy of processes 190
3.1.11 process creation 191
3.1.12 processes and threads 191
summary 193
exercises 194
4 scheduling 195–228
4.1 cpu scheduling algorithms 195
4.1.1 allocation of different resources 195
4.1.2 scheduling queues 196
4.1.3 different scheduling algorithms 207
4.1.4 algorithm evaluation 226
summary 227
exercises 228
5 discussion on concurrency control 229–335
5.1 bernstein’s concurrency conditions 229
5.1.1 fork and join construct 230
5.1.2 alternative to fork-join 235
5.2 process states and precedence graphs 238
5.3 dijkstra’s concurrent statement in the form of fork and join constructs 238
5.4 the critical section problem 239
5.4.1 bounded buffer producer–consumer problem 239
5.4.2 critical section problem description and their solution 245
5.5 hardware solution to the critical section problem 264
5.6 new synchronization tool—semaphore 266
5.6.1 usage of semaphores 266
5.7 classical process coordination problems 269
5.7.1 bounded buffer problem 269
5.7.2 the reader’s and writer’s problem 272
5.7.3 dining philosophers’ problem 294
5.7.4 sleeping barber problem 299
5.7.5 cigarette smoker’s problem 307
5.8 language constructs for synchronization and modularization 310
5.8.1 critical regions 311
5.8.2 conditional critical region 313
5.8.3 monitor construct 315
summary 334
exercises 334
6 deadlock 336–361
6.1 introduction 336
6.2 definition of deadlock 337
6.3 deadlock and starvation 338
6.4 resource allocation graph 339
6.5 ways to solve deadlock problem 341
6.5.1 tackling deadlock using deadlock prevention 341
6.5.2 deadlock avoidance 342
6.5.3 deadlock detection 351
6.5.4difference between deadlock detection algorithm (multiple instances of each resource type) and safety algorithm 356
6.5.5 solution of deadlock under different scenarios 357
summary 360
exercises 360
7 main memory management 362–386
7.1 introduction 362
7.2 memory management schemes 363
7.3 partitioned allocation 364
7.4 logical vs physical address space 366
7.4.1address binding 366
7.4.2address translation 367
7.5 simple paging 367
7.6 the role of the long-term scheduler 369
7.6.1problem assignment 369
7.7 implementation of the page table 377
7.8 multiple process using a text editor code 378
7.9 simple segmentation 378
7.10 details of segmentation 379
7.11 combined system 381
7.1.11combination used in ge645 multics system 382
7.12 inner details of segmentation and paging for intel systems 383
summary 385
exercises 386
8 virtual memory technique 387–431
8.1 introduction 387
8.2 overlays technique 388
8.3 virtual memory 389
8.3.1virtual memory concept 389
8.4 demand paging 395
8.4.1performance of demand paging 396
8.5 page replacement algorithm 397
8.5.1fifo (simplest page replacement algorithm is first in first out) 398
8.5.2optimal replacement 400
8.5.3least recently used (lru) algorithm 405
8.5.4second chance replacement (with the help of reference bit) 422
8.5.5ad hoc page replacement algorithms 423
8.6 free frame allocation algorithm 424
8.6.1equal allocation 424
8.6.2proportional allocation (according to their needs rather than equal) 424
8.7 thrashing 425
8.8 working set 426
8.8.1 prepaging 427
8.8.2 i/o interlock 427
8.8.3 page size anomaly 427
8.9 program structure 428
summary 429
exercises 430
9 spooler and disk scheduling432–455
9.1 introduction to the design of a spooling system 432
9.2 relationship between spooling and job scheduling 434
9.2.1 a printer spooler 435
9.3 device management 443
9.4 physical characteristics of disks 443
9.4.1 disks 443
9.5 fcfs disk scheduling 444
9.6 searching an item in the disk with indexed sequential file directory 448
9.6.1 shortest seek time first (sstf) 452
summary 454
exercises 454
10 file system architecture 456–512
10.1 overview 456
10.2 initial notions 457
10.2.1 files 457
10.2.2 directories 457
10.2.3 different types of directories under the unix system 458
10.2.4 the directory and file naming conventions 458
10.2.5 difference between com and exe program 459
10.2.6 abbreviations for path names 460
10.2.7 paths are used 462
10.3 attributes of unix files (for the beginners) 462
10.3.1 the file owner and the group 462
10.3.2 access permissions 463
10.3.3 creating a file 463
10.3.4 removing files 466
10.3.5 maintaining files 466
10.4 file system and their type 467
10.4.1 evolution of file system over the years 468
10.5 introduction of ext2 fs 468
10.5.1 the view of inodes from the point of view of a blocks group 469
10.5.2 the allocated blocks 472
10.5.3 user and group id 473
10.6 virtual file system (vfs) 481
10.6.1 the linux virtual file system layer 481
10.6.2 registration procedures of vfs 481
10.6.3 registering the file systems in kernel 484
10.7 program designs 488
appendix 490
end notes 509
summary 512
exercises 512
11 device driver for operating system 513–549
11.1 introduction 513
11.2 initial notions for the design 514
11.3 interfacing device drivers with the kernel 530
11.3.1 character devices 530
11.3.2 block devices 531
11.3.3 network device 533
11.4 theory to practice 535
summary 548
exercises 548
12 linux kernel and security550–614
12.1 introduction 550
12.2 basics notions 550
12.2.1 what are lkms 550
12.2.2 what are system calls 552
12.2.3 what is kernel symbol table 557
12.2.4 how to transform kernel to user space memory 558
12.2.5 ways to use user space like functions 560
12.2.6 list of daily needed kernel space functions 561
12.2.7 what is kernel daemon 563
12.2.8 creating your own devices 563
12.3 experiments with linux system calls 565
12.3.1 how to intercept syscalls 565
12.3.2 interesting system calls to intercept 566
12.3.3 file system-related hacks 571
12.3.4 process-related hacks 578
12.3.5 network (socket)-related hacks 583
12.3.6 virus writing with lkms 587
12.4 directives to the system administrators for secured system 593
12.4.1 theory and ideas on lkm detector 593
12.5 the last word on the ‘lkm story’ 613
summary 613
exercises 613
13 role of os towards low power design 615–628
13.1 low power design from various angles 616
13.2 power management in embedded linux platform 618
13.2.1 dynamic power management 618
13.2.2 main generic points in the low power design 621
13.2.3 d-bus interface 627
13.2.4 hotplug mechanism 627
summary 628
exercises 628
bibliography629–634
index 635–640