Giáo trình Hệ điều hành - Chương 2: Quản lý tiến trình

HỆ ĐIỀU HÀNH

Chương 2

QUẢN LÝ TIẾN TRÌNH

4. Tiến trình

4.1. Khái niệm tiến trình

Một tiến trình là một chương trình trong quá trình thực hiện. Một

tiến trình có thể có nhiều đoạn mã chương trình.

Một chương trình tự nó không phải là một tiến trình. Một chương

trình chỉ là một thực thể thụ động, chỉ là nội dung của một file được lưu

trên đĩa. Trong khi đó, một tiến trình là một thực thể tích cực, hoạt động.

Hai tiến trình có thể được sinh từ cùng một đoạn mã hoặc từ hai

đoạn mã khác nhau.

Trạng thái tiến trình

Tiến trình trong quá trình thực hiện, nó thay đổi trạng thái. Trạng

thái của một tiến trình được định nghĩa bởi hoạt động hiện thời của tiến

trình. Mỗi tiến trình có thể ở một trong các trạng thái sau:

Mới

Kết thúc

Nạp vào

Thoát

Bị ngắt

Sẵn sàng

Thực hiện

Bộ lập lịch gửi đến

Chờ đợi

Đợi

sự

kiện

Sự kiện

vào ra

hoàn tất

Hình 4.1: Sơ đồ chuyển đổi trạng thái của tiến trình

Phạm Ngọc Hưng

41

Quản lý tiến trình

- Mới (new): Tiến trình bắt đầu được tạo ra

- Đang thực hiện (running): Các lệnh đang được thực hiện

- Chờ đợi (waiting): Tiến trình đang chờ đợi một số sự kiện xuất

hiện

- Sẵn sàng (ready): Tiến trình đang chờ đợi để được cấp phát bộ

- Kết thúc (terminated): Tiến trình vừa kết thúc quá trình thực hiện

xử lý

Khối điều khiển tiến trình

Mỗi tiến trình được biểu diễn trong hệ điều hành bằng một khối

điều khiển tiến trình (PCB - Process Control Block), còn được gọi là khối

điều khiển tác vụ. Một PCB được thể hiện ở hình 4.2. Nó chứa các phần

thông tin liên quan đến một tiến trình, bao gồm:

Con trỏ

Trạng thái tiến trình

Số hiệu tiến trình

Bộ đếm chương trình

Các thanh ghi

Danh sách các file đã mở

....

Hình 4.2: Khối điều khiển tiến trình (PCB)

- Trạng thái tiến trình: Trạng thái có thể mới, sẵn sàng, thực hiện,

chờ đợi hay dừng.

- Bộ đếm chương trình: Bộ đếm chương trình xác định địa chỉ câu

lệnh kế tiếp sẽ được thực hiện cho tiến trình này.

- Các thanh ghi CPU: Có nhiều loại thanh ghi với các loại khác

nhau, tuỳ thuộc vào kiến trúc của máy tính. Chúng bao gồm thanh ghi

chứa kết quả trung gian, thanh ghi chỉ số, con trỏ ngăn xếp, và các thanh

ghi công dụng chung.

42

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

- Thông tin quản lý bộ nhớ: Thông tin này có thể là thông tin giống

như giá trị thanh ghi cơ sở và thanh ghi giới hạn, bảng trang, hoặc bảng

đoạn, tuỳ thuộc vào hệ thống nhớ được hệ điều hành sử dụng.

- Thông tin tính toán: Thông tin này bao gồm thời lượng của CPU

và thời gian thực được sử dụng, giới hạn thời gian, số lượng các tính toán,

số lượng các tiến trình hay nhiệm vụ.

- Thông tin trạng thái vào ra: Thông tin bao gồm danh sách các

thiết bị vào ra được cấp phát cho tiến trình này, một danh sách các file

mở.

Các Luồng (Threads)

Mô hình tiến trình đã thảo luận phần trước là một tiến trình sinh từ

một chương trình thực hiện trong một luồng xử lý. Ví dụ, nếu một chương

trình đang chạy như Word, một luồng đơn các chỉ thị lệnh đang được thực

hiện. Luồng đơn này là một luồng điều khiển tiến trình để thực hiện duy

nhất một nhiệm vụ trong một thời điểm. Ví dụ, người sử dụng không thể

vừa gõ chữ vừa thực hiện chức năng kiểm tra lỗi chính tả trong cùng một

tiến trình. Nhiều hệ điều hành cho mở rộng khái niệm tiến trình cho phép

một tiến trình có nhiều luồng thực hiện. Chúng cho phép tiến trình thực

hiện nhiều nhiệm vụ trong một thời điểm.

4.2. Lập lịch tiến trình

Mục tiêu của đa chương trình là cho phép nhiều chương trình cùng

chạy trong một thời điểm vì thế làm gia tăng hiệu quả của làm việc của

CPU. Mục tiêu của hệ thống chia sẻ thời gian chuyển đổi CPU qua các tiến

trình một cách thường xuyên vì vậy người sử dụng có thể tương tác với

mỗi tiến trình trong khi nó thực hiện.

Hàng đợi lịch làm việc

Khi các tiến trình được nhập vào hệ thống, chúng được đưa vào

một hàng đợi các công việc. Các tiến trình đó được lưu trú trong bộ nhớ

chính, đã sẵn sàng và đang chờ đợi để thực hiện được giữ trong một danh

