Chuong 2

CHƯƠNG II HỆ ĐIỀU HÀNH THỜI GIAN THỰC

2007

Nội dung 

 



NHÂN HỆ ĐIỀU HÀNH THỜI GIAN THỰC CÁC LÝ THUYẾT CƠ SỞ TRUYỀN THÔNG VÀ ĐỒNG BỘ GIỮA CÁC TIẾN TRÌNH QUẢN LÝ BỘ NHỚ

Nhiệm vụ và tiến trình   



Nhiệm vụ (task): một đoạn chương trình máy tính được tải vào bộ nhớ. Tiến trình (process): một đoạn chương trình máy tính đang được thực hiện. Công việc (job): một hoặc một nhóm các tiến trình đang được thực hiện cho một mục đích nào đó (ví dụ: print). Tiểu trình (thread): nằm trong một tiến trình và chia sẻ tài nguyên với tiến trình chứa nó.

Trạng thái của tiến trình Được cấp thời gian CPU

Trình

Sẵn sàng

Hết thời gian được cấp

Chạy

Chờ tài nguyên

Tài nguyên được cấp

Dừng

Hoàn thành

Process Control Block (PCB)       

Định danh (Process identification) Trạng thái thực hiện (Execution state) Mức ưu tiên (Priority) Quyền truy nhập tài nguyên (Privileges) Các địa chỉ bộ nhớ của quá trình Các thuộc tính khác như thời gian thực hiện… Con trỏ tới PCB tiếp theo

Tiến trình và Tiểu trình  



 

Hệ thống có nhiều tiến trình cùng hoạt động → cạnh tranh tài nguyên → tương tranh. 1 tiến trình có thể gồm nhiều tiểu trình, các tiểu trình của cùng 1 tiến trình cũng có thể tương tranh. Các tiểu trình trong cùng 1 tiến trình nằm trong cùng 1 vùng địa chỉ, có cùng quyền truy nhập tới các tài nguyên → quản lý tương tranh dễ hơn so với tiến trình. Điều khiển tương tranh giữa các tiến trình thường là công việc của hệ điều hành. Điều khiển tương tranh giữa các tiểu trình do người lập trình ứng dụng chủ động → khái niệm lập trình tương tranh (concurrent programming) hay lập trình đa tiểu trình

Các lớp của RTOS Người sử dụng Operating System Executive

Giao diện với người sử dụng Hỗ trợ file và ổ đĩa

Kernel Truyền thông và đồng bộ giữa các (Nhân) tiến trình MicroLập lịch cho nhiệm vụ kernel Nano-kernel Quản lý thread Phần cứng

Chức năng của nhân hệ điều hành thời gian thực 





Lập lịch (Scheduling): quyết định nhiệm vụ nào sẽ được thực hiện khi nào và trong bao lâu. Điều độ (Dispatching): thực hiện các công việc cần thiết để thực hiện một nhiệm vụ. Truyền thông (Communication) và đồng bộ (Synchronization): đảm bảo việc phối hợp giữa các nhiệm vụ, bao gồm cả việc chia sẻ các tài nguyên dùng chung.

Các loại kernel   

 

Pseudo-kernel Hệ thống dựa vào ngắt Hệ thống giành ưu tiên (preemptive-priority) Hệ thống hỗn hợp Mô hình khối điều khiển nhiệm vụ (Task Control Block - TCB)

Pseudo-kernels  





Lặp hỏi vòng (Polled loop): sử dụng cờ trạng thái (flag) để biểu thị sự kiện xảy ra. Lặp hỏi vòng đồng bộ (Synchronized polled loop): sử dụng trễ để tránh hiệu ứng dao động khi tín hiệu chuyển trạng thái. Điều hành vòng (Cyclic executive): lần lượt thực hiện các tiến trình trong danh sách theo 1 thứ tự định sẵn. Mã theo trạng thái (State-driven code) và đồng thủ tục (Co-routines): chia tiến trình thành các đoạn nhỏ → cho phép dừng tiến trình, chuyển qua thực hiện tiến trình khác. Trạng thái của mỗi tiến trình sẽ cho biết tiến trình đã được thực hiện tới đâu để khi đến lượt sẽ thực hiện tiếp mà không mất các dữ

Các loại kernel   

 

Pseudo-kernel Hệ thống dựa vào ngắt Hệ thống giành ưu tiên (preemptive-priority) Hệ thống hỗn hợp Mô hình khối điều khiển nhiệm vụ (Task Control Block - TCB)

Ngắt (Interrupt) 







Ngắt cứng: tín hiệu ngắt do một thiết bị ngoại vi gửi tới CPU → CPU sẽ thực hiện một chương trình dịch vụ ngắt (Interrupt Service Routine - ISR) để đáp ứng yêu cầu. Ngắt mềm: lệnh ngắt trong tiến trình đang thực hiện cho phép chuyển quyền điều khiển cho một chương trình khác (chính là ISR). Cơ chế lập lịch: thông qua mức độ ưu tiên và thứ tự thời gian của ngắt, được thực hiện bởi bộ điều khiển ngắt (interrupt controller) của CPU. Điều độ: được thực hiện bởi bộ điều khiển ngắt, hoặc trong trường hợp phức tạp hơn, do một chương trình xử lý ngắt thực hiện. Chương trình này phải đọc vector ngắt của

