Chương VI: Chức năng và

dịch vụ của hệ điều hành

4.1. Quản lý tiến trình

4.2. Quản lý bộ nhớ

4.3. Quản lý tập tin

4.4. Quản lý thiết bị

4.5. Một số dịch vụ của hệ điều hành

4.1.Quản lý tiến trình

(Process Management)

 4.1.1 Tiến trình trong môi trường đa chương trình

 4.1.2 Trạng thái và chuyển trạng thái tiến trình

 4.1.3 Các thuật toán lập lịch tiến trình

 4.1.4 Điều độ tiến trình

4.1.1 Tiến trình trong môi trường

đa chương trình

 Nhắc lại:

 Tiến trình ?

 Đa chương ?

 Tài nguyên ?

Tiến trình trong môi trường đa

chương trình (t)

 Mỗi tiến trình cần tài nguyên:

 Ví dụ:

 Không gian bộ nhớ (mã chương trình, dữ liệu, ngăn

xếp (stack)

 CPU

 N tiến trình, 1 CPU

 N tiến trình, M CPU (N>M)

 Các tiến trình có thể xâm phạm lẫn nhau nếu truy nhập cùng một nguồn tài nguyên

 Ví dụ:

 Các giao dịch dữ liệu có thể cập nhật cùng một tập tin trong cơ sở dữ liệu

Quan hệ giữa các tiến trình

 Tiến trình tuần tự: Một tiến trình chỉ bắt

đầu sau khi tiến trình kia kết thúc

 Tiến trình song song: Thời điểm bắt đầu của một tiến trình nằm giữa thời điểm bắt đầu của một tiến trình khác

 Độc lập

 Có quan hệ thông tin

 Phân cấp

Quản lý tiến trình

 Hệ điều hành quản lý việc cấp phát tài nguyên cho các tiến trình hợp lý

 Bảo đảm một số lượng hợp lệ các tiến trình truy xuất đồng thời đến các tài nguyên không chia sẻ được.

 Cấp phát tài nguyên cho tiến trình có yêu cầu trong một khoảng thời gian trì hoãn có thể chấp nhận được.

 Tối ưu hóa sự sử dụng tài nguyên.

  quan trọng nhât: cấp phát CPU

Tiến trình hệ điều hành

 Hệ điều hành bản thân nó cũng là

một tiến trình (tập hợp của nhiều tiến trình)

 Nhanh, hiệu quả  nhường CPU cho tiến trình người dùng

 Tiến trình hệ điều hành "chạy" khi nhận

được một ngắt

 Tiến trình hệ điều hành "chạy" khi chương trình sử dụng lời gọi hệ thống (system call)

Chế độ xử lý của tiến trình

 Hệ điều hành cần phải được bảo vệ

khỏi sự xâm phạm của các tiến trình

 Bản thân các tiến trình và dữ liệu cũng cần được bảo vệ để tránh các ảnh hưởng sai lạc lẫn nhau

Chế độ không đặc quyền và chế độ đặc quyền

Chế độ xử lý của tiến trình

 Khi một tiến trình người dùng gọi đến một lời gọi hệ thống, tiến trình của hệ điều hành xử lý lời gọi này sẽ hoạt động trong chế độ đặc quyền

 Hoàn tất thì trả quyền điều khiển về cho tiến trình

người dùng trong chế độ không đặc quyền.

Xử lý ngắt

4.1.2. Trạng thái và chuyển trạng

thái tiến trình

 Trong quá trình sống, một tiến trình thay đổi trạng thái

 Trạng thái của tiến trình tại một thời điểm được xác định bởi hoạt động hiện thời của tiến trình tại thời điểm đó

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

 Trạng thái khởi tạo/new hay giữ chỗ/hold: Tiến trình được khởi tạo và chấp nhận bởi hệ thống

 Trạng thái sẵn sàng/ready: Các tài nguyên khác đã sẵn sàng và tiến trình chỉ còn đợi được phân phối CPU

 Trạng thái thực thi/running: Tiến trình thực thi

 Trạng thái đợi/waiting hay khóa/blocked: Tiến trình đang đợi một sự kiện và không thể thực thi ngay

 Trạng thái hoàn tất/finish/kết thúc/exit:

Tiến trình kết thúc hoàn tất việc thực thi

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

 Tại một thời điểm, chỉ có một tiến trình có thể nhận trạng thái running trên một bộ xử lý bất kỳ. Trong khi đó, nhiều tiến trình có thể ở trạng thái blocked hay ready

Chuyển trạng thái tiến trình

Chuyển trạng thái tiến trình

 Các cung chuyển tiếp trong sơ đồ trạng thái biễu diễn sự chuyển trạng thái có thể xảy ra trong các điều kiện sau :

 Tiến trình mới tạo được đưa vào hệ thống

 Bộ điều phối cấp phát cho tiến trình một khoảng thời gian sử dụng CPU

 Tiến trình kết thúc

 Tiến trình yêu cầu một tài nguyên nhưng chưa được đáp ứng vì tài nguyên chưa sẵn sàng để cấp phát tại thời điểm đó ; hoặc tiến trình phải chờ một sự kiện hay thao tác nhập/xuất.

 Bộ điều phối chọn một tiến trình khác để cho xử lý .

 Tài nguyên mà tiến trình yêu cầu trở nên sẵn sàng để cấp phát ; hay sự kiện hoặc thao tác nhập/xuất tiến trình đang đợi hoàn tất.

Các bộ lập lịch

 Bộ lập lịch chương trình/cấp cao: Lập lịch dài hạn:

 Sắp xếp các chương trình theo một thứ tự dựa trên đặc tính của các chương trình đó sao cho các chương trình đó có thể sử dụng được nguồn tài nguyên hệ thống một cách triệt để nhất có thể.

 Bộ lập lịch tiến trình/CPU/cấp thấp: Lập lịch ngắn hạn:

 Lựa chọn tiến trình nào sẽ được cấp phát CPU

khi tiến trình đó ở trong hàng đợi sẵn sàng

Chuyển đổi giữa các trạng thái

 Khởi tạo sang sẵn sàng: Được quyết định bởi bộ lập lịch chương trình.

 Sẵn sàng sang thực thi: Được quyết định bởi bộ lập lịch tiến trình, có đủ CPU

 Thực thi sang sẵn sàng:Ngắt

 Thực thi sang khóa: Tiến trình đợi một sự kiện xảy ra, cho phép các tiến trình khác có thể sử dụng CPU

 Khóa sang sẵn sàng: Sự kiện được chờ đợi đã hoàn tất, đánh thức tiến trình đợi.

Chuyển đổi ngữ cảnh (context

switch)

• Chuyển đổi việc thực thi tiến trình này sang thực thi tiến trình khác.

 Chuyển đổi ngữ cảnh cần có Khối thông tin trạng thái điều khiển tiến trình PCB

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

(PCB)

 Là cấu trúc dữ liệu/thông tin được hệ điều hành tạo ra nhằm lưu thông tin trạng thái cho mỗi tiến trình.

 Thông tin định danh cho tiến trình (PID, UID)

 Thông tin trạng thái cho tiến trình (biến trạng thái)

 Ngữ cảnh của tiến trình:

 Giá trị các thanh ghi của CPU mà tiến trình sử

dụng (PC)

 Không gian nhớ (địa chỉ vùng nhớ) tiến trình sử

dụng

 Danh sách các tập tin tiến trình sử dụng

 V...v

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

 Thông tin giao tiếp: Các thông tin về quan hệ của tiến trình với các tiến trình khác trong hệ thống

 Tiến trình cha: tiến trình tạo lập tiến trình này .

 Tiến trình con: các tiến trình do tiến trình này tạo lập

.

 Độ ưu tiên : giúp bộ điều phối có thông tin để lựa chọn tiến trình được cấp CPU.

 Thông tin thống kê về hoạt động của tiến trình

 Thời gian đã sử dụng CPU,

 Thời gian chờ.

Các thông tin này có thể có ích cho công việc đánh giá tình hình hệ thống và dự đoán các tình huống tương lai.

PCB

HĐH khởi tạo và kết thúc tiến

trình

 Tạo tiến trình mới

 Thêm một mục trong danh sách các tiến trình mà nó quản lý (Process table)

 Cấp phát một vùng nhớ dành cho khối thông tin mô tả tiến trình/ khối điều khiển tiến

trình (PCB_Process Control Block).

 Cấp phát đoạn (segment) bộ nhớ dành cho mã, dữ liệu và ngăn xếp của tiến trình.

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

 Các tài nguyên được giải phóng khi hủy các tiến trình

4.1.3 Các thuật toán lập lịch tiến

trình

 Mục tiêu:

 Sự công bằng ( Fairness) : không có tiến trình nào phải chờ đợi vô hạn để được cấp phát CPU

 Tính hiệu qủa (Efficiency) :Hệ thống phải tận dụng được CPU 100% thời gian.

 Thời gian đáp ứng hợp lý (Response time) : Cực tiểu hoá thời gian hồi đáp cho các tương tác của người sử dụng

 Thời gian lưu lại trong hệ thống ( Turnaround Time) : Cực tiểu hóa thời gian hoàn tất các tác vụ xử lý theo lô.

 Thông lượng tối đa (Throughput ) : Cực đại hóa số công việc được xử lý trong một đơn vị thời gian.

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

tiến trình

 FCFS (First Come-First Server): Tiến trình nào nằm trong hàng đợi sẵn sàng lâu nhất thì sẽ được lựa chọn

 RR (Round Robin):

 FCFS được sử dụng khi lựa chọn một tiến trình kế tiếp được thực thi.

 Mỗi tiến trình chỉ được thực thi trong một khoảng thời gian tối đa.

 SJF( Shortest Job First) còn được gọi là SJN hoặc SPN: Tiến trình có thời gian phục vụ ngắn nhất sẽ được lựa chọn

 SRT (Shortest Remain Time): Tiến trình có thời gian thực thi còn lại ít nhất sẽ được lựa chọn

 HRRN (Highest Response Ratio Next): Tiến trình có tỉ lệ

thời gian chờ/thời gian thực thi cao nhất sẽ được lựa chọn

4.1.4 Kỹ thuật điều độ tiến

trình

 Giúp hệ điều hành tổ chức việc sử dụng tài nguyên khác một cách hợp lý khi nhiều tiến trình cùng yêu cầu tới một tài nguyên.

 Ví dụ

 Ba lớp

 Phương pháp khóa trong

 Kiểm tra xác lập

 Đèn báo

Tham khảo (Giáo trình cơ sở chuyên ngành Hệ điều hành, Nguyễn ThanhTùng, đại học Bách Khoa, Hà Nội)

4.2.Quản lý bộ nhớ

Memory management

4.2.1 Dịch và biên tập chương trình chạy

4.2.2 Tổ chức bộ nhớ

4.2.3 Tổ chức trong máy IBM PC

4.2.1 Dịch và biên tập chương

trình chạy

 Dịch chương trình ngôn ngữ thuật toán  chương

trình ngôn ngữ máy dưới dạng các modul độc lập

 Liên kết các modul theo các cấu trúc khác nhau tùy theo yêu cầu tạo thành chương trình hoàn thiện (lưu trong bộ nhớ ngoài)

 Tải chương trình từ bộ nhớ ngoài vào bộ nhớ trong, thực hiện phép ánh xạ địa chỉ logic sang địa chỉ vật lý cụ thể của bộ nhớ định vị chương trình

 Chế độ bộ nhớ thực: Kích thước chương trình < kích

thước bộ nhớ vật lý

 Chế độ bộ nhớ ảo: Kích thước chương trình > kích

thước bộ nhớ vật lý

4.2.2 Tổ chức bộ nhớ

4.2.2.1

Phân

chương

cố định

4.2.2.2 Phân chương động

4.2.2.3 Phân đoạn

4.2.2.4 Phân trang

4.2.2.5 Phân trang - đoạn

4.2.2.1 Phân chương cố định

 Bộ nhớ chia làm n phần không bằng nhau (n chương) dành cho n chương trình chạy song song

 Chương trình nạp toàn bộ vào một chương và tồn tại cho tới khi kết thúc

 Nhược điểm

 ∑bộ nhớ tự do > Kích thước chương trình nhưng không thực thi được do phân đoạn

 Kích thước chương trình

>Kích thước max của một

chương

 Kích thước chương trình <

kích thước bộ nhớ vật lý

 Phân lại bộ nhớ

4.2.2.2 Phân chương động

 HĐH phân phối đủ dung lượng nhớ cho nhu cầu của từng chương trình.

 Chương trình nạp toàn bộ vào một chương và tồn tại cho tới khi kết thúc

 Nhược điểm

 Phân mảnh bộ nhớ sau một thời gian

 Kích thước chương trình <kích thước bộ nhớ vật lý

 Sắp xếp lại bộ nhớ

4.2.2.3 Phân đoạn

 Chương trình được phân thành nhiều modul, các modul được nạp khi cần thiết và không nhất thiết phải liên tục

 Bảng quản lý phân đoạn SCB (Segment Control Block

 1 phần tử tương ứng với

1 modul (D:dấu hiệu;

A: địa chỉ; L: kích

thước )

 Địa chỉ SCB = Rs

 Địa chỉ truy nhập dữ liệu

(s:d)

4.2.2.3 Phân đoạn

 Kiểm tra modul đã được nạp hay chưa :

 Phần tử thứ s trong SCB = Rs + s

 D = 0  Xin cấp phát dung lượng nhớ L, định vị modul s, cập nhật D = 1 và A = địa chỉ vật lý của đoạn/modul trong bộ nhớ

 Truy nhập dữ liệu (đọc/ghi) bằng địa chỉ (A + d)

 Ưu điểm:

 Không đòi hỏi công cụ tổ chức đặc biệt nên có thể áp dụng trên máy bất kỳ

 Nhược điểm:

 Gây phân đoạn ngoài

 Cần phân bố lại bộ nhớ: chọn modul để đưa ra bộ nhớ

ngoài.

 Đưa ra modul tồn tại lâu nhất trong bộ nhơ

 Đưa ra modul có số lần sử dụng cuối cùng cách đây lâu

nhất

 Đưa ra modul có tần suất sử dụng thấp nhất

4.2.2.4 Phân trang

 Chương trình và bộ nhớ được chia thành các trang có kích thước bằng nhau, các trang của chương trình được nạp khi cần thiết và không nhất thiết phải liên tục

 Bảng quản lý phân trang

PCB (Page Control Block)

 Một phần tử của PCB xác lập quan hệ một trang vật lý và một trang logic((D: trường dấu hiệu; A: thông tin/ địa chỉ)

 Địa chỉ dầu PCB: Rp

 Địa chỉ truy nhập dữ liệu

(s:p)

4.2.2.4 Phân trang

 Kiểm tra trang đã được nạp hay chưa

 Phần tử thứ p trong PCB = Rp + p

 Nếu D = 0  định vị trang chương trình p vào trang vật lý f, cập nhật D = 1 và A = địa chỉ vật lý của trang trong bộ nhớ

 Truy nhập dữ liệu (đọc/ghi) bằng địa chỉ (A

ghép với d)

 Ưu điểm

 Không xảy ra hiện tượng phân đoạn ngoài trong bộ

nhớ

 Nhược điểm

 Hiệu quả của phương pháp phụ thuộc vào cách nạp trang và thay thế trang

  Dành nhiều không gian cho PCB

4.2.2.4 Phân trang

 Chiến lược nạp trang:

 Nạp tất cả các trang của chương trình ngay từ đầu

 Nạp trang trước thông qua việc dự báo trang cần thiết sắp tới cho chương trình

 Nạp trang theo yêu cầu Hiệu quả nếu phân bố trang hợp lý

 Chiến lược thay trang: đưa ra bộ nhớ những trang không dùng tới khi bộ nhớ bị thiếu. Các trang này càng được it dùng lại càng tốt.

 Vòng tròn

 Ngẫu nhiên

 FIFO( First In First Out): Nạp trước thì thay thế trước

 LRU (Last Recently Used): Đưa ra trang có lần sử dụng cuối cùng cách đây lâu nhất

 LFU (Least Frequently Used): Đưa ra trang có tần suất sử dụng thấp nhất

4.2.2.5 Phân trang-đoạn

 Chương trình được phân thành các đoạn/modul và được quản lý bởi bảng SCB. Mỗi đoạn được chia thành các trang và được quản lý bời PCB của từng đoạn.

 Phần tử của SCB (D: dấu hiệu, A: địa chỉ của

PCBi đã được nạp , L: kích thước PCBi)

 Địa chỉ đầu của SCB được đưa vào thanh ghi Rs

 Địa chỉ truy nhập dữ liệu (s,p,d)

4.2.2.5 Phân trang đoạn

 Truy nhập dữ liệu

 Phần tử s của SCB = Rs + s

 D = 0 nạp PCBi vào bộ nhớ trong, cập nhật D = 1, A =địa chỉ của PCBi

 Phần tử p trong PCBi = A + p

 Đọc/ ghi dữ liệu (nếu Dp = 1) qua địa chỉ

(Ap ghép d)

4.2.3 Tổ chức bộ nhớ trong

máy IBM-PC

 Tham khảo sách

Giáo trình cơ sở chuyên ngành Hệ điều hành, Nguyễn Thanh Tùng, Đại học Bách Khoa Hà Nội (trang 35- trang 52)

Chỉ mục

 System Call: Lời gọi hệ thống

 PCB (Process Control Block): Khối điều khiển tiến trình

 Schedular: Bộ lập lịch

 Context switch: Chuyển đổi ngữ cảnh

 SCB (Segment Control Block): Bảng quản lý phân đoạn

 PCB (Page Control Block): Bảng quản lý phân trang