sách được gọi là hàng đợi sẵn sàng. Hàng đợi này là một danh sách liên

kết chứa các con trỏ trỏ tới PCBs đầu tiên và cuối cùng trong danh sách.

Phạm Ngọc Hưng

43

Quản lý tiến trình

Mỗi PCB có một trường con trỏ trỏ tới PCB kế tiếp trong hàng đợi sẵn

sàng.

Hệ điều hành cũng có các hàng đợi khác. Khi một tiến trình được

cấp phát CPU, nó thực hiện cho đến khi dừng hoặc bị ngắt hoặc đợi cho

đến khi một sự kiện cụ thể xuất hiện như hoàn tất một yêu cầu vào ra.

Trong trường hợp có một yêu cầu vào ra, như yêu cầu đến một bộ điều

khiển băng hay một thiết bị được chia sẻ như một đĩa. Với hệ điều hành

có nhiều tiến trình, đĩa có thể bị bận với các yêu cầu vào ra bởi các tiến

trình khác. Các tiến trình vì vậy phải đợi đĩa. Danh sách các tiến trình đợi

một thiết bị vào ra cụ thể được gọi là hàng đợi thiết bị. Mỗi thiết bị có

riêng một hàng đợi của mình.

Một thể hiện của lịch làm việc của tiến trình dưới dạng sơ đồ hàng

đợi như hình 4.3. Mỗi hộp chữ nhật thể hiện cho một hàng đợi. Hai kiểu

hàng đợi được trình bày: hàng đợi sẵn sàng và một tập các hàng đợi thiết

bị các hình tròn thể hiện cho tài nguyên phục vụ cho các hàng đợi và các

mũi tên chỉ định luồng của các tiến trình trong hệ thống.

Hàng đợi sẵn sàng

CPU

Hàng đợi I/O

Yêu cầu I/O

Hết hạn

I/O

Tiến trình con

Phân nhánh cho tiến trình con

thực hiện

Đợi một ngắt

Ngắt xuất hiện

Hình 4.3: Sơ đồ hàng đợi biểu diễn sự lập lịch tiến trình

44

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

Khi một tiến trình mới được khởi động và đưa vào hàng đợi sẵn

sàng nó chờ đợi trong hàng đợi sẵn sàng cho đến khi được lựa chọn để

thực hiện. Khi tiến trình được liên kết với CPU và trong quá trình thực

hiện, có thể xảy ra một số sự kiện sau:

- Tiến trình có thể phát sinh một yêu cầu vào ra và sau đó nó được

đặt vào hàng đợi và ra.

- Tiến trình có thể tạo một tiến trình con mới và đợi cho đến khi nó

kết thúc.

- Tiến trình có thể bị loại bỏ khỏi CPU khi một ngắt xuất hiện và bị

đưa trở lại hàng đợi sẵn sàng.

Ở hai trường hợp đầu, tiến trình cuối cùng sẽ chuyển sang trạng

thái chờ đợi rồi đến trạng thái sẵn sàng và sau đó sẽ được đưa trở lại

hàng đợi sẵn sàng.

Các bộ lập lịch

Một tiến trình sẽ chuyển qua lại giữa các hàng đợi lịch khác nhau

trong suốt thời gian thực hiện. Hệ điều hành phải lựa chọn tiến trình từ

các hàng đợi theo một số cách và công việc này được thực hiện bởi bộ lập

lịch thích hợp.

Có hai bộ lập lịch: Bộ lập lịch dài hạn (long-term scheduler) và bộ

lập lịch ngắn hạn (short-term scheduler). Sự khác nhau cơ bản giữa hai hệ

thống lập lịch là mức độ thường xuyên thực hiện của chúng.

Bộ lập lịch ngắn hạn phải lựa chọn một tiến trình mới cho CPU một

cách thường xuyên hơn. Thời gian để hệ thống này chọn tiến trình thường

là rất ngắn để giảm sự lãng phí thời gian thực hiện của CPU.

Bộ lập lịch dài hạn lại làm việc ít thường xuyên hơn. Nó có thể phải

mất vài phút để tạo một tiến trình mới trong hệ thống. Trong khi đó, bộ

lập lịch ngắn hạn chỉ mất vài chục mini giây. Hệ thống lập lịch dài hạn

điều khiển mức độ đa chương trình (số lượng tiến trình trong bộ nhớ).

Chuyển ngữ cảnh

Việc chuyển CPU sang phục vụ cho một tiến trình khác đòi hỏi phải

lưu lại trạng thái của tiến trình cũ và nạp các trạng thái đã được ghi của

tiến trình mới. Nhiệm vụ này được gọi là chuyển ngữ cảnh (Context Switch

Phạm Ngọc Hưng

45

Quản lý tiến trình

- CS). Khi xuất hiện sự chuyển đổi ngữ cảnh, nhân hệ thống sẽ lưu lại ngữ

cảnh của tiến trình cũ trong PCB của nó và nạp ngữ cảnh đã được cất giữ

của tiến trình mới được lập lịch để thực hiện. Thời gian chuyển ngữ cảnh

là một thời gian vô nghĩa, vì hệ thống sẽ không làm được gì trong khảng

thời gian này. Tuỳ thuộc vào tốc độ bộ bộ nhớ và số lượng thanh ghi phải

sao chép mà thời gian này có thể được thay đổi. Thông thường, tốc độ

