Hệ điều hành

Phần 1: Hệ điều hành
Chương 3
What is an operating system
History of operating systems
The operating system zoo
Computer hardware review
Operating system concepts
System calls
Tài liệu tham khảo: chương 1 của quyển
Andrew S. Tanenbaum: Modern Operating Systems, 2nd ed, Prentice Hall
http://www.prenhall.com/divisions/esm/app/author_tanenbaum/custom/mos2e/

Giới thiệu
A computer system consists of
hardware
system programs
application programs
Hệ điều hành là gì?
It is an extended machine
Hides the messy details which must be performed
Presents user with a virtual machine, easier to use (by using system calls)
It is a resource manager
Multiplexing the resource in time: each program gets time with the resource, e.g. CPU, printer
Multiplexing the resource in space: each program gets space on the resource, e.g. memory, disk
Lịch sử hệ điều hành
First generation 1945 - 1955
vacuum tubes, plug boards
Inventors: Aiken (USA), Zuse (Germany)
Second generation 1955 - 1965
transistors
batch systems
Third generation 1965 – 1980
ICs (Integrated Circuits)
multiprogramming, spooling, time-sharing
Fourth generation 1980 – present
LSI (Large Scale Integration)
Hệ điều hành cho PC
Lịch sử hệ điều hành
Thế hệ thứ 2
Early batch system (hệ thống xử lý bó)
bring cards to 1401
read cards to tape
put tape on 7094 that does computing
put tape on 1401 that prints output
Lịch sử hệ điều hành
Thế hệ thứ 2
Structure of a typical FMS job
(FMS: Fortran Monitor System, hệ điều hành của IBM cho mainframe 7094)
Lịch sử hệ điều hành
Thế hệ thứ 3
Multiprogramming system
Spooling (Simultaneous Peripheral Operation On Line)
Time sharing
(Các vùng của bộ nhớ)
OS/360 của IBM
MULTICS (MIT, Bell Labs)
Lịch sử hệ điều hành
Thế hệ thứ 4
1974, first microcomputer
Intel 8080, first general-purposed 8-bit CPU
floppy disk
CP/M (Control Program for Microcomputers)
early 1980s, IBM PC
DOS (Disk Operating System)
MS-DOS (Microsoft Disk Operating System)
1983, IBM PC/AT (Intel 80286 CPU)
1985-1995, Windows on top of MS-DOS
Pentium PC
UNIX, Linux, Windows 2000
X Windows system (UNIX, Linux)
The Operating System Zoo
Mainframe operating systems High-end Web servers
OS/390
Server operating systems Web service, file service
UNIX, Linux, Windows 2000
Multiprocessor operating systems
Personal computer operating systems
Linux, Windows XP, Macintosh
Real-time operating systems Control systems
VxWorks, QNX
Embedded operating systems Mobile phones
uCLinux, PalmOS, Windows CE
Smart card operating systems Smart cards
Computer Hardware Review
Các thành phần của một PC đơn giản
Monitor
Bus
Computer Hardware Review
Processors
Special registers
Program counter
Stack pointer
Program Status Word (PSW)
kernel mode
user mode
TRAP instruction
System call