Đồng bộ 



Tiến trình bị ngắt giữa chừng phải dừng và đợi tới khi tiến trình thực hiện ngắt hoàn thành → yêu cầu truyền thông và đồng bộ ở mức tối thiểu. Khi tiến trình thực hiện ngắt đang chạy: mọi ngắt khác có mức ưu tiên thấp hơn sẽ bị cấm cho đến khi tiến trình đó thực hiện xong → tiến trình chỉ có thể bị ngắt bởi ngắt có mức ưu tiên cao hơn.

Chương trình dịch vụ ngắt (ISR) 



Khi bắt đầu thực hiện, việc đầu tiên ISR phải làm là lưu lại ngữ cảnh (context) của tiến trình bị nó ngắt, thường là nội dung của các thanh ghi (bao gồm cả con trỏ chương trình – Program Counter), vào một stack. Sau khi thực hiện xong nhiệm vụ được yêu cầu bởi ngắt, ISR phải khôi phục lại ngữ cảnh trước đó để tiến trình bị nó ngắt tiếp tục thực hiện.

Các loại kernel   

 

Pseudo-kernel Hệ thống dựa vào ngắt Hệ thống giành ưu tiên (preemptive-priority) Hệ thống hỗn hợp Mô hình khối điều khiển nhiệm vụ (Task Control Block - TCB)

Hệ thống giành ưu tiên 





Nhiệm vụ có quyền ưu tiên cao hơn sẽ giành quyền (pre-empt) khi cần thực hiện nếu tiến trình đang thực hiện có quyền ưu tiên thấp hơn nó. Quyền ưu tiên của mỗi nhiệm vụ có thể cố định hay động → các hệ thống với quyền ưu tiên động mềm dẻo hơn trong trường hợp tầm quan trọng của mỗi nhiệm vụ thay đổi trong quá trình hoạt động của hệ thống. Hệ thống tần suất đơn điệu (ratemonotonic): quyền ưu tiên được cấp theo nguyên tắc nhiệm vụ nào có tần

Các loại kernel   

 

Pseudo-kernel Hệ thống dựa vào ngắt Hệ thống giành ưu tiên (preemptive-priority) Hệ thống hỗn hợp Mô hình khối điều khiển nhiệm vụ (Task Control Block - TCB)

Hệ thống hỗn hợp 



Hệ thống chỉ dựa vào ngắt có thời gian đáp ứng nhanh (việc lập lịch đơn giản và được thực hiện bởi phần cứng), nhưng khó thực hiện các công việc phức tạp đòi hỏi phối hợp nhiều nhiệm vụ. Giải pháp: hệ thống hỗn hợp – Các tiến trình bề mặt (foreground processes): được điều khiển bởi ngắt. – Các tiến trình nền (background processes): không điều khiển bởi ngắt.

Tiến trình nền 

 

Thường là các tiến trình không cấp bách về mặt thời gian (kiểm tra hệ thống, cập nhật màn hình, giao tiếp với các thiết bị có tốc độ chậm…). Các tiến trình nền thực hiện trong theo một vòng lặp (kiểu điều hành vòng). Các tiến trình nền có mức độ ưu tiên thấp hơn các tiến trình bề mặt → có thể bị giành quyền thực hiện bởi tiến trình bề mặt khi ngắt xuất hiện.

Tiến trình bề mặt  



Thường là các tiến trình có yêu cầu về thời gian thực. Các tiến trình có mức ưu tiên cao hơn sẽ giành quyền của tiến trình có mức ưu tiên thấp hơn. Các tiến trình có cùng mức ưu tiên thực hiện theo chế độ quay vòng (round-robin): mỗi tiến trình thực hiện trong một khoảng thời gian rồi nhường quyền thực hiện cho tiến trình kế tiếp.

Đặc điểm của hệ thống Foreground/Backgroun d 



Thời gian đáp ứng nhanh đối với các nhiệm vụ thời gian thực (do sử dụng ngắt). Để thiết kế hệ thống hiệu quả cần biết trước số tiến trình bề mặt và mức độ quan trọng để xác định mức ưu tiên của chúng → khi kết nối thêm thiết bị vào hệ thống cần phải thiết kế lại toàn bộ hoặc hệ thống sẽ hoạt động kém hiệu quả.

Các loại kernel   

 

Pseudo-kernel Hệ thống dựa vào ngắt Hệ thống giành ưu tiên (preemptive-priority) Hệ thống hỗn hợp Mô hình khối điều khiển nhiệm vụ (Task Control Block - TCB)

Các đặc điểm chính 