đạt trong khoảng từ 1 đến 100 micro giây.

Thời gian chuyển ngữ cảnh cao hay thấp thuỳ thuộc vào sự hỗ trợ

phần cứng máy tính. Ví dụ, một số bộ xử lý (như Sun UltraSPARC) cung

cấp nhiều tập các thanh ghi. Việc chuyển ngữ cảnh chỉ đơn thuần là

chuyển con trỏ đến tập thanh ghi hiện thời, tốc độ chuyển ngữ cảnh sẽ

diễn ra nhanh hơn.

4.3. Sự thực hiện của các tiến trình

Các tiến trình trong hệ thống có thể thực hiện song song, và chúng

phải được tạo và xoá một cách tự động. Vì vậy, hệ điều hành phải cung

cấp một một cơ chế (khả năng) cho phép tạo và kết thúc các tiến trình.

Tạo các tiến trình

Một tiến trình có thể tạo nhiều tiến trình mới bằng lời gọi hệ thống

tạo tiến trình. Tiến trình thực hiện việc tạo ra một tiến trình được gọi là

tiến trình cha. Tiến trình được tạo ra gọi là tiến trình con của tiến trình đã

thực hiện việc tạo tiến trình đó. Đến lượt tiến trình mới, nó lại có thể tạo

ra các tiến trình con của nó. Theo cách này, một cây tiến trình sẽ xuất

hiện trong quá trình thực hiện của các tiến trình.

Một tiến trình cần tới các tài nguyên như thời gian CPU, bộ nhớ, các

file, các thiết bị vào ra để hoàn thành công việc của mình. Khi một tiến

trình con được tạo, tiến trình đó có thể nhận tài nguyên trực tiếp từ hệ

điều hành, hoặc có thể buộc phải chia sẻ một phần tài nguyên của tiến

trình cha. Tiến trình cha phải chia sẻ các phần tài nguyên của nó cho các

tiến trình con.

Khi một tiến trình được tạo nó nhận bổ sung nhiều tài nguyên logic

và vật lý khởi tạo dữ liệu những điều này có thể được tiến trình cha

chuyển cho.

46

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

Ví dụ :

Một tiến trình con có chức năng hiện thị trạng thái của một file

được gọi là F1 trên mà hình của thiết bị đầu cuối. Khi nó được tạo nó sẽ

tiếp nhận, như là một đầu vào từ tiến trình cha tên của file F1, và nó sẽ

thực hiện việc phân tích các thông tin của file đó. Nó cũng có thể lấy tên

của thiết bị ra. Một vài hệ điều hành chuyển các tài nguyên cho các tiến

trình con.

Khi một tiến trình tạo ra một tiến trình con mới, hai khả năng tồn

tại trong thời gian thực hiện:

-

Tiến trình cha tiếp tục thực hiện song song với tiến trình con

của nó.

Tiến trình cha đợi cho đến khi một số hoặc tất cả các tiến trình

con đã kết thúc mới tiếp tục thực hiện.

Vì vậy cũng có hai đặc tính đối với các tiến trình con về không

gian địa chỉ:

-

Tiến trình con là một bản sao của tiến trình cha.

Tiến trình con có một chương trình được nạp vào cho nó.

Kết thúc tiến trình

Khi một tiến trình kết thúc nó sẽ ngừng quá trình thực hiện và yêu cầu

hệ thống xoá nó bằng cách sử dụng lời gọi hệ thống ”thoát”. Ở thời điểm

đó tiến trình có thể trả lại dữ liệu cho tiến trình cha của nó. Tất cả các

tài nguyên của tiến trình (bao gồm bộ nhớ vật lý, bộ nhớ ảo, các file

được mở và bộ đệm vào ra) đều được hệ điều hành giải phóng.

Một tiến trình cha có thể kết thúc quá trình thực hiện của các tiến

trình con của nó bởi một số lý do ví dụ như:

- Tiến trình con đã xâm phạm một số các tài nguyên. Điều này đòi

hỏi tiến trình cha phải có kỹ thuật để nhận biết trang thái của các tiến

trình con.

-

Nhiệm vụ được giao cho tiến trình con không cần thiết nữa.

Phạm Ngọc Hưng

47

Quản lý tiến trình

Tiến trình cha kết thúc và hệ điều hành không cho phép các tiến

-

trình con được kết thúc nếu như tiến trình cha của nó được kết

thúc.

4.4. Tiến trình cộng tác

Trong khi các tiến trình thực hiện song song trong hệ thống, chúng

có thể là các tiến trình độc lập hoặc cộng tác với nhau. Một tiến trình được

gọi là độc lập nếu nó không thể ảnh hưởng hoặc bị ảnh hưởng bởi sự hoạt

động của các tiến trình khác trong hệ thống. Một cách rõ ràng hơn các

tiến trình không chia sẻ bất cứ dữ liệu gì với những tiến trình độc lập

khác. Trong khi đó, một tiến trình gọi là cộng tác nếu như nó có thể ảnh

hưởng hoặc bị ảnh hưởng bởi sự thực hiện của các tiến trình khác trong

hệ thống. Nói khác đi, các tiến trình chia sẻ dữ liệu của mình với các tiến

trình cộng tác khác.

Chúng ta có thể mong muốn hỗ trợ một môi trường cho phép các

tiến trình cộng tác hoạt động vì một số lý do sau:

-

Chia sẻ các thông tin: một số người dung có thể truy nhập vào

cùng một phần thông tin (ví dụ như một file dùng chung),

chúng ta phải cung cấp một môi trường truy nhập song song tới

các kiểu tài nguyên đó.

-

Tăng tốc độ tính toán: để công việc tính toán thực hiện nhanh

hơn chúng ta phải chia một nhiệm vụ thành nhiều nhiệm vụ nhỏ

hơn, mỗi nhiệm vụ có thể thực hiện song song với các nhiệm vụ

khác.

-

Tính linh hoạt

Hiệu quả: chỉ với một người dùng cũng có thể thực hiện nhiều

công việc trong cùng một thời điểm

4.5. Giao tiếp trong các hệ thống khách chủ

Sử dụng Socket

Một socket là một thiết bị truyền thông hai chiều tương tự như tập

tin, chúng ta có thể đọc hay ghi lên nó, tuy nhiên mỗi socket là một thành

phần trong một mối nối nào đó giữa các máy trên mạng máy tính và các

48

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

thao tác đọc/ghi chính là sự trao đổi dữ liệu giữa các ứng dụng trên nhiều

máy khác nhau.

Sử dụng socket có thể mô phỏng hai phương thức liên lạc trong

thực tế : liên lạc thư tín (socket đóng vai trò bưu cục) và liên lạc điện

thoại (socket đóng vai trò tổng đài) .

Các thuộc tính của socket:

- Domain: định nghĩa dạng thức địa chỉ và các nghi thức sử dụng.

Có nhiều domaines, ví dụ UNIX, INTERNET, XEROX_NS, ...

- Type: định nghĩa các đặc điểm liên lạc:

a) Sự tin cậy

b) Sự bảo toàn thứ tự dữ liệu

c) Lặp lại dữ liệu

d) Chế độ nối kết

e) Bảo toàn giới hạn thông điệp

f) Khả năng gởi thông điệp khẩn

Để thực hiện liên lạc bằng socket, cần tiến hành các thao tác ::

- Tạo lập hay mở một socket

- Gắn kết một socket với một địa chỉ

- Liên lạc : có hai kiểu liên lạc tùy thuộc vào chế độ nối kết:

Sử dụng lời gọi thủ tục từ xa

Một trong số các kiểu dịch vụ từ xa phổ biến nhất là mô hình RPC

(Remote Procedure Calls). Mô hình này được thiết kế theo cách trừu

tượng hoá các kỹ thuật gọi thủ tục giữa các hệ thống với kết nối mạng.

Ý nghĩa của RPCs là cho phép một máy khách có thể yêu cầu một

thủ tục trên một máy chủ từ xa như nó có thể yêu cầu một thủ tục cục

bộ. Hệ thống RPC thực hiện việc này bằng cách cung cấp một stub phía

máy khách. Thông thường thì mỗi một thủ tục từ xa có một stub riêng.

Khi máy khách yêu cầu đến một thủ tục từ xa, hệ thống RPC sẽ gọi stub

tương ứng, chuyển các tham số được cung cấp cho thủ tục từ xa. Stub

này sẽ tìm cổng trên máy dịch vụ và kết nối các tham số. Các tham số

được đóng gói theo khuôn mẫu thích hợp và truyền đi qua một mạng.

Stub truyền thông điệp đến máy dịch vụ bằng phương pháp gửi thông

Phạm Ngọc Hưng

49

Quản lý tiến trình

điệp. Tương tự, stub trên máy dịch vụ sau khi nhận được thông điệp này

sẽ yêu cầu đến thủ tục trên máy dịch vụ. Nếu cần thiết, giá trị trả lại sẽ

được gửi về cho máy khách bằng kỹ thuật tương tự.

5. Luồng

5.1. Giới thiệu

Luồng, đôi khi còn được gọi là Lightweight process (LWP) hay tiểu

trình, là một đơn vị cơ bản ứng dụng của CPU; nó bao gồm một chỉ số

luồng (thread ID), một bố đếm chương trình, một tập thanh ghi và một

ngăn xếp. Nó chia sẻ với các luồng khác liên quan đến cùng một xử lý.

Một tiến trình truyền thống (heavyweight) có một luồng điều khiển. Nếu

một tiến trình có nhiều luồng điều khiển, nó có thể thực hiện được nhiều

việc trong cùng một thời điểm.

Các tiến trình tạo thành những thực thể độc lập. Mỗi tiến trình có

một tập tài nguyên và một môi trường riêng (một con trỏ lệnh, một Stack,

các thanh ghi và không gian địa chỉ). Các tiến trình hoàn toàn độc lập với

nhau, chỉ có thể liên lạc thông qua các cơ chế thông tin giữa các tiến trình

mà hệ điều hành cung cấp. Ngược lại, các tiểu trình trong cùng một tiến

trình lại chia sẻ một không gian địa chỉ chung, điều này có nghĩa là các

tiểu trình có thể chia sẻ các biến toàn cục của tiến trình. Một tiểu trình có

thể truy xuất đến cả các stack của những tiểu trình khác trong cùng tiến

trình. Cấu trúc này không đòi hỏi một cơ chế bảo vệ nào, và điều này

cũng không thật cần thiết vì các tiểu trình trong cùng một tiến trình thuộc

về cùng một chủ sỡ hữu đã tạo ra chúng trong ý định cho phép chúng