Computer Hardware Review
Memory (1)
Typical memory hierarchy
numbers shown are rough approximations
Computer Hardware Review
Memory (2)
Cấu trúc của một ổ đĩa cứng
Computer Hardware Review
Memory (3)
Một cặp base-limit
Hai cặp base-limit
Computer Hardware Review
I/O Devices
(a) Steps in starting an I/O device and getting interrupt
(b) Interrupt processing
Device driver là gì?
Computer Hardware Review
Buses
Cấu trúc của một hệ thống Pentium
IDE bus
SCSI bus
Các ý niệm chủ đạo trong hệ điều hành
Quá trình (process)
Deadlock
Quản lý bộ nhớ (memory management)
Nhập/xuất dữ liệu (input/output)
Tập tin (file)
An ninh dữ liệu (security)
The shell
Các ý niệm chủ đạo trong hệ điều hành
Quá trình
Một cây quá trình (process tree)
A đã tạo hai quá trình con, B và C
B đã tạo ba quá trình con, D, E, và F
Quá trình là một chương trình đang thực thi
Các ý niệm chủ đạo trong hệ điều hành
Deadlocks
Khi hai hay nhiều quá trình tương tác với nhau thì chúng có thể lâm vào tình trạng deadlock
Ví dụ: một máy tính với một ổ băng từ và một ổ ghi CD. Hai quá trình A và B muốn ghi lên CD từ dữ liệu trên băng từ
Quá trình A yêu cầu và được cấp phát ổ băng từ
Quá trình B yêu cầu và được cấp phát ổ ghi CD
Quá trình A yêu cầu ổ ghi CD, bị tạm dừng
Quá trình B yêu cầu ổ băng từ, bị tạm dừng
Các ý niệm chủ đạo trong hệ điều hành
Files (1)
File system for a university department
(Thư mục gốc)
Path name cho một file
/Faculty/Prof.Brown/Courses/CS101
Các ý niệm chủ đạo trong hệ điều hành
Files (2)
Before mounting (gắn),
files on floppy are inaccessible
After mounting floppy on b,
files on floppy are part of file hierarchy
Trong UNIX
Floppy disk
Các ý niệm chủ đạo trong hệ điều hành
Files (3)
Two processes connected by a pipe
Trong UNIX
Các ý niệm chủ đạo trong hệ điều hành
Shell
Ví dụ một shell: UNIX command interpreter
Là chương trình đợi và nhận lệnh của người dùng từ terminal, gọi system call tương ứng với lệnh
shell không phải là một phần của hệ điều hành!
System Calls
There are 11 steps in making the system call
read(fd, buffer, nbytes)
System Calls
Process Management





System Calls
Process Management (2)
A stripped down shell:

while (TRUE) { /* repeat forever */
type_prompt( ); /* display prompt */
read_command (command, parameters) /* input from terminal */

if (fork() != 0) { /* fork off child process */
/* Parent code */
waitpid( -1, &status, 0); /* wait for child to exit */
} else {
/* Child code */
execve (command, parameters, 0); /* execute command */
}
}
System Calls
Process Management (3)
Processes have three segments: text, data, stack
Trong UNIX
System Calls
File Management
(file: tập tin)
System Calls
Directory Management
(directory: thư mục)
System Calls
Directory Management (2)
(a) File system before the mount
(b) File system after the mount
Trong UNIX
System Calls
Miscellaneous Tasks
System Calls
The Windows Win32 API
Some Win32 API calls
(API: Application Programming Interface)
Metric Units
The metric prefixes
Quá trình
Nói thêm về
Mô hình của quá trình
(a) Multiprogramming of four programs
(b) Conceptual model of 4 independent, sequential processes
(c) Only one program active at any instant
Mô hình: kết quả của sự trừu tượng hóa (rút trích các thông tin chính yếu),
thường được biểu diễn bằng một sơ đồ.
Tạo quá trình
Các biến cố chính gây ra việc tạo quá trình
System initialization
Execution of a process creation system call by a running process
User request to create a new process
Initiation of a batch job
Sự chấm dứt của quá trình
Quá trình chấm dứt dưới một trong các điều kiện sau
Normal exit (voluntary, tự ý)
Error exit (voluntary)
Fatal error (involuntary, không tự ý)
Killed by another process (involuntary)
Process Hierarchies
Parent creates a child process, child processes can create its own process
Forms a hierarchy
UNIX calls this a "process group"
Windows has no concept of process hierarchy
all processes are created equal
Trong UNIX
Các trạng thái của quá trình (1)
Possible process states
running
blocked
ready
Transitions between states shown
Các trạng thái của quá trình (2)
Lowest layer of process-structured OS
handles interrupts, scheduling
Above that layer are sequential processes
Hiện thực quá trình (1)
Fields of a typical process table entry
process table
process table entry (= process control block)
Hiện thực quá trình (2)
Skeleton of what lowest level of OS does when an
interrupt occurs
Định thời
Nói thêm về
Giới thiệu về định thời
Mục tiêu của giải thuật định thời dưới các tình huống khác nhau
(Hệ thống tương tác)
(Hệ thống thời gian thực)
(Hệ thống xử lý bó)
Định thời trong hệ thống xử lý bó
An example of shortest job first scheduling
Running four jobs in the original order
Running them in shortest job first order

