Hệ điều hành - Chương 4: Quản lý tiến trình, đồng bộ hóa tiến trình & tắc nghẽn - Trần Công Án

Hệ Điều Hành Chương 4. Quản Lý Tiến Trình, Đồng bộ hóa Tiến trình & Tắc nghẽn Giảng viên TS. Trần Công Án tcan@cit.ctu.edu.vn Khoa Công Nghệ Thông Tin & Truyền Thông Đại học Cần Thơ 2018 [HĐH] Ch4. Quản lý tiến trình Mục Tiêu Giới thiệu các khái niệm về Tiến trình và những thao tác cơ bản trong Quản lý Tiến trình như tạo, định thời và kết thúc tiến trình. Các phương thức Giao tiếp liên tiến trình và vấn đề Tắc nghẽn của tiến trình cũng sẽ được trình bày. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 2 [HĐH] Ch4. Quản lý tiến trình Nội Dung Tổng quan về tiến trình Giao tiếp liên tiến trình Định thời tiến trình Các giải thuật định thời Đồng bộ hóa tiến trình Tắc nghẽn (Deadlock) TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 3 [HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Tổng quan về tiến trình TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 4 [HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Khái niệm Tiến trình Khái Niệm Tiến Trình I Tiến trình là thể hiện (instance) của một chương trình máy tính trong bộ nhớ, đang thực thi hoặc chờ thực thi. I Mỗi tiến trình thường được gán 1 số định danh tiến trình (process identifier, pid), dùng để định danh các tiến trình. I Một tiến trình bao gồm: I Mã lệnh chương trình (program code) I Bộ đếm chương trình (program counter) và các thanh ghi của CPU I Ngăn xếp (stack) I Phần dữ liệu (data section) I Có thể gồm phần bộ nhớ cấp phát động khi tiến trình thực thi (heap) TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 5 [HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Khái niệm Tiến trình Chương Trình & Tiến Trình I Chương trình là một thực thể bị động, được lưu trữ trên đĩa. I Tiến trình là một thực thể chủ động, lưu trú trên bộ nhớ chính. I Khi một chương trình được kích hoạt (nhấp chuột, CLI, . . . ), một thể hiện của chương trình sẽ được nạp lên bộ nhớ, tạo ra 1 tiến trình. I Một chương trình có thể có vài tiến trình trong bộ nhớ. text 0 max data heap stack TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 6 [HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Trạng thái của Tiến trình (Process state) Trạng Thái Của Tiến Trình (Process State) I Một tiến trình có thể có một trong các trạng thái sau: I new: tiến trình đang được khởi tạo. I running: các chỉ thị của tiến trình đang được thực thi. I waiting: tiến trình đang chờ đợi một sự kiện nào đó xảy ra (hoàn thành I/O, tín hiệu từ tiến trình khác, . . . ). I ready: tiến trình sẵn sàng để thực thi (đang đợi để được sử dụng CPU). I terminated: tiến trình đã kết thúc. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 7 [HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Trạng thái của Tiến trình (Process state) Sơ Đồ Chuyển Trạng Thái Của Tiến Trình new terminated runningready admitted interrupt scheduler dispatchI/O or event completion I/O or event wait exit waiting TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 8 [HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Khối điều khiển Tiến trình (Process Control Block – PCB) Khối Điều Khiển Tiến Trình (PCB) I Chứa thông tin của tiến trình trong Hệ điều hành: I Trạng thái của quá trình: ready, running, . . . I Bộ đếm chương trình: chỉ thị kế tiếp sẽ được thực thi I Các thanh ghi: phụ thuộc vào k/trúc máy tính I Thông tin về định thời sử dụng CPU I Thông tin về quản lý bộ nhớ I Thông tin về chi phí: t/gian sử dụng CPU, pid, . . . I Thông tin về trạng thái nhập/xuất: các thiết bị đang được cấp phát, danh sách tập tin đang mở, . . . process state process number program counter memory limits list of open files registers • • • TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 9 [HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Chuyển CPU giữa các Tiến trình Chuyển CPU Giữa Các Tiến Trình I PCB là nơi lưu giữ trạng thái của tiến trình I Trạng thái của tiến trình phải được lưu trữ vào PCB khi một interrupt xuất hiện, nhằm cho phép tiến trình có thể tiếp tục chính xác về sau. I Tác vụ chuyển CPU còn được gọi là chuyển ngữ cảnh (context switch). process P0 process P1 save state into PCB0 save state into PCB1 reload state from PCB1 reload state from PCB0 operating system idle idle executingidle executing executing interrupt or system call interrupt or system call • • • • • • TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 10 [HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Các thao tác trên Tiến trình Tạo Tiến Trình I Một tiến trình (cha) có thể tạo những tiến trình khác (con) . . . I Quan hệ “cha–con” của các tiến trình tạo nên cây tiến trình. init! pid = 1! login! pid = 2234! kthreadd! pid = 2! sshd! pid = 2244! khelper! pid = 6! bash! pid = 8111! khelper! pid = 6! sshd! pid = 2244! . . . . . . . . . . . . TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 11 [HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Các thao tác trên Tiến trình Kết Thúc Tiến Trình I T/trình thực thi câu lệnh cuối cùng và yêu cầu HĐH xóa nó (exit()) I Truyền dữ liệu từ tiến trình con lên tiến trình cha (wait()). I Thu hồi tài nguyên đã được cấp phát cho tiến trình. I Tiến trình con kết thúc trước khi t/trình cha gọi wait() ⇒ zombie I Tiến trình con còn thực thi khi t/trình cha đã kết thúc ⇒ orphan I Tiến trình cha có thể kết thúc tiến trình con (abort()): I Tiến trình con đã có vượt quá số tài nguyên được cấp. I Công việc giao cho tiến trình con làm nay không còn cần thiết nữa. I Tiến trình cha đang thoát: một vài HĐH không cho phép orphan. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 12 [HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Giao tiếp liên tiến trình TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 13 [HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Hợp Tác Tiến Trình (Cooperating Process) I Tiến trình độc lập: không thể ảnh hưởng hoặc không bị ảnh hưởng bởi sự thực thi của quá trình khác. I Hợp tác tiến trình: có thể ảnh hưởng hoặc bị ảnh hưởng bởi sự thực thi của quá trình khác. I Thuận lợi của sự hợp tác quá trình: I Chia sẻ thông tin I Gia tăng tốc độ tính toán (nếu máy có nhiều CPU) I Module hóa I Tiện dụng TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 14 [HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Giao Tiếp Liên Tiến Trình I Các tiến trình muốn trao đổi dữ liệu với nhau cần sử dụng cơ chế giao tiếp liên tiến trình (interprocess communication, IPC): bộ nhớ chia sẻ 124 Chapter 3 Processes process A message queue kernel (a) (b) process A shared memory kernel process B m0 m1 m2 ...m3 mn process B Figure 3.12 Communications models. (a) Message passing. (b) Shared memory. memory regions. Once shared memory is established, all accesses are treated as routine memory accesses, and no assistance from the kernel is required. Recent research on systems with several processing cores indicates that message passing provides better performance than shared memory on such systems. Shared memory suffers from cache coherency issues, which arise because shared data migrate among the several caches. As the number of processing cores on systems increases, it is possible that we will see message passing as the preferred mechanism for IPC. In the remainder of this section, we explore shared-memory and message- passing systems in more detail. 3.4.1 Shared-Memory Systems Interprocess communication using shared memory requires communicating processes to establish a region of shared memory. Typically, a shared-memory region resides in the address space of the process creating the shared-memory segment. Other processes that wish to communicate using this shared-memory segment must attach it to their address space. Recall that, normally, the operating system tries to prevent one process from accessing another process’s memory. Shared memory requires that two or more processes agree to remove this restriction. They can then exchange information by reading and writing data in the shared areas. The form of the data and the location are determined by these processes and are not under the operating system’s control. The processes are also responsible for ensuring that they are not writing to the same location simultaneously. To illustrate the concept of cooperating processes, let’s consider the producer–consumer problem, which is a common paradigm for cooperating processes. A producer process produces information that is consumed by a consumer process. For example, a compiler may produce assembly code that is consumed by an assembler. The assembler, in turn, may produce object modules that are consumed by the loader. The producer–consumer problem truyền thông điệp process A message queue kernel process B m0 m1 m2 ...m3 mn TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 15 [HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Bộ nhớ chia sẻ (Shared-memory) Bộ Nhớ Chia Sẻ (Shared-Memory) I Một vùng đệm (buffer) được dùng để chia sẻ dữ liệu giữa các t/trình: I kích thước không giới hạn (unbounded buffer): tiến trình đọc có thể chờ, tiến trình ghi không bao giờ chờ. I kích thước có giới hạn (bounded buffer): cả tiến trình đọc và ghi có thể chờ. I Ví dụ kinh điển “Nhà sản xuất – Người tiêu thụ”: tiến trình Nhà sản xuất sinh dữ liệu, được sử dụng bởi tiến trình Người tiêu thụ. I Tạo 1 vùng nhớ đệm (buffer) chung. I Tiến trình Nhà sản xuất ghi dữ liệu lên buffer. I Tiến trình Người tiêu thụ lấy dữ liệu từ buffer. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 16 [HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Bộ nhớ chia sẻ (Shared-memory) Tạo Vùng Đệm (Buffering) #define BUFFER_SIZE 10 ! ! typedef struct {! . . . ! } item;! ! item buffer[BUFFER_SIZE]; ! ! int in_item = 0; ! int out_item = 0; TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 17 [HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Bộ nhớ chia sẻ (Shared-memory) Nhà Sản Xuất (Producer) item next_produced; ! ! while (true) { ! /* produce an item in next produced */! ! while (((in_item + 1) % BUFFER_SIZE) == out_item) ! ; /* do nothing */! ! buffer[in_item] = next_produced; !! in_item = (in_item + 1) % BUFFER_SIZE;! counter++;! }   TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 18 [HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Bộ nhớ chia sẻ (Shared-memory) Người Tiêu Dùng (Consumer) item next_consumed; ! ! while(true){ 
 while(in_item == out_item)! ; /* do nothing */ !! ! next_consumed = buffer[out_item]; !! out_item = (out_item + 1) % BUFFER_SIZE; 
 ! /* consume the item in next consumed */ ! }   TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 19 [HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Truyền thông điệp (Message passing) Truyền Thông Điệp (Message Passing) I Giao tiếp giữa các tiến trình không cần dùng bộ nhớ chia sẻ ⇒ hữu ích trong môi trường phân tán, giao tiếp qua mạng. I Cần hai thao tác: send(msg) và receive(msg). I Tiến trình P và Q muốn giao tiếp với nhau: I Tạo một nối kết giao tiếp (communication link) I Trao đổi thông điệp thông qua send/receive I Phương thức cài đặt nối kết giao tiếp (mức luận lý): I Giao tiếp trực tiếp hay gián tiếp I Đồng bộ hay bất đồng bộ I Kích thước thông điệp cố định hay biến đổi TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 20 [HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Truyền thông điệp (Message passing) Giao Tiếp Trực Tiếp (Direct Communication) I Các quá trình phải được đặt tên rõ ràng: I Send(P, msg): gởi thông điệp tới quá trình P. I Receive(Q, msg): nhận thông điệp từ quá trình Q. I Các thuộc tính của nối kết giao tiếp: I Các nối kết được thiết lập tự động. I Một nối kết kết hợp với chính xác một cặp quá trình. I Giữa mỗi cặp quá trình tồn tại chính xác một nối kết. I Nối kết có thể một hướng, nhưng thường là hai hướng. I Giao tiếp bất đối xứng: Send(P, msg), Receive(id, msg). TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 21 [HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Truyền thông điệp (Message passing) Giao Tiếp Gián Tiếp (Indirect Communication) I Các thông điệp được gửi và nhận thông qua mailbox hay port. I Mỗi mailbox có một định danh (id) duy nhất. I Các quá trình chỉ có thể giao tiếp nếu chúng dùng chung mailbox. I Send/Receive(A, msg): gởi/nhận thông điệp tới/từ hộp thư A. I Các thuộc tính của nối kết gián tiếp: I Nối kết chỉ được thiết lập nếu các quá trình chia sẻ một hộp thư chung. I Một nối kết có thể kết hợp với nhiều quá trình. I Mỗi cặp quá trình có thể dùng chung nhiều nối kết giao tiếp. I Nối kết có thể một hướng hay hai hướng. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 22 [HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Truyền thông điệp (Message passing) Các Tác Vụ Trong Giao Tiếp Gián Tiếp I Các tác vụ cơ bản: tạo mailbox mới, gửi và nhận thông điệp qua mailbox, và xóa mailbox. I Chia sẻ mailbox: I Các tiến trình có thể chia sẻ cùng 1 mailbox. I Vấn đề: nếu 1 tiến trình gửi thì tiến trình nào sẽ nhận? I Giải pháp cho việc chia sẻ mailbox: I Một liên kết chỉ tương ứng với 2 tiến trình. I Chỉ cho phép 1 tiến trình thực hiện thao tác nhận tại 1 thời điểm. I HĐH chỉ định tiến trình nhận (1 tiến trình), và thông báo cho tiến trình gửi biết người nhận. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 23 [HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Truyền thông điệp (Message passing) Đồng Bộ Hóa (Synchronisation) I Truyền thông điệp có thể chặn (blocking) hay không chặn (non-blocking). I Blocking được xem là đồng bộ (synchronous): I Blocking send: tiến trình gửi chờ cho đến khi thông điệp được nhận. I Blocking receive : tiến trình nhận chờ cho đến khi thông điệp sẵn sàng . I Non-blocking được xem là bất đồng bộ (asynchronous): I Non-blocking send: gửi thông điệp và tiếp tục thực hiện công việc khác. I Non-blocking receive: nhận một thông điệp hay rỗng. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 24 [HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Truyền thông điệp (Message passing) Tạo Vùng Đệm (Buffering) I Vùng đệm dùng để chứa các thông điệp của 1 nối kết. I Ba cách cài đặt: I Sức chứa là 0 (zero capacity): tiến trình gửi bị chặn đến khi thông điệp được nhận (no buffering!?). I Sức chứa giới hạn (bounded capacity): kích thước vùng đệm giới hạn n thông điệp. Tiến trình gửi bị chặn khi vùng đệm bị đầy. I Sức chứa không giới hạn (unbounded capacity): kích thước không giới hạn. Tiến trình gửi không bao giờ bị chặn. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 25 [HĐH] Ch4. Quản lý tiến trình Định thời tiến trình Định thời tiến trình TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 26 [HĐH] Ch4. Quản lý tiến trình Định thời tiến trình I Định thời biểu CPU là một chức năng cơ bản và quan trọng của các HĐH đa chương. I Chức năng: phân bổ thời gian/thời điểm sử dụng CPU cho các tiến trình trong hệ thống, nhằm: I tăng hiệu năng (CPU utilisation) sử dụng CPU I giảm thời gian đáp ứng (response time) của hệ thống I Ý tưởng cơ bản: phân bố thời gian rãnh rỗi của CPU (khi chờ đợi tiến trình đang thực thi thực hiện các thao tác nhập xuất) cho các tiến trình khác trong hệ thống. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 27 [HĐH] Ch4. Quản lý tiến trình Định thời tiến trình Chu Kỳ CPU–I/O (CPU–I/O Burst) I Chu kỳ CPU–I/O: I Sự thực thi của tiến trình bao gồm nhiều chu kỳ CPU–I/O. I Một chu kỳ CPU–I/O bao gồm chu kỳ thực thi CPU (CPU burst) và chu kỳ chờ đợi vào/ra (I/O burst). I Sự phân bổ sử dụng CPU: I Chương trình hướng nhập xuất (I/O-bound) thường có nhiều chu kỳ CPU ngắn. I Chương trình hướng xử lý (CPU-bound) thường có nhiều chu kỳ CPU dài. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 28 [HĐH] Ch4. Quản lý tiến trình Định thời tiến trình Ví Dụ Về Chu Kỳ CPU–I/O ••• load store add store read from file wait for I/O store increment index write to file wait for I/O wait for I/O load store add store read from file ••• CPU burst I/O burst CPU burst CPU burst I/O burst I/O burst TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 29 [HĐH] Ch4. Quản lý tiến trình Định thời tiến trình Bộ Định Thời CPU (CPU Scheduler) I Còn gọi là bộ định thời ngắn kỳ, chọn một trong các tiến trình trong hàng đợi sẵn sàng và cấp phát CPU cho nó thực thi. I Quyết định định thời xảy ra khi một tiến trình: 1. chuyển từ trạng thái đang chạy sang trạng thái chờ đợi 2. chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng 3. chuyển từ trạng thái chờ đợi sang trạng thái sẵn sàng 4. kết thúc TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 30 [HĐH] Ch4. Quản lý tiến trình Định thời tiến trình Định Thời Trưng Dụng & Không Trưng Dụng I Định thời không trưng dụng (nonpreemptive scheduling): I Tiến trình được phân CPU có quyền sử dụng CPU đến khi sử dụng xong (k/thúc hoặc chuyển sang trạng thái chờ, như trường hợp 1 và 4). I Định thời trưng dụng (preemptive scheduling): I Bộ định thời có thể thu hồi CPU của tiến trình bất kỳ lúc nào để phân cho tiến trình khác (trường hợp 2 và 3). I Phức tạp hơn định thời không trưng dụng vì nó phải giải quyết: I sự cạnh tranh dữ liệu giữa các tiến trình. I sự trưng dụng khi tiến trình đang thực thi trong chế độ kernel. I dàn xếp giữa sự trưng dụng và xử lý các ngắt của hệ thống. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 31 [HĐH] Ch4. Quản lý tiến trình Định thời tiến trình Bộ Điều Phối (Dispatcher) I Có nhiệm vụ thực thi việc trao quyền sử dụng CPU cho tiến trình được cấp phát CPU bởi bộ định thời. I Bao gồm các tác vụ: I Chuyển ngữ cảnh I Chuyển sang chế độ người dùng I Nhảy tới vị trí thích hợp trong chương trình người dùng để khởi động lại chương trình đó. I Độ trễ điều phối (dispatcher latency): thời gian dispatcher cần để ngưng một tiến trình và khởi động một tiến trình khác. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 32 [HĐH] Ch4. Quản lý tiến trình Định thời tiến trình Tiêu chí cho việc định thời Tiêu Chí Cho Việc Định Thời 1. Hiệu suất sử dụng CPU: tỷ lệ giữa thời gian CPU được sử dụng trên tổng thời gian hoạt động của hệ thống. 2. Thời gian đáp ứng (response time): lượng thời gian từ lúc một yêu cầu được đệ trình cho đến khi bắt đầu được đáp ứng. 3. Thời gian chờ đợi (waiting time): tổng thời gian 1 tiến trình nằm trong hàng đợi sẵn sàng (ready queue). 4. Thời gian xoay vòng (turnaround time): tổng thời gian để thực thi một t/trình, bao gồm các khoảng t/gian: thực thi, chờ I/O, chờ trong ready queue (= t/điểm kết thúc – t/điểm bắt đầu vào ready queue). 5. Thông lượng (throughput): số lượng tiến trình hoàn thành trên một đơn vị thời gian. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 33 [HĐH] Ch4. Quản lý tiến trình Định thời tiến trình Tiêu chí cho việc định thời Tối Ưu Hóa Các Tiêu Chí Các giải thuật định thời được đánh giá thông qua khả năng tối ưu hóa các tiêu chí định thời của nó: 1. Hiệu suất sử dụng CPU: càng lớn càng tốt 2. Thông lượng: càng lớn càng tốt 3. Thời gian xoay vòng: càng nhỏ càng tốt 4. Thời gian chờ đợi: càng nhỏ càng tốt 5. Thời gian đáp ứng: càng nhỏ càng tốt TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 34 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Các Giải Thuật Định Thời 1. First-come, first-served (FCFS): đến trước được phục vụ trước. 2. Shortest-job-rirst (SJF): công việc ngắn nhất trước. 3. Priority: dựa trên độ ưu tiên. 4. Round-robin (RR): xoay vòng. 5. Multilevel scheduling: hàng đợi đa cấp. 6. Multilevel feedback-queue scheduling: hàng đợi phản hồi đa cấp. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 35 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời First-come, first-served First-Come, First Served (FCFS) I Là giải thuật định thời đơn giản nhất, dựa trên nguyên tắc đến trước, được phục vụ trước. I Cài đặt: phương pháp đơn giản nhất là dùng hàng đợi FIFO. I Ưu điểm: cài đặt dễ dàng, đơn giản và dễ hiểu. I Nhược điểm: I Thời gian chờ đợi trung bình thường là dài. I Không thích hợp cho hệ thống phân chia thời gian do đây là giải thuật định thời không trưng dụng (nonpreemptive). TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 36 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời First-come, first-served FCFS – Ví Dụ 1 I Cho các tiến trình với thời gian thực thi và thứ tự xuất hiện như sau: Process   TG  sử  dụng  CPU   Thứ  tự  xuất  hiện   P1    24   1   P2    3   2   P3    3   3   (g/s tgian xuất hiện là t = 0) I Biểu đồ Gantt cho lịch biểu: P1   P2   P3   0 24 27 30 I Thời gian chờ đợi: P1 = 0; P2 = 24; P3 = 27 I Thời gian chờ đợi trung bình: (0+ 24+ 27)/3 = 17 TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 37 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời First-come, first-served FCFS – Ví Dụ 2 I Giả sử các tiến trình trong ví dụ 1 xuất hiện theo thứ tự P2,P3,P1; biểu đồ Gantt của lịch biểu là: P2   P3   P1   0 3 30 6 I Thời gian chờ đợi: P1 = 6,P2 = 0,P3 = 3 I Thời gian chờ đợi trung bình: (6+ 0+ 3)/3 = 3 ⇒ tốt hơn nhiều so với ví dụ 1 (17) I Tình trạng thời gian chờ đợi dài do tiến trình ngắn nằm sau tiến trình dài được gọi là “hiệu ứng nối đuôi” (convoy effect). TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 38 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Shortest-job-first Shortest-Job-First (SJF) I Ý tưởng cơ bản: phân phối CPU cho tiến trình nào có thời gian thực thi CPU (CPU burst) kế tiếp nhỏ nhất (shortest-next-CPU-burst alg.) I Mỗi tiến trình sẽ được gán 1 độ dài thời gian của lần sử dụng CPU kế tiếp (dự đoán). I Có 2 cách tiếp cận cho việc phân bổ CPU: I Không trưng dụng: tiến trình được giao CPU sẽ chiếm giữ CPU đến khi nó thực thi xong CPU burst. I Trưng dụng: nếu 1 tiến trình mới đến có CPU burst ngắn hơn thời gian thực thi còn lại của tiến trình đang thực thi, CPU sẽ được lấy lại để giao cho tiến trình mới (shortest-remaining-time-first algorithm, SRTF) I SJF cho thời gian chờ đợi trung bình tối ưu (ngắn nhất). TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 39 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Shortest-job-first SJF Không Trưng Dụng – Ví Dụ Process   TG  sử  dụng  CPU  kế  3ếp   Thời  gian  xuất  hiện   P1   7   0   P2   4   2   P3   1   4   P4   4   5   I Biểu đồ Gantt cho lịch biểu: 0 P1   P3   P2   P4   7 8 12 16 I Thời gian chờ đợi trung bình: (0+ 6+ 3+ 7)/4 = 4 TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 40 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Shortest-job-first SJF Trưng Dụng – Ví Dụ Process   TG  sử  dụng  CPU  kế  3ếp   Thời  gian  xuất  hiện   P1   7   0   P2   4   2   P3   1   4   P4   4   5   I Biểu đồ Gantt cho lịch biểu: 0 2 P1   P2   P3   P2   P4   P1   4 7 11 16 5 I Thời gian chờ đợi trung bình: (9+ 1+ 0+ 2)/4 = 3 TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 41 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Shortest-job-first Thời Gian Sử Dụng CPU Lần Kế Tiếp I Chỉ có thể ước lượng, dựa vào lịch sử của những lần sử dụng CPU trước đó. I Thời gian sử dụng CPU kế tiếp (công thức trung bình mũ): Tn+1 = αtn + (1− α)Tn I Tn+1: ước lượng thời gian sử dụng CPU lần n + 1 I tn: thời gian sử dụng CPU thực tế lần thứ n I α ∈ [0, 1]: hệ số trung bình mũ, dùng để điều chỉnh trọng số cho các giá trị lịch sử (thông thường được gán giá trị 1/2) TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 42 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Shortest-job-first Thời Gian Sử Dụng CPU Lần Kế Tiếp I Ví dụ: ước lượng thời gian sử dụng CPU lần kế tiếp, với α = 1/2,T0 = 10 6 4 6 4 13 13 13 810 6 6 5 9 11 12 CPU burst (ti) "guess" (τi) ti τi 2 time 4 6 8 10 12 TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 43 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Shortest-job-first Tùy Biến Hệ Số Trung Bình Mũ I α = 0 ⇒ Tn+1 = Tn = . . . = T0 ⇒ không tính đến lịch sử: tình trạng/sự thực thi “hiện thời” được coi như nhất thời, không có ý nghĩa. I α = 1⇒ Tn+1 = tn ⇒ chỉ tính đến thời gian sử dụng CPU thực tế gần nhất. I α = 1/2: các giá trị lịch sử thực tế và dự đoán có trọng số tương đương. I Nếu mở rộng công thức, ta có: Tn+1 = αtn + (1− α)αtn−1 + . . .+ (1− α)jαtn−j + . . . (1− α)n+1T0 I Vì α và (1− α) ≤ 1, trọng số của giá trị lịch sử càng xa thì càng nhỏ. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 44 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật định thời có ưu tiên Giải Thuật Định Thời Có Ưu Tiên (Priority) I Ý tưởng: I Mỗi tiến trình sẽ được gán một chỉ số ưu tiên (priority number, int) . I CPU sẽ được cấp phát cho tiến trình có chỉ số ưu tiên cao nhất, thông thường là nhỏ nhất. I SJF là trường hợp đặc biệt của giải thuật này, trong đó thời gian thực thi CPU kế tiếp đóng vai trò là chỉ số ưu tiên. I Có thể cài đặt theo phương pháp trưng dụng hay không trưng dụng. I Có thể xảy ra tình trạng “chết đói” (starvation): các tiến trình độ ưu tiên thấp không bao giờ được thực thi. ⇒ Giải pháp: dùng sự “lão hóa” (aging) – các tiến trình đang chờ đợi trong hệ thống sẽ được tăng dần độ ưu tiên theo thời gian chờ đợi. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 45 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật định thời có ưu tiên Ví Dụ Process   Thời  điểm  xuất  hiện   Độ  ưu  8ên   Thời  gian  xử  lý   P1   0   3    24   P2   1   1    3   P3   2   2    3   I Không trưng dụng: T/gian chờ đợi trung bình = (0+ 23+ 25)/3 = 16 Biểu đồ Gantt: P1   P2   P3   0 24 27 30 I Trưng dụng: T/gian chờ đợi trung bình = (6+ 0+ 2)/3 = 2.7 Biểu đồ Gantt: P1   P2   P3   P1   0 1 4 7 30 TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 46 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật định thời luân phiên (Round-Robin, RR) Giải Thuật Định Thời Luân Phiên I Bộ điều phối cấp phát xoay vòng cho mỗi tiến trình trong hàng đợi sẵn sàng một đơn vị thời gian, gọi là định mức thời gian (time quantum, thường khoảng 10–100ms). I Sau khi sử dụng hết t/gian được cấp, CPU bị thu hồi để cấp cho tiến trình khác, tiến trình bị thu hồi CPU sẽ chuyển vào hàng đợi sẵn sàng. I Bộ đếm thời gian (timer) sẽ phát ra các ngắt sau mỗi định mức thời gian để xoay vòng cấp phát CPU. I Nếu hàng đợi sẵn sàng có n tiến trình, định mức thời gian là q: I mỗi tiến trình sẽ nhận được 1/n tổng thời gian CPU, trong đó thời gian mỗi lần sử dụng tối đa là q I không có tiến trình nào chờ đợi quá lượng thời gian (n − 1)× q TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 47 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật định thời luân phiên (Round-Robin, RR) Các Tùy Biến & Hiệu Năng I q lớn: RR trở thành giải thuật FCFS (FIFO) I q nhỏ: q phải đủ lớn so với thời gian chuyển ngữ cảnh, nếu không, hao phí chuyển ngữ cảnh sẽ rất cao. process time  10 quantum context switches 12 0 6 1 1 9 0 10 0 10 0 1 2 3 4 5 6 7 8 9 10 6 TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 48 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật định thời luân phiên (Round-Robin, RR) Các Tùy Biến & Hiệu Năng a ve ra ge tu rn ar ou nd ti m e 1 12.5 12.0 11.5 11.0 10.5 10.0 9.5 9.0 2 3 4 time quantum 5 6 7 P1 P2 P3 P4 6 3 1 7 process time TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 49 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật định thời luân phiên (Round-Robin, RR) Ví Dụ Process   Thời  gian  sử  dụng  CPU   P1    53   P2    17   P3    68   P4    24   I Với time quantum = 20 I Biểu đồ Gantt: P1   P2   P3   P4   P1   P3   P4   P1   P3   P3   0 20 37 57 77 97 117 121 134 154 162 I Thông thường, RR có thời gian chờ đợi trung bình lớn hơn SJF, nhưng đảm bảo thời gian đáp ứng tốt hơn. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 50 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật hàng đợi đa cấp (Multilevel Queue) Giải Thuật Hàng Đợi Đa Cấp I Chia hàng đợi s/sàng ra thành nhiều hàng đợi với độ ưu tiên khác nhau, ví dụ: I foreground: tương tác, cần ưu tiên cao hơn. I background: bó, cần ít ưu tiên hơn. I Các tiến trình sẽ được phân phối vào các hàng đợi dựa trên các đặc tính như loại tiến trình (foreground/background), độ ưu tiên, . . . I Mỗi hàng đợi sẽ được áp dụng một giải thuật định thời riêng, tùy vào tính chất của hàng đợi; ví dụ: I foreground (tương tác): cần thời gian đáp ứng nhanh hơn ⇒ RR I background (bó): có thể đáp ứng chậm hơn ⇒ FCFS TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 51 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật hàng đợi đa cấp (Multilevel Queue) Chiến Lược Định Thời Giữa Các Hàng Đợi I Định thời với độ ưu tiên cố định: I Phục vụ tất cả các t/trình trong hàng đợi ưu tiên cao (vd: foreground) rồi mới đến hàng đợi có độ ưu tiên thấp hơn (vd: background). I Có khả năng dẫn đến tình trạng “chết đói” (starvation) CPU. I Định thời với phân chia thời gian (time-slice): I Mỗi hàng đợi sẽ nhận được một khoảng thời gian nào đó của CPU để định thời cho các tiến trình nằm trong đó. I Ví dụ: 80% cho foreground với RR, và 20% cho background với FCFS. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 52 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật hàng đợi đa cấp (Multilevel Queue) Ví Dụ Hàng Đợi Đa Cấp system processes highest priority lowest priority interactive processes interactive editing processes batch processes student processes TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 53 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật hàng đợi phản hồi đa cấp (Multilevel Feedback Queue) Giải Thuật Hàng Đợi Phản Hồi Đa Cấp I Hàng đợi sẵn sàng cũng tổ chức giống như trong giải thuật Hàng đợi đa cấp. I Một tiến trình có thể di chuyển giữa các hàng đợi khác nhau. I Cơ chế định thời có thể được cài đặt theo cách: I Nếu tiến trình dùng quá nhiều thời gian CPU, nó sẽ được di chuyển vào hàng đợi có độ ưu tiên thấp hơn. I Nếu tiến trình đã chờ quá lâu trong 1 hàng đợi với độ ưu tiên thấp, nó sẽ được chuyển sang hàng đợi có độ ưu tiên cao hơn (cơ chế “sự lão hóa”). TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 54 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật hàng đợi phản hồi đa cấp (Multilevel Feedback Queue) Tham Số Của Bộ Định Thời I Bộ định thời đa cấp có phản hồi có thể được định nghĩa bằng những tham số sau: I Số lượng hàng đợi I Giải thuật định thời cho từng hàng đợi I Phương thức dùng để quyết định khi nào thì nâng cấp một tiến trình. I Phương thức dùng để quyết định khi nào thì hạ cấp một tiến trình I Phương thức dùng để quyết định là nên đặt tiến trình vào hàng đợi nào khi tiến trình này cần được phục vụ. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 55 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật hàng đợi phản hồi đa cấp (Multilevel Feedback Queue) Ví Dụ Về Hàng Đợi Phản Hồi Đa Cấp I Các hàng đợi: I Q0: FCFS + quantum-time 8ms I Q1: FCFS + quantum-time 16ms I Q2: original FCFS I Định thời: I Một tiến trình mới P sẽ được phân vào Q0 với giải thuật định thời FCFS. Khi có được CPU, nó sẽ được sử dụng tối đa 8ms. quantum  8 quantum  16 FCFS I Nếu sau 8ms, P chưa hoàn thành thì CPU sẽ bị thu hồi để phân phối cho tiến trình khác và P sẽ được chuyển sang Q1. I Tại Q1, việc định thời diễn ra tương tự, với quantum-time là 16ms. Nếu P vẫn chưa hoàn thành thì nó sẽ được chuyển sang Q2 với giải thuật FCFS. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 56 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Định thời trong Windows Định Thời Trong Windows I Đơn vị cấp phát CPU trong các HĐH hiện nay là luồng (thread) thay vì tiến trình. I HĐH Windows dùng giải thuật định thời dựa trên độ ưu tiên (32 mức) và định mức thời gian (RR), sử dụng chiến lược trưng dụng. I Mỗi độ ưu tiên sẽ có 1 hàng đợi riêng. I Một luồng được chọn thực thi bởi bộ điều phối sẽ t/thi cho đến khi: I bị trưng dụng bởi luồng có mức ưu tiên cao hơn, hoặc I kết thúc (terminate), hoặc I hết định mức thời gian (time quantum), hoặc I thực hiện lời gọi I/O. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 57 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Định thời trong Windows Định Thời Trong Windows I Độ và nhóm ưu tiên của các luồng được chia như sau: high above normal normal below normal idle priority time-critical real- time 31 26 25 24 23 22 16 15 15 14 13 12 11 1 15 12 11 10 9 8 1 15 10 9 8 7 6 1 15 8 7 6 5 4 1 15 6 5 4 3 2 1 highest above normal normal lowest idle below normal I Ngoài ra, một số cơ chế để nâng/hạ độ ưu tiên cho cá luồng cũng được sử dụng (tương tự ý tưởng của g/thuật hàng đợi phản hồi đa cấp) TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 58 [HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Định thời trong Windows Chọn Lựa Tiến Trình Trong Windows I Bộ định thời duyệt qua các hàng đợi theo độ ưu tiên từ cao đến thấp. I Nếu không có tiến trình nào sẵn sàng, bộ định thời khởi động 1 tiến trình đặc biệt gọi là idle process. I Độ ưu tiên của t/trình bị trưng dụng có thể bị thay đổi. I Nếu sử dụng hết time quantum: độ ưu tiên giảm, nhưng không dưới mức “normal”. I Chuyển từ trạng thái chờ (waiting): độ ưu tiên tăng, mức độ tăng phụ thuộc vào t/trình đã chờ cái gì: đĩa – tăng nhiều, I/O – tăng ít hơn. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 59 [HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Đồng bộ hóa tiến trình TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 60 [HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Cạnh tranh và sự nhất quán dữ liệu Cạnh Tranh Và Sự Nhất Quan Dữ Liệu I Các tiến trình thực thi đồng thời, chia sẻ dữ liệu dùng chung có thể dẫn đến tình trạng không nhất quán (inconsistency) của dữ liệu. I Nhất quán = đúng đắn và chính xác; tùy thuộc vào ngữ cảnh, giao dịch. I Có 2 lý do chính để thực hiện đồng thời (cạnh tranh) các tiến trình: I Tăng hiệu suất sử dụng tài nguyên hệ thống. I Giảm thời gian đáp ứng trung bình của hệ thống. I Việc duy trì sự nhất quán của dữ liệu yêu cầu một cơ chế để đảm bảo sự thực thi một cách có thứ tự của các tiến trình có hợp tác với nhau. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 61 [HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Cạnh tranh và sự nhất quán dữ liệu Ví Dụ 1 – Giao Dịch Cạnh Tranh I Cho hai giao dịch: I T1: A mua hàng trị giá 50$ của P (50$: A → P) I T2: B mua hàng trị giá 100$ của P (100$: B → P) I Khởi tạo ban đầu: A=500; B=500; P=1000 T1 R(A) A = A - 50 W(A) R(P) P = P + 50 W(P) T2 R(B) B = B - 100 W(B) R(P) P = P + 100 W(P) I Yêu cầu về tính nhất quán: (A + B + P) không đổi; cụ thể hơn: I giá trị A, B, P sau khi thực hiện T1, T2 là: A=450; B=400; P=1150 I Nhận xét: I Nếu thực hiện tuần tự T1 → T2 hoặc T2 → T1, dữ liệu sẽ nhất quán. I Nếu thực hiện cạnh tranh (đồng thời), dữ liệu sẽ nhất quán??? TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 62 [HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Cạnh tranh và sự nhất quán dữ liệu Ví Dụ 1 – Giao Dịch Cạnh Tranh T1 T2 A/B P R(A) A = A - 50 W(A) R(P) P = P + 50 W(P) R(B) B = B - 100 W(B) R(P) P = P + 100 W(P) 450 400 1050 1100 Schedule 1 T1 T2 A/B P R(A) A = A – 50 W(A) R(P) P = P + 50 W(P) R(B) B = B - 100 W(B) R(P) P = P + 100 W(P) 400 450 1050 1150 Schedule 2 TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 63 [HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Tình trạng tranh đua (Race condition) Tình Trạng “Tranh Đua” (Race Condition) I Là tình trạng mà nhiều tiến trình cùng truy cập và thay đổi lên dữ liệu được chia sẻ, và giá trị cuối cùng của dữ liệu chia sẻ phụ thuộc vào tiến trình hoàn thành sau cùng. I giá trị của P trong ví dụ 1 I hoặc giá trị biến counter trong ví dụ 2 I Tình trạng tranh đua có thể dẫn đến tình trạng không nhất quán. I Để ngăn chặn tình trạng tranh đua, các tiến trình cạnh tranh cần phải được đồng bộ hóa (synchronize). TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 64 [HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Vấn đề miền tương trục (Critical-section problem) Vấn Đề Miền Tương Trục (CSP) I Xét 1 hệ thống có n tiến trình đang cạnh tranh {P0,P1, . . . ,Pn−1} I Miền tương trục (critical section): là một đoạn mã lệnh của các tiến trình có chứa các hành động truy cập dữ liệu được chia sẻ như: thay đổi các biến dùng chung, cập nhật CSDL, ghi tập tin, . . . ⇒ Để tránh tình trạng tranh đua, các hệ thống phải đảm bảo khi một tiến trình đang trong miền tương trục, không có một tiến trình nào khác được phép chạy trong miền tương trục của nó. I Vấn đề miền tương trục (critical-section problem): Thiết kế các giao thức để các tiến trình có thể sử dụng để hợp tác/cạnh tranh với nhau. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 65 [HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Vấn đề miền tương trục (Critical-section problem) Vấn Đề Miền Tương Trục (CSP) I Cần phải xác định được phần entry section và exit section. I Mỗi tiến trình phải xin phép để được vào miền tương trục (đi qua vùng entry section), và sau đó thoát khỏi miền tương trục (đi qua vùng exit section) và thực hiện phần còn lại (remainder section). I Giải pháp cho vấn đề miền tương trục tương đối phức tạp với với các hệ thống định thời trưng dụng. do { entry section critical section exit section remainder section } while (true); TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 66 [HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Các giải pháp cho vấn đề miền tương trục Yêu Cầu Đối Với Các Giải Pháp Cho CSP I Một giải pháp cho vấn đề miền tương trục phải thỏa 3 yêu cầu: 1. Loại trừ hỗ tương (mutual exclusion): Nếu 1 t/trình đang thực thi trong miền tương trục, không một tiến trình nào khác được đi vào miền tương trục của chúng. 2. Tiến triển (progress): Nếu không có tiến trình nào đang thực thi trong miền tương trục và tồn tại tiến trình đang chờ được thực thi trong miền tương trục của chúng, thì việc lựa chọn cho một tiến trình bước vào miền tương trục không thể bị trì hoãn vô hạn. 3. Chờ đợi hữu hạn (bounded wait): Mỗi t/trình chỉ phải chờ để được vào miền tương trục trong một khoảng t/gian có hạn định (không xảy ra tình trạng “chết đói” – starvation). TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 67 [HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Các giải pháp cho vấn đề miền tương trục Phân Loại Các Giải Pháp I Các giải pháp phần mềm: dựa trên các giải thuật phần mềm, như: I Cho trường hợp chỉ có 2 tiến trình cạnh tranh: I Giải thuật Peterson (Peterson’s algorithm) I Cho trường hợp có n ≥ 2 tiến trình cạnh tranh: I Giải thuật Bakery I Các giải pháp phần cứng: I Lệnh vô hiệu hóa ngắt (disable interrupt) I Lệnh máy đặc biệt: TestAndSet TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 68 [HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Giải thuật chờ bận Peterson - 2 tiến trình Giải Thuật Peterson I Kết hợp cả biến khóa chia sẻ (GT1) và biến khóa riêng (GT2): I int turn ; //turn = i: Pi được phép vào miền tương trục. I boolean flag [2]; //flag[i] = true: Pi sẵn sàng vào miền tương trục. I Tổ chức đoạn mã của 1 tiến trình Pi : do { f l a g [ i ] := t r u e tu rn := j ; wh i l e ( f l a g [ j ] && tu rn=j ) ; critical section f l a g [ i ] = f a l s e ; remainder section } wh i l e ( t r u e ) ; I Nhận xét: I Loại trừ hỗ tương: I Tiến triển: I Chờ đợi hữu hạn: TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 69 [HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Giải thuật Bakery - n tiến trình Giải Thuật Bakery I Miền tương trục cho n tiến trình: I Mỗi t/trình sẽ nhận được 1 số trước khi vào miền tương trục. I Tiến trình có số nhỏ nhất sẽ có quyền ưu tiên cao nhất. I Nếu hai tiến trình Pi và Pj nhận được cùng một số, nếu i < j thì Pi được phục vụ trước. I Bộ sinh số luôn sinh các số theo thứ tự tăng, ví dụ: 1, 2, 3, 3, 3, 4, . . . I Dữ liệu chia sẻ: boolean choosing[n] int number[n] I Khởi tạo: tất cả các phần tử của choosing = false và number = 0. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 70 [HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Giải thuật Bakery - n tiến trình Giải Thuật Bakery Cho Tiến Trình Pi do { choo s i ng [ i ] = t r u e ; number [ i ] = max( number [ 0 ] , number [ 1 ] , . . . , number [ n−1]) + 1 ; choo s i ng [ i ] = f a l s e ; f o r ( j = 0 ; j < n ; j++) { wh i l e ( choo s i ng [ j ] ) ; wh i l e ( ( number [ j ] != 0) && ( ( number [ j ] , j ) < ( number [ i ] , i ) ) ; } // f o r $\ framebox { c r i t i c a l s e c t i o n }$ number [ i ] = 0 ; $\ framebox { rema inde r s e c t i o n }$ } wh i l e ( t r u e ) ; > (number #1, i) < (number #2, j) nếu (number #1 < number #2) hoặc (number #1 = number #2) AND (i < j) TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 71 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Tắc nghẽn (Deadlock) TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 72 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Deadlock là gì? Deadlock Là Gì? I Deadlock là một trạng thái của hệ thống trong đó: I một tập hợp các tiến trình đang bị nghẽn I mỗi tiến trình đang giữ một tài nguyên và cũng đang chờ một tài nguyên đang bị giữ bởi một tiến trình khác trong tập các tiến trình đang bị nghẽn. I Ví dụ 1: I Giả sử 1 hệ thống có 2 tiến trình P và Q và F1, F2 là 2 tập tin. I Tiến trình P đang giữ F1 và cần truy xuất thêm F2. I Tiến trình Q đang giữ F2 và cần truy xuất thêm F1. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 73 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Deadlock là gì? Ví Dụ 2 – Traffic Deadlock 342 Chapter 7 Deadlocks • • • • • • • • • • • • Figure 7.10 Traffic deadlock for Exercise 7.11. 7.14 In Section 7.4.4, we describe a situation in which we prevent deadlock by ensuring that all locks are acquired in a certain order. However, we also point out that deadlock is possible in this situation if two threads simultaneously invoke the transaction() function. Fix the transaction() function to prevent deadlocks. 7.15 Compare the circular-wait scheme with the various deadlock-avoidance schemes (like the banker’s algorithm) with respect to the following issues: a. Runtime overheads b. System throughput 7.16 In a real computer system, neither the resources available nor the demands of processes for resources are consistent over long periods (months). Resources break or are replaced, new processes come and go, and new resources are bought and added to the system. If deadlock is controlled by the banker’s algorithm, which of the following changes can be made safely (without introducing the possibility of deadlock), and under what circumstances? a. Increase Available (new resources added). b. Decrease Available (resource permanently removed from system). c. Increase Max for one process (the process needs or wants more resources than allowed). d. Decrease Max for one process (the process decides it does not need that many resources). TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 74 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Điều kiện phát sinh deadlock Điều Kiện Phát Sinh Deadlock 1. Loại trừ hỗ tương: ít nhất một tài nguyên được giữ ở chế độ không chia sẻ (nonsharable mode). 2. Giữ và chờ: một tiến trình đang giữ ít nhất một tài nguyên và đợi thêm tài nguyên đang bị giữ bởi tiến trình khác. 3. Không trưng dụng tài nguyên: không trưng dụng tài nguyên cấp phát tiến trình, trừ khi tiến trình tự hoàn trả. 4. Chờ đợi vòng tròn: tồn tại một tập các tiến trình {P0,P1, . . . ,Pn} đang chờ đợi như sau: P0 đợi một tài nguyên P1 đang giữ, P1 đợi một tài nguyên P2 đang giữ, . . . , Pn đang đợi một tài nguyên P0 đang giữ. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 75 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Mô hình hóa hệ thống Mô Hình Hóa Hệ Thống I Hệ thống gồm một tập các loại tài nguyên, kí hiệu R1,R2, . . . ,Rm I Ví dụ: CPU cycles, memory space, I/O devices, . . . I Mỗi loại tài nguyên Ri có một tập các thể hiện (instances) Wi I Tiến trình sử dụng tài nguyên theo các bước: 1. Yêu cầu (request) – phải chờ nếu không được đáp ứng ngay. 2. Sử dụng (use) 3. Giải phóng (release) I Các tác vụ yêu cầu và hoàn trả được thực hiện bằng các lời gọi hệ thống. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 76 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) Đồ Thị Cấp Phát Tài Nguyên – RAG I Là đồ thị có hướng, với tập đỉnh V và tập cạnh E I Tập đỉnh V gồm 2 loại: I Tập P = {P1,P2, . . . ,Pn}: tập các tiến trình trong hệ thống I Tập R = {R1,R2, . . . ,Rm}: tập các tài nguyên của hệ thống I Tập cạnh cũng gồm 2 loại: I Cạnh yêu cầu (request edge): có hướng từ Pi đến Rj I Cạnh cấp phát (assignment edge): có hướng từ RJ đến Pi TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 77 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) Ký Hiệu I Tiến trình: Pi   I Loại tài nguyên (với 4 thể hiện): ● ● ● ● I Pi yêu cầu 1 thể hiện của Rj : ● ● ● ● Pi   Rj I Pi đang giữ 1 thể hiện của Rj : ● ● ● ● Pi   Rj TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 78 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) Đồ Thị Cấp Phát Tài Nguyên – Ví Dụ 1 I Đồ thị cấp phát tài nguyên (không có chu trình và không deadlock):320 Chapter 7 Deadlocks R1 R3 R2 R4 P3P2P1 Figure 7.1 Resource-allocation graph. ◦ R = {R1, R2, R3, R4} ◦ E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3} • Resource instances: ◦ One instance of resource type R1 ◦ Two instances of resource type R2 ◦ One instance of resource type R3 ◦ Three instances of resource type R4 • Process states: ◦ Process P1 is holding an instance of resource type R2 and is waiting for an instance of resource type R1. ◦ Process P2 is holding an instance of R1 and an instance of R2 and is waiting for an instance of R3. ◦ Process P3 is holding an instance of R3. Given the definition of a resource-allocation graph, it can be shown that, if the graph contains no cycles, then no process in the system is deadlocked. If the graph does contain a cycle, then a deadlock may exist. If each resource type has exactly one instance, then a cycle implies that a deadlock has occurred. If the cycle involves only a set of resource types, each of which has only a single instance, then a deadlock has occurred. Each process involved in the cycle is deadlocked. In this case, a cycle in the graph is both a necessary and a sufficient condition for the existence of deadlock. If each resource type has several instances, then a cycle does not necessarily imply that a deadlock has occurred. In this case, a cycle in the graph is a necessary but not a sufficient condition for the existence of deadlock. To illustrate this concept, we return to the resource-allocation graph depicted in Figure 7.1. Suppose that process P3 requests an instance of resource I P = {P1,P2,P3} I R = {R1,R2,R3,R4} I E = {P1 → R1,P2 → R3,R1 → P2, R2 → P2,R2 → P1,R3 → P3} I Thể hiện của các loại tài nguyên: R1 : 1;R2 : 2;R3 : 1;R4 : 3. I Trạng thái của các tiến trình: I P1: giữ (R2, 1); chờ (R1, 1) I P2: giữ (R1, 1), (R2, 1); chờ (R3, 1) I P3: giữ (R3, 1) TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 79 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) Đồ Thị Cấp Phát Tài Nguyên – Ví Dụ 2 I Đồ thị cấp phát tài nguyên với chu trình và deadlock:7.2 Deadlock Characterization 321 R1 R3 R2 R4 P3P2P1 Figure 7.2 Resource-allocation graph with a deadlock. type R2. Since no resource instance is currently available, we add a request edge P3 → R2 to the graph (Figure 7.2). At this point, two minimal cycles exist in the system: P1 → R1 → P2 → R3 → P3 → R2 → P1 P2 → R3 → P3 → R2 → P2 Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which is held by process P3. Process P3 is waiting for either process P1 or process P2 to release resource R2. In addition, process P1 is waiting for process P2 to release resource R1. Now consider the resource-allocation graph in Figure 7.3. In this example, we also have a cycle: P1 → R1 → P3 → R2 → P1 R2 R1 P3 P4 P2 P1 Figure 7.3 Resource-allocation graph with a cycle but no deadlock. I Trạng thái của các tiến trình: I P1: giữ (R2, 1); chờ (R1, 1) I P2: giữ (R1, 1), (R2, 1); chờ (R3, 1) I P3: giữ (R3, 1); chờ (R2, 1) I 2 chu trình nhỏ nhất (minimal cycles): P1 → R1 → P2 → R3 → P3 → R2 → P1 P2 → R3 → P3 → R2 → P2 I Deadlock: cả 3 tiến trình P1,P2,P3 TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 80 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) Đồ Thị Cấp Phát Tài Nguyên – Ví Dụ 3 I Đồ thị cấp phát tài nguyên có chu trình nhưng không deadlock: 7.2 Deadlock Characterization 321 R1 R3 R2 R4 P3P2P1 Figure 7.2 Resource-allocation graph with a deadlock. type R2. Since no resource instance is currently available, we add a request edge P3 → R2 to the graph (Figure 7.2). At this point, two minimal cycles exist in the system: P1 → R1 → P2 → R3 → P3 → R2 → P1 P2 → R3 → P3 → R2 → P2 Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which is held by process P3. Process P3 is waiting for either process P1 or process P2 to release resource R2. In addition, process P1 is waiting for process P2 to release resource R1. Now consider the resource-allocation graph in Figure 7.3. In this example, we also have a cycle: P1 → R1 → P3 → R2 → P1 R2 R1 P3 P4 P2 P1 Figure 7.3 Resource-allocation graph with a cycle but no deadlock. I Chu trình: P1 → R1 → P3 → R2 → P1 I Tại sao không deadlock? TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 81 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) Đồ Thị Cấp Phát Tài Nguyên & Deadlock I Nếu đồ thị không có chu trình: chắc chắn không có deadlock I Nếu đồ thị có chu trình: I Nếu mỗi loại tài nguyên chỉ có một thể hiện: chắc chắn có deadlock. I Nếu mỗi loại tài nguyên có nhiều thể hiện: có thể có deadlock. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 82 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Các Cách Tiếp Cận Đối Với Vấn Đề Deadlock Các Cách Tiếp Cận Đối Với Vấn Đề Deadlock 1. Đề ra các giao thức để đảm bảo cho hệ thống không bao giờ rơi vào trạng thái deadlock. 2. Cho phép hệ thống rơi vào trạng thái deadlock, sau đó sử dụng các giải thuật để phát hiện deadlock và phục hồi. 3. Không quan tâm và không xử lý vấn đề deadlock trong hệ thống I Khá nhiều hệ điều hành sử dụng phương pháp này. I Tuy nhiên, nếu deadlock không được phát hiện và xử lý sẽ dẫn đến việc giảm hiệu suất của hệ thống. Cuối cùng, hệ thống có thể ngưng hoạt động và phải khởi động lại. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 83 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Các Cách Tiếp Cận Đối Với Vấn Đề Deadlock Ngăn chặn và tránh deadlock I Có hai biện pháp để đảm bảo hệ thống không rơi vào trạng thái deadlock: 1. Ngăn chặn deadlock (deadlock prevention): không cho phép (ít nhất) một trong bốn điều kiện cần cho deadlock xảy ra. 2. Tránh deadlock (deadlock avoidance): các tiến trình cần cung cấp thông tin về tài nguyên nó cần để hệ thống cấp phát tài nguyên một cách thích hợp. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 84 [HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Các Cách Tiếp Cận Đối Với Vấn Đề Deadlock Phát Hiện Deadlock I Trong cách tiếp cận “phát hiện và phục hồi” đối với vấn đề deadlock: I Chấp nhận cho deaclock xảy ra trong hệ thống. I Sử dụng các giải thuật để phát hiện deadlock. I Nếu có deadlock thì sẽ tiến hành phục hồi hệ thống, dùng 1 sơ đồ phục hồi thích hợp. I Các giải thuật phát hiện deadlock thường sử dụng RAG. I Có 2 loại giải thuật: I Cho trường hợp mỗi loại tài nguyên chỉ có 1 thể hiện. I Cho trường hợp mỗi loại tài nguyên có nhiều thể hiện. TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 85 [HĐH] Ch4. Quản lý tiến trình Tổng Kết Tổng Kết Tổng quan về tiến trình Giao tiếp liên tiến trình Định thời tiến trình Các giải thuật định thời Đồng bộ hóa tiến trình Tắc nghẽn (Deadlock) TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 86