hợp tác với nhau.

Động cơ để phát triển đa luồng

Rất nhiều các gói phần mềm chạy trên mô hình máy tính để bàn là

đa luồng. Một chương trình thông thường được thực hiện như một tiến

trình riêng biệt với vài luồng điều khiển. Một trình duyệt web có thể có

một luồng hiển thị các tranh ảnh trong khi đó lại có một luồng khác đang

nhận dữ liệu từ mạng. Một trình xử lý văn bản có thể có một luồng hiển

50

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

thị đồ hoạ, trong khi luồng khác đang nhận phím được gõ từ người dùng,

luồng thứ 3 lại đang tiến hành kiểm tra lỗi chính tả phía sau.

Tất nhiên là trong một số trường hợp, một ứng dụng đơn luồng có

thể thực nhiều nhiệm vụ tương tự. Ví dụ một trình dịch vụ web, nó chấp

nhận các yêu cầu về các trang web, tranh ảnh, âm thanh,... từ phía người

dùng. Một trình dịch vụ web đang bận nó có thể đang phải xử lý đến hàng

trăm các yêu cầu của nhiều người dùng trong cùng một thời điểm. Nếu

trình dịch vụ web chạy như một tiến trình đơn luồng truyền thống thì nó

chỉ có thể đáp ứng được yêu cầu của một máy khách trong một thời điểm.

Khi đó các máy khách khác phải chờ đợi. Thời gian các máy khách phải

chờ đợi có thể rất lớn.

Một giải pháp để xử lý cho trình dịch vụ đơn luồng chấp nhận nhiều

yêu cầu là khi nhận được yêu cầu, server tạo ra một tiến trình mới để dáp

ứng yêu cầu đó. Trong thực tế, giải pháp tạo tiến trình mới đã được sử

dụng phổ biến trước khi các luồng trở lên phổ biến. Giải pháp tạo tiến

trình mới cho mỗi dịch vụ như vậy sẽ khiến cho hệ thống phải chịu một tải

trọng rất lớn. Trong khi đó, một tiến trình đa luồng có thể đáp ứng được

yêu cầu này rất dẽ dàng mà không phải lãng phí nhiều tài nguyên của hệ

thống.

Lợi ích của đa luồng

Lợi ích của lập trình đa luồng có thể được chia thành 4 nhóm sau:

- Đáp ứng nhanh (Responsveness): Đa luồng một ứng dụng tương

tác cho phép một chương trình tiếp tục chạy trong khi một phần của nó bị

ngăn cản hoặc đang thực hiện một xử lý kéo dài, bằng cách ấy khả năng

đáp ứng yêu cầu người dùng được gia tăng.

- Chia sẻ tài nguyên: Mặc định, các tiến trình chia sẻ bộ nhớ và các

nguồn tài nguyên của các tiến trình có liên quan. Lợi ích của đoạn mã chia

sẻ là nó cho phép một ứng dụng có một vài luồng khác nhau cùng hoạt

động trong một không gian địa chỉ.

- Kinh tế: Cấp phát bộ nhớ, tài nguyên cho một tiến trình được tạo

ra là cả một chi phí đáng kể. Thay vào đó, các luồng chia sẻ tài nguyên

Phạm Ngọc Hưng

51

Quản lý tiến trình

của tiến trình có liên quan, điều đó sẽ kinh tế hơn trng việc tạo và chuyên

đổi ngữ cảnh các luồng. Thời gian để tạo ra một tiến trình lớn hơn so với

thời gian để tạo ra một luồng và chuyển ngữ cảnh. Trong hệ thống Solaris

2, tạo ra một tiến trình chậm hơn đến 30 lần so với việc tạo ra một luồng,

chuyển ngữ cảnh chậm hơn khoảng 5 lần.

- Khai thác được các hệ thống đa xử lý: Lợi ích của đa luồng lại

càng được gia tăng trong các hệ thống đa xử lý. Trong hệ thống này các

luồng có thể được thực hiện song song, mỗi luồng trên một bộ xử lý

riêng. Trong khi đó, một tiến trình đơn luồng chỉ khai thác được một bộ

xử lý.

Các luồng người dùng và luồng nhân hệ thống

Sự hỗ trợ các luồng có thể hoặc là mức người dùng, luồng người

dùng (user threads), hoặc mức nhân hệ thống (kernel), luồng nhân hệ

thống (kernel threads).

User threads là một hỗ trợ bên trên kernel, và được thực hiện bằng

một thư viện luồng tại mức người dùng (user level). Thư viện này cung

cấp các hỗ trợ cho việc tạo luồng, lập lịch, và quản lý các luồng không

được hỗ trợ từ kernel.

Kernel threads được hỗ trợ trực tiếp bởi hệ điều hành. Kernel thực

hiện việc tạo luồng, lập lịch và quản lý các luồng trong không gian của

kernel. Các luồng này được tạo và quản lý bởi hệ điều hành nên thường

tạo và quản lý chậm hơn so với luồng người dùng.

5.2. Các mô hình đa luồng

Mô hình nhiều-một

Mô hình này ánh xạ nhiều luồng người dùng vào một luồng nhân.

Quản lý luồng được thực hiện trong không gian người dùng nên khá hiệu

quả, nhưng toàn bộ tiến trình sẽ khị khoá nếu có một luồng tạo ra một lời

