NHẬP MÔN HỆ ĐIỀU HÀNH

Chương 3 Khái niệm Tiến trình (Process)

3.1 Mở đầu

Trong chương này chúng ta sẽ xem xét khái niệm process, một khái niệm quan trọng nhất để hình dung về công việc của máy tính ngày nay.

Chúng ta sẽ tìm hiểu khái niệm về các trạng thái (rời rạc) của process và cũng như cách mà process chuyển từ trạng thái này sang trạng thái khác cùng với các thao tác cơ bản trên process.

Khái niệm process lần đầu tiên được các kỹ sư thiết kế hệ thống MULTICS vào những năm 60. Trong thời kỳ đầu tiên, process được hiểu trong nhiều trường hợp đồng nghĩa như là chương trình, bài toán (task) hay là đối tượng được bộ xử lý phục vụ,..

Người ta thường dùng định nghĩa process như là chương trình trong lúc chạy.

3.2 Trạng thái của process

Trong thời gian tồn tại của mình, process tồn tại trong các trang thái tách biệt (rời rạc). Sự đổi từ trạng thái này sang trạng thái khác có thể xảy ra bởi các sự kiện khác nhau.

Nói rằng process ở trạng thái hoạt động (running state) nếu nó đang được BXL phục vụ. Còn nếu process đã sẵn sàng để được BXL phục vụ nhưng đang chờ đến lượt thì proces ở trạng thái sẵn sàng - ready state. Nói rằng process ở trạng thái bị cản, chặn - blocked state nếu như nó đang chờ một sự kiện nào đó (ví dụ kết thúc tác vụ vào/ra) để có thể tiếp tục hoạt động. Ngoài 3 trạng thái nói trên còn một số trạng thái khác nhưng tạm thời chúng ta chỉ xem xét quan hệ giữa 3 trạng thái trên.

Để đơn giản chúng ta xem xét trường hợp máy tính chỉ có một BXL. Trong hệ thống một BXL, tại một thời điểm chỉ có thể có một process được thực hiện, còn một số process nằm trong trạng thái sẵn sàng (ready) và một số khác trong trạng thái bị chặn (blocked). Do đó chúng ta có thể lập một danh sách chứa các process ở trạng thái ready và một danh sách các blocked process. Mỗi ready process nằm trong list thứ nhất sẽ có mức độ ưu tiên riêng (priority) của mình- tức là các process đó được sắp xếp theo thứ tự và process nằm ở đầu danh sách sẽ là process có độ ưu tiên cao nhất và sẽ được BXL thực hiện tiếp theo (có nhiều tiêu chuẩn để gán priority và thay đổi priority). Còn danh sách các blocked process nói chung không có thứ tự vì blocked process sẽ được giải phóng (unblock) bởi các sự kiện mà nó đang chờ.

3.3 Sự chuyển trạng thái của process

Khi có một chương trình - task bắt đầu được thực hiện, hệ thống sinh ra một process tương ứng và process đó được đưa vào danh sách các ready process, đơn giản nhất là đưa vào cuối danh sách - tức là có mức ưu tiên priority thấp nhất. Process này sẽ dịch chuyển dần lên phía đầu list bởi vì các process trước nó dần dần được BXL phục vụ. Khi process nằm ở đầu list và BXL được giải phóng thì process này được BXL phục vụ và lúc đó xảy ra sự thay đổi trạng thái của process - chuyển từ trạng thái ready sang running. Việc trao quyền sử dụng BXL cho process đầu tiên trong danh sách các ready processes gọi là quá trình dispatching, điều đó được thực hiện bởi module chương trình nằm trong OS gọi là dispatcher.

Quá trình đổi trạng thái đó có thể biểu diễn bằng ký hiệu:

dispatch(process name): ready  running

Process đang sử dụng BXL được gọi là process đang được thực hiện

Để ngăn chặn trường hợp vô tình hoặc cố ý độc quyền chiếm tài nguyên hệ thống của process, hệ điều hành sinh ra một ngắt cứng đặc biệt - timer interrupt (ngắt thời gian), xác định khoảng thời gian lớn nhất mà một process được sử dụng BXL liên tục. Nếu như sau khoảng thời gian đó, process không tự giải phóng BXL thì hệ thống sẽ sinh ngắt, theo đó quyền điều khiển được chuyển lại cho HĐH. Lúc đó HĐH sẽ chuyển process đang được thực hiện từ trạng thái running về trạng thái, đưa nó vào danh sách các ready process, sau đó đưa process đầu tiên trong danh sách (process có mức ưu tiên cao nhất) vào thực hiện (running state). Các sự biến đổi này có thể biểu diễn bằng hai thao tác:

interval gone (process name): running  ready

dispatch (process name) : ready  running

Nếu như một process đang sử dụng BXL (running state) trong quá trình hoạt động của mình thực hiện tác vụ vào/ra (I/O) thì nó sẽ tự mình giải phóng BXL (tự mình chuyển vào trạng thái blocked để chờ tác vụ vào/ra kết thúc). Sự chuyển trạng thái này có thể biểu diễn:

blocking (process name): running  blocked.

Còn một quá trình thay đổi trạng thái cuối cùng, đó là khi kết thúc tác vụ vào/ra (hay nói chung xảy ra một sự kiện mà blocked process đang chờ) lúc đó process chuyển từ trạng thái blocked sang trạng thái ready - sẵn sàng để thực hiện tiếp. Quá trình này có thể biểu diễn:

waikup(npocess name): blocked  ready.

Với 3 trạng thái cơ bản trên, chúng ta có 4 khả năng chuyển trạng thái của một process đó là:

dispatch (process name): ready  running

interval gone(process name): running  ready

blocking (process name): running  blocked

waikup (process name): blocked  ready

Chú ý rằng trong 4 khả năng trên, chỉ có khả năng thứ 3 là có thể sinh ra bởi chính chương trình người sử dụng, còn lại các khả năng khác đều do các đối tượng khác ở bên ngoài process gây ra.

3.4 Process control Block (PCB)- khối điều khiển tiến trình

Đại diện cho một process trong HĐH là khối điều khiển process (PCB). PCB là một cấu trúc dữ liệu chứa những thông tin quan trọng về process và có thể khác nhau trong các hệ thống khác nhau, trong đó thường có:

trạng thái hiện tại của process

ID (identifier) duy nhất cho process

độ ưu tiên (priority) của process

thông tin về bộ nhớ

thông tin về các tài nguyên process đang sử dụng

vùng để cho các thanh ghi

PCB là đối tượng quan trọng, nhờ nó HĐH có thể có được toàn bộ thông tin cơ bản nhất về một process. Khi HĐH chuyển (switch) BXL từ đang phục vụ process này sang phục vụ process khác, nó dùng vùng cho các thanh ghi trong PCB lưu thông tin giá trị các thanh ghi của hệ thống để có thể tiếp tục thực hiện process mỗi khi process đến lượt được sử dụng BXL.

Tóm lại, PCB là đối tượng chính đại diện cho process đối với HĐH. Vì HĐH phải có khả năng thực hiện các thao tác với các PCB khác nhau một cách nhanh chóng, trong nhiều hệ thống có những thanh ghi đặc biệt luôn chỉ tới PCB của running process. Và cũng có những lệnh cài đặt ngay trong phần cứng để đảm bảo nhanh chóng ghi thông tin trạng thái vào PCB và tiếp theo là nhanh chóng đọc các thông tin đó.

3.5 Các thao tác với process

Hệ thống điều khiển process cần có khả năng thực hiện các thao tác với process, trong đó có:

tạo process (create)

huỷ process (free, destroy)

thay đổi độ ưu tiên priority

dừng - block process

kích hoạt - waikup process

thực hiện process (dispatch)

Quá trình tạo một process gồm nhiều thao tác nhỏ:

gán tên cho process

đưa tên process vào danh sách các process của hệ thống

xác định mức ưu tiên priority ban đầu cho process

tạo, nạp thông tin PCB

phân chia tài nguyên khởi đầu cho process

Một process có thể tạo ra process mới. Process đầu tiên là parent còn process mới được tạo ra là child process. Để tạo process chỉ cần một process tức là mỗi child process chỉ có một parent còn một parent có thể có nhiều child. Các quan hệ đó tạo ra kiến trúc process

Xoá một process là loại bỏ nó khỏi hệ thống. Khi đó các tài nguyên được phân chia cho process sẽ được giải phóng, trả lại cho HĐH, tên của process được xoá khỏi tất cả các danh sách của hệ thống, còn PCB cũng được giải phóng.

Một suspended process (bị hoãn, dừng) là process không tiếp tục được thực hiện đến khi có một process khác kích hoạt nó. Suspending (tạm dừng) là một thao tác quan trọng được sử dụng trong nhiều hệ thống với các cách cài đặt, thực hiện khác nhau. Suspending thường chỉ diễn ra trong khoảng thời gian ngắn. Ví dụ HĐH phải suspend một số process (không phải luôn là tất cả) trong thời gian ngắn khi hệ thống quá tải,.. Trong trường hợp process bị dừng trong thời gian dài hơn thì các tài nguyên của nó phải được giải phóng trả lại cho HĐH. Việc một loại tài nguyên có cần giải phóng hay không còn phụ thuộc vào kiểu của nó. Ví dụ bộ nhớ cần được giải phóng ngay, còn thiết bị vào ra có thể vẫn thuộc quyền sử dụng process trong trường hợp process bị suspend trong thời gian ngắn còn sẽ được giải phóng khi thời gian suspend dài hay không xác định.

Quá trình activate - kích hoạt là thao tác chuẩn bị để process có thể tiếp tục thực hiện từ đúng trạng thái mà nó bị dừng trước đó.

Quá trình huỷ bỏ một process sẽ khá phức tạp nếu nó là parent process. Trong một số hệ thống thì các children process sẽ tự động bị huỷ bỏ theo, còn trong một số hệ thống khác thì children process vẫn tồn tại (độc lập với parent process).

Sự thay đổi priority process thường đơn giản là thay đổi giá trị priority trong PCB bởi HĐH.

3.6 Suspending and Activating - dừng và kích hoạt

Chúng ta đã biết các khái niệm suspend and activate. Các thao tác này khá quan trọng do các lý do:

nếu hệ thống hoạt động không ổn định có dấu hiệu trục trặc thì các process đang diễn ra cần suspend để lại được activate sau khi sửa lỗi.

Người sử dụng (lập trình viên) có thể cần tạm dừng (không phải huỷ bỏ) process để kiểm tra kết quả trung gian xem chương trình có hoạt động đúng hay không.

Một số process có thể bị suspend trong khoảng thời gian ngắn khi hệ thống quá tải và sau đó lại được activate khi có đủ tài nguyên (hệ thống trở về trạng thái bình thường).

So với mục trước- có thêm hai trạng thái ứng với các thao tác suspend và activate.

Tác nhân dừng có thể là chính bản thân process hay là process khác. Trong hệ có một BXL thì process chỉ có thể dừng chính bản thân nó vì không có proces khác nào đang chạy đồng thời với nó. Còn trong hệ có nhiều BXL thì một process có thể bị dừng bởi process khác đang chạy trên BXL khác.

Một process ở trạng thái ready chỉ có thể bị dừng bởi process khác, lúc đó xảy ra sự chuyển trạng thái:

suspend (process name): ready  suspended-ready

Process đang ở trạng thái suspended-ready có thể chuyển về trạng thái ready bởi process khác; quá trình chuyển trạng thái đó có thể biểu diễn bởi

activate (process name): suspend-ready  ready

Process đang ở trạng thái blocked có thể chuyển sang trạng thái suspend bởi một process khác, khi đó diễn ra sự đổi trạng thái

suspend (process name): blocked  suspend-blocked

Và ngược lại, prrocess ở trạng thái suspended blocked có thể được kích hoạt bởi một process khác

activate (process name): suspended-blocked  blocked

Chúng ta có thể đặt vấn đề tại sao không thay vì suspend một process ở trạng thái blocked, ta vẫn chờ đến khi có sự kiện (kết thúc I/O) mà process đợi xảy ra để process chuyển về trạng thái ready. Tuy nhiên tác vụ I/O hay sự kiện process chờ có thể không xảy ra hay không biết khi nào mới xảy ra. Như thế, các nhà thiết kế cần phải chọn lựa: hoặc suspend một blocked process (đưa về trạng thái suspended-blocked) hoặc phải sinh ra cơ chế cho phép đưa process từ trạng thái blocked sang trạng thái ready và sau đó chuyển thành trạng thái suspened-ready khi kết thúc I/O hay diễn ra sự kiện process đang chờ. Mặt khác thao tác suspending thường có mức ưu tiên cao và cần thực hiện ngay, do đó phần lớn các hệ thống sử dụng cách thứ nhất. Khi sự kiện process đang chờ xảy ra (nếu như nó xảy ra), trạng thái của process sẽ chuyển từ suspended-blocked sang trạng thái suspended-ready:

Incommingevent (process name): suspended-blocked  suspended-ready

3.7 Xử lý ngắt

Trong thực tế có nhiều trường hợp tương tự ngắt trong máy tính.

Trong kỹ thuật máy tính, ngắt (interupt) là sự kiện làm thay đổi trình tự thực hiện lệnh bình thường của BXL. Tín hiệu ngắt được xử lý bởi phần cứng. Khi xảy ra ngắt, trình tự thực hiện như sau:

Điều khiển chuyển cho HĐH

HĐH lưu lại trạng thái của process bị ngắt. Trong nhiều hệ thống thì thông tin đó được lưu trong PCB của process bị ngắt.

HĐH phân tích loại ngắt và chuyển điều khiển cho chương trình xử lý ngắt tương ứng.

Tác nhân gây ra ngắt có thể là chính bản thân process đang chạy, hay là một sự kiện có thể liên quan hoặc không liên quan đến process đó.

3.7.1 Các dạng ngắt

Chúng ta xem xét các dạng ngắt trong các hệ thống máy lớn của IBM:

SVC- interrupt: ngắt này do process đang chạy sinh ra. SVC do chương trình ứng dụng sinh ra để yêu cầu một dịch vụ nào đó của hệ thống, ví dụ thực hiện tác vụ vào/ra, cấp phát bộ nhớ... Cơ chế SVC giúp bảo vệ HĐH, người sử dụng không được tự do xâm nhập OS mà anh ta phải yêu cầu dịch vụ thông qua lệnh SVC. Do đó HĐH luôn kiểm soát được các thao tác vượt quá giới hạn ứng dụng và hoàn toàn có thể từ chối yêu cầu.

Ngắt vào/ra: do các thiết bị vào/ra sinh ra. Các ngắt này thông báo cho BXL về sự thay đổi trạng thái nào đó ví dụ kết thúc tác vụ in, máy in hết giấy,...

External interrupt: ngắt này có thể do nhiều nguyên nhân sinh ra, trong đó có ngắt thời gian overtime, ngắt bàn phím, ngắt từ các BXL khác trong hệ thống đa BXL, ...

Restart interrupt: sinh ra khi người điều kiển cần khởi động lại hệ thống, hay lệnh restart SIGP của một processor (BXL) khác trong hệ thống đa BXL.

Program check interrupt: ngắt sinh ra do lỗi hoạt động của chương trình ví dụ lệnh chi cho 0, ...

Machine check interrupt: sinh ra do lỗi phần cứng trong hệ thống.

3.8.2 Context switching - Đổi ngữ cảnh

Để xử lý các loại ngắt, trong HĐH có chương trình chuyên biệt gọi là interrupt handler. Như trên đã nói, trong hệ thống có 6 loại ngắt, như thế trong HĐH có 6 IH (interrupt handler) để xử lý 6 loại ngắt khác nhau. Khi có ngắt thì HĐH ghi lại trạng thái của process bị ngắt và chuyển điều khiển cho chương trình xử lý ngắt tương ứng. Điều đó được thực hiện bởi phương pháp gọi là "chuyển đổi ngữ cảnh" (context switching).

Trong phương pháp này sử dụng các thanh ghi trạng thái chương trình PSW (program status word), trong đó chứa thứ tự thực hiện lệnh và các thông tin khác nhau liên quan đến trạng thái của process. Có 3 loại PSW: PSW hiện thời (current), PSW mới (new) và PSW cũ (old)

Địa chỉ của lệnh tiếp theo (sẽ được thực hiện) được chứa trong current PSW, trong current PSW cũng chứa thông tin về những loại interrupt nào hiện đang bị cấm (disable) hay được phép (enable). BXL chỉ phản ứng với những loại interrupt được phép, còn các interrupt đang bị cấm sẽ được xử lý sau hoặc bỏ qua. Có một số interupt không bao giờ bị cấm: SVC, restart,..

Trong hệ có một BXL thì chỉ có một current PSW, nhưng có 6 new PSW (tương ứng cho mỗi loại ngắt) và 6 old PSW tương ứng. New PSW của một loại ngắt chứa địa chỉ của chương trình xử lý ngắt (interupt handler) loại đó.

Khi xảy ra ngắt (nếu loại ngắt đó không bị cấm) lúc đó sẽ tự động (do phần cứng thực hiện) xảy ra quá trình chuyển đổi PSW như sau:

current PSW trở thành old PSW của loại ngắt tương ứng

new PSW của loại ngắt đó trở thành current PSW

Như thế, sau khi chuyển đổi thì current PSW chứa địa chỉ của chương trình xử lý ngắt và sau đó chương trình xử lý ngắt sẽ được thực hiện. Khi kết thúc chương trình xử lý ngắt, BXL lại hoạt động bình thường, BXL sẽ tiếp tục phục vụ process bị ngắt hoặc có thể một process khác trong danh sách các ready process. Trong trường hợp process không cho phép giải phóng (nhường) quyền sử dụng BXL thì nó sẽ tiếp tục được BXL phục vụ, còn nếu nó cho phép thì nó tiếp tục được sử dụng BXL khi không có ready process nào.

Trong các hệ thống, có nhiều mô hình xử lý ngắt khác nhau không hoàn toàn như mô hình trên.

3.8 Hạt nhân của OS

Tất cả các thao tác liên quan đến process, thực hiện bởi một phần HĐH gọi là hạt nhân - kernel. Kernel chỉ là một phần không lớn (về kích thước code) của HĐH nhưng nó là một trong số những thành phần được sử dụng nhiều nhất trong HĐH. Do đó kernel thường luôn được nạp vào bộ nhớ, trong khi các thành phần khác có thể nằm ở bộ nhớ ngoài và chỉ được nạp vào khi cần.

Một trong những chức năng quan trọng nhất trong kernel là xử lý ngắt. Trong các hệ lớn nhiều thành phần (component) thường xuyên có dòng lớn (nhiều) ngắt. Do đó xử lý ngắt nhanh đóng vai trò quan trọng trên quan điểm sử dụng tài nguyên hệ thống và đảm bảo thời gian phản ứng với các yêu cầu của người dùng một cách nhanh chóng.

Khi kernel xử lý ngắt, nó cấm các ngắt khác và chỉ cho phép tiếp tục xử lý ngắt sau khi xử lý xong ngắt hiện thời. Trong trường hợp có dòng liên tục các ngắt thì có thể xuất hiện tình huống các ngắt bị chặn trong thời gian tương đối lớn tức là hệ thống không phản ứng kịp thời với các sự kiện. Do đó kernel thường được thiết kế sao cho nó chỉ thực hiện việc tiền xử lý tối thiểu và chuyển việc xử lý tiếp theo cho process hệ thống (system process) tương ứng và có thể cho phép xử lý các ngắt tiếp theo. Theo đó các ngắt bị cấm trong khoảng thời gian nhỏ hơn do đó tốc độ phản ứng của hệ thống tăng đáng kể.

3.8.1 Các chức năng chính của kernel

Kernel thường gồm các chương trình thực hiện các chức năng sau:

xử lý ngắt

tạo và xoá các process

đổi trạng thái của process

dispatching

suspend and activate process

đồng bộ (synchronize) các process

xử lý, tổ chức mối quan hệ giữa các process

điều khiển PCBs

quản lý bộ nhớ

hỗ trợ làm việc hệ thống file

3.8.2 Cho phép (enable) và cấm (diasable) ngắt

Xâm nhập kernel thường được thực hiện thông qua ngắt, khi kernel phản ứng với ngắt nào đó thì nó cấm các ngắt khác. Sau khi phân tích nó chuyển việc xử lý cho một system process chuyên làm việc với loại ngắt đó.

Trong một số hệ thống mỗi ngắt đều đươc xử lý bởi cả HĐH cồng kềnh, do đó các ngắt thường bị cấm trong phần lớn thời gian nhưng về nguyên tắc HĐH lại đơn giản hơn. Cách này thường áp dụng cho các máy nhỏ, làm việc với ít process. Còn với các hệ thống phức tạp, thường có một phần HĐH chuyên xử lý ngắt cho phép nâng cao các chỉ số của cả hệ thống.

3.8.3 Kiến trúc phân cấp của hệ thống

Trong việc thiết kế HĐH, phương pháp xây dựng HĐH phân cấp thành nhiều khối có nhiều ưu điểm. Tầng thấp nhất của kiến trúc thường là phần cứng, ở các lớp tiếp theo thường là các module với các chức năng khác nhau của HĐH. Tổng hợp các module của kernel ta có máy tính mở rộng (extended machine), nhờ đó hệ thống cung cấp nhiều dịch vụ khác nhau cho người dùng. Các chức năng mở rộng đó (do kernel cung cấp) được gọi là các primitive.

Phía trên kernel là các system process của HĐH để phục vụ cho các process của người dùng. Còn trên cùng là các user process.

Kinh nghiệm cho thấy kiến trúc lớp làm cho công việc thiết kế, sửa đổi, test dễ dàng hơn. Trong hệ thống mà kernel gồm nhiều lớp, thì cần xem xét cẩn thận chức năng nào nằm ở lớp nào. Trong các hệ đó thường người ta hạn chế cho phép truy xuất từ trên xuống tức là tại mỗi lớp chỉ có thể thâm nhập đến lớp dưới kế tiếp mà thôi.

3.8.4 Thực hiện kernel với microcode

Xu hướng: thiết kế nhiều chức năng với microcode đó là cách hiệu quả bảo vệ kernel ngoài ra viết microprogram tốt có thể nâng cao tốc độ của cả hệ thống. Tất nhiên đổi lại việc thiết kế phức tạp hơn rất nhiều.

Chương 4: Các process song song không đồng bộ

asynchronous concurent process

4.1 Mở đầu

Các process gọi là song song nếu các process đó tồn tại đồng thời. Các process song song (concurent process) có thể hoạt động hoàn toàn độc lập với nhau hoặc song song không đồng bộ - asynchronous, tức là theo chu kỳ chúng cần đồng bộ và tương tác với nhau. Asynchronism - song song không đồng bộ là một vấn đề phức tạp.

Chúng ta sẽ xem xét một số vấn đề liên quan đến điều khiển các quá trình song song không đồng bộ - asynchronous concurent process. Các ví dụ được đưa ra với ngôn ngữ giả pascal. Một số ví dụ về ngôn ngữ cho phép lập trình song song là ngôn ngữ Modula (Nicolar Witt), ngôn ngữ Ada.

4.2 Xử lý song song

Theo sự phát triển của máy tính chúng ta có thấy sự phổ biến của các hệ thống đa BXL (multiprocessor) và cùng với nó là sự phổ biến của xử lý song song. Nếu như một quá trình logic có thể xử lý song song logic thì các hệ thống mới có thể xử lý chúng song song thực sự và có thể công việc được phân chia giữa các BXL khác nhau.

Xử lý song song là vấn đề được quan tâm và có nhiều khó khăn do một loạt nguyên nhân khác nhau. Con người theo tự nhiên có xu hướng chỉ chú ý đến một công việc tại mỗi thời điểm hơn là nghĩ đến nhiều việc khác nhau cúng một lúc. Thông thường khó mà xác định những thao tác nào có thể thực hiện song song. Và theo dõi một chương trình song song khó hơn nhiều so với chương trình xử lý tuần tự.

Các asynchronous process cần tương tác qua lại lẫn nhau theo chu kỳ thời gian và tương tác này có thể khá phức tạp. Cuối cùng, việc chứng tỏ sự đúng đắn cho các chương trình song song khó hơn nhiều so với trường hợp chương trình tuần tự. Và chúng ta cũng đến phương pháp hiệu quả để chứng minh tính đúng đắn của chương trình, có như thế chúng ta mới có thể xây dựng các hệ thống có tính ổn định cao.

4.3 Các lệnh chỉ thị xử lý song song: parbegin và parend

Trong nhiều ngôn ngữ lập trình đã có các chỉ thị yêu cầu xử lý song song(như trong Ada, Modula,...) các chỉ thị này thường đi theo cặp:

Chỉ thị đầu tiên chỉ ra rằng bắt đầu từ sau lệnh đó, chương trình được tách thành một số dòng điều khiển (thread control) thực hiện song song.

Chỉ thị thứ hai chỉ ra rằng từ đó chương trình lại được xử lý tuần tự.

Có nhiều tên khác nhau nhưng người ta thường dùng cặp parbegin/parend (Dijktra - cooperating sequenical process). Nói chung đoạn mã chương trình được thực hiện song song có dạng

parbegin

operator 1

operator 2

. . . . . .

operator n

parend

Việc thực hiện đoạn chương trình song song có thể hình dung như sau. Chương trình được thực hiện theo một luồng điều khiển tuần tự, đến khi gặp lệnh parbegin, luồng xử lý sẽ được chia thành n quá trình xử lý độc lập, mỗi quá trình sẽ xử lý một thao tác tương ứng từ operator 1, ... đến operator n. Thao tác này có thể là các lệnh đơn, lời gọi hàm, khối các lệnh tuần tự nằm giữa begin/end hay là tổ hợp các thao tác đó.

Các quá trình xử lý sẽ dần thực hiện đến lệnh parend lúc đó luồng điều khiển lại hợp nhất thành một luồng xử lý các lệnh tiếp theo một cách tuần tự.

Ví dụ xét biểu thức:

x:= ( -b + ( b2 - 4*a*c ) * 5 ) / (2*a)

nếu quá trình xử lý là hoàn toàn tuần tự chúng ta có thể làm theo các bước sau:

b2

4*a

(4*a)*c

b2 - (4*a*c)

(b2 - (4*a*c))*5

-b

-b + ((b2 - (4*a*c))*5)

2*a

(-b + ((b2 - (4*a*c))*5)) / (2*a)

Các bước xử lý trên theo đúng trình tự quy tắc thực hiện phép toán.

Với hệ thống hỗ trợ xử lý song song chúng ta có thể làm như sau:

parbegin

temp1 := -b

temp2 := b2

temp3 := 4*a

temp4 := 2*a

parend

temp5 := temp3*c

temp5 := temp2 - temp5

temp5 := temp5 * 5

temp5 := temp1 + temp5

x := temp5 / temp4

Ta thấy nếu thực hiện xử lý song song thì thời gian tính toán giảm đi đáng kể so với khi tính tuần tự.

4.4 Mutual exclusion (loại trừ nhau)

Xét trường hợp hệ thống phục vụ trong chế độ phân chia thời gian cho nhiều thiết bị đầu cuối - terminal. Giả sử khi người sử dụng đánh hết một dòng và gõ Enter, cần tính số dòng của tất cả các người sử dụng đã gõ từ tất cả các terminal. Để thực hiện điều đó, mỗi khi một người sử dụng nào đó gõ enter thì process của người dùng đó sẽ tăng thêm 1 đơn vị cho một biến toàn cục (global) totalLine. Vì hệ thống là đa xử lý và đa người dùng, do đó hoàn toàn có khả năng là hai người dùng khác nhau gõ enter gần như đồng thời, khi đó 2 process điều khiển ứng với 2 người dùng đó sẽ đồng thời muốn truy nhập đến biến toàn cục totalLine. Để tăng biến đó giả sử mỗi process ứng dụng đều dùng các lệnh sau:

1- load totalline

2- totalline := totalline + 1

3- store totalline

Giả sử tại một thời điểm, totalline có giá trị 62829

Bây giờ nếu mới process 1 thực hiện được 2 lệnh đầu tiên:

load totalline (đọc giá trị hiện thời của biến) và tăng 1 cho giá trị biến totalline := totalline + 1 khi đó trong một thanh ghi (ví dụ Ax) chứa giá trị mới 62830 của biến totalline.

Sau đó process 1 không được quyền sử dụng BXL nữa (ví dụ do ngắt thời gian) và đến lượt process 2 được thực hiện. Giả sử process 2 kịp thực hiện cả 3 lệnh trên, khi đó giá trị của biến totalline sau khi thực hiện xong sẽ có giá trị 62830. Sau đó điều khiển được trả lại cho HĐH và đến lượt process 1 được tiếp tục, nó thực hiện nốt lệnh thứ 3 tức là ghi lại giá trị 62830 vào biến totalline. Chúng ta thấy do sự điều khiển truy xuất không đúng mà chương trình hoạt động không đúng.

Ta thấy rằng vấn đề này có thể khắc phục nếu mỗi process có quyền truy nhập duy nhất đến biến totalline, tức là khi một process đang truy nhập đến biến totalline thì các process khác phải đợi đến khi process đầu tiên kết thúc truy nhập.

Như thế, khi một process truy nhập đến dữ liệu chung thì cần cấm tất cả các process khác truy nhập đến cùng dữ liệu vào thời điểm đó. Điều đó gọi là mutual exclusion (loại trừ lẫn nhau)

4.5 Khoảng tới hạn Critical region

Loại trừ lẫn nhau chỉ cần thiết trong trường hợp khi các process cùng truy nhập đến dữ liệu chung, hay khi chúng thực hiện các thao tác có thể dẫn tới tranh chấp (conflic) dữ liệu nói chung, còn khi chúng thực hiện các thao tác operation không dẫn tới tranh chấp thì hoàn toàn có thể thực hiện song song đồng thời. Khi process truy nhập đến dữ liệu chung thì người ta nói rằng lúc đó process nằm trong khoảng tới hạn - critical region.

Rõ ràng là để giải quyết tranh chấp thì khi có một process nằm trong khoảng tới hạn, cần phải không cho phép process khác (ít nhất là các process truy nhập đến cùng một dữ liệu) được vào khoảng tới hạn (tất nhiên chúng vẫn có thể thực hiện các thao tác khác ngoài khoảng thới hạn). Còn khi proces ra khỏi khoảng tới hạn thì một trong số các process đang chờ vào khoảng tới hạn phải được tiếp tục vào khoảng tới hạn. Đảm bảo 'loại trừ lẫn nhau' là một trong những vấn đề mấu chốt của lập trình xử lý song song. Có nhiều phương pháp được đề xuất từ thực hiện hoàn toàn bằng phần mềm đến thực hiện bằng phần cứng, từ mức thấp đến mức cao, có những phương pháp cho phép loại trừ lẫn nhau trong điều kiện tương đối thoải mái, còn có những phương pháp thì bắt buộc phải có thêm các điều kiện chặt chẽ.

Khi một process nằm trong khoảng tới hạn thì có nhiều vấn đề cần quan tâm. Trong chế độ này nó có toàn quyền truy nhập dữ liệu chung còn các process khác phải chờ. Do đó các process cần ra khỏi chế độ này càng nhanh càng tốt, trong chế độ này nó không được chuyển sang trạng thái blocked, do đó các khoảng tới hạn cần thiết kế, kiểm tra cẩn thận (để ví dụ không cho phép xảy ra vòng lặp chờ trong khoảng tới hạn...)

Khi process kết thúc (ra khỏi) khoảng tới hạn (bình thường hoặc ngay cả khi có lỗi) thì HĐH phải kiểm soát được để huỷ bỏ chế độ tới hạn, nhờ thế các process khác có thể đến lượt vào khoảng tới hạn.

4.6 Mutual exclusion Primitive

Chương trình song song dưới đây đảm bảo bài toán trong mục 4.4 hoạt động đúng. Từ đây trở đi chúng ta xét trường hợp chỉ có hai process song song, cần phải nói rằng trường hợp có n process (n>2) thì bài toán phức tạp hơn rất nhiều.