Đơn vị: phút
Định thời trong hệ thống tương tác (1)
Round Robin Scheduling (Định thời xoay vòng)
list of runnable processes
list of runnable processes after B uses up its time quantum
Định thời trong hệ thống tương tác (2)
A scheduling algorithm with four priority classes:
Round-robin scheduling within each class
Run the processes of the higher priority classes first
Quản lý bộ nhớ
Nói thêm về
Basic memory management
Swapping
Virtual memory
Segmentation
Quản lý bộ nhớ
Ideally programmers want memory that is
large
fast
nonvolatile (bền vững)
Memory hierarchy
small amount of fast, expensive memory – cache
some medium-speed, medium-price main memory
gigabytes of slow, cheap disk storage
Memory manager handles the memory hierarchy
Basic Memory Management
i.e. without Swapping or Paging
Monoprogramming: three simple ways of organizing memory with an operating system and one user process
Multiprogramming with Fixed Partitions
Fixed memory partitions
separate input queues for each partition
single input queue
Swapping
Memory allocation changes as
processes come into memory: process A is swapped in from disk, Fig. (g)
leave memory: process A is swapped out to disk, Fig. (d)
Shaded regions are unused memory
Bộ nhớ ảo
Phân trang (Paging) (1)
The position and function of the MMU
(Memory Management Unit)
Bộ nhớ ảo: programs may be only partially in main memory
Phân trang (2)
The relation between
virtual addresses
and physical
memory addres-
ses is given by
the page table
Bảng các trang (Page table)
Internal operation of MMU with 16 4 KB pages
Phân đoạn bộ nhớ (1)
One-dimensional address space with growing tables
One table may bump into another

Tables during a compilation
Phân đoạn bộ nhớ (2)
Allows each table to grow or shrink, independently
Phân đoạn bộ nhớ (3)
So sánh phân trang và phân đoạn
Implementation of Segmentation
Paging the segments: the virtual memory on the Intel Pentium

Hệ thống file
Nói thêm về
Files
Directories
File system implementation
Example file systems
Long-term Information Storage
Yêu cầu đặt ra cho việc lưu trữ thông tin lâu dài
Must be possible to store large amounts of data
Information stored must survive the termination of the process using it
Multiple processes must be able to access the information concurrently

Lời giải: lưu thông tin trên đĩa cứng (hay CD-ROM,…) dưới dạng các tập tin (file).
File, dưới cái nhìn của người sử dụng
Tên (naming)
Cấu trúc
Kiểu
Truy cập file
Thuộc tính
Thao tác lên file

File Naming
Typical file extensions
File Structure
Three kinds of files
byte sequence
record sequence
tree
File Types
(a) An executable file (b) An archive
Truy cập file (File Access)
Sequential access
read all bytes/records from the beginning
cannot jump around, could rewind or back up
convenient when medium was mag tape
Random access
bytes/records read in any order
essential for data base systems
read can be …
move file marker (seek), then read or …
read and then move file marker
File Attributes
Possible file attributes
Các thao tác lên tập tin
Create
Delete
Open
Close
Read
Write

Append
Seek
Get attributes
Set Attributes
Rename
An Example Program Using File System Calls (1/2)
An Example Program Using File System Calls (2/2)


Directories (Folders)
Single-Level Directory Systems
Example of a single-level directory system that
contains 4 files
owned by 3 different people, A, B, and C
Được sử dụng trên máy CDC 6600
Two-level Directory Systems
Letters indicate owners of the directories and files
Hierarchical Directory Systems
A hierarchical directory system
A UNIX directory tree
Path names cho file trong một directory tree
/usr/lib/dict
Các thao tác lên thư mục
Create
Delete
Opendir
Closedir
Readdir
Rename
Link
Unlink

Trong UNIX
File và directory dưới cái nhìn của người hiện thực
Layout của file system
Hiện thực file
Hiện thực directory

File System Implementation
A possible file system layout
Implementing Files (1)
(a) Contiguous allocation of disk space for 7 files
(b) State of the disk after files D and E have been removed
Implementing Files (2)
An example i-node
Implementing Directories
A simple directory
fixed size entries
disk addresses and attributes in directory entry
(b) Directory in which each entry just refers to an i-node
The MS-DOS File System
The MS-DOS directory entry
The UNIX V7 File System (1)
A UNIX V7 directory entry
The UNIX V7 File System (2)
A UNIX i-node
The UNIX V7 File System (3)
The steps in looking up /usr/ast/mbox