gọi hệ thống bị cấm. Trong mô hình này, chỉ một luồng có thể truy nhập

kernel trong một thời điểm.

52

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

user thread

kernel thread

Hình 5.1: Mô hình nhiều-một

Mô hình một-một

Mô hình này ánh xạ mỗi một luồng của người dùng với một luồng

nhân. Nó gia tăng khả năng chạy song song so với mô hình nhiều-một

bằng cách cho phép các luồng khác có thể chạy trong khi một luồng tạo

ra một lời gọi hệ thống bị cấm. Nó cũng cho phép nhiều luồng chạy song

song trên các đa xử lý. Trong mô hình này, số luồng được tạo ra là hạn

chế. Windows NT, Windows 2000 và OS/2 thực hiện trong mô hình này.

user thread

kernel thread

Hình 5.2: Mô hình một-một

Phạm Ngọc Hưng

53

Quản lý tiến trình

Mô hình nhiều-nhiều

Mô hình này dồn nhiều các luồng mức người dùng vào một số

lượng tương ứng hoặc nhỏ hơn các luồng nhân. Mô hình này cho phép tạo

ra nhiều luồng với số lượng tuỳ thích. Solaris 2, IRIX, HP-UX, Tru64 UNIX

hỗ trợ mô hình này.

user thread

kernel thread

Hình 5.3: Mô hình nhiều-nhiều

5.3. Luồng trong Window 2000

Một ứng dụng trong windows được thực hiện như một tiến trình

riêng biệt, mỗi tiến trình có thể có nhiều luồng. windows 2000 sử dụng

mô hình một-một.

Các thành phần chính của một luồng bao gồm:

- Thread UD: xác định duy nhất luồng

- Tập các thanh ghi: thể hiện trạng thái của bộ xử lý

- Ngăn xếp người dùng: được sử dụng khi thực hiện trong chế độ

người dùng

- Vùng lưu trữ riêng: được sử dụng bởi nhiểu các run-time libraries

và dynamic link libraries.

Tập các thanh ghi, ngăn xếp và vùng lưu trữ riêng cho biế ngữ

cảnh của luồng, là một cấu trúc chỉ định phần cứng mà hệ điều hành dang

chạy. Cấu trúc dữ liệu chính của một luồng bao gồm:

ETHREAD (execitive thread block)

54

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

KTHREAD (kernel thread block)

TEB (thread environment block)

Các thành phần của ETHREAD bao gồm một con trỏ trỏ tới tiến

trình liên quan đến luồng và địa chỉ đoạn mã luồng bắt đầu thực hiện.

Ngoài ra nó còn chứa một con trỏ trỏ đến KTHREAD.

KTREAD bao gồm các thông tin về sự lập lịch và đồng bộ cho

luồng. Ngoài ra nó còn chứa ngăn xếp kernel (được sử dụng khi luồng

chạy trong chế độ kernel) và một con trỏ trỏ đến TEB.

ETHREAD và KTHREAD tồn tại trong không gian kernel, điều đó có

nghĩa là kernel có thể truy nhập đến chúng. TEB là một cấu trúc dữ liệu

trong không gian người dùng, nó được truy nhập bởi luồng chạy trong chế

độ người dùng. Các trường trong TEB chứa ngằn xếp người dùng và một

mảng dữ liệu xác định của luồng.

5.4. Luồng trong Linux

Linux cho phép tạo ra các bản sao của tiến trình, ngoài khả năng

này, nó còn cho phép tạo ra nhiều tiến trình cùng chia sẻ một không gian

địa chỉ của tiến trình gọi. Việc cho phép chia sẻ không gian địa chỉ với tiến

trình cha của tiến trình được sao chép khá giống với nhiều luồng.

Sự chia sẻ không gia địa chỉ là cho phép bởi vì một tiến trình được

biểu diễn ở trong nhân của Linux. Một cấu trúc dữ liệu nhân duy nhất tồn

tại cho mỗi tiến trình trong hệ thống. Cấu trúc dữ liệu này không chỉ chứa

dữ liệu của tiến trình mà nó còn chứa một con trỏ trỏ đến cấu trúc khác

nơi mà dữ liệu này được lưu trữ.

5.5. Bài tập

1. Hãy đưa ra hai ví dụ cho thấy đa luồng cải thiện khả năng thực

hiện của hệ thống hơn đơn luồng.

2. Hãy đưa ra hai ví dụ cho thấy đa luồng không cải thiện khả năng

thực hiện của hệ thống hơn đơn luồng.

3. Hai sự khác nhau giữa luồng mức người dùng và luồng mức hệ

thống là gì?

4. Những tài nguyên nào được sử dụng khi một luồng được tạo ra?

Phạm Ngọc Hưng

55

Quản lý tiến trình

6. Lập lịch CPU

6.1. Các khái niệm cơ bản

CPU-I/O Burst Cycle

Sự thành công của việc lập lịch cho CPU phụ thuộc vào các đặc tính

của tiến trình được chú ý đến. Sự thực hiện của các tiến trình bao gồm

một chu kỳ thực hiện CPU và đợi vào ra. Một tiến trình thực hiện bắt đầu

với một CPU Burst, tiếp theo là một I/O Burst, rồi lại đến CPU Burst và cứ

tiếp tục như vậy. CPU Burst cuối cùng sẽ kết thúc quá trình thực hiện của

tiến trình với một lời gọi hệ thống kết thúc tiến trình.