Trong chương trình 4.2 chúng ta dùng hai chỉ thị: enterMutualExclusion và exitMutualExclusion trong mỗi process ở đoạn code truy nhập đến dữ liệu chung (biến toàn cục totalLine), hai chỉ thị này bao hai đầu khoảng tới hạn. Đôi khi các chỉ thị này được gọi là mutual exclusion primitive

Chương trình 4.2

Program MutualExclusionSample

var

totalLine: integer;

procedure process1

while true do begin

get line {readln}

enterMutualExclusion;

totalLine := totalLine +1;

exitMutualExclusion;

processing line ...

end;

end;

procedure process2

while true do begin

get line {readln}

enterMutualExclusion;

totalLine := totalLine +1;

exitMutualExclusion;

processing line ...

end;

end;

totalLine := 0;

parbegin

process1;

process2;

parend;

end.

Trong trường hợp có hai process, các lệnh primitive làm việc như sau: khi process 1 thực hiện chỉ thị enterMutualExclusion (và lúc đó process 2 ở ngoài khoảng tới hạn) thì nó được vào khoảng tới hạn, thực hiện các lệnh trong khoảng tới hạn và đến khi thực hiện lệnh exitMutualExclusion là lúc báo hiệu nó ra khỏi khoảng tới hạn. Còn nếu khi process1 muốn vào khoảng thới hạn, trong lúc đó process 2 đã ở trong khoảng tới hạn thì process1 nó phải chờ đến khi process2 ra khỏi khoảng tới hạn để có thể tiếp tục vào khoảng tới hạn.

Nếu cả hai process thực hiện enterMutualExclusion cùng một lúc thì một trong hai process sẽ được phép vào khoảng tới hạn còn process kia sẽ phải chờ, có thể sự lựa chọn là ngẫu nhiên.

4.7 Thực hiện mutual exclusion primitive

Chúng ta sẽ tìm cách thực hiện các primitive enter và exit với các hạn chế sau:

Vấn đề giải quyết hoàn toàn bằng chương trình (phần mềm) trên hệ thống không có lệnh chuyên cho mutual exclusion. Mỗi lệnh được thực hiện trọn vẹn không bị ngắt giữa chừng. Khi có nhiều process cùng muốn truy nhập đến dữ liệu chung thì tranh chấp được giải quyết bằng phần cứng, một cách tình cờ sẽ có một process được chọn.

Không có bất cứ giả sử gì về tốc độ tương đối của các asynchronous parallel process

Các process nằm ngoài khoảng tới hạn không thể cấm các process khác vào khoảng tới hạn.

Không được để process chờ vô hạn để vào khoảng tới hạn.

Cơ chế thực hiện loại trừ lẫn nhau bằng chương trình được nhà toán học Hà lan Dekker đề ra đầu tiên. Chúng ta sẽ xem xét các version của thuật toán Dekker do Dijkstra thực hiện.

4.8 Thuật toán Dekker

Đầu tiên, chúng ta xem xét version đầu tiên

Có thể coi mỗi process như là một vòng lặp vô tận với nhiều lần lặp vào chế độ mutual exclusion. Trong version này primitive enter mutual exclusion được thực hiện nhịp vòng lặp while chờ đến khi biến processno bằng số của process, còn primitive exit mutual exclusion thực hiện như một lệnh đặt biến processno bằng số của process khác.

Chương trình 4.3

Program Version1

var

processNo: integer;

procedure process1

while true do begin

....

while processNo = 2 do ;

{critical region}

processNo := 2;

....

end;

end;

procedure process2

while true do begin

....

while processNo = 1 do ;

{critical region}

processNo := 1;

....

end;

end;

processNo := 1;

parbegin

process1;

process2;

parend;

end.

Hoạt động: cả hai process cùng thực hiện. Vì đầu tiên biến processNo gán bằng 1 do đó chỉ process1 được vào critical region. Process 2 khi muốn vào critical region kiểm tra thấy biến processno có giá trị 1 do đó nó phải chờ bằng vòng lặp rỗng, nó chờ đến khi processNo=2 tức là khi process 1 ra khỏi critical region và đặt processNo :=2. Vậy chương trình đã đảm bảo loại trừ lẫn nhau (mutual exclusion).

Version1 có nhiều nhược điểm, process 1 phải vào critical region trước tiên (tức là dù process 2 sẵn sàng trước thì nó vẫn phải chờ) và các process lần lượt vào critical region theo thứ tự cố định (do đó nếu một process thực hiện các lệnh trong critical region thường xuyên hơn thì nó phải làm việc với tốc độ chậm hơn nhiều). Chương trình này đảm bảo không rơi vào tình trạng deadlock vì khi cả hai process cùng muốn vào critical region thì có ít nhất một process tiếp tục. Còn khi một process kết thúc thì sau đó process còn lại cũng kết thúc.

Trong version 1 việc thực hiện mutual exclusion chỉ bằng một biến do đó có vấn đề các process vào khoảng tới hạn theo thứ tự cố định. Để cải tiến, trong version 2 sử dụng hai biến logic: flag1 và flag2, chúng nhận giá trị true khi process tương ứng nằm trong critical region.

Trong version này process 1 chủ động chờ (active wait) trong khi biến flag2 vẫn là true. Khi process 2 ra khỏi khoảng tới hạn, nó đặt lại flag2 := false và do đó process1 ra khỏi vòng chờ while, đặt biến flag1 = true và vào khoảng tới hạn. Khi flag1 còn là true thì process 2 không thể vào khoảng tới hạn.

Chương trình 4.4

Program Version2

var

flag1, flag2: boonlean;

procedure process1

while true do begin

....

while flag2 = true do ;

flag1 := true;

{critical region}

flag1 := false;

....

end;

end;

procedure process2

while true do begin

....

while flag1 = true do ;

flag2 := true;

{critical region}

flag2 := false;

....

end;

end;

flag1 := false;

flag2 := false;

parbegin

process1;

process2;

parend;

end.

Nhưng lại xuất hiện một số vấn đề liên quan đến lập trình song song. Vì process 1 và process 2 là song song do đó chúng có thể đồng thời thử vào critical region. Đầu tiên các biến flag1 và flag2 có giá trị false. Process 1 kiểm tra biến flag2 thấy flag2=false và thoát khỏi vòng lặp chờ, trước khi nó kịp đặt flag1 thành true bằng lệnh flag1:= true thì đến lượt process 2 được chiếm BXL, process2 cũng có thể kiểm tra thấy flag1 là false (vì lúc đó process1 chưa kịp đặt)- lúc đó process 2 đặt flag2:= true và cũng vào critical region. Như thế cả hai process cùng vào chế độ critical, do đó version 2 không đảm bảo loại trừ lẫn nhau.

Điểm yếu của version 2 là giữa thời điểm khi process nằm trong vòng chờ xác định thấy nó có thể đi tiếp và thời điểm nó đặt cờ (biến flag) nói rằng nó đã vào critical region. Do đó cần thiết để vào lúc process kết thúc vòng lặp chờ, process khác không thể ra khỏi vòng lặp chờ. Trong chương trình version3 (4,5) để giải quyết vấn đề này người ta đặt cờ cho mỗi process trước khi thực hiện vòng lặp chờ.

Chương trình 4.5

Program Version3

var

flag1, flag2: boonlean;

procedure process1

while true do begin

....

flag1 := true;

while flag2 = true do ;

{critical region}

flag1 := false;

....

end;

end;

procedure process2

while true do begin

....

flag2 := true

while flag1 = true do ;

{critical region}

flag2 := false;

....

end;

end;

flag1 := false;

flag2 := false;

parbegin

process1;

process2;

parend;

end.

Version 3 giải quyết được một vấn đề nhưng lại nảy sinh vấn đề khác. Nếu như mỗi process trước khi vào vòng chờ đặt cờ của mình thì mỗi process có thể kiểm tra thấy cờ của process khác đã đặt và cả hai process đều chờ ở vòng lặp vô tận. Chương trình này là một ví dụ của khái niệm deadlock - tắc ngẽn.

Điểm yếu của Version 3 là ở chỗ mỗi process đều có thể bị block ở vùng chờ. Chúng ta cần có biện pháp thoát khỏi vòng chờ này.

Trong version 4 để làm điều đó, ta đặt lại cờ (biến flag) trong khoảng thời gian ngắn về giá trị false để process kia có cơ hội thoát khỏi vòng chờ.

Chương trình 4.6

Program Version4

var

flag1, flag2: boonlean;

procedure process1

while true do begin

....

flag1 := true;

while flag2 = true do begin

flag1 := false;

Delay(random);

flag1 := true;

end;

{critical region}

flag1go := false;

....

end;

end;

procedure process2

while true do begin

....

flag2 := true

while flag1 = true do begin

flag2 := false;

Delay(random);

flag2 := true;

end;

{critical region}

flag2 := false;

....

end;

end;

flag1 := false;

flag2 := false;

parbegin

process1;

process2;

parend;

end.

Thoạt xem, version4 đảm bảo sự loại trừ lẫn nhau và không bị deadlock, nhưng lại xuất hiện vấn đề khác cũng rất quan trọng, và cũng là vòng chờ vô tận. Chúng ta xét xem tại sao điều đó xảy ra. Vì chúng ta không có giả sử gì về tốc độ tương đối giữa các process do đó có thể có trường hợp các process lần lượt thực hiện dãy thao tác như sau trong một interval:

1. đặt cờ flag giá trị true, vào vòng lặp chờ,

2. đặt lại cờ flag giá trị false, chờ random

3. lại đặt cờ giá trị true và lặp lại quá trình trong vòng chờ.

Khi đó các process thực hiện xong tất cả các thao tác đó, điều kiện kiểm tra luôn đúng và không thể thoát khỏi vòng chờ. Mặc dù trường hợp đó rất hiếm nhưng về nguyên tắc là có thể, do đó version 4 cũng không thể áp dụng ví dụ như trong hệ thống điều khiển chuyến bay vũ trụ, ... dù xác suất nhỏ.

Như thế chúng ta cần khắc phục sự chờ vô tận. Thuật toán Dekker loại trừ tình trạng chờ vô tận trong Version 4. Với một số lượng không lớn code, chương trình theo thuật toán của Dekker cho phép giải quyết triệt để vấn đề loại trừ lẫn nhau cho hai process, không đòi hỏi các lệnh đặc biệt nào.

Chương trình 4.7

Program Dekker

var

flag1, flag2go: boonlean;

selection : byte; {set of 1,2}

procedure process1

while true do begin

....

flag1 := true;

while flag2 = true do begin

if selection = 2 then begin

flag1 := false;

while selection = 2 do ;

flag1 := true;

end;

end;

{critical region}

selection := 2;

flag1 := false;

....

end;

end;

procedure process2

while true do begin

....

flag2 := true

while flag1 = true do begin

if selection = 1 then begin

flag2 := false;

while selection = 1 do ;

flag2 := true;

end;

end;

{critical region}

selection := 1;

flag2 := false;

....

end;

end;

flag1 := false;

flag2 := false;

selection := 1;

parbegin

process1;

process2;

parend;

end.

Process 1 thông báo rằng muốn vào khoảng tới hạn bằng cách đặt cờ của mình (process1go := true). Sau đó nó vào vòng lặp kiểm tra xem process 2 có muốn vào khoảng tới hạn hay không. Nếu như cờ của process 2 không đặt (process2go = true) thì nó ra khỏi vòng lặp và vào khoảng tới hạn. Giả sử trong vòng lặp kiểm tra nói trên nó thấy cờ của process 2 đã đặt thì nó phải vào vòng lặp kiểm tra biến selectprocess- biến dùng để giải quyết tranh chấp khi cả hai process đồng thời muốn vào khoảng tới hạn. Nếu select process =1 thì nó ra khỏi vòng lặp của lệnh if và lặp lại kiểm tra cờ của process 2- cho đến khi process 2 bỏ cờ của mình (chúng ta sẽ thấy process 2 nhất định sẽ bỏ cờ của mình).

Nếu process 1 xác định thấy quyền ưu tiên thuộc về process 2 (biến select process =2) thì nó vào lệnh if và bỏ cờ của mình, sau đó lặp trong vòng chờ khi select process vẫn là 2. Với việc bỏ cờ của mình process 1 cho phép process 2 ra khỏi vòng kiểm tra và đi vào khoảng tới hạn.

Cùng với thời gian, process 2 ra khỏi khoảng tới hạn và thực hiện chỉ thị exit critical region bằng 2 lệnh đặt quyền ưu tiên cho process 1 (select process:=1) và bỏ cờ của mình (process2go := false). Khi đó process 1 có cơ hội ra khỏi vòng chờ và đi vào khoảng tới hạn nếu như process2go = false. Nếu process 2 ngay lập tức lại muốn vào khoảng tới hạn tức là nó lại đặt process2go := true thì process1 chưa thoát khỏi vòng lặp chờ ở ngoài (while process2go = true do), khi đó process 2 vào vòng chờ, vào lệnh kiểm tra if và vì selectprocess=1 - quyền ưu tiên thuộc về process1 nên process2 bỏ cờ của nó, do đó process 1 ra khỏi vòng lặp ngoài để vào khoảng tới hạn còn process 2 chờ đến lượt mình.

Còn một khả năng mà chúng ta cần xem xét. Khi process 1 ra khỏi vòng lặp ở trong, nó chưa kịp đặt cờ của nó thì bị mất quyền sử dụng BXL, đến lượt process 2 cũng muốn vào khoảng tới hạn; Nó đặt cờ của mình, kiểm tra thấy cờ của process 1 chưa dựng và lại đi vào khoảng tới hạn. Khi process 1 lại có BXL, nó đặt cờ của mình và bị tiếp tục chờ ở vòng lặp ngoài. Vì select process sẽ có giá trị 1 nên khi process 2 ra khỏi khoảng tới hạn process 2 sẽ không thể vào khoảng tới hạn một lần nữa và phải chờ ở vòng lặp trong, do đó process 1 có cơ hội vào khoảng tới hạn.

4.9 Loại trừ lẫn nhau cho N process

Giải pháp thực hiện bằng chương trình cho vấn đề Mutual Exclusion Primitive đối với N process lần đầu tiên được Dijkstra đề xuất. Sau đó Knuth hoàn thiện thêm phương pháp của Dijkstra, loại trừ được tình trạng chờ vô tận, nhưng vẫn còn nhược điểm là một số process vẫn có thể bị chờ lâu. Do đó nhiều nhà nghiên cứu tìm tòi những thuật toán cho phép rút ngắn thời gian trễ (chờ). Eisenberg và McGuite đã đề ra lời giải đảm bảo rằng process bất kỳ sẽ được vào khoảng tới hạn sau không quá N-1 lần thử. Lamport đã thiết kế thuật toán được áp dụng riêng cho các hệ cơ sở dữ liệu phân tán.

4.10 Thực hiện loại trừ lẫn nhau bằng phần cứng: lệnh test and set

Thuật toán Decker là giải pháp phần mềm cho vấn đề loại trừ lẫn nhau. Bây giờ chúng ta sẽ xem xét giải páp phần cứng. Điều quan trọng để đảm bảo giải quyết vấn đề là có một lệnh phần cứng: lệnh này đọc biến, ghi giá trị của biến vào vùng lưu trữ và đặt giá trị cụ thể cho biến đó. Lệnh này thường gọi là test and set. Tất cả các thao tác trên được gói gọn trong một lệnh và được thực hiện trọn vẹn không bị ngắt.

Lệnh test and set (a,b) đọc giá trị của biến logic b, copy giá trị vào biến a và sau đó đặt giá trị true cho b. Ví dụ sử dụng lệnh testandset để thực hiện Mutual Exclusion được thể hiện trong chương trình 4.8

Biến active kiểu boolean có giá trị true khi một trong các process nằm trong khoảng tới hạn và giá trị false trong trường hợp ngược lại. Process1 có được vào khoảng tới hạn hay không phụ thuộc vào giá trị biến local kiểu boolean disable1. Nó đặt disable1 := true, sau đó vào vòng lặp kiểm tra thực hiện lệnh testandset đối với biến toàn cục active. Nếu lúc đó process2 không nằm trong khoảng tới hạn, biến active có giá trị false. Lệnh test and set sẽ ghi giá trị đó vào biến disable1 và đặt giá trị active= true. Do đó process 1 ra khỏi vòng lặp chờ kiểm tra và vào khoảng tới hạn. Vì biến active có giá trị true nên process 2 không thể vào khoảng tới hạn.

Chương trình 4.8

Program TestAndSet

var

disable1, disable 2: boonlean;

active: boolean;

procedure process1

var

disable1: boonlean;

while true do begin

....

disable1 := true;

while disable1 = true do

testAndSet(disable1, active);

{critical region}

active := false;

....

end;

end;

procedure process2

var

disable2: boonlean;

while true do begin

....

disable2 := true;

while disable2 = true do

testAndSet(disable2, active);

{critical region}

active := false;

....

end;

end;

active := false;

parbegin

process1;

process2;

parend;

end.

Giả sử rằng process 2 đã nằm trong khoảng tới hạn, khi process 1 muốn vào khoảng tới hạn nó đặt biến disable1 := true và vào vòng kiểm tra. Vì giá trị của active là true (do process 2 đang trong khoảng tới hạn) nên lệnh test and set copy giá trị đó (true) vào biến disable1 và như vậy điều kiện vòng lặp vẫn đúng và process1 phải thực hiện vòng lặp kiểm tra. Khi process 2 ra khỏi khoảng tới hạn, nó đặt lại biến active := false, lúc đó lệnh testandset (trong vòng lặp kiểm tra của process 1) thấy biến active= false, copy giá trị này vào biến disable1 và đặt active:= true (làm cho proces 2 không thể tiếp tục vào khoảng tới hạn), và vì disable1 có giá trị false nên process 1 có thể đi vào khoảng tới hạn.

Nhưng phương pháp này không loại trừ được tình huống chờ vô tận dù xác suất xảy ra thấp, đặc biệt khi hệ thống có lớn hơn hai BXL. Khi một process ra khỏi khoảng tới hạn, đặt biến active= false, lệnh test and set của process khác có thể 'chiếm' biến active (đặt lại giá trị bằng true) trước khi process đầu kịp thực hiện xong thao tác.

4.11 Semaphore

Các khái niệm trên liên quan đến laọi trừ nhau, đã được Dijkstra tổng kết qua khái niệm semaphore. Semaphore là biến được bảo vệ, giá trị của nó chỉ có thể đọc, ghi bằng các lệnh đặc biệt P, V và lệnh khởi tạo. Semaphore nhị phân (binary semaphore) chỉ có thể nhận 2 giá trị: 0 và 1. Semaphore đếm (counting semaphore) chỉ có thể nhận giá trị tự nhiên.

Lệnh P trên semaphore S, ký hiệu P(S) thực hiện như sau:

if S > 0 then S := S - 1

else waiting for S

Lệnh V trên semaphore S, ký hiệu V(S) thực hiện như sau:

if (exist process waiting for S) then

allow one of them (waiting process) continue

else S:=S+1;

Chúng ta sẽ giả sử rằng hàng đợi các process đối với một semaphore S sẽ được phục vụ theo nguyên tắc FIFO.

Cũng giống như lệnh TetsAndSet, các lệnh P và V trên semaphore S là một đơn vị, không chia cắt. Đoạn chương trình laọi trừ nhau đối với semahore S của process sẽ được bao bởi các lệnh P(S) và V(S). Nếu đồng thời có nhiều process cùng muốn thực hiện lệnh P(S) thì chỉ có 1 process được phép, còn các proces khác sẽ phải chờ.

Semaphore và các lệnh trên S có thể được xây dựng-cài đặt (implement) bằng phần mềm cũng như bằng phần cứng. Nói chung chúng được cài đặt trong nhân của HĐH, là nơi thực hiện việc đổi trạng thái của process.

Chương trình 4.9 sau cho ta ví dụ đảm bảo loại trừ nhau bằng semaphore. Trong đó, lệnh P có vai trò như giả lệnh EnterExclusion còn lệnh V báo về sự kết thúc.

program Semaphore1

var active: semaphore

procedure process1;

while true do begin

P(active);

critical region;

V(active);

end;

end;

procedure process2;

while true do begin

P(active);

critical region;

V(active);

end;

end;

initilizeSemaphore(active,1);

parbegin

process1;

process2;

parend

end.

4.12 Đồng bộ tiến trình dùng semaphore

Khi process yêu cầu thực hiện I/O, nó tự block và chuyển sang trạng thái chờ sự kiện kết thúc thao tác I/O (blocked process). Process ở trạng thái blocked cần phải được kích hoạt bởi 1 process nào đó. Sự kích hoạt đó có thể được thực hiện ví dụ bằng hàm nào đó liên quan đến giao thức khoá/kích hoạt.

Chúng ta xem xét trường hợp tổng quát hơn, khi 1 process cần phải được thông báo về một sự kiện nào đó xảy ra. Chúng ta giả sử rằng có 1 process khác nhận biết được sự kiện đó. Ví dụ sau đây là ví dụ chúng ta có thể dùng semaphore để thực hiện đồng bộ giữa 2 process.

program block_activate

var event: semaphore;

procedure process1;

P(event);

end;

procedure process2;

V(event);

end;

initializeSemaphore(event,0)

parbegin

process1;

process2;

parend

end.

Trong chương trình này, process 1 thực hiện bình thường, sau khi thực hiện yêu cầu I/O thì thực hiện lệnh P(event), bởi vì ban đầu, event = 0 nên process 1 sẽ phải chờ event. Theo thời gian, khi sự kiện xảy ra, process2 nhận biết nó và thực hiện V(event), bởi vì lúc đó có process1 đang chờ event nên lệnh V rẽ nhánh true và cho phép process1 tiếp tục.

Cần để ý rằng chương trình này vẫn thực thi đúng nhiệm vụ của nó ngay cả khi sự kiện xảy ra trước khi process1 thực hiện lệnh P(event). Khi có sự kiện, process2 thực hiện V(event) theo đó event:=event+1=1 vì không có process nào chờ. Sau đó, khi process1 thực hiện đến lệnh P(event) thì vì event=1 nên nó rẽ nhánh đặt lại event:=event-1=0 và tiếp tục mà không chờ.

4.13 Cặp "Cung - cầu"

Trong chương trình hoạt động tuần tự, khi một thủ tục (procedure) gọi thủ tục thứ 2 và truyền thông tin cho nó, hai thủ tục này là thành phần của chương trình và không hoạt động song song. Nhưng khi 1 process truyền thông tin cho process khác, có thể xuất hiện vấn đề. Sự truyền thông tin đó có thể như là một ví dụ về loại trừ nhau.

program prog1

var enable,

Chúng ta xem xét hoạt động của cặp process. Giả sử 1 process (process cho) sinh thông tin được process thứ 2 (process nhận) sử dụng. Giả sử chúng tương tác với nhau thông qua biến số nguyên mang thông tin có tên buffer. Process cho tạo thông tin và lưu kết quả vào biến buffer, sau đó process nhận đọc thông tin từ biến buffer đó để có thông tin.

Các process có thể hoạt động với tốc độ như nhau hoặc khác nhau nhiều. Nếu mỗi khi process1 có kết quả. lưu vào buffer, process2 lập tức đọc thông tin và in ra, sau đó đến process1,.. thì đầu ra là dãy kết quả đúng như dãy do process1 tính được.

Bây giờ giả sử 2 process hoạt động không đồng bộ. Nếu process2 hoạt động nhanh hơn thì sẽ dẫn đến tình huống 1 kết quả tính toán (của process1) được in 2 hay nhiều lần. Còn nếu ngược lại process1 hoạt động nhanh hơn thì sẽ có những kết quả tính toán bị bỏ qua không được in ra.

Tất nhiên chúng ta muốn trong bất kỳ trường hợp nào, các process phải tương tác sao cho kết quả tính toán được in ra không thiều và không lặp, nghĩa là ta muốn chúng đồng bộ.

Chương trình trên là một ví dụ thực hiện đồng bộ 2 process bằng semaphore. Trong đó semaphore enable đảm bảo biến buffer chung không bị truy cập đồng thời, còn semaphore bufferready đảm bảo sự đồng bộ.

4.14 Counting Semaphore

Counting semaphore hữu ích khi có tài nguyên được lấy từ nhóm (pool) các tài nguyên cùng loại. Khi khởi tạo semaphore, giá trị của nó là chỉ số lượng tài nguyên của nhóm. Mỗi lệnh P sẽ giảm giá trị của semaphore đi 1, tương ứng với việc có 1 tài nguyên đã được lấy từ nhóm. Mỗi lệnh V sẽ tăng gia strị semaphare 1 tương ứng với việc process trả lại 1 tài nguyên cho nhóm, và tài nguyên đó có thể được cấp cho process khác. Trong trường hợp thực hiện lệnh P mà giá trị của semaphore là 0, nghĩa là không còn tài nguyên trống, thì process sẽ phải chờ đến khi nào giá trị semaphore khác 0 nghĩa là có lệnh V được thực hiện (ứng với sự kienẹ có tài nguyên giải phóng)

Chương 6: Deadlock - Khóa cứng

6.1 Mở đầu

Trong hệ thống đa chương trình, một process nằm trong trạng thái deadlock hay treo, nếu như nó chờ sự kiện (event) nào đó không bao giờ xảy ra. Tình huống treo hệ thống là tình huống có một hay nhiều process nằm trong trạng thái treo.

Trong các hệ thống đa chương trình một trong những chức năng quan trọng của HĐH là quản lý, phân chia tài nguyên. Khi tài nguyên được chia sẻ giữa các user, mỗi người có toàn quyền điều khiển, sử dụng tài nguyên đã được phân chia cho anh ta, do đó hoàn toàn có thể xảy ra deadlock và process của người dùng có thể chẳng bao giờ kết thúc.

Trong chương này chúng ta xem xét vấn đề deadlock và một số kết quả nghiên cứuvề vấn đề ngăn ngừa, phòng tránh và phát hiện tình trạng deadlock cũng như khôi phục sau đó. Chúng ta cũng xem xét vấn đề liên quan là chờ vô tận (indefinite postponement- hoãn không xác định) khi process chờ một sự kiện nào đó có thể chẳng bao giờ xảy ra do lý do chủ quan nào đó trong hệ thống điều khiển tài nguyên.

Các khả năng, giải pháp cân bằng giữa giá phải trả cho các phương tiện ngăn chặn deadlock với lợi ích nó mang lại cũng được xem xét. Trong nhiều trường hợp, giá phải trả cho việc loại trừ tình trạng deadlock quá cao. Còn trong các trường hợp khác (ví dụ các hệ thống điều khiển thời gian thực) thì giá đó là không tránh khỏi vì deadlock có thể gây ra những hậu quả không lường trước.

6.2 Ví dụ tình trạng deadlock

Có lẽ cách đơn giản nhất để tạo deadlock là chương trình mà Holt đưa ra bằng ngôn ngữ PL/1, chạy dưới OS 360:

Revenge: procedure options (main, task);

wait (event)

end revenge;

process gắn với chương trình này sẽ luôn chờ sự kiện event nhưng nó lại không xem xét dấu hiệu xuất hiện event. Hệ thống bắt buộc nhận thấy process đó bị treo và sau đó phải loại bỏ process để thoát khỏi tình trạng deadlock.

Deadlock do lỗi chương trình hay thuật toán thường khó phát hiện

6.2.1 Ví dụ trong thực tế

tắc nghẽn giao thông:

6.2.2 Ví dụ deadlock trong phân chia tài nguyên

Trong HĐH, deadlock phần lớn xuất hiện do hậu quả của sự tranh chấp sử dụng (chiếm) các tài nguyên mà tại mỗi thời điểm chỉ cấp cho một user, do đó đôi khi được gọi là tài nguyên sử dụng tuần tự. Trên hình 6.2 đưa ra một ví dụ đơn giản deadlock dạng này. Trên sơ đồ phân chia tài nguyên có hai process và hai tài nguyên. Mũi tên đi ra từ tài nguyên vào process chỉ ra rằng tài nguyên đó đang thuộc quyền sử dụng của process đó. Còn mũi tên đi ra từ process vào tài nguyên chỉ ra rằng process đang yêu cầu sử dụng tài nguyên nhưng chưa được cấp phát tài nguyên tương ứng.

Sơ đồ này biểu diễn hệ thống đang ở trong tình trạng deadlock: processA đang chiếm resource1 và để tiếp tục hoạt động nó cần resource2. Trong khi đó processB đang chiếm resource2 lại cần resource1 để tiếp tục.

Mỗi process đợi để process kia giải phóng resource mà nó đang cần, mặt khác mỗi process không giải phóng resource khi mà process kia chưa giải phóng tài nguyên của mình. Tình huống đợi vòng quanh này đưa hệ thống vào tình trạng deadlock.

6.2.3 Deadlock trong hệ thống dùng spooling

Hệ thống spooling thường xảy ra deadlock. Chế độ spooling (vào/ra với buffer) được áp dụng để nâng cao hiệu suất của hệ thống bằng cách phân cách chương trình khỏi các liên lạc trực tiếp với thiết bị ngoại vi tốc độ thấp như máy in, ... Nếu như chương trình đưa một dòng text ra máy in mà phải đợi đến khi in xong dòng đó mới tiếp tục in dòng tiếp theo thì chương trình hoạt động chậm đi nhiều do hạn chế tốc độ của máy in. Để tăng tốc độ thực hiện chương trình, đầu tiên các dòng dữ liệu được ghi ra các thiết bị có tốc độ cao hơn như đĩa cứng và được lưu tạm thời ở đó trước khi được đưa ra máy in. Trong một số hệ thống spooling, chương trình phải định dạng (format) toàn bộ thông tin ra, chỉ sau đó mới bắt đầu thực sự in. Do đó khi một vài process đưa dữ liệu vào spooling file để in, hệ thống có thể rơi vào tình trạng deadlock, nếu như buffer định trước bị đầy khi chưa hoàn tất công việc. Để khôi phục, hay thoát khỏi tình trạng đó có thể phải restart system- dẫn đến mất toàn bộ kết quả công việc đã tiến hành, hoặc phải loại bỏ một số chương trình để các chương trình còn lại có thể hoạt động tiếp tục.

Khi người điều hành bắt đầu công việc anh ta thiết lập kích thước cho spooling file. Một trong những cách làm giảm khả năng xuất hiện deadlock khi spooling là thiết lập kích thước ban đầu lớn hơn so với dự tính. Nhưng cách này không phải luôn thực hiện được (khả thi) khi bộ nhớ thiếu,... Giải pháp thông dụng hơn đối với process thiết lập ngưỡng để spooling không tiếp nhận thêm công việc từ các chương trình khác khi spooling file đã sử dụng ví dụ tới 75% không gian. Giải pháp này có thể dẫn tới giảm hiệu suất của hệ thống nhưng đó là giá phải trả để giảm xác suất xảy ra deadlock.

Các hệ thống ngày nay hoàn thiện hơn, nó có thể cho phép bắt đầu in trước khi kết tất cả dữ liệu được định dạng nhờ đó một phần hay toàn bộ spooling file được giải phóng (xoá) ngay trong quá trình thực hiện công việc. Trong nhiều hệ thống có khả năng cấp phát bộ đệm (buffer) động để khi spooling file sắp đầy thì nó được tăng kích thước.

Dù sao đi nữa ưu thế của spooling vẫn lớn hơn rất nhiều những vấn đề deadlock có thể nảy sinh.

6.3 Vấn đề chờ vô tận-hoãn không xác định (indefinite postponement)

Trong hệ thống, khi các process phải chờ ví dụ khi nó chờ được cấp phát tài nguyên hay lập lịch trình, có thể xuất hiện tình huống mà (quyền) được sử dụng BXL bị hoãn không xác định. Tình huống này gọi là hoãn vô thời hạn (không xác định) có thể dẫn tới tình huống không chấp nhận được cũng như tình trạng deadlock.