Sử dụng trong các hệ thống có số lượng nhiệm vụ thời gian thực luôn thay đổi (ví dụ: hệ thống trực tuyến ở đó nhiệm vụ gắn với người sử dụng, đến rồi đi). Các tiến trình thường được lập lịch theo nguyên tắc quay vòng hoặc giành quyền ưu tiên, nhưng thường là quay vòng với một đồng hồ duy nhất. Mỗi nhiệm vụ được gắn với một cấu trúc dữ liệu gọi là TCB. Hệ thống quản lý danh sách các TCBs → nếu hệ thống có quá nhiều nhiệm vụ, phí tổn để

Khối quản lý nhiệm vụ (TCB)   

Định danh Mức độ ưu tiên Trạng thái – Sẵn sàng (Ready): nhiệm vụ đã được đưa vào lập lịch. – Chạy (Running/Executing): đã đưa vào thực hiện. – Dừng (Suspended/Blocked): chờ tài nguyên. – Ngủ (Dormant/Sleeping): thường dùng với hệ thống có số lượng TCBs cố định → nhiệm vụ được cấp TCB kể cả khi chưa sẵn sàng.

  

Con trỏ chương trình (PC) Nội dung các thanh ghi Các thông tin khác (con trỏ tới TCB tiếp…)

Trạng thái của nhiệm vụ Được cấp thời gian CPU

Sẵn sàng

Hết thời gian được cấp Bị ngắt

Trình

Được cấp TCB

Xóa

Ngủ

a Xó

Tà i đư ngu ợc yê cấ n p

Xóa (Cancelled)

Chạy

Chờ tài nguyên

Dừng

Quản lý nhiệm vụ và tài nguyên 

Hệ thống duy trì các danh sách: – Danh sách các TCBs của các nhiệm vụ ở trạng thái sẵn sàng. – Danh sách các TCBs của các nhiệm vụ ở trạng thái dừng. – Danh sách các tài nguyên. – Danh sách các yêu cầu tài nguyên của các tiến trình.

Quản lý nhiệm vụ và tài nguyên 

Hành động của hệ thống khi một sự kiện xảy ra: – Yêu cầu nhiệm vụ mới: lập lịch. – Nhiệm vụ đang thực hiện đã hết thời gian: đưa về cuối danh sách sẵn sàng. Nếu nhiệm vụ không còn cần thiết: đánh dấu xóa (ngủ). Đưa nhiệm vụ tiếp theo sẽ được thực hiện ra khỏi danh sách và đưa vào thực hiện. – Yêu cầu tài nguyên: nếu tài nguyên rảnh → cấp tài nguyên (đánh dấu trong danh sách tài nguyên đã được cấp), nếu không → đưa nhiệm vụ vào danh sách dừng, đưa yêu cầu vào danh sách yêu cầu, và đưa nhiệm vụ tiếp theo vào thực hiện. – Tài nguyên được giải phóng: kiểm tra trong danh sách dừng, nếu có nhiệm vụ đang chờ tài nguyên đã rảnh → đưa nhiệm vụ vào danh sách sẵn sàng

Nội dung 

 



NHÂN HỆ ĐIỀU HÀNH THỜI GIAN THỰC CÁC LÝ THUYẾT CƠ SỞ TRUYỀN THÔNG VÀ ĐỒNG BỘ GIỮA CÁC TIẾN TRÌNH QUẢN LÝ BỘ NHỚ

Lập lịch (Scheduling) 

Là chức năng cơ bản của RTOS – Để đáp ứng yêu cầu về thời gian của các nhiệm vụ, hệ thống cần 1 chiến lược để phân phối tài nguyên + cơ chế để dự đoán thời gian đáp ứng trong trường hợp tồi nhất (worst-case performance) ứng với mỗi chính sách lập lịch.



2 loại chính sách lập lịch: – Lập lịch trước khi chạy (pre-runtime scheduling): phải tiên liệu trước mọi sự kiện → thường áp dụng cho hệ thống có các nhiệm vụ cố định. – Lập lịch trong khi chạy (runtime scheduling): các tiến trình được gắn với mức ưu tiên và việc cấp tài nguyên dựa trên mức ưu tiên. Việc lập lịch còn cần dựa trên các cơ chế truyền thông và đồng bộ giữa các tiến trình. Sự kiện có thể xảy ra ngẫu nhiên → để đánh giá thời gian đáp ứng cần phải sử dụng các

Tham số đặc trưng của một nhiệm vụ  









Điều kiện tiên quyết: thứ tự thực hiện của nhiệm vụ. Thời gian bắt đầu (release time/arrival time): ri,j – thời gian bắt đầu lần chạy (instance) thứ j của nhiệm vụ τi. Pha φi: thời gian bắt đầu khi nhiệm vụ được thực hiện lần đầu (1st instance): φi = ri,1. Thời gian đáp ứng: khoảng thời gian từ khi nhiệm vụ bắt đầu thực hiện cho đến khi hoàn thành. Thời hạn tuyệt đối (absolute deadline) di,j: thời điểm phải hoàn thành cho lần chạy (instance) thứ j của nhiệm vụ τi. Thời hạn tương đối (relative deadline) Di: thời

Tham số đặc trưng của nhiệm vụ (tiếp) 





