Bài giảng Hệ điều hành - Chương 2: Khái niệm về quá trình - Lê Ngọc Minh

 danh duy nhất (unique process identifier)
 – Cấp phát không gian nhớ cho process image.
 – Khởi tạo process control block (PCB)
 » Một số giá trị mặc định (ví dụ: trạng thái=New, không có thiết
 bị I/O, không mở files...)
 – Thiết lập các mối liên hệ cần thiết
 » Ví dụ: thêm process mới vào linked list của hàng đợi định thời
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.31-
 Mối quan hệ cha/con 
‰ Process cha tạo ra các process con, các process con 
 tạo ra nhiều process khác,... và cứ như thế tạo thành
 một cây process trong hệ thống.
‰ 3 cách chia sẻ tài nguyên (resource sharing)
 – Process cha và con chia sẻ mọi tài nguyên
 – Process con chia sẻ một phần tài nguyên của cha
 – Process cha và con không chia sẻ tài nguyên nào
‰ Trình tự thực thi
 – Process cha và con thực thi đồng thời (concurrently)
 – Process cha đợi đến khi các process con kết thúc.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.32-
 16
 Cây process trong UNIX
 root pid= 0
 pid= 1
 pagedaem on sw apper init
 user 1 user 2 user 3
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.33-
 Mối quan hệ cha/con (t.t)
‰ Không gian địa chỉ (address space)
 – Không gian địa chỉ của process con được nhân bản từ cha
 – Không gian địa chỉ của process con được nạp chương trình khác.
‰ Ví dụ trong UNIX/Linux
 – System call fork() tạo một process mới
 – System call execlp() dùng sau fork() để nạp một chương trình
 mới vào không gian nhớ của process mới
 Cha Cha
 fork()
 Process Cha execlp()
 Con Con
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.34-
 17
 Ví dụ tạo process với fork()
 #include 
 int main (int argc, char *argv[])
 {
 int pid;
 /* create a new process */
 pid = fork();
 if ( pid < 0 ) {
 printf(“Fork error\n”);
 exit(-1);
 } 
 else if ( pid == 0 ) 
 {
 printf(“This is child process”);
 execlp(“/bin/ls”, “ls”, NULL);
 exit(0);
 }
 else {
 printf(“This is parent process”);
 exit(0);
 }
 }
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.35-
 Kết thúc thực thi process 
‰ Kết thúc bình thường (normal completion)
‰ Vượt giới hạn thời gian (time limit exceeded)
‰ Không đủ bộ nhớ (memory unavailable)
‰ Xâm phạm vùng nhớ cấm (memory bounds 
 violation)
‰ Lỗi bảo vệ (protection error)
 – Ví dụ: ghi vào file có thuộc tính read-only 
‰ Lỗi số học (arithmetic error): chia cho 0, tràn
 số,...
‰ Time overrun
 – process chờ một sự kiện lâu hơn một khoảng thời
 gian tối đa được xác định trước
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.36-
 18
 Kết thúc thực thi process (t.t)
‰ Thực hiện thất bại tác vụ I/O
‰ Lệnh không hợp lệ (invalid instruction)
‰ Privileged instruction
‰ Sự can thiệp của OS
 – Ví dụ: OS can thiệp khi có deadlock xảy ra
‰ Process cha yêu cầu kết thúc thực thi một
 process con
‰ Process cha kết thúc kéo theo các process con 
 cũng kết thúc
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.37-
 Sự cộng tác giữa các process
‰ Một process thực thi độc lập thì không ảnh hưởng và
 không bị ảnh hưởng bởi các process khác trong hệ
 thống. Tuy nhiên, một số process có thể cộng tác, trao
 đổi dữ liệu với nhau để hoàn thành công việc.
‰ Ưu điểm của sự cộng tác
 – Chia sẻ thông tin 
 – Hiệu suất tính toán cao