Tình trạng hoãn vô thời hạn có thể xảy ra do cách điều khiển tài nguyên của hệ thống. Khi tài nguyên được phân bố theo nguyên tắc ưu tiên thì có thể xảy ra trường hợp một process sẽ chờ được cấp tài nguyên lâu vô hạn, bởi vì luôn có các process khác với độ ưu tiên cao hơn.

Khi thiết kế HĐH cần xem xét các chiến lược điều khiển các process nằm trong trạng thái chờ. Trong nhiều hệ thống tình trạng hoãn vô hạn được ngăn chặn do độ ưu tiên của process tăng dần cùng với thời gian nó chờ được cấp tài nguyên. Do đó cuối cùng thì process đó có độ ưu tiên cao nhất và nó sẽ được phục vụ.

6.4 Khái niệm tài nguyên - resource

Một chức năng quan trọng của HĐH là quản lý và điều khiển các tài nguyên của hệ thống. Nó có trách nhiệm phân phối các tài nguyên thuộc các loại khác nhau của hệ thống. Chúng ta xem xét các tài nguyên được coi là preemtible (được xử dụng nhiều nhất) như là BXL hay bộ nhớ; Chương trình đang nằm trong bộ nhớ có thể bị đưa ra ngoài để cấp vùng nhớ đó cho các chương trình khác cần bộ nhớ, ví dụ như khi chương trình thực hiện yêu cầu vào/ra nói chung nó không sử dụng bộ nhớ trong suốt khoảng thời gian thực hiện thao tác vào/ra. Nói chung, trong hệ thống, tài nguyên được sử dụng nhiều nhất (năng động nhất) là BXL, BXL luôn phải phục vụ các process song song, chuyển từ process này sang process khác để tất cả process đều được tiếp tục với tốc độ chấp nhận được. Nếu một process không sử dụng hợp lý BXL ví dụ khi đang thực hiện thao tác I/O, quyền sử dụng BXL của process này cần tạn thời ngăn cấm, trao cho các process khác. Do đó, việc tổ chức phân chia tài nguyên động là chỉ tiêu rất quan trọng để đảm bảo hoạt động hiệu quả của các hệ thống đa chương trình.

Các dạng tài nguyên xác định là "không phân chia" với ý nghĩa là chúng không thể tuỳ ý lấy lại từ process mà chúng được cấp. Ví dụ như băng từ, thông thường được cấp cho một process trong khoảng thời gian dài. Thiết bị kiểu này không thể đơn giản lấy lại từ process đó để cấp cho process khác.

Có những loại tài nguyên khác cho phép chia sẻ giữa một vài process, còn có những loại chỉ do một process độc quyền sử dụng. Ví dụ ổ đĩa thường chứa các file thuộc nhiều process nhưng đôi khi do một process chiếm giữ. Bộ nhớ và BXL được sử dụng chia sẻ bởi nhiều process.

Dữ liệu và chương trình cũng là các tài nguyên và chúng cũng cần các cơ cấu điều khiển, cấp phát tương ứng. Ví dụ trong một hệ, nhiều user có thể cùng cần chạy một chương trình. Bởi vì nếu mỗi user có một bản copy của chương trình trong bộ nhớ thì không tiết kiệm, do đó có thể chỉ nạp một bản copy của chương trình vào bộ nhớ còn mỗi user sẽ có một vùng dữ liệu riêng.

Code của chương trình mà không được thay đổi trong thời gian chạy gọi là reentrant (hay có thể chạy nhiều lần đồng thời) còn code của chương trình có thể thay đổi trong thời gian chạy gọi là code sử dụng nối tiếp (serial reusable). Với reentrant code - có thể có một số process cùng làm việc còn với code nối tiếp chỉ một process làm việc với nó tại một thời điểm. Khi nói về một tài nguyên nào đó, chúng ta cần hình dung xem chúng có thể được sử dụng bởi nhiều process đồng thời hay bởi nhiều process nhưng chỉ một process tại mỗi thời điểm. Chính loại tài nguyên thứ hai thường gây ra deadlock.

6.5 Bốn điều kiện xuất hiện deadlock

Coffman, Elphick và Sheshani đã phát biểu 4 điều kiện xuất hiện deadlock:

Các process yêu cầu quyền độc quyền sử dụng tài nguyên sẽ cấp phát cho nó (điều kiện loại trừ nhau).

Process giữ cho mình các tài nguyên đã được cấp và đồng thời yêu cầu tài nguyên bổ sung (điều kiện chờ tài nguyên)

Tài nguyên không được lấy lại từ process khi các tài nguyên đó chưa được sử dụng để kết thúc công việc (điều kiện không phân chia)

Tồn tại vòng kín các process, trong đó mỗi process giữ tài nguyên mà process kế tiếp đang đòi hỏi (điều kiện chờ vòng).

6.6 Các hướng nghiên cứu cơ bản về vấn đề deadlock

Vấn đề deadlock là một trong các vấn đề được nghiên cứu nhiều trong lĩnh vực công nghệ thông tin, các thành tựu trong lĩnh vực đó cho phép đề ra các thuật toán giải quyết nhiều bài toán. Các nghiên cứu có thể chia ra làm 4 hướng chính sau:

Ngăn chặn deadlock

Tránh deadlock

Phát hiện deadlock

Khôi phục sau deadlock

Hướng thứ nhất có mục đích tìm những điều kiện để loại trừ khả năng xuất hiện tình trạng deadlock. Hướng này là giải pháp trực diện đối với vấn đề deadlock, nhưng nó thường dẫn tới việc sử dụng tài nguyên không hiệu quả. Nhưng dù sao các phương pháp ngăn chặn deadlock được áp dụng khá phổ biến.

Mục đích của các biện pháp tránh deadlock là ở chỗ cho phép những điều kiện ít nghiêm ngặt hơn so với các biện pháp ngăn chặn deadlock, và cũng đảm bảo sử dụng tài nguyên tốt hơn. Các biện pháp tránh deadlock không đòi hỏi loại bỏ hoàn toàn để không xảy ra tình trạng dealock trong hệ thống. Ngược lại nó chú ý các khả năng xuất hiện deadlock, trong trường hợp xác suất xuất hiện dealock tăng lên thì áp dụng các biện pháp tránh xảy ra deadlock.

Các phương pháp phát hiện deadlock áp dụng trong các hệ thống có khả năng xuất hiện deadlock do hậu quả của các thao tác vô ý hay cố ý. Mục đích của các biện pháp phát hiện là xác định sự tồn tại tình trạng deadlock trong hệ thống, xác định các process và tài nguyên nằm trong tình trạng deadlock. Sau đó có thể áp dụng các biện pháp thích hợp để khắc phục.

Các biện pháp khôi phục sau deadlock áp dụng khi loại bỏ tình trạng deadlock để hệ thống có thể tiếp tục hoạt động, còn các process rơi vào tình trạng deadlock có thể phải kết thúc và các tài nguyên của nó được giải phóng. Sau đó các process đó thường được nạp và bắt đầu từ đầu (các công việc đã thực hiện đến lúc xảy ra deadlock sẽ bị mất).

6.7 Ngăn chặn deadlock

Đến nay các nhà thiết kế khi giải quyết các vấn đề deadlock thường đi theo hướng loại trừ những tình huống deadlock hay xảy ra nhất. Chúng ta sẽ xem xét các phương pháp ngăn chặn deadlock và đánh giá hậu quả của nó đối với user cũng như với hệ thống đặc biệt là về mặt hiệu quả công việc và tính năng sử dụng.

Havender đã chỉ ra rằng khả năng xuất hiện deadlock không thể có ngay cả khi tồn tại một trong bốn điều kiện xuất hiện dealock. Havender đề ra các chiến lược sau:

Mỗi process phải yêu cầu tất cả các tài nguyên nó cần ngay một lần, và không thể bắt đầu cho đến khi chưa có đủ các tài nguyên đó.

Nếu process đang có các tài nguyên nào đso, bị từ chối cấp phát tài nguyên mới (bổ sung) thì nó phải giải phóng các tài nguyên ban đầu (đã có) và trong trường hợp cần thiết phải yêu cầu cấp lại cùng với các tài nguyên bổ sung.

Đưa vào các tài nguyên tuyến tính đối với tất cả process, tức là nếu process được cấp tài nguyên loại nào đó (phân loại theo thứ tự) thì sau đó nó chỉ có thể yêu cầu các tài nguyên loại có bậc lớn hơn.

Chúng ta thấy rằng chỉ có ba chiến lược (chứ không phải bốn)

Mỗi nguyên tắc có mục đích loại trừ (phá vỡ) một trong các điều kiện tồn tại của deadlock. Điều kiện đầu tiên (điều kiện loại trừ nhau), theo đó process có độc quyền điều khiển tài nguyên được cấp cho nó, chúng ta không muốn loại trừ bởi vì chúng ta cần cho phép khả năng làm việc với tài nguyên đơn.

6.7.1 Loại bỏ điều kiện "chờ tài nguyên bổ sung"

Nguyên tắc thứ nhất của Havender đòi hỏi process phải yêu cầu tất cả (toàn bộ) tài nguyên mà nó cần ngay từ đầu. Hệ thống phải cấp các tài nguyên này theo nguyên tắc "có tất cả hoặc không có gì". Nếu tập hợp các tài nguyên có đủ thì hệ thống có thể cấp tất cả để cho process có thể tiếp tục công việc. Nếu lúc đó không có đủ tài nguyên thì process phải chờ đến khi các tài nguyên có đủ (nhờ được các process khác giải phóng). Bởi vì process nằm trong trạng thái chờ không được giữ tài nguyên nào, do đó ngăn chặn được sự xuất hiện điều kiện "chờ tài nguyên bổ sung" và tình huống deadlock không thể xảy ra.

Kết quả đó được trả giá bởi việc sử dụng tài nguyên không hiệu quả. Ví dụ, chương trình vào lúc nào đó cần 10 thiết bị băng từ, bắt buộc phải yêu cầu và có được đủ cả 10 thiết bị trước khi có thể bắt đầu. Nếu như 10 thiết bị đó cần suốt trong thời gian hoạt động thì không có vấn đề gì về hiệu suất sử dụng. Nhưng nói chung thì không phải tất cả chúng đều được sử dụng trong cả quá trình tồn tại của process mà chúng chỉ cần trong những khoảng thời gian nào đó, như thế các thiết bị được sử dụng với hiệu suất rất thấp, không thể chấp nhận.

Một trong những cách để nâng cao hiệu suất là phân chia chương trình thành một vài giai đoạn tương đối độc lập với nhau. Do đó có thể thực hiện việc cấp phát tài nguyên cho từng giai đoạn chương trình thay vì cấp một lần cho cả chương trình. Điều này cho phép giảm việc lãng phí tài nguyên nhưng lại tăng chi phí khi thiết kế và cả khi thực hiện chương trình.

Chiến lược này làm tăng khả năng process phải chờ vô hạn (không xác định) bởi vì không phải tất cả tài nguyên cần thiết đều có vào lúc process cần. Như thế hệ thống phải thực hiện (đén khi kết thúc) số lượng khá lớn bài toán khác và giải phóng tài nguyên cấp cho chúng để bài toán đang chờ có thể hoạt động. Vào khoảng thời gian các tài nguyên cần có được thu thập thì chúng không thể cấp cho các task khác, tức là lúc đó chúng không hoạt động. Từ khía cạnh kinh tế thì các chi phí đó cần phải tính. Có nhiều ý kiến khác nhau về việc ai phải trả chi phí đó. Có người cho rằng vì khi đó các tài nguyên được thu thập cho người sử dụng nên người dùng phải trả tiền cả cho thời gian chúng dừng. Còn những người khác cho rằng điều đó không hợp lý vì lúc đó người dùng không thực sự sử dụng tài nguyên. Nếu người dùng muốn thực hiện chương trình vào giờ cao điểm thì anh ta sẽ phải trả nhiều hơn đáng kể so với trường hợp thực hiện vào thời gian khác.

6.7.2 Loại bỏ điều kiện "không phân bố lại"

Tiêu chuẩn thứ hai của Havender (xem xét độc lập) , ngăn chặn việc xuất hiện điều kiện "không phân bố lại". Giả sử rằng hệ thống cho phép các process yêu cầu thêm các tài nguyên bổ sung và vẫn giữ những tài nguyên đã được cấp. Nếu như hệ thống có đủ tài nguyên trống để phân phối thì không có tình trạng deadlock. Nhưng nếu yêu cầu không được giải quyết thì có thể có tình huống một process chiếm giữ tài nguyên mà process khác yêu cầu để tiếp tục hoạt động, còn process thứ hai đó lại chiếm giữ tài nguyên mà process đầu cần tức là xuất hiện deadlock.

Nguyên tắc Havender thứ hai đòi hỏi rằng nếu một process không được cấp phát tài nguyên bổ sung khi nó yêu cầu thì nó phải giải phóng tất cả tài nguyên nó đang chiếm giữ, và trong trường hợp cần thiết phải yêu cầu lại tất cả cùng với tài nguyên bổ sung.

Nguyên tắc này thật sự loại trừ được yếu tố "không phân bố lại" và có thể lấy được tài nguyên từ các process đang chiếm chúng trước khi các process hoàn thành.

Nguyên tắc này cũng có nhiều nhược điểm. Nếu như process trong quá trình làm việc sử dụng các tài nguyên mà sau đó giải phóng chúng thì nó có thể mất các kết quả làm việc đến lúc đó. Giá đó có vẻ quá lớn, tuy nhiên nó còn phụ thuộc vào tần số (xác suất) xảy ra. Nếu tình huống đó ít xảy ra thì có thể nói rằng tiêu chuẩn này không phải là quá đắt. Còn nếu như thường xuyên xảy ra thì giá của nó là quá đắt, đặc biệt với các process có mức ưu tiên cao hay khẩn cấp.

Một trong những nhược điểm lớn của biện pháp này là xác suất xảy ra 'chặn vô hạn' (indefinite posponement). Sự thực hiện process mà nhiều lần phải yêu cầu rồi giải phóng cùng một tài nguyên có thể bị dừng một thời hạn không xác định. Trong trường hợp đó hệ thống có thể phải loại process đó để các process khác có thể tiếp tục. Cũng không thể không tính khả năng khi process bị chặn vô hạn nhưng hệ thống không nhận ra, tình huống này làm lãng phí tài nguyên và giảm hiệu suất của cả hệ thống.

6.7.3 Loại trừ điều kiện "chờ vòng quanh"

Nguyên tắc thứ ba của Havender loại trừ sự xuất hiện tình trạng chờ vòng. Vì tất cả các tài nguyên được gán một số duy nhất và các process phải yêu cầu các tài nguyên với số tăng dần do đó không thể xuất hiện tình trạng 'chờ vòng quanh'. Nguyên tắc này được thực hiện trong nhiều HĐH nhưng nó cũng gây ra các khó khăn nhất định:

Vì các tài nguyên được yêu cầu (cấp phát) theo thứ tự tăng dần và các số gán cho tài nguyên được gán từ đầu do đó trong trường hợp đưa thêm vào hệ thống các tài nguyên loại mới có thể gây ra tình huống phải thiết kế lại chương trình và cả hệ thống.

Rõ ràng rằng việc gán số cho tài nguyên cần thể hiện thứ tự thông thường mà phần lớn các task sử dụng tài nguyên. Đối với các task thực hiện theo thứ tự đó thì các tài nguyên có thể được sử dụng có hiệu quả. Còn nếu như task lại yêu cầu tài nguyên theo thứ tự ngược lại thì nó sẽ chiếm giữ tài nguyên lâu hơn cần thiết (tính đến lúc tài nguyên thực sự được dùng) .

Bởi vì chức năng quan trọng của HĐH là cho phép người dùng sử dụng thuận tiện nhất. Người dùng phải có khả năng thiết kế chương trình với ít thứ không cần thiết nhất do sự hạn chế từ phía máy tính và HĐH. Nguyên tắc thứ ba của Havender ngăn chặn được tình trạng 'chờ vòng' nhưng lại ảnh hưởng xấu đến công việc của user trong quá trình làm việc (lập trình).

6.8 Ngăn chặn deadlock và thuật toán Banker

Ngay cả khi tồn tại các điều kiện xuất hiện deadlock thì vẫn có thể tránh tình trạng đó nếu như tài nguyên được cấp phát theo những qui tắc nhất định. Có lẽ thuật toán thông dụng nhất để tránh tình trạng deadlock là thuật toán banker do Dijstra đề xuất.

6.8.1 Thuật toán banker của Dijstra

Khi xem xét thuật toán banker chúng ta sẽ xem xét các tài nguyên chúng ta sẽ giới hạn xét các tài nguyên cùng một loại, nhưng thuật toán này có thể dễ dàng thay đổi để áp dụng cho các tài nguyên nhiều loại khác nhau.

Chúng ta xem trường hợp ví dụ như phân chia t thiết bị lưu trữ băng từ.

HĐH phải đảm bảo phân chia một số t thiết bị cho mốt số cố định u người sử dụng. Mỗi người dùng sẽ phải báo trước số thiết bị lớn nhất mà anh ta sẽ cần khi thực hiện bài toán. HĐH sẽ chấp nhận yêu cầu của người dùng nếu yêu cầu cao nhất đó không vượt quá số thiết bị t.

Người dùng có thể chiếm hay giải phóng từng thiết bị một. Có thể rằng anh ta sẽ phải chờ được cấp tài nguyên nhưng HĐH đảm bảo rằng sự chờ đợi đó không phải là vô hạn. Số thiết bị cấp cho người dùng tại một thời điểm không bao giờ vượt quá số thiết bị nhiều nhất anh ta cần đến. Nếu HĐH có đủ số thiết bị thoả mãn yêu cầu lớn nhất của người dùng, thì người sử dụng đảm bảo rằng các thiết bị đó sẽ được sử dụng và trả lại cho HĐH sau khoảng thời gian hữu hạn nào đó.

Trạng thái hiện thời của máy tính gọi là ổn định nếu HĐH có thể đảm bảo tất cả các chương trình ứng dụng hiện thời trong hệ thống có thể hoàn thành (kết thúc bình thường) sau một khoảng thời gian hữu hạn nào đó. Còn trong trường hợp ngược lại thì trạng thái là không ổn định.

Giả sử rằng có n người sử dụng

Giả sử l(i) là số thiết bị cấp cho người sử dụng thứ i. Ví dụ người dùng thứ 5 đang dùng 4 thiết bị thì l(5)=4.

Giả sử m(i) là số thiết bị lớn nhất mà người dùng thứ i có thể cần ví dụ người dùng thứ 5 cần nhiều nhất 6 thiết bị thì m(5)=6. Tại một thời điểm, c(i) là yêu cầu lớn nhất hiện thời của người dùng i- bằng hiệu giữa số thiết bị nhiều nhất có thể yêu cầu và số thiết bị hiện có, tức là c(i)=m(i)-l(i) ví dụ ở trên ta có c(5)= m(5)-l(5) = 6-4=2

Trong hệ thống với t thiết bị thì số thiết bị còn rỗi tại một thời điểm là a sẽ bằng t trừ tổng các thiết bị được cấp phát: a = t - l(i)

Thuật toán banker của Dijkstra yêu cầu rằng các thiết bị chỉ được cấp phát cho người dùng theo yêu cầu trong trường hợp sau khi cấp phát thì hệ thống vẫn ở trạng thái ổn định. Trạng thái ổn định là trạng thái mà với các tài nguyên đang có, tất cả ứng dụng của người dùng có khả năng kết thúc (bình thường) công việc của mình. Còn trạng thái không ổn định là trạng thái có thể dẫn tới deadlock.

6.8.2 Ví dụ về trạng thái ổn định

Giả sử hệ thống có 12 thiết bị, và chúng được phân chia giữa 3 người dùng với trạng thái status1 được biểu diễn trong bảng sau:

Trạng thái status1

Số thiết bị đang được cấp Số thiết bị lớn nhất có thể cần

Người dùng 1 1 4

Người dùng 2 4 6

Người dùng 3 5 8

Dự trữ còn lại 2

Trạng thái đó là ổn định vì cả 3 người dùng có khả năng kết thúc công việc.

6.8.3 Ví dụ về trạng thái không ổn định

Giả sử hệ thống cũng có 12 thiết bị, và chúng được phân chia giữa 3 người dùng với trạng thái status2 được biểu diễn trong bảng sau:

Trạng thái status2

Số thiết bị đang được cấp Số thiết bị lớn nhất có thể cần

Người dùng 1 8 10

Người dùng 2 2 5

Người dùng 3 1 3

Dự trữ còn lại 1

Trong trường hợp này 11 thiết bị trong trạng thái được cấp phát và chỉ còn 1 thiết bị dự trữ. Trạng thái này không ổn định vì bất cứ người dùng nào yêu cầu thêm một thiết bị và hệ thống đáp ứng thì chúng ta không thể đảm bảo các chương trình đều kết thúc bình thường.

Chúng ta cần chú ý rằng thuật ngữ 'trạng thái không ổn định' không có nghĩa là vào lúc đó hoặc thời điểm nào đó 'nhất định' sẽ xuất hiện tình trạng deadlock, mà nó chỉ nói rằng trong trường hợp xấu, hệ thống 'có thể' rơi vào tình trạng deadlock.

6.8.4 Ví dụ chuyển từ trạng thái ổn định sang không ổn định.

Nếu như trạng thái hiện thời của hệ thống là ổn định thì điều đó không có nghĩa là tất cả các trạng thái sau đó đều là ổn định. Cơ chế cấp phát cần phải phân tích các yêu cầu trước khi cấp phát tài nguyên.

Giả sử hệ thống đang ở trạng thái 3, rõ ràng trạng thái đó là ổn định. Người dùng thứ 3 yêu cầu tài nguyên bổ sung. Nếu như thoả mãn yêu cầu đó thì hệ thống chuyển sang trạng thái 4. Dễ thấy trạng thái 4 là trạng thái không ổn định.

Trạng thái 3

Số thiết bị đang được cấp Số thiết bị lớn nhất có thể cần

Người dùng 1 1 4

Người dùng 2 4 6

Người dùng 3 5 8

Dự trữ còn lại 2

Trạng thái 4

Số thiết bị đang được cấp Số thiết bị lớn nhất có thể cần

Người dùng 1 1 4

Người dùng 2 4 6

Người dùng 3 6 8

Dự trữ còn lại 1

Tất nhiên trạng thái 4 không nhất thiết dẫn tới tình trạng deadlock. Tuy nhiên hệ thống đã chuyển từ trạng thái 3 (ổn định) sang trạng thái 4 (không ổn định)

6.8.5 Phân phối tài nguyên theo thuật toán banker

Chúng ta sẽ xem xét sự phân phối tài nguyên theo Dijkstra được thực hiện thế nào. Các điều kiện 'loại trừ nhau', 'chờ tài nguyên bổ sung' và 'không phân chia lại' có thể xảy ra. Các process có thể được độc quyền sử dụng các tài nguyên cấp cho nó. Các process được quyền yêu cầu và chờ tài nguyên bổ sung trong khi vẫn giữ các tài nguyên đã được cấp, ngoài ra tài nguyên không bị lấy khỏi process. Người dùng không đặt ra cho hệ thống bài toán quá phức tạp khi tại mỗi thời điểm chỉ yêu cầu một tài nguyên. Hệ thống hoặc thoả mãn hoặc từ chối yêu cầu. Nếu yêu cầu bị từ chối thì user vẫn giữ các tài nguyên đã được cấp và chờ trong một khoảng thời gian (hữu hạn) nào đó đến khi được cấp.

Hệ thống chỉ thoả mãn các yêu cầu mà sau đó trạng thái của hệ thống vẫn ổn định. Còn các yêu cầu có thể dẫn hệ thống tới trạng thái không ổn định thì bị hoãn một khoảng thời gian nào đó và cuối cùng vẫn sẽ được thoả mãn. Bởi thế, hệ thống luôn ở trạng thái ổn định, do đó tất cả các yêu cầu sẽ được thoả mãn và tất cả user có thể kết thúc công việc.

6.8.6 Những nhược điểm của thuật toán banker

Thuật toán banker có nhiều ưu điểm bởi vì nó cho phép cấp phát tài nguyên, tránh tình trạng deadlock. Nó cho phép tiếp tục thực hiện các process mà trong trường hợp dùng các biện pháp ngăn chặn thì chúng đã bị dừng. Nhưng thuật toán banker cũng vẫn có những nhược điểm mà do đó các nhà thiết kế hệ thống có thể phải lựa chọn các cách khác nhau để giải quyết vấn đề deadlock.

1/ Thuật toán banker xuất phát từ giả thiết số tài nguyên là cố định. Nhưng bởi vì các tài nguyên không thể làm việc mãi (ví dụ dừng lại để bảo dưỡng) do đó chúng ta không thể cho rằng số lượng tài nguyên là cố định.

2/ Thuật toán đòi hỏi rằng số người dùng là không đổi. Yêu cầu đó cũng không thực tế, vì trong các hệ đa chương trình, số lượng người dùng luôn thay đổi

3/ Thuật toán đòi hỏi bộ phận phân phối tài nguyên phải đảm bảo thoả mãn tất cả các yêu cầu sau khoảng thời gian hữu hạn nào đó. Tuy nhiên trong thực tế người ta cần những con số cụ thể hơn nhiều.

4/ Cũng như thế, thuật toán đòi hỏi người dùng phải trả lại các tài nguyên được cấp, sau một khoảng thời gian nào đó- và trong thực tế cũng cần các chỉ số cụ thể.

5/ Thuật toán yêu cầu người dùng phải báo trước số lượng lớn nhất tài nguyên anh ta cần. Nhưng sự phân phối tài nguyên ngày càng phải linh động, và do đó càng khó đánh giá yêu cầu lớn nhất. Vì máy tính ngày càng thân thiện với người dùng nên sẽ ngày càng nhiều người dùng không có hình dung chính xác về số tài nguyên lớn nhất mà anh ta sẽ cần, thay vào đó khi nào cần tài nguyên người dùng mới yêu cầu.

6.9 Phát hiện deadlock

Phát hiện deadlock- là xác định sự kiện xuất hiện trạng thái deadlock, xác định các quá trình và tài nguyên nằm trong tình trạng deadlock. Các thuật toán xác định deadlock thường được áp dụng trong các hệ thống có xuất hiện ba điều kiện đầu tiên trong số các điều kiện làm xuất hiện deadlock. Và sau đó mới xác định xem có tồn tại trạng thái 'chờ vòng' hay không.

Tất nhiên sử dụng các thuật toán phát hiện deadlock cũng phải trả giá, đó là chi phí về thời gian máy. Và chúng ta lại gặp vấn đề phải xác định giải pháp trung hoà: các chi phí thực hiện thuật toán phát hiện deadlock có tiết kiệm hơn hẳn so với khi dùng các biện pháp cô lập, loại bỏ deadlock hay không.

6.9.1 Graph phân bố tài nguyên

Trong các thuật toán phát hiện deadlock, thường áp dụng cách biểu diễn phân bố tài nguyên dưới dạng đồ thị có hướng. Các hình vuông biểu diễn process, còn các hình tròn lớn biểu diễn các lớp tài nguyên. Các vòng tròn nhỏ biểu diễn số lượng tài nguyên của lớp đó.

Ví dụ trong vòng tròn lớn R1 có 3 vòng nhỏ tức là hệ thống có 3 tài nguyên thuộc lớp R1

Trên h.6.3 biểu diễn các quan hệ trên đồ thị giữa các process và tài nguyên. Trong hình 6.3(a) - process P1 đang yêu cầu tài nguyên lớp R1. Mũi tên từ P1 đến vòng tròn lớn có nghĩa rằng hiện thời yêu cầu của process đang được xem xét. Hình 6.3 (b) thể hiện rằng process P2 được cấp 1 tài nguyên lớp R2, ở đây mũi tên đi từ vòng tròn nhỏ nằm trong vòng tròn lớn R2 đến process P2.

Trên hình.6.3 (c) biểu diễn tình huống ở một ý nghĩa nào đó gần với tình trạng deadlock: process P3 yêu câu tài nguyên lớp R3 đang được cấp cho process P4

Hình 6.3(d) biểu diễn tình trạng deadlock: process P5 yêu cầu tài nguyên lớp R4, trong khi tất cả tài nguyên lớp đó được cấp cho process p6, và ngược lại process P6 yêu cầu tài nguyên lớp R5- đang được cấp cho P5- tình trạng chờ vòng này là tình trạng deadlock hay gặp.

Đồ thị phân bố và yêu cầu cấp phát tài nguyên luôn thay đổi do quá trình các process yêu cầu tài nguyên, nhận tài nguyên và sau đó trả lại cho HĐH.

6.9.2 Sử dụng đồ thị phân bố tài nguyên

Cơ chế phát hiện deadlock- xác định xem có xuất hiện tình trạng deadlock hay không. Một trong những phương pháp phát hiện là rút gọn đồ thị phân bố tài nguyên (reduction of a resource allocation graph), nó cho phép xác định các process có thể kết thúc và các process có mặt trong tình huống deadlock.

Nếu như yêu cầu tài nguyên của một process nào đó có thể thoả mãn thì chúng ta nói rằng graph có thể rút gọn đối với process đó. Sự rút gọn đó tương đương với sự biểu diễn graph dưới dạng mà nó có khi process kết thúc công việc và trả lại các tài nguyên cho hệ thống. Sự rút gọn graph đối với một process nào đó được thể hiện bằng việc ngắt bỏ các cung đi tới proces đó từ các tài nguyên (tức là tài nguyên đã được cấp cho process) và các cung từ process đến tài nguyên (tức là các yêu cầu cấp phát hiện thời của process). Nếu như graph có thể rút gọn thành tất cả process cô lập có nghĩa là không có tình trạng deadlock, còn nếu không thể làm được thì các process không rút gọn được là các process nằm trong trạng thái deadlock.

Trên hình 6.4 là dãy thao tác rút gọn graph, kết quả cho ta thấy đối với trường hợp này thì không xuất hiện trạng thái deadlock. Chúng ta cần để ý rằng thứ tự thực hiện thao tác là không quan trọng. Dù ta rút gọn theo thứ tự nào thì kết quả cuối cùng vẫn là một.

Hình 6.4

6.10 Khôi phục sau deadlock

Hệ thống nằm trong trạng thái deadlock cân thoát ra khỏi tình trnạg đó bằng cách loại bỏ các điều kiện tồn tại deadlock. Thông thường thì một số process sẽ mất một phần hay toàn bộ kết quả đã thực hiện được. Nhưng giá của nó nhỏ hơn nhiều khi hệ thống bị treo hoàn toàn. Mức độ phức tạp của việc khôi phục hệ thống phụ thuộc nhiều yếu tố:

Ngay từ đầu việc xác định tình trạng deadlock không phải luôn rõ ràng

Trong nhiều hệ thống không có các công cụ đủ hiệu quả để dừng process một thời hạn không xác định, đưa nó ra khỏi hệ thống và lại khởi động nó sau đó. Trong thực tế thì có một số process phải làm việc liên tục không cho phép dừng lại và khởi động.

Ngay cả khi hệ thống có các công cụ hữu hiệu để dừng/khởi động process thì việc sử dụng chúng cũng đòi hỏi chi phí đáng kể về thời gian máy,...

Khôi phục tình trạng deadlock ở quy mô nhỏ (có ít process nằm trong tình trạng đó) thường đòi hỏi ít công sức nhưng khi có nhiều process nằm trong tình trạng deadlock thì có thể đòi hỏi một chi phí lớn.

Trong các hệ thống hiện nay việc khôi phục thường được thực hiện bằng cách loại một số process để có thể sử dụng các tài nguyên của chúng. Kết quả của các process bị huỷ thường bị mất nhưng nhờ đó các process còn lại có thể tiếp tục, kết thúc công việc của mình. Thuật ngữ 'khôi phục' cũng không chính xác lắm, ý nghĩa của nó là khôi phục khả năng làm việc bình thường của hệ thống.