Độ lỏng (laxity type): mức độ cho phép chậm trễ trong việc thực hiện nhiệm vụ. Chu kỳ (period) pi: quãng thời gian tối thiểu giữa các lần thực hiện kế tiếp của nhiệm vụ τ i. trong trường hợp nhiệm vụ có chu kỳ đều đặn (periodic task): ri,j = φi+(j-1)pi di,k = φi+(j-1)pi +Di Thời gian thực hiện (execution time) ei: quãng thời gian tối đa cần để hoàn thành nhiệm vụ τi nếu hệ thống chỉ thực hiện nhiệm vụ này và các tài nguyên được yêu cầu đều sẵn sàng. Điều kiện để hệ thống hoạt động

Mô hình nhiệm vụ  

 



Tất cả các nhiệm vụ đều có chu kỳ thực hiện đều đặn (strictly periodic). Thời hạn tương đối của nhiệm vụ đúng bằng chu kỳ (Di = pi) → tại một thời điểm chỉ tồn tại tối đa một phiên bản của mỗi nhiệm vụ. Các nhiệm vụ là độc lập (không có điều kiện tiên quyết). Các nhiệm vụ đều có thể bị giành quyền vào bất cứ thời điểm nào, phí tổn của việc giành quyền có thể bỏ qua được. Việc lập lịch chỉ xét tới các yêu cầu về thời gian CPU, bỏ qua các yêu cầu tài nguyên khác.

Các khái niệm lập lịch   



Lập lịch quay vòng (Round-robin) CE (Cyclic Executive) Lập lịch với mức ưu tiên cố định (Fixed-priority): phương pháp RMA (Rate-Monotonic Algorithm) Lập lịch với mức ưu tiên động (Dynamic-priority): phương pháp EDF (Earliest Deadline First)

Các phương pháp quay vòng  



Quay vòng tuần tự: các tiến trình thực hiện tuần tự cho đến khi kết thúc. Quay vòng và phân chia thời gian: mỗi tiến trình được gán một lượng thời gian cố định để thực hiện. Khi chạy hết thời gian được cấp, nếu chưa hoàn thành, nhiệm vụ sẽ được lưu lại ngữ cảnh và chuyển tới cuối danh sách thực hiện. Quay vòng kết hợp với giành quyền ưu tiên: các tiến trình có cùng mức ưu tiên được thực hiện theo chế độ quay vòng, nhưng có thể bị giành quyền bởi tiến trình có mức ưu tiên cao hơn.

Các khái niệm lập lịch   



Lập lịch quay vòng (Round-robin) CE (Cyclic Executive) Lập lịch với mức ưu tiên cố định (Fixed-priority): phương pháp RMA (Rate-Monotonic Algorithm) Lập lịch với mức ưu tiên động (Dynamic-priority): phương pháp EDF (Earliest Deadline First)

Cyclic Executive 





CE là bộ lập lịch trong khi chạy: có nhiệm vụ xen kẽ và tuần tự hóa việc thực hiện các nhiệm vụ trên 1 CPU theo 1 lịch trình đã lập trước. CE đưa ra các quyết định theo chu kỳ: khoảng thời gian giữa các quyết định này được gọi là khung (frame) hay chu trình nhỏ (minor cycle) → giành quyền không được xảy ra bên trong các khung. Chu trình lớn hay siêu chu kỳ (major cycle/hyper-period): khoảng thời gian tối thiểu trong đó mọi tiến trình đều kết thúc chu kỳ thực hiện → chu trình lớn có độ dài đúng bằng bội số chung nhỏ nhất của các chu kỳ

Tính kích thước khung (frame size)  





Kích thước khung: f. Khung phải đủ lớn để mỗi tiến trình có thể bắt đầu và kết thúc trong cùng một khung: f ≥ max(ei). Chu trình lớn cần có độ dài bằng một số nguyên lần của kích thước khung để giảm thiểu thời gian phí phạm: LCM(p1,p2,…,pn) = kf. Khung phải đủ nhỏ để giữa thời điểm bắt đầu và thời hạn của mọi tiến trình đều phải có ít nhất một khung → đảm bảo mọi tiến trình đều có thể hoàn thành đúng hạn: 2f ≤ Di. Có thể sử dụng một điều kiện rộng rãi hơn, cho

Ví dụ

 

τi

τ1

pi 22ms ei

15ms 1ms

τ2

τ3 20ms

2ms

Di 14ms 22ms f ≥ ei → f ≥ 3ms

3ms 18ms

LCM(p1,p2,p3) = 660ms → f = 3/4/5/6/10/11/15/20/22ms…

Các khái niệm lập lịch   



Lập lịch quay vòng (Round-robin) CE (Cyclic Executive) Lập lịch với mức ưu tiên cố định (Fixed-priority): phương pháp RMA (Rate-Monotonic Algorithm) Lập lịch với mức ưu tiên động (Dynamic-priority): phương pháp EDF (Earliest Deadline First)

Định lý RM 