‰ Sự cộng tác của các process yêu cầu OS hỗ trợ cơ chế
 giao tiếp (communication) và cơ chế đồng bộ hoạt động
 của các process (synchronization)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.38-
 19
 Bài toán Producer-Consumer 
‰ Mô hình cho sự cộng tác giữa các process, producer tạo
 ra các thông tin, dữ liệu và consumer tiêu thụ, sử dụng
 các dữ liệu đó. Sự trao đổi thông tin thực hiện qua buffer:
 – unbounded-buffer: kích thước buffer không giới hạn.
 – bounded-buffer: kích thước buffer có giới hạn.
‰ Producer và consumer phải được đồng bộ hoạt động
 – Consumer không thể sử dụng một dữ liệu mà producer chưa kịp
 tạo ra.
 – Producer không được tạo thêm sản phẩm khi buffer đã đầy
 (bounded buffer)
‰ Hiện thực buffer
 – Shared memory
 – Interprocess communication facility (IPC)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.39-
 Ví dụ Shared Bounded-Buffer
‰ Shared memory
 #define BUFFER_SIZE 10
 – Shared buffer: danh sách xoay
 vòng. typedefstruct{
 » in: vị trí ghi kết tiếp . . .
 » out: vị trí đọc kế tiếp } item ;
 » BUFFER_SIZE: kích thước item buffer[BUFFER_SIZE];
 của buffer (chỉ được dùng intin = 0;
 BUFFER_SIZE – 1 phần tử)
 intout = 0;
‰ Producer và consumer chia sẻ
 một buffer chung
‰ Programmer phải hiện thực
 đoạn mã truy xuất buffer chung
 cho producer và consumer
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.40-
 20
 Shared Bounded-Buffer (t.t)
 item nextProduced; item nextC onsum ed;
 while (1) {
 while (1) {
 while (in == out)
 while (((in + 1) % ; /* do nothing */
 BUFFER_SIZE) == out) nextC onsum ed = buffer[out];
 ; /* do nothing */ out = (out + 1) % 
 buffer[in] = nextProduced; BUFFER_SIZE;
 }
 in = (in + 1) % 
 BUFFER_SIZE;
 }
 Producer Process C onsum er Process
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.41-
 Interprocess Communication (IPC)
‰ IPC là cơ chế cung cấp bởi OS nhằm giúp các process 
 giao tiếp và đồng bộ hoạt động.
‰ Shared Memory
 – threads
 – mmap()
‰ Message-passing
 – blocking (synchrous) và non-blocking
 – message format, buffer size, 
 – addressing (PID, port, mailbox, )
‰ Files, pipes (FIFOs), sockets
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.42-
 21
 Message-Passing IPC
‰ Cung cấp ít nhất hai phương tiện giao tiếp:
 – send(msg)
 – receive(msg)
‰ Quá trình giao tiếp cần tuân theo một giao thức
 định trước:
 – Thiết lập kênh giao tiếp
 – Trao đổi message 
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.43-
 Hiện thực IPC ?
‰ Làm thế nào để thiết lập các kênh giao tiếp?
‰ Một kênh giao tiếp có thể liên kết với nhiều hơn 2 
 process hay không?
‰ Có thể tạo bao nhiêu kênh giao tiếp giữa các cặp
 process muốn thực hiện giao tiếp?
‰ Dung lượng của một kênh giao tiếp là bao nhiêu?
‰ Kích thước message truyền qua kênh giao tiếp là cố định
 (fixed) hay có tùy ý ?
‰ Kênh giao tiếp theo hai chiều hay một chiều?
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.44-
 22
 Đồng bộ (synchronization)
‰ Blocking hay non-blocking: synchronous hay 
 asynchronous
‰ Blocking send: sender bị block cho đến khi message đã
 được nhận bởi receiver hoặc message đã đến mailbox.
‰ Non-blocking send: sender gửi message và tiếp tục thực
 hiện công việc khác.
‰ Blocking receive: receiver sẽ bị block đến khi có một
 message được gửi đến.
