Bài giảng Hệ điều hành: Chương 4 - Trần Công Án

Mục tiêu của chương 4 nhằm 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.

Đồng bộ hóa Tiến trình & Tắc nghẽn

Giảng viên

TS Trần Công Ántcan@cit.ctu.edu.vn

Khoa Công Nghệ Thông Tin & Truyền Thông

Đại học Cần Thơ

2018

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 trongQuản lý Tiến trình như tạo, định thời và kết thúc tiến trình Các phươngthứ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

Tổng quan về tiến trình

Tổng quan về tiến trình

Khái Niệm Tiến Trình

I Tiến trìnhlà thể hiện (instance) của mộtchươ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(processidentifier, 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)

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ìnhlà một thực thể chủ động, lưu trú

trênbộ nhớ chính

I Khi một chương trình đượckí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ìnhcó thể có vài tiến trình trong

0

max

data heap stack

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áisau:

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.

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

running ready

admitted interrupt

scheduler dispatch I/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ứathông tin của tiến trìnhtrong 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

• • •

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ữ

save state into PCB 0

save state into PCB 1 reload state from PCB 1

reload state from PCB0

operating system

idle

idle

executing idle

executing

executing

interrupt or system call

interrupt or system call

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

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ìnhthực thi câu lệnh cuối cùngvà yêu cầu HĐHxóanó (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

Giao tiếp liên 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ựcthi 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

Giao Tiếp Liên Tiến Trình

I Các tiến trình muốn trao đổi dữ liệuvới nhau cần sử dụng cơ chế giaotiếp liên tiến trình (interprocess communication, IPC):

kernel

process B

m0m1m2m3 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 Aproducerprocess produces information that is consumed by a

truyền thông điệp

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ệugiữ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ảnxuấ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.

Giao tiếp liên tiến trình

Người Tiêu Dùng (Consumer)

next_consumed = buffer[out_item]; !!

!

/* consume the item in next consumed */ !

}

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

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).

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 mailboxhay 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

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 quamailbox, 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.

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.

Định thời tiến trình

Định thời tiến trình

I Định thời biểu CPUlà một chức năng cơ bản và quan trọng của cácHĐ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ếntrì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ờ đợitiến trình đang thực thi thực hiện các thao tác nhập xuất) cho cáctiến trình khác trong hệ thống

Đị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).

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

Đị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 tronghà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

Đị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.

Đị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

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êntổ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êucầ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ằmtrong 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 thimột t/trình, bao gồm các khoảng t/gian: thực thi, chờ I/O, chờ trongready 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

Đị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ăngtối ưu hóa cáctiêu chí định thờicủ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

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

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ùnghà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).

FCFS – Ví Dụ 1

I Cho các tiến trình với thời gian thực thivà thứ tự xuất hiện như sau:

P

P

I Biểu đồ Gantt cho lịch biểu:

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

Các giải thuật định thời

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ìnhdài được gọi là “hiệu ứng nối đuôi” (convoy effect)

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)

Các giải thuật định thời

Shortest-job-first

SJF Không Trưng Dụng – Ví Dụ

P P P P

I Biểu đồ Gantt cho lịch biểu: