Bài giảng - Hệ điều hành Chương 2: Tiến trình, luồng - Lương Minh Huấn

Nội dung text: Bài giảng - Hệ điều hành Chương 2: Tiến trình, luồng - Lương Minh Huấn

1. I.4 HỢP TÁC TIẾN TRèNH ➢Khi phõn loại tiến trỡnh cú 2 loại ▪ Tiến trỡnh tuần tự • Điểm bắt đầu của tiến trỡnh này nằm sau điểm kết thỳc của tiến trỡnh kia. ▪ Tiến trỡnh song song • Điểm bắt đầu của tiến trỡnh này nằm giữa điểm bắt đầu và kết thỳc của tiến trỡnh kia. • Chia ra làm 2 loại – Tiến trỡnh độc lập – Tiến trỡnh hợp tỏc
2. I.4 HỢP TÁC TIẾN TRèNH ➢Tiến trỡnh độc lập: khụng ảnh hưởng, và khụng bị ảnh hưởng bởi cỏc tiến trỡnh khỏc đang thực hiện trong hệ thống. ➢Tiến trỡnh hợp tỏc: Ảnh hưởng và chịu ảnh hưởng bởi cỏc tiến trỡnh khỏc đang thực hiện trong hệ thống. ▪ Lợi ớch của hợp tỏc tiến trỡnh: • Chia sẻ thụng tin • Tăng tốc độ tớnh toỏn • Module húa • Tiện dụng
3. I.4 HỢP TÁC TIẾN TRèNH ▪ Khi thực hiện hợp tỏc tiến trỡnh đũi hỏi cơ chế: • Truyền thụng giữa cỏc tiến trỡnh. • Đồng bộ húa hoạt động của cỏc tiến trỡnh. ▪ Vớ dụ: bài toỏn producer – consumer • Hệ thống gồm 2 tiến trỡnh: – Producer sản xuất ra cỏc sản phẩm – Consumer tiờu thụ cỏc sản phẩm này.
4. PRODUCER - CONSUMER ➢Ứng dụng: ▪ Chương trỡnh in (producer) sản xuất ra cỏc ký tự được tiờu thụ bởi bộ điều khiển mỏy in (consumer). ▪ Trỡnh dịch (producer) sản xuất ra mó hợp ngữ, trỡnh hợp ngữ (consumer/producer) tiờu thụ mó hợp ngữ rồi sản xuất ra module đối tượng được bộ thực hiện (consumer) tiờu thụ
5. PRODUCER - CONSUMER ➢Producer và Consumer hoạt động đồng thời ➢Sử dụng vựng đệm dựng chung (Buffer) chứa sản phẩm được điền vào bởi producer và được lấy ra bởi consumer. ➢Producer và Consumer phải đồng bộ. ▪ Consumer khụng tiờu thụ sản phẩm mà producer chưa sản xuất.
6. PRODUCER - CONSUMER ➢Vựng đệm giữa producer và consumer cú 2 dạng: ▪ Vựng đệm dung lượng vụ hạn: • Khi Buffer rỗng, Consumer phải đợi • Producer khụng phải đợi khi đặt sản phẩm vào buffer. ▪ Vựng đệm dung lượng hữu hạn. • Khi Buffer rỗng, Consumer phải đợi • Producer phải đợi khi vựng đệm đầy.
7. I.5 TRUYỀN THễNG LIấN TIẾN TRèNH ➢Để cỏc tiến trỡnh cú thể hợp tỏc với nhau, cần phải cú một bộ truyền thụng liờn tiến trỡnh (interprocess communication – IPC). ➢Truyền thụng liờn tiến trỡnh cú 2 hỡnh thức: ▪ Dựng bộ nhớ phõn chia (share memory) ▪ Dựng mụ hỡnh truyền thụng liờn tiến trỡnh.
8. I.5 TRUYỀN THễNG LIấN TIẾN TRèNH ➢Dựng mụ hỡnh bộ nhớ phõn chia (share memory): ▪ Cỏc tiến trỡnh chia sẻ vựng nhớ chớnh. ▪ Mó cài đặt được viết tường minh bởi người lập trỡnh ứng dụng ▪ Vớ dụ: Bài toỏn Producer-Consumer
9. I.5 TRUYỀN THễNG LIấN TIẾN TRèNH ➢Shared data #define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; ➢Solution is correct, but can only use BUFFER_SIZE-1 elements
10. I.5 TRUYỀN THễNG LIấN TIẾN TRèNH item next_produced; while (true) { /* produce an item in next produced */ while (((in + 1) % BUFFER_SIZE) == out) ; /* do nothing */ buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; }
11. I.5 TRUYỀN THễNG LIấN TIẾN TRèNH item next_consumed; while (true) { while (in == out) ; /* do nothing */ next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; /* consume the item in next consumed */ }
12. I.5 TRUYỀN THễNG LIấN TIẾN TRèNH ➢Dũng mụ hỡnh truyền thụng liờn tiến trỡnh (Interprocess communication) ▪ Là cơ chế cho phộp cỏc tiến trỡnh truyền thụng và đồng bộ cỏc hoạt động. ▪ Thường được sử dụng trong cỏc hệ phõn tỏn khi cỏc tiến trỡnh truyền thụng nằm trờn cỏc mỏy khỏc nhau (chat) ▪ Đảm bảo bởi hệ thống truyền thụng điệp.
13. HỆ THỐNG TRUYỀN THễNG ĐIỆP ➢Cho phộp cỏc tiến trỡnh trao đổi với nhau khụng qua sử dụng cỏc biến phõn chia. ➢Yờu cầu 2 thao tỏc cơ bản ▪ Send (msg) Cỏc msg cú kớch thước cố định hoặc thay đổi • Cố định : dễ cài đặt mức hệ thống, nhiệm vụ lập trỡnh khú • Thay đổi: cài đặt mức hệ thống phức tạp, lập trỡnh đơn giản ▪ Receive (msg)
14. HỆ THỐNG TRUYỀN THễNG ĐIỆP ➢Nếu 2 tiến trỡnh P và Q muốn trao đổi, chỳng cần ▪ Thiết lập một liờn kết truyền thụng (vật lý/ logic) giữa chỳng ▪ Trao đổi cỏc messages nhờ cỏc thao tỏc send/receive. ➢Cỏc vấn cài đặt: ▪ Cỏc liờn kết được thiết lập như thế nào? ▪ Một liờn kết cú thể dựng cho nhiều hơn 2 tiến trỡnh? ▪ Bao nhiờu liờn kết cú thể tồn tại giữa mọi cặp tiến trỡnh? ▪ Kớch thước thụng bỏo mà liờn kết chấp nhận cố định/thay đổi? ▪ Liờn kết một hay hai chiều?
15. HỆ THỐNG TRUYỀN THễNG ĐIỆP ➢Trong vấn đề truyền thụng điệp, cú 2 loại truyền: ▪ Truyền trực tiếp ▪ Truyền giỏn tiếp
16. TRUYỀN THễNG TRỰC TIẾP ➢Cỏc tiến trỡnh phải gọi tờn tiến trỡnh nhận/ gửi một cỏch tường minh. ▪ send (P, message) – gửi một thụng bỏo tới tiến trỡnh P ▪ receive(Q, message) – Nhận một thụng bỏo từ tiến trỡnh Q ➢Tớnh chất của liờn kết truyền thụng ▪ Cỏc liờn kết được thiết lập tự động. ▪ Một liờn kết gắn chỉ với cặp tiến trỡnh truyền thụng ▪ Chỉ tồn tại một liờn kết giữa cặp tiến trỡnh ▪ Liờn kết cú thể là một chiều, nhưng thường hai chiều
17. TRUYỀN THễNG GIÁN TIẾP ➢Cỏc thụng điệp được gửi/ nhận tới/ từ cỏc hũm thư (mailboxes), cổng (ports). ▪ Một hũm thư cú định danh duy nhất ▪ Cỏc tiến trỡnh cú thể trao đổi nếu chỳng dựng chung hũm thư ➢Tớnh chất cỏc liờn kết ▪ Cỏc liờn kết được thiết lập chỉ khi cỏc tiến trỡnh dựng chung hũm thư ▪ Một liờn kết cú thể được gắn với nhiều tiến trỡnh ▪ Mỗi cặp tiến trỡnh cú thể dựng chung nhiều liờn kết truyền thụng ▪ Liờn kết cú thể một hay hai chiều
18. TRUYỀN THễNG GIÁN TIẾP ➢Cỏc thao tỏc ▪ Tạo hũm thư ▪ Gửi/nhận thụng bỏo qua hũm thư • send(A, msg): Gỷi một msg tới hũm thư A • receive(A, msg): Nhận một msg từ hũm thư A ▪ Hủy bỏ hũm thư
19. VẤN ĐỀ ĐỒNG BỘ HểA ➢Truyền thụng điệp cú thể phải chờ đợi (blocking), hoặc khụng chờ đợi (non blocking) ▪ Blocking Truyền thụng đồng bộ ▪ Non-blocking Truyền thụng khụng đồng bộ ➢Cỏc thủ tục send() và receive() cú thể bị chờ đợi hoặc khụng chờ đợi ▪ Blocking send: Tiến trỡnh gửi thụng bỏo và đợi cho tới khi msg được nhận bởi tiến trỡnh nhận hoặc bởi hũm thư ▪ Non blockking send: tiến trỡnh gửi thụng bỏo và tiếp tục làm việc
20. VẤN ĐỀ ĐỒNG BỘ HểA ▪ Blocking receive: Tiến trỡnh nhận phải đợi cho tới khi cú thụng bỏo ▪ Non-blocking receive: Tiến trỡnh nhận trả về hoặc một thụng bỏo cú giỏ trị, hoặc giỏ trị null.
21. VÙNG ĐỆM ➢Cỏc thụng điệp trao đổi giữa cỏc tiến trỡnh được lưu trong hàng đợi tạm thời ➢Hàng đợi cú thể được cài đặt theo: ▪ Khả năng chứa 0 (Zero capacity): độ dài hàng đợi là 0 • Khụng tồn tại thụng điệp trong đường liờn kết • Sender phải đợi cho tới khi thụng điệp được nhận ▪ Khả năng chứa cú giới hạn(Bound capacity) • Hàng đợi cú độ dài n, chứa nhiều nhất n thụng điệp • Nếu hàng đợi đầy, sender phải đợi cho tới khi cú chỗ trống
22. VÙNG ĐỆM ▪ Khả năng chứa khụng giới hạn (Unbound capacity) • Sender khụng bao giờ phải đợi
23. TRUYỀN THễNG TRONG HỆ THỐNG CLIENT - SERVER ➢Socket ➢RPC (Remote Procedure Calls) ➢RMI (Remote Method Invocation) Cơ chế truyền thụng của Java
24. SOCKET ➢Được xem như một đầu mỳt cho truyền thụng ➢Bao gồm cặp địa chỉ IP và cổng: 146.86.5.20:1625
25. SOCKET
26. NỘI DUNG II. Luồng 1. Giới thiệu 2. Mụ hỡnh đa luồng 3. Vấn đề đa luồng
27. II.1 GIỚI THIỆU
28. II.1 GIỚI THIỆU
29. II.1 GIỚI THIỆU ➢Chương trỡnh: Dóy lệnh, cỏc biến, ➢Tiến trỡnh: Chương trỡnh đang thực hiện: Stack, thiết bị, VXL, ➢Luồng: Chương trỡnh đang thực hiện trong ngữ cảnh tiến trỡnh
30. II.1 GIỚI THIỆU ➢Hệ điều hành truyền thống (MS-DOS, UNIX) ▪ Tiến trỡnh cú một luồng điều khiển (heavyweight process) ➢Hệ điều hành hiện nay (Windows, Linux) ▪ Tiến trỡnh cú thể gồm nhiều luồng ▪ Cú thể thực hiện nhiều nhiệm vụ tại một thời điểm
31. II.1 GIỚI THIỆU
32. II.1 GIỚI THIỆU
33. KHÁI NIỆM LUỒNG ➢Là đơn vị sử dụng CPU cơ bản gồm: ▪ Định danh luồng (ID Thread) ▪ Bộ đếm chương trỡnh (Program Computer) ▪ Tập cỏc thanh ghi (Rigisters) ▪ Khụng gian stack ➢Chia sẻ cựng cỏc luồng khỏc trong cựng một tiến trỡnh ▪ Đoạn mó lệnh ▪ Đọan dữ liệu (đối tượng toàn cục) ▪ Cỏc tài nguyờn hệ điều hành khỏc (file đang mở)
34. KHÁI NIỆM LUỒNG ➢Cỏc luồng cú thể thực hiện cựng đọan mó với ngữ cảnh (Tập thanh ghi, Bộ đếm chương trỡnh, stack) khỏc nhau ➢Cũn được gọi là tiến trỡnh nhẹ (LWP: Lightweight Process) ➢Một tiến trỡnh cú ớt nhất là một luồng
35. LỢI ÍCH CỦA LẬP TRèNH ĐA LUỒNG ➢Tăng tớnh đỏp ứng với người dựng ▪ Cho phộp chương trỡnh vẫn thực hiện ngay khi một phần đang chờ đợi (block) hoặc đang thực hiện tớnh toỏn tăng cường ▪ Vớ dụ trỡnh duyệt Web (Web browser) đa luồng • Một luồng tương tỏc với người dựng • Một luồng thực hiện nhiệm vụ tải dữ liệu
36. LỢI ÍCH CỦA LẬP TRèNH ĐA LUỒNG ➢Chia sẻ tài nguyờn ▪ Cỏc luồng chia sẻ bộ nhớ và tài nguyờn của tiến trỡnh chứa nú • Tốt cho cỏc thuật toỏn song song (sử dụng chung cỏc CTDL) • Trao đổi giữa cỏc luồng thụng qua bộ nhớ phõn chia ▪ Cho phộp một ứng dụng chứa nhiều luồng hoạt động trong cựng khụng gian địa chỉ.
37. LỢI ÍCH CỦA LẬP TRèNH ĐA LUỒNG ➢Tớnh kinh tế ▪ Cỏc thao tỏc khởi tạo, hủy bỏ và luõn chuyển luồng ớt tốn kộm • Minh họa được tớnh song song trờn bộ đơn VXL do thời gian luõn chuyển CPU nhanh (Thực tế chỉ một luồng thực hiện) ➢Sử dụng kiến trỳc nhiều vi xử lý ▪ Cỏc luồng chạy song song thực sự trờn cỏc bộ VXL khỏc nhau.
38. LỢI ÍCH CỦA LẬP TRèNH ĐA LUỒNG
39. CÀI ĐẶT LUỒNG
40. LUỒNG NGƯỜI DÙNG ➢Quản lý cỏc luồng được thực hiện bởi chương trỡnh ứng dụng ➢Nhõn hệ thống khụng biết gỡ về sự tồn tại luồng ▪ Điều phối tiến trỡnh như một đơn vị duy nhất ▪ Gỏn cho mỗi tiến trỡnh một trạng thỏi duy nhất • Sẵn sàng, chờ đợi, thực hiện, ➢Chương trỡnh ứng dụng được lập trỡnh theo mụ hỡnh đa luồng bởi sử dụng thư viện luồng ▪ Thư viện hổ trợ tạo, hủy bỏ, truyền thụng điệp giữa cỏc luồng, điều phối, lưu trỳ, khụi phục trạng thỏi (context) luồng ,
41. LUỒNG NGƯỜI DÙNG ➢Ưu điểm ▪ Nhanh chúng trong tạo và quản lý luồng ➢Nhược điểm ▪ Khi một luồng rơi vào trạng thỏi chờ đợi, tất cả cỏc luồng trong cựng tiến trỡnh bị chờ đợi theo => Khụng tận dụng được ưu điểm của mụ hỡnh lập trỡnh đa luồng
42. LUỒNG MỨC HỆ THỐNG ➢Nhõn duy trỡ thụng tin về tiến trỡnh và càc luồng ➢Quản lý luồng được thực hiện bởi nhõn ▪ Khụng tồn tại cỏc mó quản lý luồng trong ứng dụng ▪ Điều phối luồng được thực hiện bởi nhõn, dựa trờn cỏc luồng ➢Nhược điểm: ▪ Chậm trong tạo và quản lý luồng
43. LUỒNG MỨC HỆ THỐNG ➢Ưu điểm: ▪ Một luồng chờ đợi vào ra, khụng ảnh hưởng tới luồng khỏc ▪ Trong mụi trường đa VXL, nhõn cú thể điều phối cỏc luồng cho cỏc VXL khỏc nhau ➢Hệ điều hành: Windows NT/2000/XP, Linux, OS/2,
44. II.2 Mễ HèNH ĐA LUỒNG ➢Nhiều hệ thống hổ trợ cả luồng mức người dựng và luồng mức hệ thống => Nhiều mụ hỡnh đa luồng khỏc nhau
45. Mễ HèNH NHIỀU MỘT ➢Ánh xạ nhiều luồng mức người dựng tới một luồng mức hệ thống ➢Quản lý luồng được thực hiện trong khụng gian người dựng ▪ Hiệu quả ▪ Cho phộp tạo nhiều luồng tựy ý ▪ Toàn bộ tiến trỡnh sẽ bị khúa nếu một luồng bị khúa ➢Khụng thể chạy song song trờn cỏc mỏy nhiều vi xử lý (Chỉ một luồng cú thể truy nhập nhõn tại một thời điểm) ➢Dựng trong hệ điều hành khụng hổ trợ luồng hệ thống
46. Mễ HèNH NHIỀU MỘT
47. Mễ HèNH MỘT MỘT ➢Ánh xạ mỗi luồng mức người dựng tới một luồng hệ thống ▪ Cho phộp thực hiện luồng khỏc khi một luồng bị chờ đợi ▪ Cho phộp chạy song song đa luồng trờn mỏy nhiều vi xử lý ➢Tạo luồng mức người dựng đũi hỏi tạo một luồng mức hệ thống tương ứng ▪ Ảnh hưởng tới hiệu năng của ứng dụng ▪ Chi phớ cao => Giới hạn số luồng được hệ thống hổ trợ ➢Được sử dụng trong Window NT/2000/XP
48. Mễ HèNH MỘT MỘT
49. Mễ HèNH NHIỀU NHIỀU ➢Nhiều luồng mức người dựng ỏnh xạ tới một số nhỏ luồng mức hệ thống ➢Số lượng luồng nhõn cú thể được xỏc định theo mỏy hoặc theo ứng dụng ▪ VD: Được cấp nhiều luồng nhõn hơn trờn hệ thống nhiều VXL ➢Cú được ưu điểm của 2 mụ hỡnh trờn ▪ Cho phộp tạo nhiều luồng mức ứng dụng theo yờu cầu ▪ Cỏc luồng nhõn tương ứng cú thể chạy song song trờn hệ nhiều VXL ▪ Một luồng bị khoỏ, nhõn cú thể cho phộp luồng khỏc thực hiện ➢Vớ dụ: UNIX
50. Mễ HèNH NHIỀU NHIỀU
51. II.3 VẤN ĐỀ ĐA LUỒNG
52. II.3 VẤN ĐỀ ĐA LUỒNG
53. II.3 VẤN ĐỀ ĐA LUỒNG
54. II.3 VẤN ĐỀ ĐA LUỒNG
55. II.3 VẤN ĐỀ ĐA LUỒNG