....

CPU

Burst

I/O

Burst

CPU

Burst

I/O

Burst

CPU

Burts

I/O

Burst

....

Đọc file

Đợi I/O

Ghi file

Đợi I/O

Đọc file

Đợi I/O

CPU Scheduler

Ngay khi CPU rỗi, hệ điều hành phải lựa chọn một tiến trình trong

hàng đợi sẵn sàng để thực hiện. Sự lựa chọn các tiến trình này được thực

hiện bằng bộ lập lịch ngắn hạn. Bộ lập lịch lựa chọn một trong số các tiến

trình trong bộ nhớ và cấp phát CPU cho nó.

Hàng đợi sẵn sàng không nhất thiết phải có dạng FIFO, mà nó có

thể là hàng đợi ưu tiên, một cây hoặc chỉ đơn giản là một danh sách liên

kết không sắp xếp. Tất cả các tiến trình trong hàng đợi sẵn sàng đều

được xếp hàng và chờ cơ hội được thực hiện. Các bản ghi trong hàng đợi

này thông thường là các PCBs của các tiến trình.

Preemptive Scheduling

Sự lập lịch CPU quyết định vào một trong 4 trường hợp sau:

- Khi một tiến trình chuyển từ trạng thái thực hiện sang trạng thái

chờ đợi (đợi I/O)

- Khi một tiến trình chuyển từ trạng thái thực hiện sang trạng thái

sẵn sàng (khi có ngắt)

- Khi một tiến trình chuyển từ trạng thái chờ đợi sang trạng thái

sẵn sàng (hoàn tất I/O)

56

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

- Khi một tiến trình kết thúc

Ở các thời điểm 1 và 4 không được chọn trong thời gian lập lịch.

Với một tiến trình mới, nếu tồn tại trong hàng đợi sẵn sàng, nó phải được

chọn để thực hiện. Việc quyết định chọn lựa thường chỉ diễn ra ở thời

điểm 2 và 3.

Khi bộ lập lịch chỉ thực hiện ở thời điểm 1 và 4 thì sự lập lịch đó

được gọi là lược đồ nonpreemtive (không dừng), còn lại là lược đồ

preemtive (có dừng). Trong lược đồ không dừng, khi CPU được cấp phát

cho một tiến trình, tiến trình đó sẽ giữ CPU liên tục và chỉ trả lại khi kết

thúc hoặc chuyển sang trạng thái chờ đợi. Phương pháp lập lịch này được

sử dụng trong Microsoft Windows 3.1 và hệ điều hành Apple Macintosh.

Không may là lập lịch có dừng lại phải chấp nhận một chi phí. Hãy

xem xét trường hợp hai tiến trình cùng chia sẻ dữ liệu. Một tiến trình đang

cập nhật dữ liệu thì bị dừng và tiến trình thứ hai chạy. Tiến trình thứ hai

có thể lại đọc dữ liệu hiện đang ở trạng thái cập nhật giữa chừng (trạng

thái lấp lửng).

Dispatcher

Một thành phần khác liên quan đến chức năng lập lịch CPU đó là

Dispatcher. Dispatcher là một module trao quyền điều khiển CPU tới tiến

trình được lựa chọn bởi bộ lập lịch ngắn hạn. Chức năng này bao gồm:

- Chuyển ngữ cảnh

- Chuyển chế độ người dùng

- Chuyển đến vị trí thực hiện của chương trình người dùng để thực

hiện

Dispatcher làm việc càng nhanh càng tốt.

6.2. Các tiêu chuẩn lập lịch

Các thuật toán lập lịch khác nhau có các đặc điểm khác nhau. Việc

lựa chọn giải thuật sử dụng trong một tình huống cụ thể phải căn cứ vào

các đặc điểm của các thuật toán khác nhau. Rất nhiều các tiêu chuẩn đã

được để nghị để so sánh các giải thuật lập lịch cho CPU. Các đặc tính

được dùng để so sánh có thể tạo nên sự khác nhau đáng kể trong việc

xác định giải thuật tốt nhất. Các tiêu chuẩn bao gồm:

Phạm Ngọc Hưng

57

Quản lý tiến trình

- Khai thác CPU: làm cho CPU càng bận càng tốt, tính toán, xử lý

nhiều

- Thông suốt: CPU mắc bận trong suốt quá trình tiến trình thực

hiện cho đến khi tiến trình hoàn tất công việc. Một thước đo công việc là

số lượng tiến trình hoàn tất trên một đơn vị thời gian được gọi là

throughtput.

- Thời gian luân chuyển (quay vòng): tổng thời gian tiến trình phải

chờ bên được nạp vào bộ nhớ, chờ đợi, thực hiện CPU, thực hiện I/O

- Thời gian chờ đợi: tổng thời gian tiến trình phải chờ đợi trong

hàng đợi sẵn sàng

- Thời gian trả lời: là khoảng thời gian chờ đợi để có được sự bắt

đầu trả lời yêu cầu.

6.3. Các thuật toán lập lịch

Đến trước phục vụ trước (First come, first served)

Đây là thuật toán lập lịch CPU đơn giản nhất, gọi tắt là FCFS. Với

lược đồ này, tiến trình yêu cầu CPU đầu tiên sẽ được cấp phát CPU trước.

Việc cài đặt giải thuật này cũng khá đơn giản, chỉ cần dùng một hàng đợi