Liu (1973): Nếu có thể lập lịch được cho 1 tập các nhiệm vụ (nghĩa là các thời hạn và chu kỳ đều được đáp ứng) với các mức ưu tiên cố định thì việc gắn cho các nhiệm vụ đó các mức ưu tiên theo nguyên tắc nhiệm vụ có chu kỳ ngắn hơn có mức ưu tiên cao hơn sẽ cho phép đưa ra một thuật toán lập lịch tối ưu. Chứng minh: dùng phương pháp quy nạp (xem Laplante).

Định lý giới hạn của RMA 





Liu (1973): Một tập hợp bao gồm n nhiệm vụ có chu kỳ sẽ lập lịch được bằng phương pháp RM (RMschedulable) nếu hệ số sử dụng CPU với tập hợp đó thỏa mãn điều kiện sau đây: U ≤ n(21/n−1). Chú ý: điều kiện trên chỉ là điều kiện đủ. Khi n → ∞: U → ln2 ≈ 0,69 (xem

Ví dụ τi

τ1

τ2

τ3

pi

4ms

5ms

20ms

ei

1ms

2ms

5ms

1 3

2 2

3 1

Ưu tiên RM Non-RM  

RM Non-RM

τ1

τ2 τ3

τ3 τ1

τ2 τ2

τ3 τ1 τ3 τ2

τ1

τ2

τ1

τ3

τ2

τ1 τ1 τ1

Các khái niệm lập lịch   



Lập lịch quay vòng (Round-robin) CE (Cyclic Executive) Lập lịch với mức ưu tiên cố định (Fixed-priority): phương pháp RMA (Rate-Monotonic Algorithm) Lập lịch với mức ưu tiên động (Dynamic-priority): phương pháp EDF (Earliest Deadline First)

Phương pháp EDF 



Nguyên lý: Trong các nhiệm vụ của danh sách sẵn sàng, nhiệm vụ nào có thời hạn sớm nhất sẽ được gán mức ưu tiên cao nhất. Định lý: Xét 1 tập hợp của n nhiệm vụ với giả thiết rằng cho mỗi nhiệm vụ τi ta đều có pi = Di. Khi đó, điều kiện cần và đủ để có thể lập lịch cho tập hợp này bằng phương pháp EDF là hệ số sử dụng CPU của tập hợp đó thỏa mãn điều kiện: U ≤ 1.

Ví dụ

 

τi

τ1

τ2

pi

5ms

6ms

ei

2ms

4ms

RMA EDF

τ1 τ1

τ2 τ2

τ1

τ2 τ1

τ2

τ1 τ2

τ2

τ2

τ1

τ2

So sánh EDF và RMA 





EDF mềm dẻo hơn và do đó hiệu quả hơn về mặt sử dụng thời gian của CPU: không có chuyện CPU không làm gì khi vẫn còn nhiệm vụ đang chờ, điều vẫn có thể xảy ra với RMA. Về mặt hành vi, hệ thống sử dụng RMA dễ dự liệu hơn: trong trường hợp quá tải, với RMA chỉ có các nhiệm vụ có mức ưu tiên thấp mới bị lỡ hạn, còn các nhiệm vụ có mức ưu tiên cao không bị ảnh hưởng, trong khi với EDF không thể nói trước nhiệm vụ nào sẽ bị lỡ hạn. Với EDF, nhiệm vụ bị lỡ hạn sẽ có mức ưu tiên cao hơn các nhiệm vụ chưa tới hạn → có thể gây lỡ hạn dây chuyền khi hệ thống quá tải → cần cơ chế loại bỏ những nhiệm vụ đã lỡ hạn mà không còn quan trọng.

Nội dung 

 



NHÂN HỆ ĐIỀU HÀNH THỜI GIAN THỰC CÁC LÝ THUYẾT CƠ SỞ TRUYỀN THÔNG VÀ ĐỒNG BỘ GIỮA CÁC TIẾN TRÌNH QUẢN LÝ BỘ NHỚ

Truyền thông và Đồng bộ 



Giả thiết các nhiệm vụ độc lập và có thể bị giành quyền bất cứ lúc nào là không thực tế, bởi vì các yêu cầu truy nhập tài nguyên chưa được quan tâm đến . Khái niệm truyền thông và đồng bộ ở đây sẽ chỉ được đề cập trong phạm vi vấn đề duy trì tính nhất quán và toàn vẹn của tài nguyên hay dữ liệu dùng chung giữa các nhiệm vụ.

Mô hình các vấn đề    

Critical Section (CS) Dining Philosophers Producers – Consumers Readers – Writers

Critical Section 



Với một số tài nguyên được chia sẻ bởi nhiều nhiệm vụ, tính toàn vẹn của tài nguyên có thể bị vi phạm nếu các truy nhập tài nguyên của các tiến trình không được phối hợp. Ví dụ: Chương trình thực hiện việc rút tiền từ tài khoản ngân hàng theo yêu cầu qua máy ATM số_dư = Đọc_số_dư(số_TK); If số_dư >= số_tiền_yêu_cầu { Cấp_tiền(); Ghi_số_dư(số_TK, số_dư−số_tiền_yêu_cầu); }

Critical Section (tiếp) 



Ví dụ (tiếp): Nếu có 2 giao dịch cùng truy nhập 1 tài khoản từ 2 máy ATM tại cùng 1 thời điểm → trong hệ thống sẽ có 2 tiến trình tương tranh cùng truy nhập 1 tài khoản → nếu không đồng bộ có thể dẫn tới sai sót. Định nghĩa: CS là một đoạn chương trình thực hiện việc truy nhập một tài nguyên dùng chung không được phép truy nhập đồng thời bởi nhiều hơn một tiến trình tại cùng một thời điểm → các truy nhập vào tài nguyên đó được gọi là loại trừ lẫn nhau (mutually exclusive).

Mô hình các vấn đề    

Critical Section (CS) Dining Philosophers Producers – Consumers Readers – Writers

Mô hình vấn đề quyền truy nhập tài nguyên 





5 nhà triết học (philosophers) ngồi quanh một bàn tròn, trước mặt mỗi người là một đĩa thức ăn, cứ giữa 2 đĩa có 1 chiếc dĩa → cả bàn có 5 chiếc dĩa. Mỗi nhà triết học đều dành toàn bộ thời gian quanh bàn cho 2 việc: suy nghĩ và ăn khi đói. Mỗi nhà triết học chỉ có thể ăn bằng cả 2 chiếc dĩa để 2 bên đĩa của mình → sẽ phải đợi nếu 1 trong 2 hoặc cả chiếc 2 dĩa đều đang có người khác dùng.

Các vấn đề có thể xảy ra 



Đói (Starvation): 1 nhà triết học có thể chết đói nếu ông ta không có cách nào có được cả 2 chiếc dĩa (ví dụ: khi 2 người 2 bên cứ thay nhau ăn) → Starvation là trạng thái của 1 tiến trình không thể truy nhập tài nguyên nó cần. Tắc nghẽn (Deadlock): Các nhà triết học phải đợi lẫn nhau nên không có ai được ăn (ví dụ: khi mỗi người đều giữ được 1 chiếc dĩa và không ai chịu bỏ ra) → Deadlock là trạng thái của hệ thống trong đó các tiến trình đều không thể truy nhập tài nguyên chúng

Mô hình các vấn đề    

Critical Section (CS) Dining Philosophers Producers – Consumers Readers – Writers

Mô hình vấn đề với vùng đệm dùng chung 

Xét hệ thống với 2 loại tiến trình: Producers và Consumers, các tiến trình này dùng chung một vùng đệm (buffer pool) có kích thước hữu hạn.

– Các tiến trình Producers gửi các thông điệp (messages) vào vùng đệm. – Các tiến trình Consumers lấy thông điệp ra khỏi vùng đệm.



Các điều kiện phải tuân thủ:

– Producers không thể gửi thêm thông điệp nếu vùng đệm đã đầy. – Consumers không thể lấy thông điệp nếu vùng đệm rỗng.

Các vấn đề cần quan tâm 





Tính toàn vẹn dữ liệu: tránh các sai sót do nhiều tiến trình cùng đọc và ghi vào vùng đệm như ghi đè lên dữ liệu của nhau, lấy nhầm dữ liệu do con trỏ vùng đệm bị sai. Cơ chế thông báo cho các tiến trình đang chờ đợi ghi/đọc khi vùng đệm đã sẵn sàng. Lựa chọn kích thước vùng đệm phù hợp: Nếu kích thước vùng đệm quá nhỏ, các tiến trình sẽ thường xuyên

Mô hình các vấn đề    

Critical Section (CS) Dining Philosophers Producers – Consumers Readers – Writers

Mô hình vấn đề truy nhập CSDL dùng chung  

  

Xét hệ thống với 2 loại tiến trình: Readers và Writers. Tài nguyên dùng chung là một cơ sở dữ liệu (file): Các Readers có thể đọc từ file, còn các Writers có thể ghi vào file. Nhiều Readers có thể đọc file cùng một lúc. Tối đa 1 Writer có thể được phép ghi vào file tại một thời điểm. Readers không thể đọc nếu có một

Các kỹ thuật Truyền thông và Đồng bộ     

Đệm kép (Double buffering) Hộp thư (Mailbox) Cờ hiệu (Semaphore) Giải quyết tắc nghẽn Priority Inheritance Protocol và Priority Ceiling Protocol

Đệm kép 





Thường sử dụng khi các tiến trình gửi và lấy thông điệp với tốc độ khác nhau, đồng thời các thông điệp có tính nhạy cảm về thời gian → trường hợp đặc biệt của mô hình Producers-Consumers. Sử dụng 2 bộ đệm: đệm vào (buffer-in) và đệm ra (buffer-out). Khi 1 bộ thông điệp được gửi xong vào bộ đệm vào, dữ liệu sẽ được chuyển sang bộ đệm ra để đảm bảo dữ liệu luôn toàn vẹn về mặt thời gian. Trong quá trình chuyển dữ liệu giữa 2 vùng đệm, mọi ngắt đều bị cấm (tiến trình thực

Ví dụ 

Hệ thống thực hiện hàm f(t) = f(x(t),y(t),z(t)), ở đó x(t), y(t) và z(t) được đo bởi 3 cảm biến, mỗi cảm biến gửi dữ liệu một lần trong mỗi 10ms. Một tiến trình sẽ thực hiện việc tính toán cứ mỗi 40ms. Producers: τ1, τ2, τ3 (e1+e2+e3 < 10ms) Consumer: τ4 (e1+e2+e3+e4 > 10ms), có mức ưu τ2, τ3. t tiên thấp hơn τ1,t+10 τ1

τ2

τ3

τ4 đọc x, y

τ1

τ2

τ3

τ4

đọc nốt z tính f(x,y,z)

Ví dụ (tiếp) 





Chỉ dùng một vùng đệm: kết quả tính được tại thời điểm cuối trong hình vẽ trên là f(x(t),y(t),z(t+10)). Một giải pháp: cấm ngắt (cấm τ1, τ2, τ3) trong khi thực hiện tính toán (τ4 chạy) → số tiến trình phải chờ đợi rất lớn (τ1, τ2, τ3 có tần suất cao hơn nhiều so với τ4). Giải pháp đệm kép: Cấm_ngắt(); xb = x; yb = y; zb = z; Bỏ_cấm_ngắt();

Các kỹ thuật Truyền thông và Đồng bộ     

Đệm kép (Double buffering) Hộp thư (Mailbox) Cờ hiệu (Semaphore) Giải quyết tắc nghẽn Priority Inheritance Protocol và Priority Ceiling Protocol

Hộp thư  

 

Hình thức truyền thông và/hoặc đồng bộ giữa các tiến trình. Mỗi hộp thư phải cài đặt 2 hàm: post(p,message) và pend(p,message), ở đó p là một biến (như địa chỉ hộp thư). post dùng để gửi thông điệp vào hộp thư. pend thực hiện nhiệm vụ lấy thông điệp ra khỏi hộp thư. Nếu chưa có thông điệp, pend sẽ bị dừng và tiếp tục lại khi thông điệp được đưa vào →

Các kỹ thuật Truyền thông và Đồng bộ     

Đệm kép (Double buffering) Hộp thư (Mailbox) Cờ hiệu (Semaphore) Giải quyết tắc nghẽn Priority Inheritance Protocol và Priority Ceiling Protocol

Cờ hiệu  

 



Thường được sử dụng để bảo vệ các Critical Sections. Mỗi tài nguyên dùng chung theo chế độ loại trừ được gắn với một biến, gọi là biến semaphore. 2 thao tác: Wait và Signal Wait: dùng để đặt semaphore, thường được cài đặt dưới dạng hàm P(S), ở đó S là biến semaphore. Signal: dùng để xóa semaphore, thường được cài đặt dưới dạng hàm

Sử dụng semaphore 



Giả sử 2 tiến trình A và B đều cần truy nhập một tài nguyên R trong quá trình thực hiện. Các truy nhập của A và B vào R là loại trừ lẫn nhau. Sử dụng một biến semaphore S để bảo vệ các CS của A và B khi truy nhập R: Tiến trình A Tiến trình B … … P(S); P(S); CS: truy nhập R; CS: truy nhập R; V(S); V(S);

Cài đặt semaphore 



Binary semaphore: True → tài nguyên đang ở trong CS, False → tài nguyên không ở trong CS. Cách thông thường void P(S) void V(S) { { while(S); S=False; S=True; } } Giá trị khởi tạo của S là False

Cài đặt semaphore (tiếp) 

Sử dụng hòm thư void P(S) void V(S) { { pend(S,m); post(S,m); } } Thông điệp m chỉ là biến dummy (giá trị không có ý nghĩa). Hòm thư khi khởi tạo sẽ chứa sẵn một thông điệp.

Counting semaphore 



Sử dụng 1 semaphore cho 1 tập hợp các tài nguyên, hoặc cho 1 tài nguyên có thể được truy nhập cùng lúc bởi nhiều hơn 1 tiến trình → mở rộng khái niệm CS: nhiều hơn 1 tiến trình (nhưng có giới hạn) có thể vào CS cùng một lúc. Semaphore S có giá trị ban đầu > 0 (bằng số tối đa các tiến trình có thể cùng vào CS):

Counting semaphore (tiếp) 

Cài đặt P(S) và V(S): void P(S) { while(S==0); S=S−1; }

void V(S) { S=S+1; }

Giải pháp Semaphore cho Readers-Writers int nreaders = 0; Semaphore S=Sw=Sr=False; void reader(f:file) { P(S); if(nreaders==0) { nreaders=nreaders+1; P(Sw); } else nreaders=nreaders+1; V(S) read(f); P(S); nreaders=nreaders-1; if(nreaders==0) V(Sw); V(S) }

void writer(f:file) { P(Sr); P(Sw); write(f); V(Sw); V(Sr); }

Lệnh Test_and_Set 





Vấn đề với việc sử dụng semaphore: hàm P(S) là một đoạn chương trình gồm nhiều lệnh → có thể gây ra vấn đề nếu tiến trình bị giành quyền khi đang thực hiện hàm P(S). Ví dụ: Nếu tiến trình bị giành quyền sau khi đã thoát khỏi vòng lặp while trong P(S) nhưng trước khi kịp gán S=True → tiến trình khác vẫn có thể vào CS. Sử dụng lệnh Test_and_Set void P(S) {while(Test_and_Set(S));} Với hầu hết CPU, lệnh Test_and_Set khi dịch ra ngôn ngữ máy chỉ là 1 lệnh → không thể bị ngắt giữa chừng.

Các kỹ thuật Truyền thông và Đồng bộ     

Đệm kép (Double buffering) Hộp thư (Mailbox) Cờ hiệu (Semaphore) Giải quyết tắc nghẽn Priority Inheritance Protocol và Priority Ceiling Protocol

Các điều kiện cần để có thể xảy ra tắc nghẽn   

 

Các tiến trình là loại trừ lẫn nhau đối với tài nguyên dùng chung. Các tiến trình chờ đợi vòng tròn. Giữ và đợi (Hold and wait): Khi tiến trình được cấp tài nguyên, nó sẽ giữ cho tới khi tất cả các yêu cầu về tài nguyên của nó được thỏa mãn. Không có giành quyền ưu tiên đối với tài nguyên. Ví dụ điển hình: bài toán Dining Philosophers

Giải pháp 



Loại bỏ tắc nghẽn: Tìm cách loại bỏ ít nhất 1 trong 4 điều kiện của tắc nghẽn. Ví dụ: mỗi tiến trình chỉ được giữ tài nguyên trong một khoảng thời gian có giới hạn. Tránh tắc nghẽn: Chỉ cấp tài nguyên cho 1 yêu cầu nếu điều đó đảm bảo hệ thống vẫn ở trạng thái an toàn (Banker’s algorithm → mô phỏng hành vi của một ngân hàng). An toàn: Số tài nguyên còn rảnh của hệ thống đủ để đáp ứng tất cả yêu

Ví dụ: Banker’s algorithm 1 tài nguyên có 10 blocks Tiến trình Max. Yêu cầu Đã cấp Còn cần A 6 2 0 6 B 5 3 0 5 C 7 1 0 7 Cấp 6 blocks theo yêu cầu → còn 4 blocks (an toàn) Tiến trình Max. Yêu cầu Đã cấp Còn cần A 6 2 2 4 B 5 0 3 2 C 7 0 1 6

Ví dụ: Banker’s algorithm (tiếp) Tiến trình Max. Yêu cầu Đã cấp Còn cần A 6 0 4 2 B 5 0 3 2 C 7 1 1 6 Nếu cấp 1 block theo yêu cầu → còn 1 block → hệ thống sẽ rơi vào trạng thái không an toàn → không cấp.

Các kỹ thuật Truyền thông và Đồng bộ     

Đệm kép (Double buffering) Hộp thư (Mailbox) Cờ hiệu (Semaphore) Giải quyết tắc nghẽn Priority Inheritance Protocol và Priority Ceiling Protocol

Hiện tượng đảo mức ưu tiên 

Tiến trình có mức ưu tiên cao hơn có thể bị chặn bởi tiến trình có mức ưu tiên thấp hơn: Tiến trình có mức ưu tiên thấp vào CS trước và bị giành quyền trong khi đang ở trong CS, tiến trình có mức ưu tiên cao giành được quyền thực hiện, nhưng sẽ không vào được CS của tài nguyên do tiến trình có mức ưu tiên thấp đang chiếm giữ → hiện tượng tiến trình có mức ưu tiên cao bị chặn bởi tiến trình có mức ưu

Giải pháp 1: Priority Inheritance Protocol 



Tiến trình đang ở trong CS sẽ tạm thời nhận mức ưu tiên của tiến trình có mức ưu tiên cao nhất trong số các tiến trình bị nó chặn ở CS. Tuy nhiên, PIP không hoàn toàn loại bỏ tắc nghẽn. Ví dụ: Xét 2 tiến trình A và B như sau A: …P(S1)…P(S2)…V(S2)…V(S1)… B: …P(S2)…P(S1)…V(S1)…V(S2)… Nếu A có mức ưu tiên cao hơn, B vào được CS bảo vệ bởi S2 rồi bị giành quyền → A sẽ vào được CS bảo vệ bởi S1 → tắc nghẽn.

Giải pháp 2: Priority Ceiling Protocol 

Tiến trình đang ở trong CS của một tài nguyên sẽ tạm thời nhận mức ưu tiên của tiến trình có mức ưu tiên cao nhất trong số các tiến trình có quyền truy nhập tài nguyên đó → tiến trình đang ở trong CS không thể bị giành quyền.

Nội dung 

 



NHÂN HỆ ĐIỀU HÀNH THỜI GIAN THỰC CÁC LÝ THUYẾT CƠ SỞ TRUYỀN THÔNG VÀ ĐỒNG BỘ GIỮA CÁC TIẾN TRÌNH QUẢN LÝ BỘ NHỚ