Việc lựa chọn process để loại ra khỏi hệ thống cần phải theo một chỉ tiêu nào đó, ví dụ mức độ ưu tiên của process. Nhưng cũng có một số khó khăn.

Process nằm trong tình trạng deadlock có thể không còn giá trị priority

Priority của proces có thể không đúng do nguyên nhân nào đó ví dụ priority của process có thể tăng lên theo thời gian nó phải chờ.

Có lẽ phương pháp khôi phục tốt nhất là cơ chế tạm dừng/khởi động process (suspend/activate). Cơ chế này cho phép chúng ta chuyển process vào trạng thái chờ, sau đó nó sẽ được khởi động, các kết quả làm việc vẫn giữ nguyên không bị mất.

Deadlock có thể dẫn tới những hậu quả lớn trong các hệ thống thời gian thực. Các hệ thống đó phải hoạt động liên tục do đó không cho phép xảy ra tình trạng deadlock. Nhưng không thể đảm bảo tuyệt đối là nó không xảy ra - đó vẫn là một vấn đề cần giải quyết.

Phần III

Chương 7: Bộ nhớ vật lý

7.1 Mở đầu

Việc tổ chức và điều khiển bộ nhớ vật lý là một trong những yếu tố quan trọng nhất xác định cách xây dựng HĐH. Để thực hiện các chương trình hay truy nhập dữ liệu, chúng cần được nạp vào bộ nhớ vật lý. Bộ nhớ ngoài (bộ nhớ thứ cấp như ổ đĩa cứng) thường có dung lượng rất lớn và giá rẻ dùng để chứa chương trình và dữ liệu.

7.2 Tổ chức bộ nhớ

Trước kia bộ nhớ vật lý là tài nguyên đắt nhất. Do đó nó cần được tổ chức tốt để có thể sử dụng với hiệu quả cao nhất. Tổ chức bộ nhớ là cách mà chúng ta hình dung và sử dụng bộ nhớ vật lý. Ví dụ như chúng ta sẽ nạp vào bộ nhớ một chương trình hay nhiều chương trình cùng một lúc? Nếu như trong bộ nhớ có một số chương trình thì mỗi chương trình sẽ được cấp vùng nhớ bằng nhau hay chia bộ nhớ thành các phần (section, part) với kích thước khác nhau. Chúng ta có cần đòi hỏi các chương trình ứng dụng được thiết kế để nạp vào phần bộ nhớ cố định hay cho phép nạp vào bất cứ vùng nào phù hợp. Chúng ta có cần mỗi chương trình nằm trong một vùng nhớ liên tục hay có thể chia chương trình thành các khối nằm trong các vùng nhớ bất kỳ.

7.3 Điều khiển bộ nhớ.

Không phụ thuộc vào cách tổ chức bộ nhớ, chúng ta cần giải quyết cần dùng các tiêu chuẩn nào để đạt được các thông số tối ưu. Các phương pháp điều khiển bộ nhớ xác định cách làm việc của bộ nhớ với tổ chức cụ thể nào đó trong các cách giải quyết khác nhau các vấn đề: chúng ta nạp chương trình vào chỗ nào, nêu như không còn đủ bộ nhớ trống thì chương trình nào đang nằm trong bộ nhớ sẽ phải đưa ra...

7.4 Phân lớp bộ nhớ

Vào những năm 50/60 bộ nhớ vật lý rất đắt. Do đó việc chọn lựa kích thước bộ nhớ vật lý cần phải tính toán trước. Khách hàng không muốn mua lớn hơn anh ta có thể, mặt khác anh ta phải mua một số ít nhất nào đó để đảm bảo hoạt động của HĐH và số lượng định trước các user. Vấn đề là xác định dung lượng bộ nhớ tối thiểu thoả mãn bài toán và đồng thời nằm trong khả năng tài chính cho phép.

Để có thể chạy chương trình hay truy nhập dữ liệu, chúng cần phải được nạp vào bộ nhớ vật lý. Các chương trình và dữ liệu chưa cần có thể lưu trong bộ nhớ ngoài, khi cần thiết sẽ được nạp vào bộ nhớ vật lý. Bộ nhớ ngoài (đĩa cứng,...) thường rẻ hơn và có dụng lượng lớn hơn nhưng thời gian truy cập bộ nhớ vật lý lại nhanh hơn nhiều. Ví dụ về tốc độ truy cập, bộ nhớ vật lý: 60ns, HDD: 9ms.

Hệ thống với các lớp bộ nhớ có đặc tình tần suất trao đổi chương trình, dữ liệu giữa các lớp khác nhau tương đối lớn. Sự trao đổi đó cũng làm hao hụt tài nguyên hệ thống ví dụ thời gian BXL,...

Vào những năm 60 xuất hiện thêm một lớp (ngoài bộ nhớ vật lý và bộ nhớ ngoài) nữa, đó là cache memory, cho phép làm tăng tốc độ và hiệu quả sử dụng bộ nhớ. Cache memory có tốc độ truy cập nhanh hơn nhiều (15ns) so với bộ nhớ vật lý. Nhưng nó cũng đắt hơn nhiều, do đó trong hệ thống thông thường dung lượng cache không lớn.

Cache memory làm tăng thêm một lớp trao đổi nhưng chi phí đó được bù lại bởi tốc độ truy cập. Và do đó tốc độ của cả hệ thống được nâng lên nhiều.

Hình vẽ

7.5 Các chiến lược điều khiển bộ nhớ

Để đảm bảo sử dụng tốt các tài nguyên giá trị, chúng cần được điều khiển một cách có hiệu quả. Các chiến lược điều khiển bộ nhớ theo hướng đảm bảo sử dụng tốt nhất bộ nhớ vật lý, và chia theo các hướng sau:

1/ Chiến lược lựa chọn

a- chiến lược lựa chọn theo yêu cầu (demand fetch)

b- chiến lược lựa chọn trước

2/ Chiến lược phân bố

3/ Chiến lược loại ra

Mục đích của chiến lược lựa chọn là xác định xem khi nào phải nạp block chương trình hay dữ liệu vào bộ nhớ vật lý. Trong nhiều năm người ta cho rằng cách tốt nhất là lựa chọn theo yêu cầu: theo đó block chương trình hay dữ liệu được nạp vào bộ nhớ khi chương trình đang hoạt động đòi hỏi đến. Bởi vì rằng nói chung khó mà nói trước được điều khiển sẽ được chuyển đến đâu (địa chỉ lệnh tiếp theo) và chi phí thêm gắn với việc dự đoán trước sẽ tăng đáng kể thời gian chờ. Còn ngày nay, nhiều nhà thiết kế tin rằng lựa chọn dự đoán trước hoàn toàn có thể đảm bảo tăng tốc độ của hệ thống.

Các chiến lược phân bố có mục đích xác định xem chương trình mới sẽ được nạp vào vị trí nào của bộ nhớ. Chúng ta sẽ xem xét một số chiến lược như 'first suitalbe' (chọn block đầu tiên phù hợp), 'most suitable' (chọn block phù hợp nhất) và 'least suitable' (block ít phù hợp nhất), theo kích thước các vùng trống.

Các chiến lược loại bỏ xác định xem block chương trình hoặc dữ liệu nào sẽ bị loại ra khỏi bộ nhớ để giải phóng chỗ cho việc nạp chương trình hay dữ liệu.

7.6 Phân bố bộ nhớ liên tục và không liên tục

Trong các máy tính đầu tiên bộ nhớ được phân bố liên tục- tức là mỗi chương trình phải nằm trong một vùng nhớ. Chỉ sau khi xuất hiện khái niệm đa chương trình với phân đoạn thay đổi (variable partition multi programming) thì việc phân bố bộ nhớ không liên tục mới chứng tỏ sự hiệu quả của mình.

Trong phân bố bộ nhớ không liên tục, chương trình được chia làm nhiều phân đoạn (block hay segment), và chúng có thể nằm tại các vùng nhớ khác nhau, không nhất thiết phải liền nhau. Về phía HĐH, việc đảm bảo phân bố bộ nhớ không liên tục là rất phức tạp, nhưng nó đem lại nhiều ưu thế: nếu bộ nhớ có nhiều vùng nhớ trống thay vì một vùng lớn thì HĐH vẫn có thể nạp và thực hiện chương trình mà trong trường hợp ngược lại sẽ phải chờ.

7.7 Phân bố bộ nhớ liên tục đối với một user

Trong các máy đầu tiên tại mỗi thời điểm chỉ có một user (một chương trình ứng dụng) và tất cả tài nguyên đều thuộc quyền của anh ta. Và tiền sử dụng máy được tính theo nguyên tắc đơn giản- bởi vì user toàn quyền sử dụng các tài nguyên do đó anh ta phải trả cho tất cả, không phụ thuộc việc chương trình của anh ta có sử dụng hết các tài nguyên hay không. Do đó cơ chế tính tiền thực hiện theo thời gian máy đã sử dụng. Trong các hệ làm việc trong chế độ phân chia thời gian thì việc tính toán sử dụng các thuật toán phức tạp hơn nhiều.

Đầu tiên mỗi user đều phải tự mình viết toàn bộ chương trình kể cả các hàm thực hiện vào/ra bằng ngôn ngữ máy. Sau đó thì phần lệnh thực hiện các thao tác vào/ra cơ bản được đưa vào IOCS- hệ thống điều khiển vào/ra, và người dùng không phải viết lại các hàm vào/ra mà chỉ phải gọi các hàm tương ứng của hệ thống. Điều đó làm đơn giản và tăng hiệu quả lập trình và có thể cho rằng đó là bắt đầu sự phát triển khái niệm về OS hiện đại. Tổ chức bộ nhớ trong trường hợp phân bố liên tục đối với một người dùng được biểu diễn bằng h.7.2

Hình 7.2

Thông thường thì kích thước chương trình phụ thuộc dung lượng bộ nhớ (hay không gian quản lý bởi HĐH), nếu kích thước chương trình nhỏ hơn kích thước bộ nhớ thì không có vấn đề nảy sinh, còn khi kích thước chương trình vượt quá thì sao? Nhờ cơ chế overlay cho phép chúng ta có thể viết các chương trình lớn hơn giới hạn trên. Khái niệm của nó được thể hiện trong hình 7.3. Nếu như module nào đó của chương trình không hoạt động trong cả quá trình thực hiện chương trình thì nó hoàn toàn có thể được lưu trong bộ nhớ ngoài, khi cần thiết mới được nạp vào bộ nhớ vật lý và sau khi kết thúc nó lại được ghi ra bộ nhớ ngoài, giải phóng bộ nhớ vật lý cho module tiếp theo.

Chế độ overlay cho phép lập trình viên thiết kế các chương trình lớn vượt qua hạn chế bộ nhớ. Nhưng việc thiết kế overlay module đòi hỏi nhiều công sức và trí tuệ.

Các chương trình với cấu trúc overlay phức tạp rất khó thay đổi. Ngày nay chúng ta không còn phải dùng chế độ overlay để vượt qua giới hạn về bộ nhớ do đã có các hệ thống với bộ nhớ ảo - virtual memory

Hình 7.3 Cấu trúc overlay

Bảo vệ bộ nhớ trong hệ thống đơn nhiệm

Trong hệ thống đơn nhiệm, user được cấp vùng nhớ liên tục và nói chung là có quyền điều khiển, truy nhập toàn bộ bộ nhớ vật lý. Trong trường hợp này bộ nhớ thường chia làm 3 vùng: vùng cho HĐH, vùng cho chương trình ứng dụng và vùng trống. Vấn đề bảo vệ bộ nhớ trong trường hợp này cũng tương đối đơn giản. Bảo vệ bộ nhớ trong trường hợp này là bảo vệ HĐH để chương trình ứng dụng không làm hỏng nó.

Nếu như chương trình hoạt động không đúng, điều đó có thể dẫn tới phá vỡ HĐH, nếu như HĐH bị hỏng đến mức chương trình khác ứng dụng không thể tiếp tục hoạt động thì người dùng ít nhất cũng nhận thấy, sửa lỗi và chạy lại chương trình. Trong trường hợp này thì sự cần thiết bảo vệ HĐH không phải là rõ ràng.

Nếu trong trường hợp khác, chương trình ứng dụng phá hỏng HĐH một cách 'tinh vi'. Ví dụ như nó 'vô tình' làm thay đổi một hàm vào/ra của hệ thống. Khi đó chương trình có thể vẫn hoạt động nhưng tất cả kết quả có thể bị mất. Còn có thể xảy ra trường hợp tồi tệ hơn là hệ thống đưa ra kết quả sai mà việc phát hiện ra không dễ dàng.

Do đó rõ ràng cần phải bảo vệ HĐH. Việc bảo vệ có thể thực hiện bằng thanh ghi biên nằm trong BXL (h.7.4)

Hình 7.4

Thanh ghi biên chứa địa chỉ thấp nhất của lệnh. Nếu như user cố gắng truy nhập vào vùng của HĐH thì lệnh đó bị cấm và sẽ đưa ra thông báo lỗi.

Tất nhiên, user cũng cần truy nhập đến HĐH, ví dụ như thực hiện các thao tác vào/ ra. Để phục vụ điều này user có thể dùng các lệnh đặc biệt, với chúng anh ta có thẻ yêu cầu dịch vụ nào đó của HĐH (ví dụ như ngắt SVC) Trong trường hợp này OS thực hiện dịch vụ được yêu cầu và sau đó trả lại điều khiển cho chương trình ứng dụng.

Với việc OS ngày càng phức tạp, cần phải có các cơ chế tốt hơn để bảo vệ OS đối với user cũng như giữa các user với nhau.

7.8 Đa chương trình với các đoạn cố định (fixed partition multiprogramming)

Đối với các hệ thống đơn nhiệm và ngay cả hệ thống xử lý gói (packeg processing) thì vẫn bị lãng phí một phần đáng kể tài nguyên. Trên h.7.5 ta thấy rằng chương trình chỉ thực sự sử dụng BXL khi mà nó không thực hiện thao tác vào/ra. Sau khi bắt đầu thao tác vào/ra chương trình không thể tiếp tục cho đến khi kết thúc thao tác. Tốc độ thực hiện thao tác vào/ra thường chậm hơn nhiều so với tốc độ của BXL. Như vậy BXL bị bỏ phí trong suốt thời gian chờ thực hiện tác vụ vào/ra, và phần này chiếm đáng kể thời gian chung.

Hình 7.5 Sử dụng BXL trong hệ thống đơn nhiệm

Các nhà thiết kế thấy rằng hoàn toàn có thể tăng hiệu quả sử dụng BXL. Họ đã thực hiện các hệ thống đa nhiệm, trong đó các user cùng 'cạnh tranh' để có được tài nguyên. Chương trình đang chờ kết thúc thao tác vào/ra sẽ phải nhường BXL cho chương trình đã sẵn sàng hoạt động (tất nhiên nếu có chương trình như thế). Do đó đảm bảo khả năng cùng thực hiện thao tác vào/ra và BXL- nâng cao hiệu quả sử dụng BXL và cả hệ thống.

Các ưu thế của multiprogramming chỉ có thể tận dụng hết khi trong bộ nhớ có nhiều chương trình. Nhờ đó khi một chương trình thưc hiện thao tác vào/ra thì BXL có thể chuyển sang phục vụ chương trình khác và thực hiện tính toán với thời gian trễ nhỏ nhất. Khi chương trình thứ hai giải phóng BXL thí đến chương trình thứ ba khác lại có thể sẵn sàng sử dụng nó.

Multiprogramming đòi hỏi dung lượng bộ nhớ lớn hơn so với trường hợp đơn nhiệm nhưng chi phí đó được bù lại bởi việc sử dụng hiệu quả các tài nguyên khác (BXL, thiết bị vào/ra)

7.8.1 Fixed partition multiprogramming (đa nhiệm với phân đoạn cố định) dịch và nạp theo chương trình theo địa chỉ tuyệt đối

Trong các hệ đa nhiệm đầu tiên, bộ nhớ được chia thành các phần (phân đoạn) với kích thước cố định. Trong mỗi đoạn chỉ có thể nạp một chương trình. Còn BXL nhanh chóng chuyển từ chương trình này sang chương trình khác, do đó tạo ra hiệu quả là tất cả chương trình dường như được thực hiện đồng thời.

Việc biên dịch chương trình được thực hiện bởi assembler và compiler với địa chỉ tuyệt đối bị giới hạn bởi việc chương trình chỉ có thể chạy trong một phân đoạn cụ thể (h.7.6)

Hình 7.6

Nếu như chương trình đã sẵn sàng nhưng phân đoạn của nó đã có chương trình khác thì nó phải đợi dù rằng các phân đoạn khác có thể trống (h.7.7). Điều này dẫn tới sự lãng phí bộ nhớ nhưng việc thiết kế OS lại tương đối đơn giản.

Trên hình 7.7 thể hiện tình huống xấu nhất của phương pháp phân bố bộ nhớ liên tục với phân đoạn cố định và chương trình được dịch và nạp vào địa chỉ tuyệt đối (phân đoạn cố định). Cả hai phân đoạn một và hai đều bỏ phí còn hàng chờ của phân đoạn ba quá nhiều trong khi chúng đã có thể được nạp vào phân đoạn một và hai.

Hình 7.7

7.8.2 Đa nhiệm với phân đoạn cố định: dịch và nạp chương trình các module tự do.

Các chương trình dịch, assembler và loader tự do được sử dụng để dịch và nạp các chương trình có thể thực hiện tại bất cứ phân đoạn trống nào đủ lớn (hình 7.8). Phương pháp này khắc phục được một số nhược điểm về sử dụng bộ nhớ trong trường hợp trước (đa nhiệm với phân đoạn cố định, dịch và nạp chương trình theo địa chỉ tuyệt đối). Nhưng để đạt được điều đó, việc thiết kế lại phức tạp hơn nhiều.

Hình 7.8

7.8.3 Bảo vệ bộ nhớ trong các hệ đa nhiệm

Trong các hệ thống đa nhiệm với phân bố bộ nhớ liên tục (contiguous memory allocation), thường người ta sử dụng các thanh ghi biên để bảo vệ bộ nhớ. Hai thanh ghi chỉ ra cận dưới và cận trên của phân đoạn, hoặc một cận và kích thước của phân đoạn; chương trình có yêu cầu truy nhập đến các dịch vụ của OS phải dùng ngắt SVC để yêu cầu.

Hình 7.9

7.8.4 Vấn đề chia nhỏ bộ nhớ (fragmentation) trong đa chương trình với phân đoạn cố định

Fragmentation xảy ra trong bất kỳ hệ thống nào không phụ thuộc vào tổ chức bộ nhớ. Trong các hệ đa nhiệm với các phân đoạn cố định, fragmentation xảy ra do các chương trình ứng dụng không chiếm hết toàn bộ phân đoạn của nó hoặc là do các phân đoạn quá nhỏ để có thể nạp các chương trình đang chờ vào đó.

7.9 Đa nhiệm với các phân đoạn thay đổi

Khi xem xét các vấn đề của đa nhiệm với phân đoạn cố định, các kỹ sư thiết kế OS thấy rằng tốt hơn là cho phép các chương trình chỉ chiếm bộ nhớ kích thước vừa đủ kích thước nó cần. Không chia bộ nhớ thành các đoạn cố định mà có kích thước thay đổi theo chương trình ứng dụng. Phương pháp đó gọi là đa nhiệm với các phân đoạn thay đổi. Sự phân bố bộ nhớ ban đầu được thể hiện trong h.7.10

Chúng ta chỉ xem xét phương pháp phân chia bộ nhớ liên tục tức là mỗi chương trình nạp vào vùng nhớ liên tục. Trong phương pháp đa nhiệm với các phân đoạn thay đổi chúng ta không đề ra bất cứ giả sử gì về chương trình (trừ khi kích thước của chúng không vượt quá kích thước bộ nhớ). Các chương trình khi được nạp (thực hiện) sẽ được cấp vùng nhớ chúng cần. Mỗi phân đoạn có kích thước đúng bằng kích thước chương trình nằm trong đó.

Hình 7.10

Mỗi sơ đồ tổ chức bộ nhớ đều có sự lãng phí nhất định. Trong trường hợp đa nhiệm với các phân đoạn thay đổi, sự lãng phí này xuất hiện khi các chương trình kết thúc và trong bộ nhớ xuất hiện các vùng trống (hole) như h.7.11. Các vùng trống này có thể sử dụng để nạp các chương trình khác nhưng dù sao vẫn sẽ còn các vùng trống vì không phải các chương trình đều có kích thước đúng bằng vùng trống. Như vậy đa nhiệm với các phân đoạn thay đổi vẫn không tránh khỏi lãng phí bộ nhớ.

Hình 7.11

7.9.1 Hợp nhất các vùng trống liền nhau

Để khắc phục tình trạng bộ nhớ bị chia nhỏ chúng ta có thể dồn các vùng nhớ trống kể nhau.

Trong đa nhiệm với các phân đoạn thay đổi, khi một chương trình kết thúc chúng ta có thể kiểm tra xem vùng được giải phóng có nằm liền kề với vùng trống khác không? Nếu tồn tại thì chúng ta có thể hoặc đưa thêm vào danh sách các phân đoạn trống thêm một bản ghi nữa hoặc nối liền với vùng trống liền kề thành một vùng trống. Quá trình hợp nhất (nối liền) các vùng trống kề nhau biểu diễn trên hình 7.12. Nhờ sự hợp nhất này mà chúng ta tạo được các vùng nhớ liên tục với kích thước lớn nhất có thể.

Hình 7.12

7.9.2 Dồn bộ nhớ

Như chúng ta thấy sau khi thực hiện hợp nhất các vùng trống (holes) liền kề nhau thì nhìn tổng thể thì trong bộ nhớ vẫn tồn tại các vùng trống - cho dù ít hơn và kích thước lớn hơn. Đôi khi chương trình cần thực hiện tiếp theo lại khó lớn đến mức không có vùng trống nào đủ lớn để nạp cho dù tổng cộng kích thước các vùng trống vẫn lớn hơn cần thiết.

Vấn đề này được khắc phục nhờ phương pháp gọi là dồn bộ nhớ (h.7.13) và bản chất là chuyển (dồn) tất cả các phân đoạn đang có chương trình về một phía bộ nhớ. Nhờ đó thay vì có nhiều phân đoạn trống (vùng trống) vụn vặt chúng ta có được một vùng trống lớn duy nhất trong bộ nhớ. Khi đó chương trình tiếp theo có xác suất lớn sẽ có đủ bộ nhớ cần thiết để chạy. Đôi khi phương pháp 'dồn bộ nhớ' còn gọi là 'dọn rác'.

Tuy có nhiều ích lợi nhưng phương pháp dồn bộ nhớ vẫn có những nhược điểm nhất định:

Nó cũng làm hao phí tài nguyên hệ thống có thể được sử dụng vào mục đích khác tốt hơn.

Vào thời gian dồn bộ nhớ, hệ thống phải dừng tất cả các công việc khác. Kết quả dần tới thời gian không thể dự đoán trước trong việc phản ứng lại các sự kiện (trả lời user trong chế độ dialog chẳng hạn) và điều đó có thể không chấp nhận được trong các hệ thống thời gian thực.

Dồn bộ nhớ dịch chuyển các task trong bộ nhớ. Điều đó có nghĩa là thông tin về sự phân bố chương trình phải được lưu lại ở dạng nào đó.

Trong TH các bài toán thực hiện liên tục thì tần số thực hiện thao tác dồn bộ nhớ có thể trở nên thường xuyên và hao phí thực hiện nó có thể vượt quá lợi ích nó mang lại.

Hình 7.13

7.9.3 Các chiến lược phân bố thông tin trong bộ nhớ.

Các chiến lược phân bố bộ nhớ được áp dụng để xác định chương trình và dữ liệu sẽ được tiếp tục nạp vào vùng nào của bộ nhớ. Chúng ta thường gặp 3 chiến lược được biểu diễn trên h.14

1. Chiến lược 'first suitable': chương trình sẽ được nạp vào vùng trống gặp đầu tiên (trong danh sách các vùng trống) có kích thước đủ lớn. Chiến lược này có vẻ trực giác và thực tế vì nó cho phép tìm lời giải nhanh nhất.

2. Chiến lược 'most suitable': Chương trình được nạp vào vùng trống 'vừa nhất' do đó không gian lãng phí là ít nhất. Với nhiều người thì chiến lược này trực giác có vẻ là đúng nhất.

3. Chiến lược 'least suitable': đầu tiên thì chiến lược này có vẻ lạ lùng, nhưng xem xét kỹ thì nó cũng có các ưu điểm nhất định. Với chiến lược này chương trình nạp vào vùng trống lớn nhất. Ưu điểm là sau khi đã nạp chương trình, vẫn còn đủ không gian trống tương đối lớn đẻ có thể nạp thêm chương trình mới khá lớn.

Hình 7.14

7.10 Đa nhiệm với swapping

Trong các hệ đa nhiệm đã xem xét ở trên thì chúng ta đều giả sử rằng chương trình ứng dụng luôn nằm trong bộ nhớ đến khi nó kết thúc. Còn có cơ chế khác gọi là swapping mà không cần điều kiện đó.

Trong một số hệ thống dùng swapping (h.7.15) thì mỗi thời điểm trên cả bộ nhớ chỉ có một chương trình ứng dụng. Chương trình đó thực hiện đến khi có thể sau đó nó giải phóng cả BXL và bộ nhớ để cho chương trình tiếp theo. Như thế, toàn bộ bộ nhớ được giành cho một chương trình trong khoảng thời gian ngắn, và sẽ bị đưa ra khỏi bộ nhớ, chương trình tiếp theo được nạp vào bộ nhớ. Bình thường thì một chương trình trong quá trình chạy từ đầu đến lúc kết thúc sẽ bị swap nhiều lần.

Trong các hệ thống phân chia thời gian có sử dụng swapping, khi số chương trình khá ít thì hệ thống có thể đảm bảo thời gian trả lời chấp nhận được, còn khi số chương trình nhiều thì các nhà thiết kế hiểu rằng cần có các phương pháp và công cụ hiệu quả hơn. Trên cơ sở hệ thống với swapping đầu những năm 60, người ta đã xây dựng nhiều hệ thống với sự tổ chức bộ nhớ theo trang (page) và ngày nay trở nên thông dụng.

Cũng đã có xây dựng các hệ thống phức tạp hơn với swapping, trong đó cho phép phân bố trong bộ nhớ nhiều chương trình. Trong các hệ thống đó, chương trình bị đưa ra khỏi bộ nhớ chỉ khi vùng bộ nhớ của nó cần thiết để nạp chương trình khác. Trong TH dung lượng bộ nhớ khá lớn thì các hệ thống đó hoạt động tốt hơn đáng kể do giảm được thời gian thực hiện swapping.

Hình 7.15

Hệ thống đa nhiệm với swapping, tại mỗi thời điểm chỉ có một chương trình trong bộ nhớ. Chương trình đó tiếp tục đến khi có một trong các sự kiện sau xảy ra:

Xuất hiện tín hiệu timer

Nó kết thúc

Vùng swapping của chương trình đó sẽ được copy vào bộ nhớ ngoài, còn ảnh bộ nhớ của chương trình tiếp theo sẽ được nạp vào vùng swapping. Chương trình thứ hai tiếp tục được thực hiện, quá trình cứ thế tiếp tục.

Chương 8: Tổ chức bộ nhớ ảo

8.1 Mở đầu

Thuật ngữ virtual memory thường gắn liền với khả năng đánh địa chỉ cho không gian nhớ lớn hơn nhiều dung lượng bộ nhớ vật lý. Virtual memory xuất hiện (ứng dụng) lần đầu vào năm 1960 tại trường đại học Manchester và sau đó nhanh chóng được phổ biến.

Có hai phương pháp được chấp nhận một cách tự nhiên khi thực hiện (tổ chức) bộ nhớ ảo: đó là tổ chức theo trang (page) và theo phân đoạn (segment). Trong một số hệ thống, ứng dụng một trong hai phương pháp đó còn trong một số khác thì áp dụng tổ hợp cả hai phương pháp.

Tất cả các cơ chế bộ nhớ ảo đều đặc trưng bởi tính chất rằng địa chỉ được tính bởi chương trình, không nhất thiết phải trùng với địa chỉ bộ nhớ (vật lý). Trong thực tế địa chỉ ảo thể hiện không gian lớn hơn nhiều so với thực tế bộ nhớ vật lý.

8.2 Quá trình phát triển các dạng tổ chức bộ nhớ

H.8.1 biểu diễn quá trình phát triển từ các hệ thống bộ nhớ thực đơn nhiệm (1 user) đến các hệ thống bộ nhớ ảo sử dụng tổ hợp cả hai phương pháp page và segment. Vì tổ chức bộ nhớ ảo phức tạp hơn nhiều nên có hai chương: C8: tổ chức bộ nhớ ảo và C9: điều khiển bộ nhớ ảo

Hình 8.1

8.3 Bộ nhớ ảo: các khái niệm cơ bản

Cốt lõi các khái niệm về bộ nhớ ảo là ở chỗ địa chỉ mà process có thể truy nhập gọi là không gian địa chỉ ảo V của process đó, còn vùng địa chỉ thực tồn tại trong bộ nhớ gọi là không gian địa chỉ thực R.

Dù rằng process làm việc với địa chỉ ảo thì thật sự chúng phải làm việc với bộ nhớ. Do đó vào thời gian thực hiện process, các địa chỉ ảo cần phải biến đổi thành địa chỉ thực, ngoài ra việc xử lý phải nhanh chóng vì nếu không thì hiệu quả của máy tính có thể giảm tới mức không chấp nhận được và lợi ích của tổ chức bộ nhớ ảo không thể ứng dụng được.

Hình vẽ: ánh xạ các ô nhớ từ bộ nhớ vật lý sang bộ nhớ ảo

Để xác định ánh xạ giữa địa chỉ thực và ảo, người ta đã thiết kế các phương pháp khác nhau. Cơ chế biến đổi địa chỉ động (DAT-dynamic address translation) đảm bảo sự biến đổi địa chỉ ảo sang địa chỉ ảo vào thời gian thực hiện process. Tất cả các hệ thống đó đều có tính chất chung: đó là các địa chỉ ảo liền nhau chưa chắc đã tương ứng với các địa chỉ thực liền nhau (h.8.3). Như thế user không cần phải quan tâm đến việc nạp chương trình hay dữ liệu của mình trong bộ nhớ (vật lý). Anh ta có được khả năng viết chương trình một cách tự nhiên hơn, chỉ phải quan tâm đến các vấn đề thiết kế chương trình, thuật toán mà không cần để ý đến chi tiết cụ thể của thíêt bị. Khi đó máy tính (có thể) được coi như là một cài gì đó trừu tượng hơn- một công cụ logic nào đó để chạy chương trình chứ không phải như một cái máy vật lý với các chi tiết cần để ý, làm khó khăn cho quá trình thiết kế chương trình.

Hình 8.3

8.4 Tổ chức bộ nhớ nhiều lớp

Nếu như chúng ta đề ra rằng không gian địa chỉ ảo của user sẽ lớn hơn không gian địa chỉ thực, và nếu chúng ta định hướng rằng hệ thống sẽ làm việc tốt trong chế độ đa nhiệm và tài nguyên bộ nhớ được chia sẻ (dùng chung), thì chúng ta cần có môi trường, công cụ lưu trữ chương trình, dữ liệu trong bộ nhớ thứ cấp. Thường thì người ta sử dụng mô hình bộ nhớ hai cấp (h.8.4). Lớp thứ nhất- bộ nhớ vật lý, tại đó cần nạp các chương trình đựơc thực hiện và các dữ liệu cần truy cập. Lớp thứ hai- bộ nhớ ngoài có dung lượng lớn để lưu trữ các chương trình, dữ liệu lúc đó chưa cần nạp.