‰ Non-blocking receive: không bị block, tuy nhiên receiver 
 hoặc là nhận được một message hoặc không nhận được
 gì cả.
‰ Rendezvous: blocking-send và blocking-receive
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.45-
 Bộ đệm (buffering)
‰ Tương ứng với mỗi kênh giao tiếp có một hàng
 đợi message. Hiện thực của hàng đợi message 
 là một bộ đệm (buffer) với một trong ba kiểu sau
 – Bộ đệm dung lượng bằng 0 (zero capacity), nghĩa là
 giữa sender và receiver không có hàng đợi, sender 
 phải đợi receiver.
 – Bộ đệm có dung lượng hạn chế (bounded capacity): 
 kích thước bộ đệm là một số hữu hạn định trước. Nếu
 bộ đệm bị đầy thì sender phải đợi.
 – Bộ đệm có dung lượng không hạn chế (unbounded 
 capacity), sender không bao giờ phải đợi
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.46-
 23
 Mô hình giao tiếp Client-Server 
‰ Sockets
‰ Remote Procedure Calls (RPC)
‰ Remote Method Invocation (RMI)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.47-
 Socket
‰ Socket: đầu cuối (endpoint) của một kênh giao tiếp
 – Bao gồm địa chỉ IP và số hiệu port
 » Ví dụ: socket 172.28.11.120:1234 tham chiếu đến port 1234 
 trên máy có địa chỉ IP là 172.28.11.120
 – Ví dụ: FTP server lắng nghe ở port 21, telnet ở port 23, web 
 server tại port 80
 – Quá trình giao tiếp được thực hiện qua một cặp socket.
‰ Socket là cơ chế giao tiếp mức thấp (low-level)
 – Gửi nhận một chuỗi byte dữ liệu không có cấu trúc (unstructured)
‰ Có hai cơ chế giao tiếp qua socket
 – Connectionless
 – Connection-oriented
‰ Berkeley socket (BSD socket): trên Unix/Linux
‰ WinSock: thư viện socket trên họ MS Windows 
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.48-
 24
 Cơ chế gửi/nhận qua Socket 
 Hàm thư viện Diễn giải
 socket() Tạo một socket
 bind() Gắn một địa chỉ cục bộ vào một socket
 listen() Xác định độ lớn/kích thước hàng đợi
 accept() (server) chờ kết nối đến từ client
 connect() (client) kết nối đến một server
 send()/sendto() Gửi dữ liệu qua kênh giao tiếp đã thiết lập
 recv()/recvfrom() Nhận dữ liệu qua kênh giao tiếp
 close() Đóng kết nối
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.49-
 Connectionless Socket 
 Process A Process B
 socket() socket()
 bind() bind()
 sendto()/ sendto()/
 recvfrom () recvfrom ()
 close() close()
» sendto(socket, buffer, buffer_length, flags, destination_address, addr_len)
»recvfrom (socket, buffer, buffer_length, flags, from _address, addr_len)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.50-
 25
 Connection-Oriented Client/Server 
 Server
 socket() bind() listen() accept() recv() send() close()
 Synchronization point
 com m unication
 (rendezvous)
 socket() connect() send() recv() close()
 Client
 » send(socket, buffer, buffer_length, flags)
 »recv(socket, buffer, buffer_length, flags)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.51-
 Remote Procedure Call (RPC)
‰ Cơ chế RPC cho phép thực hiện tác vụ gọi thủ tục
 (procedure call) giữa các process nằm trên hai máy tính
 kết nối bằng hệ thống mạng.
‰ Các vấn đề khi hiện thực RPC
 – Truyền tham số và kết quả trả về của lời gọi thủ tục
 – Chuyển đổi dữ liệu khi truyền trên mạng (data conversion)
 – Kết nối client đến server
 – Biên dịch chương trình
 –Kiểmsoátlỗi
 – Security 
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.52-
 26
 Nguyên lý của RPC
 chờ kết quả trả về
 (suspend)
 CLIENT
 Gọi Remote
 Kết quả trả về
 Procedure
 R equest R eply