dạng FIFO. Khi một tiến trình được đưa vào hàng đợi sẵn sàng, PCB của

nó sẽ được liên kết vào cuối hàng đợi. Khi CPU rỗi, nó sẽ được cấp phát

cho tiến trình trên đầu hàng đợi. Tiến trình đang chạy sau đó sẽ bị loại bỏ

khỏi hàng đợi.

Thời gian chờ đợi trung bình của chính sách FCFS nói chung là khá

dài. Hãy xem xét tập các tiến trình đến vào thời điểm 0 sau, với độ dài

CPU-burst time là mini giây:

Process

P1

Burst time

24

3

P2

P3

3

58

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

Nếu các tiến trình đến theo trật tự: P1,P2,P3 và được phục vụ theo

thứ tự FCFS biểu đồ Gantt thể hiện như sau:

P1 P2

P3

0

24

27

30

- Thời gian chờ đợi của P1: 0 mini giây

- Thời gian chờ đợi của P2: 24 mini giây

- Thời gian chờ đợi của P3: 27 mini giây

Thời gian chờ đợi trung bình: (0+24+27)/3=17 mini giây

Nếu các tiến trình này đến theo trật tự: P2, P3, P1 thì

P2

0

P3

3

P1

6

30

Thời gian chờ đợi trung bình: (6+0+3)/3=3 mini giây

Lập lịch hàng đợi nhiều mức

Trong quá trình thực hiện, hệ thống có thể có nhiều loại tiến trình

khác nhau. Có tiến trình chạy với giao diện trên Desktop, có tiến trình

chạy Background. Các tiến trình này có mức ưu tiên khác nhau. Tiến trình

chạy trên Desktop thường có mức ưu tiên cao hơn tiến trình chạy

background. Để đáp ứng tốt nhất cho các loại tiến trình này, cần thiết

phải có một thuật toán lập lịch khác có quan tâm tới mức ưu tiên của các

tiến trình.

Thuật toán lập lịch cho nhiều mức hàng đợi chia hàng đợi sẵn sàng

thành nhiều hàng đợi khác nhau. Các tiến trình được liên kết cố định vào

một hàng đợi nào đó dựa trên một số thông số đặc trưng như kích thước

bộ nhớ chiếm dụng, độ ưu tiên của tiến trình hoặc kiểu tiến trình. Mỗi

hàng đợi có một thuật toán lập lịch riêng. Thêm vào đó, cần phải có thuật

toán lập lịch giữa các hàng đợi.

Ví dụ: thuật toán lập lịch cho các hàng đợi với hệ thống có nhiều

hàng đợi như sau:

1. Các tiến trình hệ thống

2. Các tiến trình tương tác

3. Các tiến trình soạn thảo tương tác

Phạm Ngọc Hưng

59

Quản lý tiến trình

4. Các tiến trình xử lý gói

5. Các tiến trình người dùng

Tại mỗi hàng đợi có mức ưu tiên cao hơn so với hàng đợi bên dưới

nó. Mỗi hàng đợi được cung cấp một khoảng thời gian sử dụng CPU, sau

đó mỗi hàng đợi sẽ sử dụng thời gian này lập lịch cho các tiến trình trong

hàng đợi đó.

Trong giải thuật trên, các tiến trình được liên kết cố định tại một

hàng đợi, không được phép chuyển sang hàng đợi khác. Điều này làm

giảm tính linh hoạt của hệ thống. Khi một hàng đợi có ít tiến trình (do đã

có một số tiến trình hoàn tất công việc và kết thúc) khi đó thời gian dành

cho hàng đợi đó có thể bị lãng phí. Các tiến trình trong hàng đợi đó có

nhiều thời gian để thực hiện trong khi các tiến trình ở những hàng đợi

đông khác chỉ có ít thời gian thực hiện. Để giải quyết vấn đề này, người ta

cho phép điều chỉnh, sắp xếp lại các tiến trình ở các hàng đợi, chuyển tiến

trình qua lại giữa các hàng đợi để phân bố tải trọng đều cho các hàng đợi,

khai thác hiểu quả tài nguyên tính toán của hệ thống hơn. Giải thuật thực

hiện như vậy được gọi là giải thuật Mutilevel Feedback Queue. Thông

thường giải thuật này được định nghĩa bởi một số thông số sau:

- Số hiệu hàng đợi

- Thuật toán lập lịch cho mỗi hàng đợi

- Phương pháp sử dụng để xác định để chuyển một tiến trình lên

hàng đợi có mức ưu tiên cao hơn.

- Phương pháp sử dụng để xác định tiến trình cần chuyển đến hàng

đợi có mức ưu tiên thấp hơn

- Phương pháp xác định hàng đợi một tiến trình sẽ nhập vào khi

tiến trình cần dịch vụ

6.4. Lập lịch cho hệ thống đa xử lý

Có hai phương pháp để lập trình cho hệ thống có nhiều CPU:

- Mỗi CPU có một bộ lập lịch riêng, mỗi CPU có một số hàng đợi sẵn

sàng của mình và tự lựa chọn tiến trình trong đó để thực hiện. Với giải

pháp này có thể có hai tiến trình cùng cố gắng truy nhập vào một cấu trúc

60

Phạm Ngọc Hưng

Giáo trình Hệ điều hành - Chương 2: Quản lý tiến trình - Phạm Ngọc Hưng