Để chạy chương trình, code và dữ liệu của nó cần được đưa vào bộ nhớ

Hình 8.4

Bởi vì bộ nhớ thực hiện được chia sẻ giữa nhiều chương trình và mỗi chương trình (process) có thể có không gian địa chỉ ảo lớn hơn không gian địa chỉ thực do đó vào thời gian thực hiện, chỉ có một phần mã (code) và dữ liệu của mỗi process nằm trong bộ nhớ thực. Trên h.8.5 thể hiện cấu trúc bộ nhớ hai lớp, trong bộ nhớ thực lưu chỉ một phần bộ nhớ ảo của các chương trình.

Hình 8.5

8.5 Blocking mapping: ánh xạ theo khối

Cơ chế biến đổi địa chỉ động (DAT) phải sử dụng các bảng ánh xạ - chỉ rằng các ô nhớ ảo nào tại thời điểm hiện thời nằm trong bộ nhớ và ở ô nhớ thực nào. Nếu như ánh xạ được thực hiện theo từng byte hay word thì rõ ràng thông tin về ánh xạ còn lớn hơn bản thân bộ nhớ thực. Do đó để có thể áp dụng bộ nhớ ảo, cần có phương pháp cho phép giảm kích thước của bảng ánh xạ.

Vì ánh xạ từng ô nhớ là không thể chấp nhận, chúng ta phải gộp theo các khối - block, và hệ thống theo dõi xem các block của bộ nhớ ảo nằm đâu trong bộ nhớ. Kích thước block càng lớn thì thông tin về ánh xạ càng nhỏ, nhưng các block lớn lại cần nhiều thời gian nạp hơn và ngoài ra với xác suất lớn còn hạn chế số process có thể chia sẻ chung bộ nhớ vật lý.

Khi thiết kế cơ chế bộ nhớ ảo xuất hiện câu hỏi là các block có kích thước như nhau hay khác nhau. Nếu các block có kích thước như nhau thì chúng (block) được gọi là các trang (page), còn tổ chức bộ nhớ ảo tương ứng gọi là tổ chức theo trang. Nếu các block có thể có kích thước khác nhau thì chúng được gọi là các đoạn (segment), tổ chức bộ nhớ ảo là tổ chức theo đoạn. Trong một số hệ thống cả hai cách được tổ hợp tức là các segment được tạo thành từ các page có kích thước như nhau.

Các địa chỉ trong các hệ thống ánh xạ theo khối là các địa chỉ gồm hai thành phần (hai chiều). Để truy nhập đến một dữ liệu cụ thể, program chỉ ra block và offset của dữ liệu trong block của dữ liệu trong block đó (h.8.6)

Địa chỉ ảo V được chỉ ra với cặp số v=(b,d) trong đó b- số block (số thứ tự) còn d- offset (độ lệch) tương đối so với đầu block.

Sự biến đổi từ địa chỉ ảo v=(b,d) thành địa chỉ thực r được thực hiện như trên hình 8.7. Mỗi process có bảng ánh xạ block của mình (nằm trong bộ nhớ thực). Địa chỉ thực a của bảng này được nạp vào thanh ghi riêng của BXL gọi là thanh ghi địa chỉ (đầu) của bảng ánh xạ (block table origin register). Mỗi dòng của bảng ánh xạ chứa ánh xạ của một block của process, ngoài ra các dòng được sắp xếp theo thứ tự số block, từ block 0, block 1. Số block b được cộng với địa chỉ cơ sở của bảng ánh xạ a, ta được địa chỉ thực của dòng chứa ánh xạ của block b. Dòng này chứa địa chỉ thực b' của block b. Sau đó cộng thêm vào địa chỉ b' này với offset d ta được địa chỉ thực cần tìm r=b'+d. Tất cả các phương pháp block mapping dùng trong các hệ thống tổ chức theo trang, segment hay tổ hợp được thể hiện trên h.8.7

Hình 8.7

Cần phải để ý rằng block mapping được thực hiện động (dynamic) ngay trong thời gian thực hiện process. Nếu cơ chế biến đổi địa chỉ DAT không đủ hiệu quả, thì chi phí của nó có thể làm giảm hiệu suất của hệ thống tới mức vượt quá ưu thế mà bộ nhớ ảo mang lại.

8.6 Tổ chức theo trang: các khái niệm cơ bản

Chúng ta xem xét ánh xạ theo khối với kích thước cố định tức là tổ chức bộ nhớ theo trang. Trong phần này chúng ta chỉ xem xét tổ chức theo trang thuần tuý.

Địa chỉ ảo trong hệ thống theo trang được thể hiện bằng cặp v=(p,d) trong đó p- số thứ tự trang trong bộ nhớ ảo còn d-offset trong trang p (h.8.8)

Hình 8.8

Process có thể được thực hiện tiếp nếu trang hiện thời cần đến của nó nằm trong bộ nhớ thực. Các trang được ghi từ bộ nhớ ngoài vào bộ nhớ thực, theo các block gọi là page frame và có kích thước đúng bằng kích thước trang. Các page frame bắt đầu từ các địa chỉ (trong bộ nhớ thực) là bội số của kích thước trang (h.8.9). Các trang có thể được nạp vào bất kỳ page frame trống nào.

Hình 8.9

Biến đổi địa chỉ động trong hệ thống tổ chức theo trang, thực hiện theo cách sau: Process truy nhập đến địa chỉ ảo v=(p,d). Cơ chế ánh xạ trang thể hiện trên h.8.10, đầu tiên tìm số trang p trong bảng ánh xạ trang và xác định được page frame p' tương ứng với trang p. Địa chỉ thực được tính bằng tổng của p' và d.

Hình 8.10

Chúng ta sẽ xem xét quá trình này kỹ hơn. Trong thực tế, thường thì không phải tất cả các page của process đều nằm trong bộ nhớ, do đó bảng ánh xạ phải chỉ ra là trang cần truy nhập có nằm trong bộ nhớ không và nằm ở đâu, còn nếu không thì nó nằm đâu trong bộ nhớ ngoài. Trên h.8.11 biểu diễn một dòng dữ liệu trong bảng ánh xạ trang. Bit flag r chỉ ra sự hiện diện của trang trong bộ nhớ: nếu r=1 tức là trang nằm trong bộ nhớ thực, còn nếu r=0 thì trang đó hiện không có trong bộ nhớ thực. Nếu như trang đó không có trong bộ nhớ thì s là địa chỉ (vị trí) của trang trong bộ nhớ ngoài, còn nếu nó nằm trong bộ nhớ thì p' là số page frame. Chú ý rằng p' không phải là địa chỉ thực thật sự. Địa chỉ thực a - của page frame p' được tính bằng a=(p)*(p') (số trang p có giá trị từ 0.1.2.3...)

Hình 8.11

Để tiết kiệm bộ nhớ (giảm kích thước của bảng ánh xạ) thì mỗi dòng có thể không cần chứa thông tin địa chỉ của trang trong bộ nhớ ngoài.

8.6.1 Biến đổi địa chỉ, ánh xạ trực tiếp

Chúng ta sẽ xem xét một số phương pháp biến đổi địa chỉ trang. Đầu tiên chúng ta sẽ xem xét biến đổi (ánh xạ) trực tiếp, được biểu diễn trên h.8.12

Hình 8.12

Process đưa yêu cầu truy cập địa chỉ ảo v=(p,d). Trước khi process tiếp tục thực hiện, OS nạp địa chỉ thực của bảng ánh xạ trang vào thanh ghi. Địa chỉ cơ sở b này được cộng với số trang p, thu được địa chỉ thực b+p của dòng chứa ánh xạ trang p. Dòng này chỉ ra page frame p' của p. Sau đó page frame được cộng với offset d và ta có địa chỉ thực r. Cách tính này gọi là phương pháp biến đổi trực tiếp (ánh xạ trực tiếp), bởi vì bảng ánh xạ trang chứa từng dòng cho mỗi trang bộ nhớ ảo của process. Nếu process có n trang bộ nhớ ảo thì bảng ánh xạ trong phương pháp ánh xạ trực tiếp chứa n dòng liên tiếp cho các trang từ 0 đến n-1

Địa chỉ ảo cần tính và địa chỉ bảng ánh xạ đều chứa trong các thanh ghi của BXL do đó các thao tác với chúng có thể thực hiện rất nhanh trong vòng xử lý lệnh. Nhưng còn bảng ánh xạ, kích thước khá lớn, thường nằm trong bộ nhớ, do đó để truy nhập nó cần một thao tác đọc bộ nhớ. Vì thời gian đọc dữ liệu từ bộ nhớ lớn hơn nhiều thời gian xử lý lệnh và chúng ta cần thêm một lần đọc bộ nhớ để lấy được dòng cần thiết của bảng anhý xạ, điều đó có nghĩa là phương pháp ánh xạ trực tiếp có thể làm giảm tốc độ của hệ thống khi thực hiện chương trình gần hai lần. Điều đó tất nhiên không chấp nhận được, do đó cần có các phương pháp biến đổi địa chỉ nhanh hơn. Nhưng điều đó cũng không có nghĩa là phương pháp này hoàn toàn không thể áp dụng, ví dụ như trong một số hệ thống đã sử dụng phương pháp này thành công bằng cách lưu toàn bộ bảng ánh xạ trong cache memory có tốc độ rất cao.

8.6.2 Biến đổi địa chỉ trang dùng bộ nhớ kết hợp associative memory

Một trong số các phương pháp cải thiện tốc độ của DAT là lưu toàn bộ bảng ánh xạ trang trong associative memory (bộ nhớ kết hợp)- với associative memory thời gian truy nhập (access cycle) nhỏ hơn nhiều lần so với bộ nhớ thông thường. Trên h.8.13 biểu diễn quá trình thực hiện biến đổi địa chỉ động chỉ dùng associative memory. Chương trình truy nhập đến địa chỉ ảo v=(p,d). Tất cả các dòng (record) của bảng (nằm trong associative memory) được so sánh đồng thời với p. Associative memory trả lại giá trị p' - địa chỉ của page frame của p. Sau đó cộng p' với offset d ta có địa chỉ thực r.

Hình 8.13

Chúng ta để ý rằng các mũi tên đi đi tới associative memory tới tất cả các bản ghi (dòng) của bảng. Điều đó có nghĩa là mỗi phần tử của associative memory được phân tích đồng thời với địa chỉ p. Cũng vì tính chất này mà bộ nhớ kết hợp rất đắt.

ở đây chúng ta lại gặp vấn đề kinh tế: để có thể ứng dụng thành công bộ nhớ ảo cần có cơ chế biến đổi địa chỉ động (DAT) tốc độ cao. Nhưng dù sao sử dụng cache memory hay associative memory thì đều quá đắt. Chúng ta cần có một giải pháp trung gian nào đó vẫn đảm bảo tốc độ nhưng giá cả phải chăng.

8.6.3 Biến đổi địa chỉ trang sử dụng kết hợp associative với ánh xạ trực tiếp.

Đến lúc này chúng ta luôn định hướng đến các công cụ phần cứng để thực hiện bộ nhớ ảo. Nhưng chúng ta sẽ xem xét các thiết bị một cách logic (trừu tượng) hơn là vật lý. Chúng ta quan tâm không phải là một thiết bị cụ thể (vật lý) mà là tổ chức, chức năng và tốc độ của chúng.

Vì giá của cache memory và associative mrmory quá đắt so với RAM do đó chúng ta cần giải pháp trung gian để thực hiện ánh xạ trang. Trong giải pháp này chúng ta sử dụng associative memory để lưu giữ một phần của bảng ánh xạ (h.8.14). Trong bảng đó chỉ chứa các ánh xạ trang được truy nhập gần nhất (về thời gian)- điều đó xuất phát từ kết quả tương đối là trang đã được truy nhập trong thời gian gần nhất hoàn toàn có thể (với xác suất lớn) lại được truy nhập tiếp. Trong các hệ thống hiện xđại sử dụng phương pháp kết hợp này, chỉ số tốc độ đạt tới 90% hoặc hơn nữa so với khi hoàn toàn chỉ dùng associative memory.

Hình 8.14

Sự biến đổi địa chỉ động được thực hiện theo cách sau: Chương trình cần truy nhập theo địa chỉ ảo v=(p,d). Cơ chế biến đổi địa chỉ đầu tiên sẽ thử tìm ánh xạ của trang ảo p trong phần bảng ánh xạ nằm trong associative memory. Nếu như ánh xạ trang p có ở đó thì bảng ánh xạ trong associative memory trả lại kết quả số page frame p' tương ứng với trang ảo p và giá trị p' này được cộng với offset d, ta có được địa chỉ thực r tương ứng với địa chỉ ảo v=(p,d).

Để đảm bảo chỉ số tốc độ cao, bảng ánh xạ trong asociative memory phải không lớn quá. Thật vậy, trong thực tế, với các hệ thống sử dụng chỉ 8 hoặc 16 thanh ghi asociative memory, có thể đạt được 90% hoặc hơn nữa tốc độ khi sử dụng hoàn toàn associative memory (khi đó kích thước associative memory có thể lớn gấp hàng chục đến 100 lần). Có được kết quả đó là nhờ tính chất đặc biệt của các process hoạt động, gọi là tính địa phương - locality, hiện tượng này chúng ta sẽ xem xét sau.

Sử dụng cơ chế kết hợp đó là lời giải kỹ thuật dựa trên các thông số kinh tế của các thiết bị hiện có.

8.6.4 Chia sẻ (dùng chung) chương trình và dữ liệu trong hệ thống tổ chức trang

Trong các hệ đa nhiệm, đặc biệt các hệ phân chia thời gian, thường xảy ra trường hợp nhiều user cùng chạy các chương trình giống nhau. Nếu mỗi user đều dùng riêng một bản copy của chương trình thì một phần đáng kể bộ nhớ bị lãng phí. Rõ ràng có một giải pháp- đó là sử dụng chung (chia sẻ) các trang có thể chia sẻ.

Sử dụng chung cần phải xử lý , theo dõi cẩn thận để ngăn chặn tình huống khi một process cố thay đổi dữ liệu mà cùng lúc đó process khác đang đọc. Trong nhiều hệ thống tiên tiến, có sử dụng chung bộ nhớ, thường các chương trình cấu tạo từ hai phần riêng biệt- vùng chương trình (procedure) và vùng dữ liệu (data). Các procedure cố định (không thay đổi) hay còn gọi là reentrant procedure, có thể dùng chung. Các dữ liệu tĩnh (ví dụ bảng thông tin cố định nào đó)- có thể dùng chung. Các procedure động (thay đổi) cũng không thể dùng chung.

Tất cả điều đó nói lên rằng mỗi trang bộ nhớ cần xác định xem có thể dùng chung hoặc không. Sau khi các trang của mỗi process được chia ra hai loại, trong hệ thống tổ chức theo trang thuần tuý việc chia sẻ bộ nhớ được biểu diễn trên h.8.15. Việc chia sẻ bộ nhớ làm giảm dung lượng bộ nhớ sử dụng và hệ thống có thể phục vụ số lượng user lớn hơn.

Hình 8.15

8.7 Tổ chức theo đoạn (segment)

Trong chương trước nói về bộ nhớ thực, chúng ta đã thấy rằng trong các hệ thống đa nhiệm với phân đoạn thay đổi, việc phân bố bộ nhớ thường thực hiện theo các thuật toán 'first suitable', 'most suitable' hay 'least suitable' theo tương quan về kích thước các vùng trống. Nhưng vẫn có hạn chế là chương trình phải nạp vào một vùng liên tục.

Trong các hệ thống tổ chức theo segment, sự hạn chế đó có thể vượt qua, và cho phép chương trình (và dữ liệu) có thể nằm trong nhiều khối nhớ không liên tục (h.8.16); Tuy rằng bản thân các khối nhớ là một vùng nhớ liên tục nhưng chúng có thể có kích thước khác nhau.

Hình 8.16

Trong giải pháp này xuất hiện một số vấn đề thú vị. Ví dụ như vấn đề bảo vệ chương trình, bộ nhớ. Sử dụng cặp thanh ghi biên không còn tác dụng nữa. Vấn đề tương tự như thế với việc kiểm soát việc truy nhập bộ nhớ của một chương trình nào đó. Một trong những phương pháp thực hiện bảo vệ bộ nhớ trong các hệ thống tổ chức theo segment- đó là sử dụng khoá bảo vệ, như trên h.8.17

Hình vẽ: Bảo vệ bộ nhớ dùng khoá trong các hệ đa nhiệm với phân bố bộ nhớ thành các block. Khi giá trị khoá trong BXL được đặt bằng hai- tương ứng với user B, chương trình của user B chỉ có thể truy nhập đến các block bộ nhớ có cùng khoá (2) Việc điều khiển khoá bảo vệ được thực hiện bởi OS.

Địa chỉ ảo trong các hệ thống segment- là cặp số v=(s,d) trong đó s- số segment của bộ nhớ ảo, còn d- offset trong đoạn đó.

Hình 8.18: dạng địa chỉ ảo

Process có thể tiếp tục chỉ trong trườngh hợp segment hiện tại nằm trong bộ nhớ. Segment được nạp từ bộ nhớ ngoài vào bộ nhớ vật lý theo cả segment, và segment phải được nạp vào một vùng nhớ liên tục. Segment có thể được nạp vào bất kỳ vùng trống liên tục nào đủ lớn. Các chiến lược phân bố segment cũng giống như trong các hệ thống đa nhiệm với phân đoạn thay đổi, thường thì các thuật toán ' first suitable' và 'most suitable' hay được áp dụng.

Quá trình biến đổi địa chỉ động được thực hiện như h.8.19. Process truy nhập theo địa chỉ ảo v=(s,d). Cơ chế ánh xạ segment tìm và (nếu có) thì xác định địa chỉ đầu segment s'. Sau đó địa chỉ thực r được tính bằng tổng s' và d. Các chi tiết của quá trình biến đổi địa chỉ chúng ta sẽ xem xét sau.

Hình 8.19

8.7.1 Điều khiển truy nhập trong hệ thống tổ chức segment

Cho phép mỗi process truy nhập không hạn chế đến segment bất kỳ là không thực tế. một trong những ưu thế của hệ thống tổ chức theo segment là khả năng kiểm soát truy nhập chặt chẽ. Mỗi process được trao một số quyền truy nhập xác định đối với một số segment nào đó còn phần lớn segment khác là hoàn toàn không được truy nhập.

Trong bảng 8.20 có liệt kê những dạng quyền truy nhập phổ thông nhất được áp dụng trong các hệ thống tiên tiến. Nếu process có quyền read thì nó có thể đọc (truy nhập) đến bất kỳ ô nhớ nào trong segment và khi cần nó có thể copy toàn bộ cả segment.

Nếu như process có quyền write thì nó có thể thay đổi nội dung của bất kỳ ô nhớ nào trong segment, và có thể thêm thông tin bổ sung vào segment. Khi cần nó cũng có thể xoá toàn bộ segment. Process có quyền execute thì nó có thể làm việc với segment như là với chương trình. Còn quyền truy nhập đến các segment dữ liệu thường là bị cấm.

Khi process có quyền append thì nó có thể thêm thông tin vào cuối segment, nhưng không được phép thay đổi thông tin đã có.

Bảng 8.20

Quyền Ký hiệu Giải thích

Read R có quyền đọc thông tin

Write W có quyền thay đổi nội dung

Execute E có quyền thực hiện (chương trình)

Append A có quyền thêm thông tin vào cuối block

Trong bảng hệ thống có phân biệt 4 loại quyền truy nhập như trên, có thể có 16 chế độ điều khiển truy nhập- cho phép hay cấm mỗi loại. Tuy nhiên một số trong chúng là không có ý nghĩa, còn một số khác thì có. Để đơn giản chúng ta xem xét 8 tổ hợp quyền truy nhập đối với các quyền read, write và execute- như trong bảng 8.21

Hình 8.21

Trong chế độ 0 tất cả các hình thức truy nhập đều bị cấm. Chế độ này ngăn chặn sự truy nhập bất hợp pháp, process sẽ không thể truy nhập đến segment. Chế độ 1 chỉ cho phép thực hiện. Chế độ này cần thiết khi process chỉ cần được phép sử dụng chương trình trong segment nhưng không được thay đổi nó hay copy.

Chế độ 2 và 3 thực tế không áp dụng- không có logic khi cho phép process thay đổi nội dung của segment mà không cho pép đọc.

Chế độ 4 chỉ cho phép đọc. Chế độ này cần cho các quá trình tìm kiếm thông tin, nhưng không cho phép thay đổi chúng.

Chế độ 5 cho phép đọc và thực hiện. Chế độ này áp dụng trong các TH process được phép thực hiện chương trình trong segment nhưng không được thay đổi nó. Tuy nhiên process có thể copy segment và sau đó có thể thay đổi bản copy của mình.

Chế độ 6 cho phép đọc và ghi. Chế độ này thường áp dụng với segment chứa dữ liệu mà process có thể đọc hoặc ghi và dữ liệu cần tranghs TH vô tình cố thực hiện (vì segment đó không chứa chương trình)

Chế độ 7 không hạn chế quyền truy nhập. Chế độ này cần để cho phép process có toàn quyền làm việc với các segment của mình, hoặc khi user khác tin tưởng hoàn toàn -cho phép toàn quyền truy nhập segment của anh ta.

Các chế độ kiểm soát quyền truy nhập là cơ sở của việc bảo vệ segment và được áp dụng trong nhiều hệ thống.

8.7.2 Biến đổi địa chỉ segment-ánh xạ trực tiếp

Cũng như trong tổ chức theo trang, trong các hệ tổ chức segment có nhiều chiến lược thực hiện biến đổi địa chỉ của segment. Việc biến đổi địa chỉ có thể là ánh xạ trực tiếp, dùng associative memory hay kết hợp. Chúng ta sẽ xem xét biến đổi trực tiếp và toàn bộ bảng ánh xạ nằm trong cache memory.

Dạng của bản ghi trong bảng ánh xạ thường có như h.8.22

Hình 8.22

Đầu tiên chúng ta xét TH khi quá trình biến đổi diễn ra bình thường và sau đó là một số TH có thể khác.

Process truy nhập theo địa chỉ ảo v=(s,d) trong đó s là số segment. Số segment s được cộng với địa chỉ cơ sở b- địa chỉ đầu của bảng ánh xạ- nằm trong thanh ghi. Ta có được địa chỉ thực của bảng ghi ánh xạ của segment s. Từ bảng ánh xạ ta có địa chỉ thực s', cộng s' với offset d ta được địa chỉ thực r=s'+d là địa chỉ thực tương ứng với địa chỉ ảo v=(s,d).

Trên h.8.22 chúng ta thấy dạng của một ánh xạ.

Bit dấu hiệu tồn tại r cho biết thời điểm đó segment có nằm trong bộ nhớ hay không. Nếu như có, thì s' là địa chỉ đầu của nó, còn nếu không có trong bộ nhớ thì a là địa chỉ bộ nhớ ngoài theo đó HĐH nạp segment để process có thể tiếp tục. Tất cả các thao tác truy nhập segment được kiểm soát theo độ dài segment l để luôn chắc chắn rằng chúng không vượt ra ngoài segment. Mỗi thao tác truy nhập segment còn được kiểm soát theo các bit bảo vệ để xác định xem thao tác đo có được phép hay không. Như thế, khi thực hiện biến đổi địa chỉ động, sau khi tìm đến dòng ánh xạ của một segment cụ thể s đầu tiên sẽ kiểm tra bit r để xác định xem lúc đó segment có nằm trong bộ nhớ hay không. Nếu không nằm trong bộ nhớ thì sinh ra một ngắt missing segment fault, theo đó OS nhận quyền điều khiển và nạp segment đó từ bộ nhớ ngoài (theo địa chỉ a). Sau khi nạp xong quá trình xử lý địa chỉ tiếp tục, offset d sẽ đựơc so sánh với độ dài l của segment. Nếu d>l thì sinh ra ngắt segment over flow fault, và OS không cho phép thực hiện. Nếu d nằm trong giới hạn thì tiếp tục kiểm tra theo các bit bảo vệ để xem tác vụ truy nhập có được phép hay không. Nếu đựơc phép thì mới cộng địa chỉ thực s' của segment với offset d và có được địa chỉ thực r=s'+d tương ứng với địa chỉ ảo v=(s,d). Còn nếu thao tác không được phép thì sẽ sinh ra ngắt segment protection fault và OS không cho thực hiện.

8.7.3 Chia sẻ (dùng chung) chương trình và dữ liệu trong các hệ thống tổ chức theo segment.

Một trong những ưu thế cơ bản của tổ chức theo segment so với tổ chức theo trang là ở chỗ tổ chức theo segment mang tính logic hơn là tính vật lý. Tổng quát thì các segment không bị giới hạn bởi kích thước cố định nào. Chúng có thể có kích thước tuỳ TH cần thiết khác nhau. Ví dụ segment để lưu một bảng nào đó sẽ có kích thước tương ứng với bảng đó. Kích thước của segment chứa cấu trúc dữ liệu thay đổi, có thể thay đổi theo dữ liệu....

Hình 8.23: Chia sẻ bộ nhớ trong tổ chức theo segment

Chia sẻ chương trình, dữ liệu trong hệ thống tổ chức theo segment cũng đơn giản hơn hệ thống tổ chức trang. Ví dụ trong hệ thống tổ chức trang, có một bảng dữ liệu dùng chung nào đó có kích thước 3,5 trang, thì thay vì một con trỏ nói rằng 'bảng này dùng chung' chúng ta cần các con trỏ cho mỗi trang. Mặt khác làm việc với một phần của trang khó hơn nhiều. Tình trạng còn phức tạp hơn trong trường hợp cấu trúc dữ liệu động. Nếu dữ liệu mở rộng thêm một trang thì dấu hiệu sử dụng chung trang cần thay đổi ngay trong thời gian hoạt động của process. Còn trong hệ thống tổ chức segment, sau khi segment đã được đánh dấu dùng chung, thì dữ liệu có thể thay đổi kích thước tuỳ ý mà không làm thay đổi dấu hiệu logic là segment đó được dùng chung.

Trên h.8.23 biểu diễn sự chia sẻ chương trình, dữ liệu trong hệ thống tổ chức segment, hai process dùng chung segment nếu trong các bảng ánh xạ segment có các bản ghi trỏ tới cùng một segment trong bộ nhớ.

8.8 Hệ thống kết hợp tổ chức trang -segment

Hệ thống tổ chức trang hay segment đều có những ưu điểm của mình trong hệ thống với bộ nhớ ảo. Từ giữa những năm 60, cụ thể hơn là bắt đầu từ hệ thống Multics của trường MIT, hệ TSS của IBM và nhiều hệ thống khác người ta đã áp dụng kết hợp tổ chức theo trang- segment. Nhờ đó có được các ưu điểm của cả hai loại mô hình tổ chức bộ nhớ ảo. Các segment thường chứa nhiều trang, ngoài ra không nhất thiết là tất cả các trang của một segment nằm trong bộ nhớ cùng lúc và các trang liền nhau trong bộ nhớ ảo chưa chắc đã ánh xạ lên các trang liền nhau trong bộ nhớ thực.

Các hệ thống tổ chức trang- segment sử dụng đánh địa chỉ gồm ba thành phần, tức là địa chỉ ảo v gồm 3 số v=(s,p,d) trong đó s- số segment, p- số trang trong segment và d- offset trong trang (h.8.24)

Hình 8.24: địa chỉ ảo v=(s,p,d)

8.8.1 Biến đổi địa chỉ động trong hệ thống kết hợp trang- segment

Bây giờ chúng ta xem xét sự biến đổi địa chỉ động trong các hệ thống tổ chức trang-segment sử dụng kết hợp ánh xạ trực tiếp và associative memory (h.8.25)

Process truy nhập theo địa chỉ ảo v=(s,p,d). Phần bảng ánh xạ trong associative memory chứa ánh xạ các trang truy nhập gần nhất. Hệ thống đầu tiên tìm kiếm bản ghi với tham số (s,p) trong associative memory. Nếu như kết quả là dương thì ta có địa chỉ page frame p' theo đó trang p nằm trong bộ nhớ thực. Cộng thêm offset d ta có địa chỉ thực r tương ứng với địa chỉ ảo v.

Thông thường thì phần lớn số yêu cầu biến đổi địa chỉ đều đạt được khi tìm trong associative memory. Nếu như không có địa chỉ cần tìm trong bộ nhớ kết hợp thì dùng phương pháp ánh xạ trực tiếp như sau: địa chỉ cơ sở b của bảng ánh xạ segment được cộng với số segment s,, ta có được địa chỉ b+s của bản ghi ánh xạ cho segment s trong bảng ánh xạ (trong RAM). Trong bản ghi này có chứa địa chỉ cơ sở s' của bảng ánh xạ trang của segment s. Sau đó cộng s' với số trang p, tạo thành địa chỉ p+ s' của bản ghi ánh xạ trang đối với trang p của segment s. Bảng này cho phép xác định trang ảo p tương ứng với số page frame p'. Cuối cùng cộng p' với offset d ta có địa chỉ thực r tương ứng với địa chỉ ảo v=(s,p,d).

Hình 8.25

Thuật toán trên thực hiện được tất nhiên là với điều kiện rằng tất cả các thông tin cần thiết phải nằm đúng chỗ của chúng. Nhưng tấ nhiên có nhiều lúc không phải như vậy. Việc tìm kiến trong bảng ánh xạ segment có thể chỉ ra rằng segment s không có trong bộ nhớ, lúc đó sinh ra ngắt missing segment fault; OS tìm segment trong bộ nhớ ngoài, tạo cho nó bảng ánh xạ trang và nạp trang tương ứng vào bộ nhớ vào chỗ có thể là của một trang của process khác hay của process đó.Ngay cả khi segment nằm trong bộ nhớ, việc tìm kiến trong bảng ánh xạ trang có thể chỉ ra rằng trang cần thiết không có trong bộ nhớ, lúc đó sinh ra ngắt mising page fault, OS tìm trang cần thiết trong bộ nhớ ngoài và nạp nó vào bộ nhớ (hoàn toàn có thể vào chỗ của một trang khác- trang thứ hai sẽ bị đưa ra khỏi bộ nhớ)

Cũng như trong TH tổ chức segment thuần tuý, địa chỉ ảo có thể vượt ra ngoài giới hạn segment, khi đó sinh ra ngắt segment overflow fault. Hoặc khi kiểm tra các bit bảo vệ thì thấy rằng thao tác truy nhập đó bị cấm, lúc đó sinh ra ngắt segment protection fault và OS phải xử lý tất cả các tình huống này.

Bộ nhớ kết hợp (associative memory) hoặc hình thức bộ nhớ tốc độ cao khác (ví dụ cache) đóng vai trò rất quan trọng trong việc đảm bảo hiệu quả (về tốc độ) của cơ chế biến đổi địa chỉ động (DAT). Nếu như chỉ sử dụng ánh xạ trực tiếp tức là chỉ có bảng ánh xạ nằm trong bộ nhớ thì để truy nhập được đến ô nhớ cần thiết, ta phải thực hiện 3 lần thao tác đọc bộ nhớ:

Lần 1 để truy nhập đến bảng ánh xạ segment

Lần 2 để đọc ánh xạ trong bảng ánh xạ trang

Lần 3 mới là truy nhập ô nhớ mong muốn

Như vậy để truy nhập bộ nhớ cần 3 thao tác đọc bộ nhớ tức là tốc độ giảm gần 3 lần trong khi chỉ cần 8-16 thanh ghi bộ nhớ kết hợp để chứa các ánh xạ mới nhất là ta đã có thể đạt 90% hoặc hơn về mặt tốc độ.