SERVER
 (Blocked)Gọi thủ tục cục bộ (Blocked)
 và trả về kết quả
 Trục thời gian
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.53-
 Lưu đồ thực hiện RPC
 CLIENT SERVER
 return reply call request call request return reply
 CLIENT STUB SERVER STUB
 m essage to param eter m essage to param eter
 param eter to m essage param eter to m essage 
 TRANSPORT TRANSPORT
 (OS 1) (OS 2)
 receive send receive send
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.54-
 27
 Truyền tham số trong RPC
‰ Marshaling: qui tắc truyền tham số và chuyển đổi dữ liệu
 trong RPC bao gồm cả đóng gói dữ liệu thành dạng thức
 có thể truyền qua mạng máy tính.
‰ Biểu diễn dữ liệu và kiểm tra kiểu dữ liệu (type checking)
 – Dữ liệu biểu diễn khác nhau trên các hệ thống khác nhau
 » ASCII, EBCDIC
 » Little Endian và Big Endian
 » Dạng biểu diễn XDR (External data representation): độc lập
 với hệ thống bên dưới (machine-independent)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.55-
 Truyền tham số trong RPC (t.t)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.56-
 28
Kết nối (bind) client và server
 Matchm aker
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.57-
Quá trình thực hiện RPC
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.58-
 29
 Remote Method Invocation
‰ Remote Method Invocation (RMI) là cơ chế tương tự
 RPC nhưng vận hành trên nền máy ảo Java.
‰ RMI cho phép một chương trình Java có thể triệu gọi
 một phương thức (method) của một đối tượng ở xa.
 JV M
 Re
 m ote JV M
 Java O bj
 ect I
 Program nvoc
 ation
 Remote
 Object
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.59-
 Remote Method Invocation (t.t)
‰ Khác biệt giữa RPC và RMI
 – RPC hỗ trợ lập trình cấu trúc (procedural 
 programming)
 » Chỉ cho phép triệu gọi thủ tục (procedure) hoặc
 hàm (functions) ở xa. 
 – RMI hỗ trợ cơ chế hướng đối tượng (object-oriented)
 » RMI cho phép triệu gọi phương thức (method) trên
 đối tượng ở xa (remote object)
 – Trong RPC, tham số truyền đến thủ tục/hàm ở xa là
 dữ liệu bình thường (số, chuỗi kí tự, dãy,...)
 – Trong RMI, tham số truyền đến đối tượng ở xa có thể
 là một đối tượng
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.60-
 30
 Cơ chế marshalling trong RMI
 client rem ote object
 val= som eM ethod(A, B) boolean som eM ethod(Objectx, Object y)
 {
 implem entation of som eM ethod
 }
 Stub Skeleton
 A, B, som eM ethod
 boolean return value
Phương thức được triệu gọi có dạng sau:
 boolean someMethod(Object x, Object y)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.61-
 Windows NT Process Object
‰ Process ID
‰ Security Descriptor
‰ Base priority
‰ Default processor affinity
‰ Quota limits
‰ Execution time
‰ I/O counters
‰ VM operation counters
‰ Exception/debugging ports
‰ Exit Status
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.62-
 31
 Windows NT Thread Object
‰ Thread ID
‰ Thread context
‰ Dynamic priority
‰ Base priority
‰ Thread processor affinity
‰ Thread execution time
‰ Alert status
‰ Suspension count
‰ Impersonation token
‰ Termination port
‰ Thread exit status
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.63-
 NT Thread Status
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.64-
 32
 Solaris
‰ Process includes the user’s address space, stack, and process 
 control block
‰ User-level threads
‰ Lightweight processes
‰ Kernel threads
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.65-
 Solaris User Level Threads
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.66-
 33
Solaris Light weight Processes
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -4.67-
 34