Trên h.8.26 biểu diễn cấu trúc các bảng cần trong hệ thống kết hợp page-segment. ở mức trên cùng là bảng các process, nó chứa các bản ghi thông tin địa chỉ bảng ánh xạ segment của process tương ứng, mỗi process (đang được hệ thống quản lý) có một bản ghi trong bảng process. Các bảng ánh xạ segment của các process chứa các bản ghi có số segment và địa chỉ bảng ánh xảtang của segment đó, còn mỗi bản ghi của bảng ánh xạ trang chỉ tới page frame của bộ nhớ thực- tại đó có trang bộ nhớ ảo tương ứng, hoặc địa chỉ bộ nhớ ngoài nơi có thể tìm đến trang đó.

Trong hệ thống có nhiều process, segmetn và trang, thì cấu trúc thông tin ánh xạ bộ nhớ có thể chiếm phần đáng kể bộ nhớ. Chúng ta lưu ý rằng quá trình biến đổi địa chỉ động thực hiện ngay trong quá trình hoạt động của process do đó các cấu trúc thông tin ánh xạ đều nằm trong bộ nhớ. Mặt khác các cấu trúc thông tin ánh xạ càng lớn thì bộ nhớ còn lại càng nhỏ và do đó số process hệ thống có thể phục vụ giảm, điều đó có thể dẫn tới giảm hiệu quả của hệ thống (giảm băng thông). Vì vậy người ta thiết kế OS cần phải chú ý đến rất nhiều nhân tố ảnh hưởng trái ngược nhau, phân tích để có được giả pháp cân bằng, có thể đảm bảo hiệu quả của hệ thống.

Hình 8.26

8.8.2 Chia sẻ chương trình, dữ liệu trong hệ thống tổ chức page-segment

Trong các hệ thống tổ chức trang-segment, các ưu thế của việc chia sẻ chương trình và dữ liệu dễ nhận hơn. Việc chia sẻ được thực hiện bằng cách trong các bảng ánh xạ segment của các process khác có các bản ghi chứa các con trỏ tới cùng một bảng ánh xạ trang (h.8.27)

Hình 8.27

Chương 9: Điều khiển bộ nhớ ảo

9.1 Mở đầu

Trong chương trước chúng ta đã xem xét các hình thức tổ chức bộ nhớ ảo: tổ chức trang, tổ chức segment, và kết hợp trang-segment: các cơ chế phần cứng cũng như chương trình, thực hiện bộ nhớ ảo. Chương này chúng ta sẽ xem xét các chiến lược điều khiển bộ nhớ ảo

9.2 Các chiến lược điều khiển bộ nhớ ảo

Trong chương 7 về bộ nhớ thực, chúng ta đã xem xét các chiến lược lựa chọn, phân bố và loại bỏ thông tin (trang). Chương này chúng ta sẽ xem xét các chiến lược đó được ứng dụng trong bộ nhớ ảo thế nào:

1- Chiến lược lựa chọn: chúng dùng để xác định thời điểm nạp trang hay segment từ bộ nhớ ngoài vào bộ nhớ. Chúng ta đã nói có hai chiến lược: Chiến lược lựa chọn theo yêu cầu- hệ thống yêu cầu (truy nhập) trang hay segment của process, chỉ sau khi đã xuất hiện yêu cầu thì trang hay segment mới được nạp vào bộ nhớ; Chiến lược dự đoán trước- hệ thống sẽ cố gắng xác định xem trang/segment nào sẽ có yêu cầu truy nhập và nếu như xác suất là lớn và có chỗ trống thì trang/segment đó sẽ được nạp trước vào bộ nhớ.

2- Chiến lược phân bố- mục đích của chúng là xác định trang/ segment sẽ được nạp vào nơi nào của bộ nhớ. Trong các hệ thống tổ chức trang thì sự phân bố tương đối rõ ràng và tự nhiên, trang có thể được nạp vào bất cứ page frame nào trống. Còn trong các hệ thống tổ chức segment thì cần các chiến lược tương tự như chúng ta đã phân tích khi xem xét cách hệ thống đa nhiệm với phân đoạn thay đổi.

3- Chiến lược loại bỏ- xác định xem trang - segment nào sẽ bị loại ra khỏi bộ nhớ để lấy chỗ trống nạp trang / segment cần thiết nếu như bộ nhớ đã hết chỗ trống.

9.3 Các chiến lược loại bỏ trang (replacement strategies)

Trong các hệ thống tổ chức trang, thường tất cả các page frame đều bận. Trong TH đó, chương trình điều khiển bộ nhớ (nằm trong OS) phải xác định trang nào sẽ phải bị loại ra khỏi bộ nhớ để có chỗ nạp trang cần thiết. Có nhiều chiến lược, thuật toán loại bỏ trang, chúng ta sẽ xem xét các chiến lược sau:

Nguyên tắc tối ưu (principle of optimality)

Loại bỏ ngẫu nhiên (random page replacement)

Loại bỏ theo nguyên tắc FIFO (first in first out)

Loại bỏ theo nguyên tắc LRU (least recently used)

Loại bỏ theo nguyên tắc LFU (least frequency used)

Loại boe theo nguyên tắc NUR (not used recently)

Nguyên tắc working set of pages

9.3.1 Nguyên tắc tối ưu (principle of optimality)

Theo nguyên tắc này, để đảm bảo các đặc tính tốc độ tốt nhất và sử dụng hiệu quả nhất tài nguyên thì phải loại bỏ trang mà trong tương lai sẽ không có yêu cầu truy nhập đến nó (trong khoảng thời gian lâu nhất). Tất nhiên có thể thấy rằng chiến lược này thật sự đưa lại kết quả tối ưu, nhưng thực hiện nó thì có thể nói là không thể bởi vì đơn giản là chúng ta không thể biết trước tương lai.

Vì thế chúng ta cố gắng tìm các chiến lược dễ dàng hơn và đạt kết quả chấp nhận được, gần với kết quả tối ưu.

9.3.2 Loại bỏ theo chiến lược ngẫu nhiên

Nếu như chúng ta cần chiến lược có thời gian trễ nhỏ và không quá thiên về một phía (trong mối tương quan với 1 user cụ thể nào đó) thì có thể theo cách đơn giản - chọn trang bất kỳ ngẫu nhiên. Trong trường hợp này tất cả các trang đang nằm trong bộ nhớ đều có thể bị chọn và với xác suất như nhau, và tất nhiên là hoàn toàn có thể trang thường xuyên phải truy nhập sẽ bị loại ra khỏi bộ nhớ. Vì tính ngẫu nhiên nên chiến lược này ít được sử dụng.

9.3.3 Chiến lược FIFO

Trong chiến lược này chúng ta gán cho mỗi trang vào lúc nó đượo nạp vào bộ nhớ một chỉ số. Khi cần phải loại bỏ trang nào đó khỏi bộ nhớ thì sẽ chọn trang nằm trong bộ nhớ lâu nhất (theo chỉ số đã gán). Một cách tự nhiên, ưu thế của chiến lược này có vẻ như rõ ràng: trang đó đã có thể 'sử dụng cơ hội của mình'(đã được truy cập) và đã đến lúc nhường cho người khác. Tiếc rằng không phải luôn như vậy và theo chiến lược FIFO, với xác suất lớn, trang thường được sử dụng (truy nhập) sẽ bị loại ra, bởi vì sự kiện rằng 1 trang nằm trong bộ nhớ trong khoảng thời gian dài hoàn toàn có thể có nghĩa rằng nó luôn được sử dụng (truy nhập).

9.3.3.1 FIFO anomaly (dị thường FIFO)

Thoạt tiên có vẻ như rõ ràng rằng khi tăng số lượng page frame cho một process, process đó sẽ hoạt động với số lần ngắt do missing page fault sẽ giảm. Nhưng thống kê theo Belady, Nelson và Shedler thì chiến lược FIFO với các thứ tự truy xuất trang xác định, khi tăng số lượng page frame dẫn tới tăng số lần ngắt do missing page fault. Hiện tượng này gọi là FIFO anomaly.

Hình 9.1

Chúng ta xét TH trên h.9.1, cột ngoài cùng bên trái-thứ tự truy xuất trang của process. Bảng 1 biểu diễn quá trình phân bố trang theo chiến lược FIFO trong TH process có 3 page frame. Bảng 2 biểu diễn cùng quá trình theo chiến lược FIFO trong TH có 4 page frame. Thực tế chúng ta thấy rằng khi số page frame tăng thì số lần ngắt missing page fault thực sự cũng tăng.

9.3.4 Chiến lược LRU

Theo chiến lược này, để loại bỏ trang chúng ta sẽ chọn trang nào không được sử dụng (truy xuất) lâu nhất. ở đây chúng ta xuất phát từ một quy luật rằng quá khứ gần- là định hướng tốt để dự đoán tương lai. Chiến lược này đòi hỏi mỗi lần truy xuất trang, chỉ số của nó (thời gian truy xuất) được làm mới (update). Điều đó có thể kéo theo thời gian trễ đáng kể, và cũng vì thế thuật toán LRU thuần tuý ít được áp dụng trong các hệ thống hiện đại mà người ta thướng sử dụng các biến thể gần với LRU đảm bảo thời gian trễ nhỏ hơn.

Khi áp dụng các qui luật có tính trực giác cần phải phân tích kỹ. Ví dụ, theo chiến lược LRU có thể xảy ra TH trang không sử dụng lâu nhất có thể là trang sẽ được truy nhập ngay sau đó, ví dụ do đến lúc đó chương trình hoàn thành vòng lặp mà thân của nó bao một vài trang. Tức là khi loại trang không sử dụng lâu nhất chúng ta có thể lại phải nạp nó vào ngay sau đó.

9.3.5 Loại bỏ theo chiến lược LFU

Một trong những chiến lược gần với thuật toán LRU là chiến lược LFU, theo đó trang ít được sử dụng nhất (theo tần số) sẽ bị loại. ở đây chúng ta kiểm soát tần số truy nhập (sử dụng) mỗi trang, và trong TH cần , sẽ loại trang nào có tần số thấp nhất. Chiến lược này có vẻ đúng(theo trực giác) nhưng có xác suất lớn là trang bị loại được lựa chọn không thực. Ví dụ như trang có tần số sử dụng thấp nhất có thể là trang vừa mới được nạp vào bộ nhớ và chỉ mới truy nhập 1 lần, còn các trang khác có tần số truy nhập lớn hơn nhưng hoàn toàn có thể là trang mới nạp vào đó lại được sử dụng nhiều ngay sau đó.

Như vậy thực tế bất cứ chiến lược nào cũng có thể dẫn tới sự lựa chọn sai. Điều đó cũng rất đơn giản bởi vì chúng ta không thể dự đoán chính xác tương lai. Do đó chúng ta cần tìm chiến lược cho phép lựa chọn đúng với xác suất cao nhất và có chi phí thấp.

9.3.6 Chiến lược NUR

Một trong những thuật toán thông dụng, gần với chiến lược LRU và có thời gian trễ thấp là chiến lược NUR. Chúng ta cũng thấy rằng có thể xảy ra TH trang không được sử dụng trong thời gian gần nhất lại có thể là trang được sử dụng trong tương lai gần và ta lại phải nạp trang đó vào bộ nhớ.

Vì muốn loại bỏ trang trong thời gian nằm trong bộ nhớ không bị thay đổi, trong thuật toán NUR sử dụng hai bit phần cứng cho mỗi trang:

1* Bit flag đọc (read)

2* bit flag thay đổi (write)

Chiến lược NUR thực hiện như sau: Đầu tiên các bit flag truy nhập (đọc/ghi) của tất cả các trang đều đặt=0. Khi đọc dữ liệu trang nào đó thì bit flag đọc của nó =1, còn TH nội dung nó thay đổi thì bit flag ghi=1. Khi cần loại bỏ trang: đầu tiên chúng ta thử tìm trang mà không xảy ra thao tác đọc (bit flag đọc=0). Trong TH không tìm được chúng ta không còn cách nào khác là phải chọn trang đã bị đọc, khi đó cần kiểm tra xem trang đó có bị thay đổi hay không (bit flag ghi) và thử tìm trang không bị thay đổi, bởi vì với trang đã bị thay đổi chúng ta buộc phải ghi vật lý ra bộ nhớ ngoài. Nếu tất cả đều bị thay đổi thì chúng ta không còn lựa chọn nào khác.

Trong các hệ đa nhiệm, bộ nhớ (tất nhiên) hoạt động với cường độ cao và do đó sớm hay muộn phần lớn các trang đều có bit flag đọc bằng 1 và chúng ta không thể lựa chọn theo bit flag đọc một cách đúng đắn. Một trong các giải pháp thông dụng là theo chu kỳ tất cả các bit flag đọc đều reset về 0. Tất nhiên trong Th này hoàn toàn có nguy cơ là các trang được sử dụng nhiều có thể bị loại vì tất cả các bit flag đọc đều bị reset về 0, nhưng vì chúng được sử dụng nhiều nên các bit flag đọc của chúng sẽ nhanh chóng =1.

Việc phân loại trên dẫn tới có 4 nhóm

Giá trị bit đọc Giá trị bit ghi

Nhóm 1 0 0

Nhóm 2 0 1

Nhóm 3 1 0

Nhóm 4 1 1

Sự lựa chọn sẽ diễn ra với các nhóm số nhỏ trước và chỉ khi không có kết quả mới đến lượt các nhóm có số lớn hơn. Để ý rằng nhóm hai có vẻ như không thể có vi là nhóm các trang có ghi mà không truy nhập, nhưng cần chú ý là các bit flag đọc bị reset về 0 theo chu kỳ, do đó tình huống trên có thể xảy ra.

9.4 Locality

Phần lớn các chiến lược điều khiển bộ nhớ đều dựa trên khái niệm tính địa phương - locality, bản chất của nó là phân bố yêu cầu truy nhập bộ nhớ của process là không đều mà tập trung tại một vùng.

Tính locality thể hiện cả theo thời gian và không gian. Locality theo thời gian đó là tính tập trung (concentrate) theo thời gian. Ví dụ như vào lúc 12 giờ trời nắng, khi đó với xác suất lớn (tất nhiên là không tuyệt đối) có thể nói rằng trời cũng nắng vào lúc 11giờ 30 phút (quá khứ) và lúc 12 giờ 30 phút (tương lai). Tính locality theo không gian thể hiện rằng các đối tượng lân cận cũng có cùng tính chất. Ví dụ cũng về thời tiết, nếu hôm nay tại Hà nội trời nắng thì có thể (không phải tuyệt đối) nói rằng ở Hà tây cũng nắng.

Tính chất locality cũng xuất hiện cả trong công việc của OS, nói riêng là điều khiển bộ nhớ. Tính chất này mang tính kinh nghiệm hơn là lý thuyết. Locality không đảm bảo hoàn toàn nhưng xác suất theo nó là lớn. Ví dụ trong các hệ thống tổ chức theo trang, người ta theo dõi thấy rằng các process thường xuyên truy nhập đến một số trang nhất định và các trang đó nằm liền nhau. Tuy nhiên điều đó không có nghĩa là process chỉ sử dụng các trang đó và không truy nhập các trang khác. Điều đó chỉ đơn giản chứng tỏ rằng process thường truy nhậpđến một số trang nhất định nào đó trong khoảng thời gian nào đó.

Tính locality đối với các hệ thống tính toán có thể giải thích nếu để ý đến cách thiết kế chương trình và tổ chức dữ liệu:

1. Locality theo thời gian có nghĩa là các ô nhớ vừa được truy nhập đến sẽ có xác suất lớn lại được truy nhập trong tương lai gần. Điều đó do các lý do sau:

Các vòng lặp chương trình

Các thủ tục của chương trình

Cơ chế stack

Các biến đếm hay

2. Locality theo không gian có nghĩa là trong việc truy nhập bộ nhớ, khi đã đọc một ô nhớ nào đó thì với xác suất lớn các ô nhớ bên cạnh cũng sẽ được truy nhập. Xuất phát từ các lý do sau:

Tổ chức dữ liệu theo các array

Chương trình thực hiện nối tiếp từng lệnh một

Xu hướng người lập trình đưa các biến có liên quan cạnh nhau

Có lẽ hệ quả quan trọng nhất của locality trong việc truy nhập bộ nhớ là chương trình có thể làm việc hiệu quả khi trong bộ nhớ có các trang active (thường xuyên truy nhập nhất)

Đã có nhiều nghiên cứu về locality. Trên h.9.2 biểu diễn phân bố truy nhập bộ nhớ đến các trang của process. Từ độ thị ta thấy rằng trong một khoảng thời gian nhất định, process truy nhập phần lớn đến chỉ một số trang nào đó.

Hình 9.2

Hình 9.3 cũng thể hiện tính locality. Trên hình vẽ này biểu diễn sự phụ thuộc giữa tần số xuất hiện ngắt mising page fault với kích thước bộ nhớ dành cho process để chứa các trang của nó. Đường thẳng biểu diễn sự phụ thuộc đó trong trường hợp process truy nhập bộ nhớ một cách ngẫu nhiên tức là xác suất truy nhập đến từng trang là như nhau. Đường cong biểu diễn sự phụ thuộc trong thực tế phần lớn các process. Nếu như số page frame dành cho process giảm thì tồn tại một khoảng nào đó mà trong khoảng đó tần số xuất hiện ngắt missing page fault tăng không đáng kể, Nhưng từ một điểm nhất định thì từ đó trở đi số lần xuất hiện ngắt mising pag èault tăng đột ngột.

Chúng ta nhận thấy rằng khi mà các trang active còn ở trong bộ nhớ thì số lần xuất hiện ngắt thay đổi không đáng kể. Còn khi một hay nhiều trang acitve không có trong bộ nhớ thì số lần ngắt tăng đột ngột (vì process thường xuyên truy nhập tới các trang active)

Hình 9.3

9.5 Working set of pages: tập hợp trang làm việc

Denning đã đề xuất đánh giá tần số nạp trang cho chương trình theo khái niệm gọi là 'working set theory of program behavior'. Nói một cách đơn giản thì working set là tập hợp các trang mà process thường xuyên truy nhập tới. Denning cho rằng để đảm bảo sự làm việc hiệu quả của chương trình thì cần thiêts phải nạp tất cả các trang active của nó vào bộ nhớ. Trong TH ngược lại htì có thể làm tăng số ngắt missing page fault.

Chiến lược điều khiển bộ nhớ theo working set cố gắng để tất cả các trang active (working set) nằm trong bộ nhớ. Giải quyết Th có đưa thêm một process mới vào hoạt động (tăng hệ số đa nhiệm) hay không, cần phải dựa trên điều kiện la bộ nhớ trống có đủ nạp working set- tất cả các trang active của process đó hay không. Giải pháp này, đặc biệt đối với các process đầu tiên, thường áp dụng một cách cảm tính, vì hệ thống không thể biết trước được tập hợp các trang acitve của process.

Tập hợp làm việc của process W (t,w) vào thời điểm t là tập hợp các trang mà process truy nhập trong khoảng thời gian từ t-w đến w (h.9.4).

Hình 9.4

Biến W gọi là kích thước cửa sổ của tập hợp working set, việc lựa chọn giá trị w đóng vai trò quyết định trong hoạt động của cơ chế điều khiển bộ nhớ theo working set. H.9.5 biểu diễn mối quan hệ

giữa kích thước cửa sổ w với kích thước của working set. Đồ thị này xuất phát từ định nghĩa toán học của working set chứ không phải từ kết quả theo dõi thực tế. Một tập hợp làm việc working set thực sự la tập hợp các trang phải nằm trong bộ nhớ để process có thể hoạt động tốt.

Hình 9.5

Vào thời gian hoạt động của process, working set của nó luôn biến đổi. Đôi khi có thêm một số trang và cũng đôi khi bớt đi. Thỉnh thoảng xảy ra sự biến đổi đột ngột, ví dụ như khi process chuyển giai đoạn, đòi hỏi một tập hợp working set hoàn toàn mới. Do đó bất cứ điều giả sử nào về kích thước và nội dung ban đầu của working set sẽ không luôn đúng đắn với quá trình hoạt động về sau của process. Điều này làm phức tạp thêm việc thực hiện điều khiển bộ nhớ theo chiến lược working set.

Trên h.9.6 biểu diễn việc sử dụng bộ nhớ trong chiến lược điều khiển bộ nhớ theo working set. Đầu tiên, vì process không yêu cầu các trang active toàn bộ ngay mà theo từng trang, nên nó dần dần nhận được đủ bộ nhớ để chứa tất cả các trang active (working set). Sau đó trong một khoảng thời gian nào đó, kích thước bộ nhớ được sử dụng này ổn định không đổi, vì process thường truy nhập đến các trang active của working set đầu tiên này. Theo thời gian process chuyển sang tập hợp làm việc (workingset) tiếp theo, được thể hiện bằng đường cong đi từ tập hợp thứ 1 đến tập hợp thứ 2. Đầu tiên đường cong này là cao hơn tập hợp 1 bởi các trang của tập hợp làm việc thứ 2 nhanh chóng được nạp vào bộ nhớ theo yêu cầu truy nhập của process. Lúc đó hệ thống không thể ngay lập tức nhận ra là process chỉ đơn giản mở rộng working set hay nó đang chuyển sang working set tiếp theo. Sau khi process bắt đầu ổn định truy nhập các trang của working set tiếp theo, hệ thống thấy rằng trong cửa sổ working set, process chỉ truy nhập đến số trang ít hơn trước kia và hệ thống thu gọn kích thước bộ nhớ cấp cho process đến mức bằng với kích thước của working set mới. Mỗi lần khi chuyển từ working set này sang working set mới, đường cong đầu tiên nâng lên và sau đó hạ xuống thể hiện cách mà hệ thống nhận ra điều đó.

Hình 9.6

H.9.6 Thể hiện một trong những khó khăn trong việc thực hiện điều khiển bộ nhớ theo chiến lược working-set, vấn đề ở chỗ working-set thay đổi theo thời gian, ngoài ra workingset tiếp theo của process có thể khác rất nhiều với working set trước đó. Chiến lược working set phải chú ý điều nay để khỏi xảy ra tình trạng quá tải bộ nhớ.

9.6 Nạp trang theo yêu cầu (demand paging)

Trước kia người ta cho rằng tốt nhất la các trang cần thiết củ process được nạp vào bộ nhớ theo yêu cầu. Tức là không có trang nào được nạp vào bộ nhớ từ bộ nhớ ngoài khi mà process chưa thực sự có yêu cầu truy nhập đến nó. Chiến lược này có mặt mạnh là vì:

Lý thuyết tính toán nói rằng con đường thực hiện của chương trình không thể dự đoán chính xác (do các lệnh điều kiện...) do đó bất cứ cố gắng nào nạp trước các trang vào bộ nhớ vì cho rằng chúng sẽ cần đến đều có thể không đúng.

Nạp trang theo yêu cầu đảm bảo rằng trong bộ nhớ sẽ chỉ có các trang thực sự cần cho hoạt động của process.

Chi phí cho việc xác định trang nào cần nạp vào bộ nhớ là nhỏ nhất. Còn trong TH nạp trang theo dự đoán có thể cần chi phí tính toán đáng kể.

Tuy vậy chiến lược nạp trang theo yêu cầu (h.9.7) có những vấn đề của mình. Process phải tích cóp các trang cần thiết cho nó trong bộ nhớ theo từng trang một. Khi có yêu cầu đến một trang mới bất kỳ, process bắt buộc phải chờ khi mà trang chưa đựoc nạp xong vào bộ nhớ. Phụ thuộc vào số lượng trang của process nằm trong bộ nhớ, các khoảng thời gian chờ này sẽ ngày càng đắt vì process chiếm ngày càng nhiều bộ nhớ. H.9.7 biểu diễn sự phu thuộc 'không gian- thời gian' sự phụ thuộc thường được áp dụng trong OS để đánh giá sự sử dụng bộ nhớ của process.

Tích giữa tỷ số 'không gian' và 'thời gian' tương ứng với phần gạch chéo trong sơ đồ. Nó là chỉ số thể hiện sự sử dụng bộ nhớ cả về thời gian và không gian (dung lượng) của process.

===== Hình 9.7

9.7 Nạp trang dự đoán trước (anticipatory paging)

Một chiến lược quan trọng trong việc điều khiển tài nguyên hiệu quả có thể phát biểu như sau: 'mức độ sử dụng của mỗi tài nguyên phải xác định tương đối với giá trị của nó'. Như thế, ngày nay giá phần cứng ngày càng giảm vì vậy giá tương đối của thời gian máy ngày càng giảm so với giá trả cho người. Ngày nay các nhà thiết kế OS tích cực tìm kiếm theo con đường giảm thời gian chờ đợi của user. Một trong những phương pháp tốt theo hướng này là nạp trang theo dự đoán trước.

trong cách này, OS cố gắng dự đoán các trang mà process sẽ cần đến, và khi bộ nhớ có đủ chỗ trống thì nạp các trang đó vào. Do đó khi process cần truy nhập đến trang mới thì nó đã có trong bộ nhớ. Nếu như sự chọn lựa là đúng thì chúng ta đã rút ngắn đáng kể thời gian thực hiện process.

Phương pháp nạp trang dự đoán trước có các ưu điểm sau:

Nếu xác suất chọn đúng la tương đối lớn thì chúng ta làm giảm đáng kể thời gian thực hiện process. Do đó hoàn toàn có lợi khi thực hiện các cơ chế dự đoán trước dù đáp số không phải đúng tuyệt đối.

Trong nhiều TH hoàn toàn có thể tìm được lời giải đúng nếu việc đó có thể thực hiện với chi phí tương đối thấp để process hoạt đọng nhanh hơn, trong khi đó không ảnh hưởng xấu đến các process khác.

Bởi phần cứng ngày càng rẻ do vậy việc giải pháp không tối ưu trở nên ít quan trọng hơn, chúng ta có thể chơ phép mình thêm các trang mà cơ chế dự đoán xác định vào bộ nhớ.

9.8 Giải phóng các trang

Trong chiến lược điều khiển bộ nhớ theo working set, các chương trình thông báo cho OS các trang mà chúng cần sử dụng. Các trang không cần nữa phải loại ra khỏi working set bằng cách nào đó. Thường tồn tại khoảng thời gian trong đó các trang không cần vẫn còn ở trong bộ nhớ.

Khi nhận thấy rằng trang nào đó không cần nữa, user có thể tự gửi tín hiệu và giải phóng trang đso. Điều đó có thể làm giảm thời gian trễ nếu để cho hệ thống xác định.

Việc tự giải phóng bộ nhớ có thể loại bỏ lãng phí bộ nhớ nhưng phần lớn các user không thể làm điều đó vì thậm chí anh ta còn không biết về các trang bộ nhớ. Ngoài ra, thêm các lệnh giải phóng trang trong chương trình ứng dụng làm phức tạp thêm việc lập trình.

Có thể hy vọng rằng vấn đề này được giản quyết với sự giúp đỡ của compiler và OS- chúng sẽ tự nhận biết tình huống khi cần loại bỏ trang và làm một cách nhanh chóng hơn là khi sử dụng working set.

9.9 Kích thước trang

Trong các hệ thống tổ chức theo trang, bộ nhớ thường chia ra thành các page frame có kích thước cố định. Vấn đề là kích thước các trang và page frame phải lựa chọn thế nào.

Để có lựa chọn đúng cần phải phân tích cẩn thận và hiểu biết toàn diện về các tính năng của thiết bị phần cứng, phần mềm và cả phạm vi ứng dụng của hệ thống. Chúng ta không có câu trả lời tổng quát cho mọi TH. Tuy nhiên có một số vấn đề cần chú ý khi lựa chọn kích thước trang:

1- Kích thước trang càng nhỏ thì số lượng trang và page frame càng lớn và bảng ánh xạ trang cũng càng lớn. Đối với các hệ thống mà bảng ánh xạ trang nằm trong bộ nhớ thì chúng ta cần thiết phải tăng kích thước trang. Việc sử dụng không hiệu quả bộ nhớ do kích thước bảng quá lớn gọi là page fragmentation. Chúng ta cần nhận thấy rằng ngày nay vấn đề đó cũng không nghiêm trọng quá, do giá thành bộ nhớ giảm trong khi dụng lượng lại tăng.

2- Khi các trang có kích thước lớn thì lúc nạp trang vào bộ nhớ lại phải nạp khối lượng thông tin lớn hơn, và nói chung không phải bao giờ cũng bắt buộc. Điều đó làm xuất hiện sự cần thiết giảm kích thước trang.

3- Vì sự trao đổi giữa bộ nhớ với bộ nhớ ngoài (HDD,...) chiếm khá nhiều thời gian do đó cần phải giảm tối thiểu số lần trao đổi xảy ra trong quá trình thực hiện chương trình và chúng ta cần giảm kích thước trang.

4- Chương trình thường có tính chất locality, ngoài ra vùng mà process thường truy nhập có kích thước không lớn. Do đó, sự giảm kích thước trang cần làm cho chương trình có số lượng trang active gọn hơn.

5- Vì các procedure và dữ liệu ít khi có kích thước chẵn (bội số kích thước trang) do đó trong các hệ thống tổ chức theo trang có tình trạng inside fragmentation (h9.8) . Theo đó kích thước trang càng nhỏ thì lãng phí do inside fragmentation càng ít.

Hình 9.8

Phần lớn các nghiên cứu về lý thuyết và cả kinh nghiệm thực tế cho thấy rằng cần chọn kích thước trang nhỏ. Trên h.9.9 có một số ví dụ về kích thước trang của một số hệ thống.

Hình 9.9

9.10 Chương trình và sự nạp trang

Tổ chức theo trang- là một cơ chế, mô hình hiệu quả. Đã có nhiều công trình nghiên cứu, phân tích hoạt động của process với tổ chức bộ nhớ theo trang.

Trên h.9.10 biểu diễn sự phụ thuộc giữa phần trăm số trang được process truy nhập và thời gian (bắt đầu từ lúc thực hiện process) .Đoạn đầu đường cong dốc đứng, thể hiện rằng ngay sau khi bắt đầu, process truy nhập đến phàn đáng kẻ các trang của mình. Theo thời gian đường cong ngang dần và nó dần tới 100%. Tất nhiên một số process sử dụng toàn bộ 100% số trang, nhưng cũng có nhiều process có thể trong thời gian dai không truy nhập đến tất cả các trang của mình.

Hình 9.10

H.9.11 thể hiện hậu quả của việc thay đổi kích thước trang trong khi kích thước bộ nhớ không đổi. Từ đồ thị ta thấy rằng đối với process đang hoạt động, số lần ngắt missing page fault tăng lên cùng với sự tăng kích thước trang. Điều đó là do khi kích thước trang tăng trong khoảng bộ nhớ cố định thì số đoạn code và dữ liệu không cần truy nhập cũng tăng, tức là tỷ lệ của code và dữ liệu hữu ích (có truy nhập) giảm. Vì thứ tự truy nhập bộ nhớ của process không phụ thuộc lượng bộ nhớ cấp cho nó, kết quả la số lần ngắt missing page fault nhiều hơn.

Hình 9.11

H.9.12 biểu diễn sự thay đổi thời gian trung bình giữa các lần ngắt mising page fault khi tăng số page frame cấp cho process. Đường cong đơn điệu tăng-tức là số page frame cấp cho process càng lớn thì khoảng thời gian giữa các lần ngắt missing page fault càng lâu.

Hình 9.12

Chúng ta thấy trên đồ thị có điểm uốn , mà từ đó trở đi độ lệch của đường cong gimả hẳn đi, Điểm này tương ứng với lúc mà tất cả working set cua rprocess nằm trong bộ nhớ. Đầu tiên khoảng thời gian giữa hai lần ngắt tăng nhanh tương ứng với sự tăng của phần working set được nằm trong bộ nhớ. Sau khi bộ nhớ đã đủ lớn để nạp toàn bộ working set thì xuất hiện điểm uốn, chỉ ra rằng từ đó, khi cấp thêm page frame cũng không làm tăng đáng kể thời gian giữa các lần ngắt.

Tóm lại tất cả những yếu tố chúng ta đã xem xét đã chứng tỏ sự ảnh hưởng của khái niệm working set và sự cần thiết phải giảm kích thước trang. Theo sự phát triên của tin học, các kết quả này cũng có thể phải phân tích lại.

Chương 10 Lập lịch và tải cho BXL

Các process chỉ thực sự hoạt động khi chúng được sử dụng BXL. Việc phân phối BXL phục vụ các process là bài toán quan trọng và phức tạp của HĐH. Trong chương này chúng ta sẽ xem xét các vấn đề liên quan đến việc phân phối BXL cho các process, việc đó gọi là lập lịch (scheduling) cho BXL.

10.1 Các mức lập lịch

Có thể chia thành 3 mức lập lịch khác nhau:

lập lịch mức cao

lập lịch mức giữa và

lập lịch mức thấp

Lập lịch mức cao, hay lập lịch cho các task: các công cụ ở mức này xác định bài toán (chương trình) nào được đưa vào hệ thống, nghĩa là tạo ra process tương ứng với chương trình đó.

Lập lịch mức giữa: mức này xác định các process được sử dụng BXL. Bộ lập lịch ở mức này phản ứng với các thay đổi về tải của hệ thống. Nó sẽ dừng hoặc kịch hoạt các process để đảm bảo hệ thống hoạt động bình thường, đạt các thông số kỹ thuật đề ra.

Lập lịch mức thấp: công cụ ở mức này xác định ready process nào tiếp theo sẽ được quyền sử dụng BXL, do đó thường được gọi là dispacher.

Hình vẽ 10.1

10.2 Các mục tiêu của việc lập lịch.

Cơ chế lập lịch cần đạt được các mục tiêu sau:

đúng đắn, nghĩa là cơ chế lập lịch cần phục vụ các process "công bằng", tránh tình huống có process bị rơi vào tình trạng chờ vô hạn.

đảm bảo khả năng thông qua lớn nhất, tức là tiến tới phụ vụ số lượng process nhiều nhất có thể trong một đơn vị thời gian.

thời gian phản ứng chấp nhận được với tất cả các process

tối thiểu chi phí, tài nguyên hệ thống.

cân đối việc sử dụng tài nguyên, cần cố gắng nang cao hiệu suất sử dụng tài nguyên, theo đó cần ưu tiên process sử dung tài nguyên giá thành thấp.

đảm bảo cân đối giữa thời gian trả lời và hiệu suất sử dụng tài nguyên. Cách tốt nhất để giảm thời gian trả lời là có đủ tài nguyên dự trữ để khi có yêu cầu có thể cấp phát ngay lập tức, nhưng điều đó cũng dẫn tới lãng phí tài nguyên.

ngăn ngừa tình huống chờ vô hạn

cần quan tâm các process đang sử dụng tài nguyên quan trọng, tránh tình trạng process có mức ưu tiên thấp chiếm tài nguyên mà process mức ưu tiên cao hơn cần. Nếu tài nguyên đó là không chia sẻ thì HĐH cần tạo điều kiện để process giải phóng tài nguyên nhanh nhất.

Chúng ta thấy rằng nhiều yêu cầu. muck tiêu trái ngược nhau, do đó việc lập lịch cho process là bài toán phức tạp.

10.3 Tiêu chuẩn lập lịch

Để đạt được các mục tiêu ở trên, cơ chế lạp lịch cần hcú ý các yếu tố sau:

process có thực hiện yêu cầu thao tác I/O không?

process có sử dụng BXL hết thời gian lượng tử (quantum) hay không

yêu cầu về thời gian trả lời hệ thống cần đạt được

mức ưu tiên của các process

tần suất ngắt missing page fault

thời gian tổng công process được sử dụng BXL

10.4 Khoảng thời gian lượng tử, ngắt thời gian

Như ta đã biết, process chỉ thực sự hoạt động khi nó sử dụng BXL. Nếu process là process hệ thống thì lúc đó HĐH thực sự hoạt động. Để tránh tình trạng độ quyền chiếm giữ BXL, HĐH có các cơ chế cho phép lấy lại quyền kiểm soát BXL.

HĐH thiết lạp đồng hồ hệ thống , xác định khoảng thời gian gọi là lượng tử theo đó sinh ra các tín hiệu ngắt thời gian. Khi đó BXL chuyển sang phục vụ process tiếp theo. Như thế process có thể chiếm BXL đến khi nó tự giải phóng hoặc khi có ngắt tiếp theo. Khi BXL được giải phóng, HĐH sẽ xác định process nào tiếp theo được chiếm BXL.

Ngắt thời gian giúp hệ thống đảm bảo thời gian trả lời chấp nhận được với tất cả process, tránh tình trạng chờ vô hạn, đồng thưòi cho phép hệ thống phản ứng với các sự kiện phụ thuộc thời gian.

10.5 Mức ưu tiên

Trong hệ thống, nói chung các process có vai trò quan trọng khác nhau. Mức độ quan trọng của process được thể hiện qua mức ưu tiên (priority) của nó. Mức ưu tiên của process được gán bởi HĐH, và phụ thuộc kiến trúc của HĐH mà mức ưu tiên đó có thể là động hoặc tĩnh, có thể được gán theo các tiêu chuẩn xác định hoặc ngẫu nhiên (trong trường hợp HĐH không phân biệt được proces nào cần mức ưu tiên cao hơn).

Trong hệ thống sử dụng mức ưu tiên tĩnh, mức ưu tiên của process được gán ngay khi nó được tạo ra và không thay đổi trong suốt quá trình tồn tại của process. Sơ đồ mức ưu tiên tĩnh dễ dàng thiết kế và cài đặt hơn. Tuy nhiên chúng không có khả năng điều chỉnh để phù hợp với sự thay đổi của môi trường.

Ngày nay trong HĐH đều sử dụng sơ đồ mức ưu tiên động. Theo đó mức ưu tiên của process có thể thay đổi khác với mức ưu tiên khởi tạo ban đầu. Cơ chế này cho phép hệ thống thích nghi với sự thay đổi của môi trường để đạt chỉ tiêu tốt hơn, tuy nhiên nó cũng khó khăn hơn trong xây dựng và cài đặt.

10.6 Lập lịch theo thời gian kết thúc.

Khi áp dụng sơ đồ này, hệ thống sử dụng tất cả khả năng hiện có để một ứng dụng nào đó có thể kết thúc trong thời hạn định trước. Ví dụ trường hợp điều khiển tên lửa, các kết quả tính toán chỉ có ý nghĩa trước thưòi điểm nào đó. Lập lịch theo cơ chế này vấp phải các khó khăn:

người dùng cần chỉ rõ các tài nguyên cần thiết phục vụ cho ứng dụng, và điều này không phải luôn dễ dàng thực hiện.

hệ thống một mặt phải thực hiện ứng dụng đúng hạn, mặt khác không được làm ảnh hưởng "quá nhiều" đến các ứng dụng khác.

rất có thể xảy ra việc tranh chấp tài nguyên giữa các ứng dụng.

nếu đồng thưòi có nhiều yêu cầu kết thúc các ứng dụng đúng thưòi hạn thì vấn đề lập lịch có thể rất phức tạp.

việc phức tạp trong lập lịch thường kéo theo chi phí tài nguyên lớn hơn cho nó và làm ảnh hưởng đến cả hệ thống.

10.7 Lập lịch theo nguyên tắc FIFO.

Có lẽ đây là nguyên tắc lập lịch đơn giản nhất. Theo đó BXL phục vụ cá process theo thứ tự trong danh sách các reađy process.

hình vẽ 10.2

Sau khi process được quyền sử dụng BXL, nó được thực hiện đến khi kết thúc. Nguyên tắc FIFO là không hoán đổi, nghĩa là BXL không thực hiện phục vụ quay vòng lần lượt các ready process mà phục vụ từng process đến khi kết thúc.

Nguyên tắc FIFO có tính xác định cao, có thể dự đoán tương đối chính xác thời gian thực hiện các bài toán. Tuy nhiên vì nó là không hoán đổi nên dễ xảy ra trường hợp bài toán quan trọng hơn phải chờ các bài toán khác, đứng trước trong danh sách kết thúc mới được thực hiện. Vì thế hiện nay nguyên tắc này không được áp dụng đơn thuần mà thường kết hợp với các phương pháp khác trong các biện pháp tổ hợp.

10.8 Nguyên tắc quay vòng (Round robin-RR)

Trong nguyên tắc này, việc điều hành thực hiện các process thực hiện theo nguyên tắc FIFO nhưng có hoán đổi, nghĩa là mỗi process trong mỗi lần được sử dụng BXL không được vượt quá khaỏng thời gian xác định - được gọi là lượng tử (quantum). Nếu nó không tự giải phóng BXL sau khoảng thời gian đó thì HĐH sẽ lấy lại quyền điều khiển BXL và chuyển sang phục vụ process tiếp theo trong danh sách. Process bị tước quyền được đưa vào cuối danh sách.

hình 10.3

Nguyên tắc quay vòng có hiệu quả trong các hệ thống phân chia thời gian và cần đảm bảo thời gian trả lời chấp nhận được với tất cả các process. Chi phí tài nguyên có thể giảm xuống nhờ cơ chế chuyển đổi ngữ cảnh và dung lượng bộ nhớ đủ lớn để đồng thời nạp nhiều ứng dụng.

10.9 Giá trị của lượng tử

Trong những nguyên tắc như RR ở trên, việc xác định giá trị của lượng tử có ảnh hưởng đến các chỉ số hoạt động của hệ thống. Giá trị đó là lớn hay nhỏ? cố định hay thay đổi? với các process nó có giá trị như nhau hay khác nhau?

Nếu giá trị đó quá lớn thì có thể lớn hơn cả thời gian thực hiện ứng dụng, nghĩa là trở thành nguyên tắc FIFO. Và như thế không đảm bảo đa nhiệm tốt. Còn nếu giá trị đó quá nhỏ thì chi phí cho việc chuyển đổi ngữ cảnh chiếm phần lớn thời gian và năng lực tính toán của cả hệ thống, chỉ số hoạt động của hệ thống sẽ quá thấp. Quan hệ giữa giá trị của lượng tử và hiệu suất của hệ thống được biểu diễn qua đồ thị sau

Có thể thấy rằng giá trị tối ưu không phải cố định, nó thay đổi theo từng hệ thống và theo tải của hệ thống, nó cũng có thể khác nhau với từng process.

10.10 Lập lịch theo nguyên tắc SJF (Shortes Job First)

Nguyên tắc SJF là nguyên tắc không hoán đổi, theo đó bài toán có thời gian thực hiện ngắn nhất theo dự đoán sẽ được thực hiện trước.

Nguyên tắc này ưu tiên các bài toán nhỏ, vì nói chung việc tạo điều kiện cho các bài toán nhỏ thực hiện và kết thúc dễ dàng hơn. Từ đó hàng đợi các bài toán giảm đi nhanh chóng. Tuy nhiên nguyên tắc này không tính đến mức ưu tiên, độ quan trọng của bài toán.

Theo nguyên tắc này bài toán nhỏ được thực hiện trước do đó hàng đợi nhanh chóng giảm đi và thời gian chờ trung bình giảm. Tuy nhiên việc xác định chính xác thời gian thực hiện bài toán là việc khó khăn và nhiều trường hợp không thể dự đoán chính xác được.

10.11 Lập lịch theo nguyên tắc SRT

Nguyên tắc SRT cũng tương tự nguyên tắc SJF, nhưng SRT là có hoán đổi. Theo nguyên tắc này, process được đánh giá là có khoảng thời gian còn lại đến khi kết thúc là ngắn nhất hoặc process mới được tạo sẽ được ưu tiên.

Process được đưa vào thực hiện sẽ được chạy đến khi nó kết thúc, hoặc khi có một process mới được đưa vào hệ thống mà có thời gian hoạt động nhỏ hơn thời gian còn lại của process đang được thực hiện.

Để thực hiện nguyên tắc này, chúng ta lại gặp phải vấn đề dự đoán chính xác thời gian còn lại của process. Nguyên tắc này đòi hỏi chi phí tính toán lớn hơn so với nguyên tắc SJF. Cơ chế SRT đòi hỏi luôn phải theo dõi thời gian thực hiện của các bài toán để có thể xử lý các tình huống ngắt. Khi số lượng các process không lớn, process có thể được thực hiện ngay, nhưng nếu số lượng bài toán

Theo nguyên tắc SRT, hệ thống cần ghi lại thời gian thực hiện của các process và điều này làm tăng chi phí tính toán. Về lý thuyết nguyên tắc SRT đảm bảo thời gian chờ cực tiểu, tuy nhiên do thao tác chuyển đổi ngữ cảnh mà điều đó không phải luôn đúng.

Giả sử process đang được thực hiện đến lúc gần kết thúc thì xuất hiện process mới có thời gian thực hiện ngắn hơn. Câu hỏi đặt ra là có ngắt process đang thực hiện hay không? vì có thể thời gian thực hiện thao tác chuyển đổi ngữ cảnh còn lớn hơn bản thân thời gian thực hiện process. Để khắc phục nhược điểm này, trong một số hệ thống người ta đặt ra ngưỡng thời gian, theo đó thời gian thực hiện process hiện tại nhỏ hơn ngưỡng đó thì sẽ không thực hiện thao tác chuyển đổi ngữ cảnh.

Một trường hợp khác cần để ý, đó là khi bài toán mới xuất hiện có thời gian thực hiện dự đoán xấp xỉ thời gian còn lại của bài toán hiện tại, khi đó nếu thực hiện chuyển đổi ngữ cảnh thì chi phí lớn hơn lợi ích thu được.

Chúng ta phân tích các trường hợp trên với mục đích cho thấy khi thiết kế hệ thống cần phải xem xét kỹ hiệu quả thu được với chi phí bỏ ra.

10.12 Lập lịch theo nguyên tắc HRN

Brinch Hansen đã đề xuất nguyên tắc HRN (Highest response Ratio Next) để khắc phục một số nhược điểm trong nguyên tắc SJF, đặc biệt sự quá ưu tiên các bài toán có thời gian thực hiện ngắn. HRN là nguyên tắc không hoán đổi và mức ưu tiên động, theo đó mức ưu tiene của process phụ thuộc không chỉ thời gian cần thực hiện nó mà còn cả thời gian nó phải chờ được phục vụ. Công thức tính toán như sau

dễ thấy mức ưu tiên càng cao khi thời gian thực hiện càng ngắn hoặc khi thời gian chờ càng lớn.

10.13 Hàng đợi nhiều mức với mối liên hệ ngược (call back)

Khi process chiếm BXL, nói chung ta khó có thể dự đoán trước về hành vi của nó - thời gian nó cần BXL. Process có thể chỉ cần BXL trong khoảng thời gian ngắn rồi thực hiện yêu cầu vào/ra, hoặc nó cũng có thể cần BXL tính toán trong khoảng thời gian dài nếu HĐH không lấy lại quyền điều khiển. Do đó cơ chế lập lịch cần

+ chú ý đến các bài toán ngắn

+ chú ý các bài toán thường thực hiện thao tác vào/ra để sử dụng thiết bị vào/ra hiệu quả

+ nhanh chóng xác định đặc điểm của bài toán để có thể lập lịch tối ưu.

Cơ chế hàng đợi nhiều mức với mối liên hệ ngược (hình10.14) là cơ chế cho phép đạt được các yêu cầu trên. Khi process mới được khởi tạo, nó được đưa vào cuối hàng đợi mức trên. Nó dần dịch chuyển lên phía đầu hàng đợi do các process khác lần lượt được sử dụng BXL. Khi process đang chiếm BXL kết thúc, hoặc thực hiện yêu cầu vào/ra, hoặc hết thời gian lượng tử hoặc có ngắt,.. BXL được giải phóng và đến process tiếp theo trong hàng đợi được sử dụng BXL.

Nếu process chưa kết thúc và hết thời gian lượng tử, nó bị tước quyền sử dụng BXL và được đưa vào cuối hàng đợi mức thấp hơn. Nếu nó thực hiện yêu cầu vào/ra thì nó sẽ được chuyển xuống cuối hàng đợi cũng mức. Nó sẽ được quyền sử dụng BXL nếu nó chuyển dịch đến đầu hàng đợi và không còn process nào trong các hàng đợi mức trên. Thường trong hệ thống có một vài hàng đợi mức thấp nhất, và hoạt động theo nguyên tắc quay vòng, theo đó các process được thực hiện quay vòng đến khi nó kết thúc.

hình 10.4

Trong nhiều hệ thống, người ta thiết kế để lượng tử đối với hàng đợi mức thấp hơn có giá trị lớn hơn. Nhờ đó process chờ càng lâu thì được chiếm BXL lâu hơn. Process ở đầu hàng đợi chỉ được chiếm BXL nếu tất cả các hàng đợi mức trên là rỗng. Việc thực hiện process có thể bị ngắt nếu xuất hiện process mới thuộc hàng đợi mức trên.

Đến đây ta phân tích nguyên tắc này, đối chiếu với các yêu cầu trên. Cơ chế cần ưu tiên các process thường xuyên thực hiện thao tác vào/ra để đảm bảo hiệu suất sử dụng thiết bị và thời gian trả lời yêu cầu là ngắn. Lượng tử được chọn đủ để process thực hiện xong tính toán và yêu cầu thao tác vào/ra trước khi kết thúc lượng tử. Process được đưa vào cuối hàng đợi và vẫn được gán mức ưu tiên cao. Process sẽ nhanh chóng dịch chuyển lên đầu hàng đợi mức trên và được phục vụ.

Còn với các process thực hiện tính toán nhiều, đầu tiên process được đưa vào hàng đợi mức trên. Process nhanh chóng dịch chuyển lên đầu hàng đợi và được phục vụ. Sau khi kết thúc lượng tử, nó được đưa vào hàng đợi mức đưới với mức ưu tiên thấp hơn. Như thế cơ chế này ưu tiên các process thường thực hiện thao tác vào/ra. Sau đó, khi không còn process ở hàngđoịư mức trên, process được phục vụ lần tiếp theo và khi kết thúc lượng tử, nó được chuyển xuống hàng đợi mức thấp hơn. Cuối cùng nó chuyển xuống hàng đợi thấp nhất và được phục vụ quay vòng đến khi kết thúc.

Cơ chế hàng đợi nhiều mức với liên hệ ngược là cơ chế tốt cho phép phân tách các process theo thời gian sử dụng BXL. Hệ thống có thể ghi lại mức hàng đợi của process, như thế khi process được đưa ngược lại hàng đợi, nó có thể được đưa vào hàng đợi cùng mức.

Ta có thể thấy rằng nếu process đã nằm ở hàng đợi mức thấp nhất thì hệ thống không thể phản ứng với thay đổi hành vi của process ví dụ như process chuyển từ pha tính toán sang pha thực hiện thao tác vào/ra. Vấn đề có thể được giải quyết nếu hệ thống ghi lại thời gian các lần process chiếm BXL, nhờ đó khi chuyển pha, hệ thống có thể nhanh chóng phát hiện sự kiện đó và đưa process vào hàng đợi thích hợp. Hoặc dùng phương án khác, theo đó mỗi khi process tự giải phóng BXL trước khi hết lượng tử, hệ thống lại tăng mức ưu tiên cho process.

Cơ chế này là cơ chế thích nghi - có thể phản ứng với các thay đổi trong hành vi của process. Thông thường cơ chế thích nghi đòi hỏi chi phí lớn hơn, nhưng nó giúp hệ thống linh động hơn, tự điều chỉnh hoạt động và lợi ích đạt được nói chung cân bằng được với chi phí.

Chương 12: Làm việc với ổ đĩa từ

12.1 Mở đầu

Sự chậm chạp của các hệ thống đa nhiệm thường gây ra bởi việc sử dụng không đúng các thiết bị lưu trữ ngoại vi như đĩa từ, trong từ,.... Trong chương này chúng ta sẽ xem xét một số phương pháp trong việc điều khiển các thiết bị đó.

Chúng ta sẽ phân tích sự làm việc của đĩa từ, xem xét các nguyên nhân dẫn đến làm việc không hiệu quả, phân tích các biện pháp nâng cao hiệu suất- so sánh sự giống nhau, khác nhau cũng như ưu, khuyết điểm của chúng- về phương diện tốc độ.

12.2 Hoạt động của ổ đĩa với đầu từ chuyển động

Trên h.12.1 biểu diễn sơ đồ của ổ đĩa cứng với các đầu từ di động. Dữ liệu được ghi trên các mặt đĩa phủ từ, các đĩa này được gắn chặt vào một trục chung và quay với tốc độ rất cao (3600 vòng/ phút- 7200 vòng/ phút)

Hình 12.1

Việc truy nhập dữ liệu (đọc hay ghi) được thực hiện với sự giúp đỡ của các đầu từ đọc/ghi, mỗi mặt đĩa có một đầu từ. Đầu từ chỉ có thể truy nhập dữ liệu trên mặt đĩa nằm trực tiếp ngay dưới (trên) nó. Do đó để có thể truy nhập đến dữ liệu, vùng đĩa chứa dữ liệu phải dịch chuyển trong quá trình quay sao cho nó nằm trực tiếp dưới đầu từ. Thời gian cần thiết để dịch chuyển (quay) vùng bề mặt đĩa đến dưới đầu từ gọi là 'thời gian trễ' (latency)

Mỗi đầu từ, nếu như nó không dịch chuyển vẽ nên trên bề mặt đĩa (đang quay) đường tròng (track) trên đó có thể lưu dữ liệu. Tất cả các đầu từ được gắn trên block điạnh vị. Block định vị với các đầu từ có thể dịch chuyển theo bán kính các đĩa. Với việc dịch chuyển đầu từ đến vị trí mới, chúng ta có thể truy nhập đến nhóm các rãnh (track) khác nhau.

Nhóm các track nằm dưới tất cả các đầu từ đọc/ghi trong một vị trí nào đó của block tạo thành cylinder. Quá trình dích chuyển đầu từ đến cylinder mới gọi là thao tác tìm cylinder (seek)

Hình 12.2

Như thế, để có thể truy nhập đến dữ liêu trên đĩa với các đầu từ đọc/ghi nói chung cần thực hiện một vài thao tác (h.12.2). Trước tiên các đầu từ cần phải được định vị trên cylinder cần thiết (seek cylinder). Sau đó cần phải chờ đến khi điểm bắt đầu của bản ghi đến đúng vị trí dưới đầu từ (tìm bản ghi-gắn với thời gian trễ), tiếp theo là bản thân bản ghi, về nguyên tắc có thể có kích thước tuỳ ý (đến toàn bộ rãng-track), cần phải đi qua dưới đầu từ (gọi la thời gian truyền- transmission time). Bởi vì tất cả các thao tác trên đều gắn với chuyển động cơ học, thời gian tổng cộng cần để truy nhập đến thông tin chiếm tới 0,01-0,1 s. Ngày nay các ổ đĩa cứng có thời gian truy nhập ngẫu nhiên trung bình 8-12ms. ta thấy khoảng thời gina đó là rất lớn nếu so sánh với tốc độ của BXL

12.3 Sự cần thiết phải planning

Trong các hệ đa nhiệm, cùng lúc có thể có nhiều process hoạt động và chúng có thể có yêu cầu truy nhập đĩa. Bởi các process thường sinh các yêu cầu nhanh hơn nhiều khả năng phục vụ của các thiết bị ngoài vi do đó với mỗi thiết bị có một hàng đợi các yêu cầu. Trong một số các hệ thống các yêu cần này được phục vụ theo nguyên tắc FCFS (first come- first served). Nguyên tắc FCFS là cách phục vụ đúng, nhưng khi số yêu cầu lớn thì nó có thể dẫn tới thời gian trễ lớn.

Phương pháp FCFS có đặc điểm là tìm kiếm ngẫu nhiên, trong đó các yêu cầu lần lượt có thể tạo ra các khoảng tìm kiếm cylinder (seek cylinder) dài, từ các track trong cùng đến các track ngoài cùng (h.12.3). Để giảm tối thiểu thời gian tìm kiếm bản ghi, chúng ta cần sắp xếp các yêu cầu theo nguyên tắc nào đó khác với nguyên tắc FCFS. Quá trình đó gọi là planning công việc với ổ đĩa.

Hình 12.3

H12.3 Tìm kiếm cylinder ngẫu nhiên do nguyên tắc FCFS

Quá trình planning cần sự phân tích cẩn thận các yêu cầu để xác định thứ tự phục vụ có hiệu quả nhất. Người ta phải phân tích các liên hệ vị trí của các yêu cầu, sau đó sắp xếp chúng sao cho đảm bảo phục vụ chúng với sự dịch chuyển cơ học ít nhất.

Có hai hướng planning phổ biến, đó là tối ưu theo thời gian tìm kiếm cylinder và tối ưu theo thời gian trễ (latency). Vì thời gian tìm kiếm cylinder lớn hơn thời gian trễ rất nhiều cho nên phần lớn các thuật toán planning đạt mục đích giảm tối thiểu thời gian tìm kiếm cylinder đối với một nhóm yêu cầu nào đó. Giảm thời gian chờ ghi- Thời gian trễ (latency) thường không ảnh hưởng đáng kể đến đặc tính tốc độ của hệ thống , nếu không tính đến chế độ tải rất lớn.

Với các TH tải nhỏ thì nguyên tắc FCFS có thể chấp nhận, còn với các hệ thống có tải trung bình đến lớn (về số yêu cầu truy nhập đĩa) thì planning có thể đảm bảo đặc tính tốc độ tốt hơn nhiều so với phương pháp FCFS đơn giản.

12.4 Các đặc tính đánh giá nguyên tắc planning

Chúng ta đã thấy rằng nguyên tắc FCFS chấp nhận được trong một số TH. Để đánh giá các nguyên tắc planning tồn tại một số tiêu chuẩn:

1- Khả năng phục vụ (throughput)

2- Thời gian trả lời trung bình (mean response time)

3- Sự khác biệt thời gian trả lời (variance in response time)

Rõ ràng rằng các nguyên tắc planning phải đảm bảo tăng khả năng phục vụ tức là số yêu cầu phục vụ được trong một đơn vị thời gian. Vì các chiến lược planning cho phép giảm thời gian tìm kiếm nên chúng hoàn toàn có thể nâng cao khả năng phục vụ so với TH dùng phương pháp FCFS. Ngoài ra các chiến lược planning phải cố gắng làm giảm tối thiểu thời gian trả lời trung bình. Vả lại planning giảm thời gian tìm kiếm cylinder cho nê chúng cũng làm rút ngắn thời gian trả lời trung bình so với FCFS.

các tiêu chuẩn kể trên cố gắng theo hướng cải thiện các chỉ số tốc độ chung của cả hệ thống, và nói chung chúng thực sự làm bức trang chung tốt hơn dù rằng có thể có một số yêu cầu sẽ bị phục vụ chậm đi đôi chút.

Một trong những chỉ số đánh giá quan trọng nhất là sự khác biệt (variance) về thời gian trả lời. Nó đánh giá việc một giá trị (ở đây la thời gian phục vụ) cụ thể đối với một phần tử nào đó có thể sai lệch (khác biệt/giao động) bao nhiêu so với giá trị trung bình. Với ý nghĩa đó chúng ta dùng vảiance như một chỉ số dự đoán trước- độ khác biệt càng nhỏ thì độ dự đoán trước càng lớn. Chúng ta cần các chiến lược planning cho phép giảm tối thiểu độ khác biệt variance.. Trong TH ngược lại, có thể xảy ra tình huống rằng thời gian phục vụ một số yêu cần nào đó không thể ước lượng trước. Điều đó không cho phép, ví dụ với hệ thống đăng ký chỗ máy bay khi mà việc trả lời nhanh, chậm ảnh hưởng đến việc bán vế. Nếu như các chiến lược planning chỉ cố theo hướng tăng khả năng phục vụ (throughput) mà không đồng thời làm giảm tối thiểu độ dao động (variance in response time), thì nó có thể xử lý chỉ các yêu cầu dễ phục vụ và bỏ qua một số yêu cầu khác.

12.5 Tối ưu hoá thời gian tìm cylinder

Chúng ta sẽ phân tích các chiến lược tối ưu thời gian tìm kiếm cylinder phổ biến nhất:

1- FCFS - các yêu cầu được phục vụ theo thứ tự xuất hiện

2- SSTF (shortes seek time first)- khi đó yêu cần nào gắn với sự dịch chuyển đầu từ ít nhất (từ vị trí hiện thời) được phục vụ trước

3- SCAN (scan-quét)- đầu từ dịch chuyển đi, về trên bề mặt đĩa và phục vụ tất cả các yêu cầu gặp trên đường. Đầu từ chỉ đổi hướng trong TH không còn yêu cầu nào nằm (ở phía trước) theo hướng hiện thời.

4- C-SCAN (cycled scan)- đầu từ chỉ phục vụ theo một hướng dịch chuyển từ ngoài vào trong, khi không còn yêu cầu nào ở phía trước thì nó nhảy trở lại phục vụ yêu cầu nào nằm ngoài cùg và tiếp tục đi vào trong.

5- N-step-SCAN- đầu từ dịch chuyển vào/ra như trong TH SCAN, nhưng tất cả các yêu cầu xuất hiện trong quá trình đang phục vụ theo một hướng nào đó, được nhóm lại theo cách nào đó để chúng có thể được phục vụ hiệu quả nhất trong quá trình phục vụ theo hướng ngược lại.

5- Sơ đồ Eschenbach (eschenbach scheme)- đầu từ dịch chuyển lặp lại như trong TH C-SCAN nhưng chiến lươc nàu khác ở một số điểm quan trọng. Khi phục vụ mỗi cylinder thì chỉ thực hiện truy nhập đến một track mà không để ý đến việc có thể có yêu cầu khác cũng thuộc cylinder đó. Cũng có phân tích sắp xếp các yêu cầu trên cùng một cylinder với tham số góc phân bố bản ghi, tuy nhiên nếu hai yêu cầu nằm trên vị trí cắt nhau (có chồng lên nhau) theo phương thẳng đứng thì chỉ có một yêu cầu được phục vụ.

12.5.1 Planning theo FCFS (first come- first served)

Theo chiến lược này yêu cầu nào đến trước sẽ được phục vụ trước. Nó đúng ở chỗ, sau khi xuất hiện yêu cầu nào đó- nó sẽ được có chỗ cố định trong hàng. Nó sẽ được phục vụ (không bị loại ra do có các yêu cầu khác được ưu tiên hơn). Nếu các yêu cầu phân bố đều theo bề mặt đĩa thì chiến lược FCFS dẫn tới tìm kiếm ngẫu nhiên. Trong đó bỏ qua các liên hệ vị trí của các yêu cầu đang chờ được phục vụ, và không có bất cứ sự tối ưu nào trong tìm kiếm.

Chiến lược FCFS chấp nhận được nếu hệ thống làm việc với tải nhỏ. Nhưng khi tải tăng lên thì thời gian phục vụ nhanh chóng trở nên quá lâu. Chiến lược FCFS đảm bảo variance không lớn.

12.5.2 Chiến lược SSTF

Khi planning theo chiến lược SSTF, đầu tiên sẽ phục vụ yêu cầu có khoảng cách nhỏ nhất (do đó có thời gian tìm cylinder ít nhất) dù yêu cầu đó không phải xuất hiện đầu tiên.

Chiến lược SSTF có đặc điểm variance nhỏ đối với các yêu cầu xác định. Việc truy nhập đĩa xuất hiện xu hướng tập trung, kết quả là yê cầu truy nhập các track trong cùng và ngoài cùng có thể được phục vụ kếm hơn nhiều so với các yêu cầu truy nhập track ở giữa.

Chiến lược SSTF đảm bảo khả năng phục vụ lớn hơn FCFS và thời gian trả lời trung bình tốt hơn với tải lớn. Một trong những khuyết điểm của nó là sự tăng độ dao động thời gian trả lời (variance in response time) với các track trong cùng và ngoài cùng. Nhược điểm của nó có thể bỏ quả trong TH yêu cầu quan trọng nhất la khả năng phục vụ và giảm thời gian trả lời trung bình, ví dụ trong các hệ thống xử lý theo gói.

12.5.3 Planning theo chiến lược SCAN

Để giảm variance đối với các track biên, Denning đã xây dựng chiến lược scan. Chiến lược này nói chung cũng tương tự như SSTF nếu không tính đến một vấn đề là nó phục vụ yêu cầu có khoảng cách tìm kiếm nhỏ nhất theo một xu hướng xác định (h.12.6)

Nếu như tại thời điểm hiện tại hướng quét là từ trong ra thì chiến lược SCAN sẽ chọn yêu cầu với khoảng cách nhỏ nhất theo hướng ra ngoài. Trong chiến lược SCAN, đầu từ không đổi hướng chuyển động cho đến khi nó đạt đến cylinder ngoài cùng hay khi không còn yêu cầu nào chờ theo hướng đó. Nguyên tắc SCAN là cơ bản trong phần lớn các hệ thống có planning công việc với đĩa từ.Chiến lược SCAN rất giống với SSTF từ quan điểm tăng khả năng phục vụ và giảm thời gian trung bình, nhưng nó gimả đáng kể độ chênh lệch đối với các yêu cầu đến track biên như của SSTF và đảm bảo variance nhỏ hơn nhiều. Trong chiến lược scan đầu từ quét từ trong ra ngoài và ngược lại nên nó quét (nằm trên) các track biên ít hơn (thưa hơn) so với các track ở giữa, nhưng đó chỉ là nhược điểm nhỏ so với variance trong TH SSTF.

12.5.4 Nguyên lý N-step SCAN

Trên nguyên tắc phương pháp SCAN ở trên có một biến thể gọi là N-step-SCAN. Trong đó đầu từ cũng dịch chuyển đi/về nhr trong phương pháp SCAN, nhưng trên mỗi chiều dịch chuyển chỉ phục vụ các yêu cầu đã xuất hiện đến lúc bắt đầu dịch chuyển. Các yêu cầu xuất hiện trong thời gian dịch chuyển được nhóm lại và sắp xếp thế nào để chúng có thể được phục vụ tốt nhất trong lần dịch chuyển ngược lại (h.12.7)

Chiến lược N-step-SCAN đảm boả chỉ số cao cả về khả năng phục vụ cũng như thời gian trung bình. Nhưng điểm quan trọng nhất của nó là độ chênh lệch (variance) nhỏ so với khi sử dụng chiến lược SSTF hay SCAN thuần tuý. Chiến lược N-step SCAN loại trừ khả năng yêu cầu bị chờ quá lâu, tình huống thường xuất hiện khi có số lượng lớn yêu cầu đến cylinder hiện thời. Chiến lược này sẽ lưu các yêu cầu đó để phục vụ vào lúc chuyển động ngược lại.

12.5.5 Chiến lược C-SCAN

Còn một biến thể của chiến lược scan gọi là C-SCAN. Chiến lược này loại trừ tính chất tăng variance đối với các track biên.

Theo chiến lược C-SCAN, đầu từ dịch chuyển từ các cylinder phía ngoài vào trong, ngoài ra phục vụ các yêu cầu theo nguyên tắc thời gian tìm kiếm cylinder nhỏ nhất. Khi đầu từ hoàn thành chuyển dịch theo chiều thuận, nó sẽ nhảy trở về phục vụ yêu cầu gần cylindẻ ngoài cùng nhất và sau đó lại tiếp tục dần vào trong. Chiến lược C-SCAN có thể thực hiện để các yêu cầu xuất hiện trong thời gian đang phục vụ sẽ được phục vụ vào lần sau (h.12.8). Nhờ đó chiến lược C-SCAN loại bỏ được sự tăng variance với các yêu cầu truy nhập cylinder biên.

Các nghiên cứu cho thấy rằng chiến lược planning tốt nhất có thể có hai chế độ. Trong chế độ tải thấp, phương pháp tốt nhất là chiến lược SCAN, còn khi tải trung bình và lớn thì kết quả tốt nhất có được khi dùng C-SCAN. Chiến lược này kết hợp với tối ưu theo thời gian trễ (tìm bản ghi) đảm bảo kết quả tốt trong các điều kiện tải rất lớn.

12.5.6 Eschenbach scheme

Chiến lược này đươc thiết kế đầu tiên cho hệ thống bán vé máy bay, với tải rất lớn. Lược đồ eschenbach là một trong những cố gắng tối ưu đầu tiên theo hướng giảm thời gian tìm kiếm theo cylinder và cả thời gian tìm bản ghi.

Phân tích cho thấy chiến lược C-SCAN với tối ưu thời gian trễ cho kết quả tốt hơn eschenbach scheme.

12.6 Tối ưu theo thời gian trễ

Trong điều kiện tải lớn, xác suất có lớn hơn một yêu cầu đến cùng cylinder nào đó tăng lên, do đó việc tối ưu theo thời gian trễ trở nên cần thiết. Tối ưu theo thời gian trễ đã được áp dụng nhiều năm trong các công việc với thiết bị có đầu từ cố định như trống từ.

Tương tự chiến lược SSTF theo hướng tối ưu thời gian tìm cylinder, trong hướng tối ưu theo thời gian trễ có chiến lược SLTF. Khi bộ định vị (với các đầu từ) nằm trên một cylinder nào đó với nhiều yêu cầu truy nhập các track khác của cylinder, chiến lược SLTF phân tích tất cả các yêu cầu và phục vụ yêu cầu với thời gian trễ nhỏ nhất trước tiên (h.12.9) không phụ thuộc thứ tự yêu cầu nào có trước.

Các nghiên cứu cho thấy chiến lược này hoàn toàn gần với kết quả tối ưu theo lý thuyết, ngoài ra việc thực hiện nó không phải là phức tạp.

12.7 Các đánh giá hệ thống

12.7.1 ổ đĩa- critical resource

Khi xem xét thầy rằng đĩa cứng là tài nguyên tới hạn (chỗ yếu) của hệ thống, một số kỹ sư khuyên nên tăng dung lượng ổ cứng. Việc này không phải bao giờ cũng giải quyết vấn đề bởi vì tình trạng critical có thể sinh ra do tần số yêu cầu truy nhập đến vùng đĩa nhỏ quá lớn. Nếu như phân tích thấy rằng tình trạng tới hạn (critical) là do vấn đề trên thì có thể áp dụng các chiến lược tối ưu để nâng cao chỉ số tốc độ và loại trừ chỗ yếu đó.

12.7.2 Mức đa nhiệm:

Tải trên đĩa va yêu cầu ngẫu nhiên, thường tăng len với sự tăng mức độ đa nhiệm. Việc sử dụng các biện pháp tối ưu (planning) công việc với đĩa có thể không hiệu quả trong các hệ thống với mức độ đa nhiệm thấp. Nhưng với các hệ thống có mức độ đa nhiệm trung bình thì planning có hiệu quả và nó đạt hiệu quả rõ rệt với các hệ với mức độ đa nhiệm cao (có thể phải xử lý hang nghìn yêu cầu)

12.7.3 Multdisk subsystem

Từ cách nhìn kinh tế và module, các ổ đĩa thường được xây dựng sao cho một vài ổ đĩa vật lý làm viêcj dưới sự điều khiển của một disk controler.

Đến lượt mình disk controller lại được nối vào kênh vào/ra đảm bảo sự trang đổi thông tin giữa các ổ đĩa và BXL. Một kênh có thể phục vụ một vài disk controler và đến lượt mình một disk controler có thể phục vụ một số ổ đĩa (h.12.1)

=====

Các kênh vào/ra không nối trực tiếp với ổ đĩa. Điều này làm chúng ta phải phân tích cẩn thận chỗ yêu trước khi áp dụng các biện pháp giải quyết. Điểm yếu có thể là do controller không đủ mạnh hay giải thông củ kênh không đu. Việc xác định điểm yếu có thể dễ dàng hơn nhờ các chương trình và thiết bị diagnostic đặc biệt, kiểm tra hoạt động (các thông số khác nhau) của kênh (channel) cũng chư controller. Nếu như điểm yếu là controller thì chúng ta có thể theo hướng đặt lại cấu hình hệ thống, giảm số lượng ổ đĩa nối vào controller. Nếu như kênh không đủ giải thông chúng ta có thể đổi một số controller sang kênh khác hay thêm kênh vào/ra. Như thế, để khắc phục các điểm yếu chúng ta có thể phải thay đổi cấu hình hệ thống.

Để giảm xác suất quá tải kênh vào/ra, trong nhiều hệ thống sử dụng các phương tiện chuyên dụng theo dõi vị trí góc quay của đĩa (RPS-rotational position sensing). Các phương tiện này cho phép giảm thời gian kênh bị bận khi tìm bản ghi trên đĩa . Khi có yêu cầu truy nhập đến bản ghi nào đó trên đĩa, RPS giải phógn kênh để kênh thực hiện các thao tác khác cho đến khi bản ghi cần thiết nằm đúng vị trí dưới đầu từ. RPS cho phép kênh có thể phục vụ đồng thời một số yêu cầu , do đó tăng hệ số sử dụng thiết bị.

12.7.4 Phân bố các yêu cầu không đều

Các nghiên cứu lý thuyết liên quan đến hoạt động cua ổ đĩa thường dựa trên một giả thiết là các yêu cầu truy nhập đĩa phân bố đồng đều. Kết luận của các nghiên cứu đó có thể không chính xác đối với nhiều hệ thống có đặc điểm các yêu cầu truy nhập đizx phân bố không đều theo bề mặt đĩa. Việc phân bố không đều đó trong một số trường hợp hoàn toàn là bình thường.

Một trong những nguyên nhân phổ biến dẫn tới sự phân bố các yê cầu không đều là các file lớn liên tục. Khi OS chọn chỗ trống để ghi chúng, nó thường ghi dữ liệu lên cùng một track và khi track đã đầy thì OS chuyển sang ghi lênn các track khác trên cùng cylinder, và khi cylindẻ đầy thì chuyển sang các cylinder bên cạnh. Như thế khi làm việc với các file liên tục hoàn toàn bình thường khi xuất hiện tình huống các yêu cầu truy nhập liên tiếp nói chung sẽ không dẫn tới thao tác tìm kiếm theo cylinder. Và ngay cả khi phải tìm theo cylinder thì nó cũng rất ngắn vì đơn giản sẽ chuyển sang cylinder ngay cạnh. Trong các tình huống này thì việc tối ưu- planning nói chung không đem lại lợi cíh gì. Ngoài ra các chi phí cho planning hoàn toàn có thể dẫn đến giảm tốc độ của hệ thống.

Một số hệ thống có kiểm soát tình trạng của bề mặt đĩa và có thể chuyển dữ liệu trên các track hỏng sang track tốt khác. Các track có thể nằm ở các vị trí rất khác nhau và có thể gây ra các dịch chuyển đầu từ thêm (tìm kiếm) vào các thời điểm không ngờ.

12.7.5 Các phương pháp tổ chức file

Các phương pháp tổ chức file, với tổ chức phức tạp ví dụ dãy chỉ số (index =====) có thể tạo ra hiện tượng số lượng lớn yêu cầu với thời gian tìm kiếm lâu. Việc phục vụ các yêu cầu trong phương pháp truy nhập chỉ số nối tiếp (index sequential access method-ISAM) có thể gắn với việc thực hiện nhiều lần truy nhập đĩa.

Trong một số TH, truy nhập bản ghi có thể đòi hỏi truy nhập đến index chính, truy nhập index của cylinder và sau đó mới xác định được vị trí bản ghi. Quá trình này có thể dẫn tới nhiều lần tìm kiếm theo cylinder bởi vì index chính và index của cylinder thường nằm trên đĩa, nên thời gian trễ trong tìm kiếm có thể khá lớn. Tuy nhiên tổ chức truy nhập ISAM thuận tiện cho những người viết phần mềm ứng dụng.

Chương 13 - File System và Database

13.1 Mở đầu

File - là tập hợp dữ liệu, thường được lưu trữ trong các thiết bị lưu trữ ngoại vi như đĩa từ, bằng từ,... Với file, ta có thể thực hiện các thao tác như với một đơn vị

open - chuẩn bị file cho truy cập

close - kết thúc truy cập file

create - tạo file mới

copy - tạo bản sao

destroy (delete) - xoá file

rename - đổi tên file

Đối với các đơn vị thông tin trong file, thường sử dụng các lệnh

read - đọc dữ liệu từ file

write - ghi các thông tin vào file

insert - chèn thêm thông tin

delete - xoá các đơn vị thông tin

File system (FS) là một cấu thành của HĐH, có nhiệm vụ điều khiển thao tác với các file trên bộ nhớ ngoài. Nó còn đảm bảo khả năng chia sẻ và an toàn thông tin giữa nhiều người dùng.

13.2 Chức năng của FS

FS phải đảm bảo nhiều chức năng khác nhau liên quan đến điều khiển truy cập, trong đó có:

Người dùng phải có khả năng tạo, thay đổi, xoá file

Cung cấp khả năng chia sẻ file dưới sự điều khiển chặt chẽ

Cơ chế chia sẻ file phải xem xét hình thức truy cập cần kiểm soát, ví dụ thao tác đọc , ghi, thay đổi, ..

Người dùng phải có khả năng thao tác dễ dàng với cấu trúc file, độc lập với phần cứng.

Đảm bảo sự troa đổi thông tin giữa các file

Cần có các công cụ khắc phục, khôi phục lại thông tin khi có sự cố

Với các thông tin quan trọng, cần có các cơ chế kiểm soát truy cập chặt chẽ, tránh các truy cập bất hợp pháp, khả năng mã hoá dữ liệu

Hệ thống cần cung cấp giao diện thân thiện với người dùng, cho phép người dùng làm việc với các cấu trúc dữ liệu logic của mình, không cần quan tâm đến các chi tiết vật lý, cụ thể

13.3 Cấu trúc dữ liệu

Tất cả các dữ liệu máy tính có thể xử lý đều tạo thành từ các bit có giá trị 0 hoặc 1. Khi kết hợp các bit thành tổ hợp, ta có thể lưu trữ, thể hiện mọi thông tin phong phú.

Mức cao hơn, ta có đơn vị byte là tổ hợp 8 bit. Như thế có thể có 256 giá trị khác nhau của 1 byte, trong số đó có các ký tự (a-z, A-Z), chữ số (0-9), các ký tự đặc biệt,..Phân bố tổ hợp các bit theo ký tự được gọi là bảng mã. Hiện nay có một số bảng mã phổ biến: EBCDIC (extend bit code decimal for interchange) thường được sử dụng để biểu diễn thông tin bên trong máy, hệ ASCII (americal standard code for interchange information) thông dụng trong các hệ thống truyền thông, ngày nay trong xu thế toàn cầu hoá, mã unicode đang được chấp nhận ngày càng rộng rãi với ưu thế có thể lưu trữ và thể hiện hầu hết các ngôn ngữ trên thế giới.

ở mức cao hơn, nhóm các ký tự liên quan đến nhau gọi là trường - field, ví dụ trường họ tên sinh viên,.. các trường liên quan tạo thành bản ghi ví fụ bản ghi thông tin sinh viên có các trường họ tên, lớp..

Nhóm các bản ghi tạo thành file và tập hợp thông tin cao nhất được gọi là cơ sở dữ liệu.

13.4 Block và Record

Bản ghi vật lý hay block là đơn vị thông tin thực sự được trao đổi với thiết bị lưu trữ. Còn bản ghi logic là tập hợp thông tin được coi là đơn vị toàn vẹn nhìn từ phía người dùng, ví dụ bản ghi sinh viên.

Với hai khái niệm trên, ta có các quan hệ sau về độ dài tương đối giữa chúng.

Một block = một bản ghi

Một block = nhiều bản ghi

Một bản ghi = nhiều block

13.5 Tổ chức file

Tổ chức file là cách phân bố bản ghi của file trong bộ nhớ ngoài. Có thể chia thành các dạng tổ chức sau

+ Nối tiếp: các bản ghi phan bố theo thứ tự vật lý, bản ghi logic tiếp theo nằm nối tiếp về vật lý. Tổ chức file theo kiểu nối tiếp thường áp dụng trong băng từ.

+ Dãy chỉ số:

các bản ghi nối tiếp về logic không nhất thiết liên tiếp về vật lý. Trong hệ thống sử dụng các chỉ mục riêng trỏ đến vị trí vật lý của bản ghi. Tổ chức này thường áp dụng trong đĩa từ.

+ Truy cập trực tiếp

Truy cập bản ghi trực tiếp theo địa chỉ vật lý. Tổ chức hệ thống đơn giản nhưng gánh nặng chuyển sang người lập trình, họ phải biết rõ cấu trúc vật lý của thiết bị. Vì thế hình thức này ít áp dụng.

+ Thư mục

Thư mục là kiến trúc cao hơn file, bao gồm tập hợp các file. Về thực chất thì thư mục cũng là file, chỉ có điều dữ liệu trong đó là thông tin về các file nằm trong thư mục.

13.7 Hệ thống file (File System)

Ta có thể đưa ra các đặc điểm sau của file

+ tần số thay đổi: static và dynamic

+ kích thước file

File System là cấu thành quan trọng của HĐH, FS thường cung cấp các công cụ

Các phương pháp truy cập: xác định, tổt chức truy cập dữ liệu

Các cơ chế điều khiển file: điều khiển truy cập, chia sẻ file cho nhiều người dùng, bảo vệ dữ liệu

Công cụ điều khiển bộ nhớ ngoài: quản lý việc phân bố, cấp phát bộ nhớ ngoài

Công cụ đảm bảo tính toàn vẹn dữ liệu

Chức năng quan trọng của FS là cấp phát bộ nhớ ngoài, điều khiển truy cập. Trong các hệ đa người dùng, đa nhiệm, cùng một lúc có thể có nhiều yêu cầu truy cập đồng thời. FS phải đảm bảo phục vụ các yêu cầu nhanh nhất, vẫn đảm bảo an toàn dữ liệu.

13.8 Cấp phát và giải phòng không gian đĩa

Vấn đề cấp phát và giải phóng không gian đĩa, ở mức độ nào đó có nhiều điểm chung với phân bố bộ nhớ trong các hệ đa nhiệm. Nếu như ban đầu file được ghi trong một vùng nhớ liên tục thì theo thời gian, các file liên tục thay đổi và không gian đĩa trở nên bị chia nhỏ (fragmentation).

Một trong những biện pháp giải quyết tình trạng đó là theo chu kỳ thực hiện việc dồn đĩa. Các file được tổ chức lại để chúng chiếm vùng đĩa liên tục. Việc này thường được thực hiện vào thời gian rỗi của hệ thống. Một số hệ thống còn có thể dọn dẹp đĩa ngay cả khi đang phục vụ người dùng.

Trong một số tình huống, khi mà số yêu cầu đọc/ghi dữ liệu rất nhiều thì việc dồn đĩa có thể không mang lại lợi ích. Ví dụ các yêu cầu có thể yêu cầu dữ liệu trên các file trên vùng đĩa cách xa nhau ngay cả khi các file nằm trên vùng đĩa liên tục.

Khái niệm locality trong bộ nhớ ảo cũng có mặt trong FS, theo đó thường khi truy cập thông tin thường scan các block dữ liệu. Do đó việc sắp xếp để các file chiếm vùng đĩa liên tục thực sự có hiệu quả.

Việc xác định thói quen của người dùng: các ứng dụng, các dữ liệu thường xuyên được dùng cũng có thể cần để ý trong thiết kế FS.

Trong các hệ thống dùng tổ chức bộ nhớ theo trang, block trao đổi bộ nhớ với bộ nhớ ngoài là bội của trang, khi đó việc tổ chức bộ nhớ ngoài theo các block có kích thước tương đương cũng có ý nghĩa. Với tính locality, việc truy xuất các trang bộ nhớ liền nhau dẫn đến việc cần phân bố dữ liệu trong bộ nhớ ngoài cũng cần liền nhau.

13.9 Phân bố

Có hai hình thức phân bố: liên tục và không liên tục.

13.9.1 Phân bố liên tục

Trong hình thức này, mỗi file được cấp phát một vùng liên tục. Nếu không có được vùng trống liên tục đủ lưu file thì file sẽ không thể được lưu.

Một trong các ưu điểm của phân bố liên tục là các bản ghi liên tiếp về logic cũng được lưu liên tục về mặt vật lý, điều đó cho phép cải thiện tốc độ truy cập.

Việc tổ chức lưu trữ cũng tương đối đơn giản.

Tuy nhiên phân bố liên tục có những hạn chế, khi các file bị xoá, thay đổi, tạo ra tình trạng phân mảnh. Hơn nữa, khi cần ghi thêm dữ liệu vào file không phải luôn có vùng trống ngay cuối file để lưu.

Để tránh tình trạng phân mảnh có thể thực hiện dồn file, tuy nhiên việc đó không phải luôn mang lại hiệu quả.

13.9.1 Phân bố không liên tục

Bởi vì thường xuyên các file bị thay đổi, do đó hình thưc phân bố liên tục đã nhanh chóng bị thay thế bởi hình thức phân bố không liên tục, mặc dù tổ chức phức tạp hơn nhưng nó cho phép xây dựng hệ thống mềm dẻo hơn. Có một số hình thức phân bố không liên tục

1. Sử dụng danh sách sector

Trong sơ đồ này, đĩa được xem như tập hợp các sector riêng rẽ. File có thể bao gồm các sector nằm trên các vị trí rải rác. Các sector thuộc cùng một file có các con trỏ đến nhau, tạo thành chuỗi/danh sách các sector. Không gian trống được chỉ ra trong một danh sách các sector trống.

Khi cần cấp phát thêm bộ nhớ, chỉ cần cấp sector từ danh sách sector trống. Còn khi file giảm kích thước thì sector được đánh dấu trống và đưa vào danh sách. Việc dồn đĩa không phải đặt ra.

Tuy nhiên nó cũng có những nhược điểm. Bởi vì các sector có thể nằm rải rác trên đĩa, việc truy cập dữ liệu liên tiếp trong file có thể kéo theo thời gian tìm kiếm sector khá lâu. Việc đọc dữ liệu kéo theo phải duyệt qua chuỗi các sector, xử lý con trỏ kết nối.

2. Phân bố theo block

Hình thức phân bố theo block là kết hợp giữa hình thức phân bố liên tục và không liên tục, trong đó bộ nhớ ngoài được chia thành các khối/block gồm nhiều sector liên tục. Khi cấp phát thêm, FS cố gắng cấp phát block trống gần nhất. Khi truy cập dữ liệu, FS xác định số blokc và sau đó số sector trong block. Có 3 hình thức phan bố theo block: chuỗi block/block chaining, cuỗi block chỉ số/index block và bảng ánh xạ block

+ Chuỗi các block dữ liệu

Trong sơ đồ này, bản ghi trong directory trỏ đến block đầu tiên của file. Mỗi block (có độ dài cố định) gồm hai phần: phần header chứa con trỏ đến block tiếp theo, và phần dữ liệu. Block cuối cùng Đơn vị cấp phát nhỏ nhất là block. Để đọc bản ghi, đầu tiên cần tìm đến block sau đó đến sector trong block chứa bản ghi.

Quá trình tìm kiếm phải bắt đầu duyệt từ block đầu tiên, theo các con trỏ đến block cần tìm. Như thế mếu block phân bố rải rác thì thời gian truy cập lâu hơn đáng kể. Việc cấp phát thêm block hay xoá bớt khá dễ dàng thông qua định hướng lại con trỏ. Trong một số hệ thống, tổ chức chuỗi block liên kết 2 chiều, mỗi block có 2 con trỏ, 1 trỏ tới block tiếp theo và 1 trỏ tới block trước.

hình 13.4: Chuỗi các block

+ Sơ đồ chuỗi block chỉ số/ index block

Trong sơ đồ này, các chỉ mục (index) được chứa trong các block chỉ số. Mỗi block chỉ số chứa số lượng cố định các phần tử, mỗi phần tử chứa con trỏ đến block dữ liệu. Nếu một index block không đủ, hệ thống dùng chuỗi các index block để chứa thông tin của file, mỗi index block có con trỏ đến index block tiếp theo trong chuỗi.

So với sơ đồ dùng chuỗi các block, sơ đồ này có một số ưu điểm. Khi tìm kiếm block dữ liệu nào đó, chỉ cần tìm (duyệt) trong số lượng ít các index block thay vì duyệt qua số lượng lớn các block dữ liệu. Để tăng tốc độ, có thể bố trí các index block nằm trên vùng liên tục trong bộ nhớ ngoài. Khi tìm thấy vị trí block dữ liệu thì chỉ cần nạp block dữ liệu đó vào bộ nhớ.

Sơ đồ này có nhược điểm chủ yếu là khi có thay đổi dữ liêu, ví dụ khi cần thêm các bản ghi dữ liệu mới có thể dẫn đến phải cấu trúc lại nhiều index block. Trong một số hệ thống, để khắc phục người ta dánh sẵn các vùng trống dự trữ cho các index block có thể có trong tương lai. Tuy nhiên khi vùng trống đó đầy thì cũng dẫn đến phải cấu trúc lại index.

Hình 13.5 Sơ đồ chuỗi index block.

+ Sơ đồ bảng ánh xạ block

Trong sơ đồ này để xác định vị trí block, không cần phải có con trỏ mà dùng số của block, bởi vì từ số block có thể dễ dàng tính toán được vị trí block trên bộ nhớ ngoài. Sơ đồ này sử dụng bảng ánh xạ block, mỗi dòng chứa thông tin ánh xạ cho 1 block. Dòng trong bảng thư mục sẽ trỏ đến một dòng trong bảng ánh xạ - tương ứng với block dữ liệu đầu tiên của file. Mỗi dòng của bảng ánh xạ chứa số của block tiếp theo của file. Như thế từ bảng ánh xạ có thể đọc được tất cả thông tin vị trí các block dữ liệu của file.

Với dòng ánh xạ tương ứng với block cuối của file, thường chứa giá trị đặc biệt (ví dụ null) thể hiện rằng không còn block nào tiếp theo-nó là block cuối cùng.

Các dòng ánh xạ của block trống chứa giá trị đặc biệt khác thể hiện rằng đó là block trống, có thể cấp phát. Hệ thống có thể tra cứu bảng ánh xạ để tìm các block trống, hoặc lưu thông tin block trống trong một danh sách riêng.

Bảng ánh xạ có thể được thay đổi để lưu cả các thông tin khác, phục vụ cho mục đích tìm kiếm.

Một trong các ưu điểm lớn nhất của sơ đồ này là chỉ cần tra cứu thông tin trong bảng ánh xạ file là có thể xác định các block trống và vị trí tương đối của chúng so với các block khác, từ đó khi cần cấp phát có thể chọn các block gần với block thuộc cùng 1 file một cách dễ dàng, nâng cao tốc độ truy cập.

Hình 13.6 bảng ánh xạ block

13.10 Mô tả file - File Descriptor

File Descriptor là bản ghi lưu đầy đủ các thông tin về file mà HĐH cần quan tâm, quản lý. Các thông tin lưu trong File Descriptor sẽ phụ thuộc vào từng hệ thống, nhưng nói chung chúng đều có các thông tin sau:

 Tên file

 Kích thước file

 Kiểu file

 Ngày tháng tạo, cập nhật ,..

 Thông tin thuộc tính

File Descriptor nằm trên bộ nhớ ngoài và chúng được nạp vào bộ nhớ khi mở (open) file. Nói chung thì File Descriptor được xử lý bởi File system, người dùng không có quyền truy cập trực tiếp.

13.11 Ma trận điều khiển quyền truy cập

Tại sao cần quản lý quyền truy cập đến file. Trong hệ thống nhiều người dùng, mỗi người đều lưu thông tin riêng của mình trên các file và các người dùng khác nói chung không được truy cập đến chúng, do đó hệ thống cần có các thông tin về quyền truy cập để điều khiển truy cập.

Có nhiều cơ chế khác nhau để quản lý quyền truy cập, một trong các sơ đồ đơn giản nhất là sử dụng ma trận điều khiển quyền truy cập (hình 13.7). Trong đó một chiều là các ID người dùng (hàng Ri), một chiều là ID file (cột Ci). Vị trí ô RiCj chứa giá trị quyền truy cập của người dùng Ui đối với file Fj. Nếu kích thước ô là 1 bit, ta có thể xác định 2 quyền, ví dụ giá trị 0 là không được đọc, 1 là có quyền đọc,.. Tất nhiên để quản lý nhiều quyền hơn thì ta cần lưu được tổ hợp nhiều quyền hơn.

Hình 13.7

Chương 11 Đa xử lý

11.1 Giới thiệu

Một trong những hướng phát triển của kỹ thuật tính toán là việc phổ biến các hệ đa xử lý, tức làcác hệ thống có nhiều BXL. Các kiến trúc đa xử lý đã xuất hiện từ lâu nhưng đến thời gian gàn đây mới trở nên phổ biến.

Đa xử lý cho phép xây dựng các hệ thống chứa hàng chục, thậm chí hàng trăm BXL, đạt được tốc độ cao với chi phí thấp.

11.2 Tính ổn định, sẵn sàng

Một trong các ưu thế chính của các hệ đa xử lý là tính sẵn sàng. Trong trường hợp có 1 BXL gặp sự cố, hệ thống vẫn có thể tiếp tục hoạt động. Để thực hiện được điều đó, BXL gapự sự cố cần thông báo cho các BXL khác về tình trạng sự cố để chuyển giao công việc. HĐH cần biết tình trạng của các BXL để xác định lại tài nguyên, điều chỉnh hoạt động của hệ thống.

11.3 Tính song song

Một mục đích quan trọng của các hệ đa xử lý là tăng tốc độ tính toán. Tuy nhiên phần lớn chương trình được thiết kế để hoạt động tuần tự. Điều đó do một số nguyên nhân:

- con người nói chung suy nghĩ tuần tự

- trong ngôn ngữ cũng không có các công cụ thuận lợi để mô tả tính song song mặc dù có các ngôn ngữ lập trình hỗ trợ song song như ADA

- bản thân các hệ đa xử lý cũng không được áp dụng tính song song để thiết kế

- việc kiểm tra tính đúng đắn của chương trình song song phức tạp hơn nhiều so với tuần tự.

11.4 Mục tiêu của các hệ đa xử lý

Nhờ việc áp dụng đa xử lý, có thể xây dựng hệ thống tốc độ cao với chi phí thấp

các hệ đa xử lý có tính ổn định và sẵn sàng cao.

Tính mềm dẻo, cho phép thay thế, mở rộng hệ thống dễ dàng.

11.5 Tính toán song song tự động

Các hệ thống đa xử lý cho phép tính toán song song, tuy nhiên phần lớn chương trình được thiết kế cho thực hiện tuần tự. Việc xác định có thể tính toán song song do người lập trình , do trình bien dịch hay OS xác định là vấn đề phức tạp

Tính toán sog song có thể do người lập trình chỉ ra, ví dụ với các lệnh tính toán song song. Tuy nhiên việc chỉ ra tính toán tường minh như trên là công việc phức tạp và khó khăn vì người lập trình còn phải xử lý các ván đề nghiệp vụ, dễ xảy ra lỗi (ví dụ những đoạn không tính song song được thì tính song song và bỏ sót các trường hợp tính toán phức tạp)

Việc phân tích xử lý song song có thể được giải quyết nhờ việc xác định tự động các tính toán có thể chạy song song. Việc xác định đó có thể do trình biên dịch hay OS hay HW đảm nhiệm.

Phân bố vòng lặp

Trong chương trình, nhiều đoạn mã được thực hiện trong vòng lặp. Nhiều trường hợp các đoạn mã trong thân vòng lặp độc lập và do đó có thể tính toán song song. Ví dụ

for i:= 1 to 10 do

G[i] := b[i] + c[i]

giSưảm độ cao cây tính toán