Giáo trình Hệ điều hành (Operating Systems) (Phần 2)

Nội dung text: Giáo trình Hệ điều hành (Operating Systems) (Phần 2)

1. CHƯƠNG 4 QUẢN LÝ BỘ NHỚ Chương “QUẢN LÝ BỘ NHỚ" sẽ giới thiệu và giải thích các vấn đề sau: 4.1 Các vấn đề phát sinh khi quản lý bộ nhớ. 4.2 Các mô hình cấp phát bộ nhớ. 4.3 Bộ nhớ ảo 4.1 CÁC VẤN ĐỀ PHÁT SINH KHI QUẢN LÝ BỘ NHỚ + Chuyển đổi địa chỉ tương đối trong chương trình thành địa chỉ thực trong bộ nhớ chính. + Quản lý bộ nhớ đã cấp phát và chưa cấp phát. + Các kỹ thuật cấp phát bộ nhớ sao cho: - Ngăn chặn các tiến trình xâm phạm đến vùng nhớ đã được cấp phát cho tiến trình khác. - Cho phép nhiều tiến trình có thể dùng chung một phần bộ nhớ của nhau. - Mở rộng bộ nhớ để có thể lưu trữ được nhiều tiến trình đồng thời. 4.1.1 Chuyển đổi địa chỉ tương đối sang tuyệt đối Các địa chỉ trong chương trình thực thi (dạng exe) là địa chỉ tương đối, và cần được chuyển đổi các địa chỉ này thành các địa chỉ tuyệt đối trong bộ nhớ chính. Việc chuyển đổi có thể xảy ra vào một trong những thời điểm sau: + Thời điểm biên dịch (compile time): Nếu tại thời điểm biên dịch, có thể biết vị trí mà tiến trình sẽ được nạp vào trong bộ nhớ, trình biên dịch có thể phát sinh ngay mã với các địa chỉ tuyệt đối. Tuy nhiên, nếu về sau có sự thay đổi vị trí của chương trình, cần phải biên dịch lại chương trình. Ví dụ các chương trình .com chạy trên hệ điều hành MS-DOS có mã tuyệt đối ngay khi biên dịch. + Thời điểm nạp (load time): Nếu tại thời điểm biên dịch, chưa thể biết vị trí mà tiến trình sẽ được nạp vào trong bộ nhớ, trình biên dịch chỉ phát sinh mã tương đối. Khi nạp chương trình vào bộ nhớ, hệ điều hành sẽ chuyển các địa chỉ tương đối thành địa chỉ tuyệt đối do đã biết vị trí bắt đầu lưu trữ tiến trình. Khi có sự thay đổi vị trí lưu trữ, cần nạp lại chương trình để thực hiện lại việc chuyển đổi địa chỉ, không cần OPEN.PTIT.EDU.VNbiên dịch lại chương trình. + Thời điểm xử lý (execution time): Nếu có nhu cầu di chuyển tiến trình từ vùng nhớ này sang vùng nhớ khác trong quá trình tiến trình xử lý, thì việc chuyển đổi địa chỉ sẽ được thực hiện vào lúc tiến trình thực thi. Chức năng chuyển đổi địa chỉ do phần cứng cung cấp gọi là MMU (memory management unit). Các hệ điều hành thường dùng việc chuyển đổi theo cách này. 101
2. 4.1.2 Không gian địa chỉ ảo và không gian địa chỉ vật lý + Địa chỉ ảo (địa chỉ logic): là địa chỉ do bộ xử lý (CPU) tạo ra. + Địa chỉ vật lý (địa chỉ physic): là địa chỉ thực trong bộ nhớ chính, địa chỉ vật lý còn gọi là địa chỉ tuyệt đối/địa chỉ thực. + Không gian địa chỉ ảo của tiến trình: là tập hợp tất cả các địa chỉ ảo của một tiến trình. + Không gian điạ chỉ vật lý của tiến trình: là tập hợp tất cả các địa chỉ vật lý tương ứng với các địa chỉ ảo. Khi chương trình nạp vào bộ nhớ các địa chỉ tương đối trong chương trình được CPU chuyển thành địa chỉ ảo, khi thực thi, địa chỉ ảo được hệ điều hành kết hợp với phần cứng MMU chuyển thành địa chỉ vật lý .Tóm lại chỉ có khái niệm địa chỉ ảo nếu việc chuyển đổi địa chỉ xảy ra vào thời điểm xử lý, khi đó tiến trình chỉ thao tác trên các địa chỉ ảo, địa chỉ vật lý chỉ được xác định khi thực hiện truy xuất bộ nhớ vật lý. Hình 4.1: CPU gởi địa chỉ ảo tới MMU, MMU chuyển địa chỉ ảo thành địa chỉ vật lý 4.1.3 Quản lý bộ nhớ đã cấp phát và chưa cấp phát Hệ điều hành cần lưu trữ thông tin về phần bộ nhớ đã cấp phát và phần bộ nhớ chưa cấp phát. Nếu đã cấp phát thì cấp cho tiến trình nào. Khi cần cấp phát bộ nhớ cho một tiến trình thì làm sao tìm được phần bộ nhớ trống thích hợp nhanh chóng và khi bộ nhớ bị phân mảnh thì cần dồn bộ nhớ lại để tận dụng bộ nhớ và để tiến trình thực thi nhanh hơn. 4.1.3.1 Các phương pháp quản lý việc cấp phát bộ nhớ: a/ Sử dụng dãy bit : bít thứ i bằng 1 là khối thứ i đã cấp phát, bằng 0 là chưa cấp phát. b/ Sử dụng danh sách liên kết: mỗi nút của danh sách liên kết lưu thông tin một vùng nhớ chứa OPEN.PTIT.EDU.VNtiến trình (P) hay vùng nhớ trống giữa hai tiến trình (H). 102
3. Hình 4.2: quản lý việc cấp phát bộ nhớ bằng dãy bit hoặc danh sách liên kết Trước khi tiến trình X kết thúc, có 4 trường hợp có thể xảy ra và khi tiến trình X kết thúc, hệ điều hành cần gom những nút trống gần nhau. Hình 4.3: các trường hợp có thể xảy ra trước khi tiến trình X kết thúc 4.1.3.2 Các thuật toán chọn một đoạn trống: + First-fit: chọn đoạn trống đầu tiên đủ lớn. + Best-fit: chọn đoạn trống nhỏ nhất nhưng đủ lớn để thỏa mãn nhu cầu. + Worst-fit : chọn đoạn trống lớn nhất. 4.2 CÁC MÔ HÌNH CẤP PHÁT BỘ NHỚ Có hai mô hình dùng để cấp phát bộ nhớ cho một tiến trình là: + Cấp phát liên tục: tiến trình được nạp vào một vùng nhớ liên tục. + Cấp phát không liên tục: tiến trình được nạp vào một vùng nhớ không liên tục 4.2.1 Mô hình cấp phát liên tục OPEN.PTIT.EDU.VNCó hai mô hình cấp phát bộ nhớ liên tục là mô hình Linker-Loader hoặc mô hình Base & Limit. 4.2.1.1 Mô hình Linker_Loader: Chương trình được nạp vào một vùng nhớ liên tục đủ lớn để chứa toàn bộ chương trình. Hệ điều hành sẽ chuyển các địa chỉ tương đối về địa chỉ tuyệt đối (địa chỉ vật lý ) ngay khi nạp chương trình, theo công thức: địa chỉ tuyệt đối = địa chỉ bắt đầu nạp tiến trình + địa chỉ tương đối. 103
4. Ví dụ: xét chương trình P.EXE có lệnh Jump 0X200, . Giả sử chương trình được nạp tại địa chỉ 0X300, khi đó địa chỉ tương đối 0X200 sẽ được chuyển thành địa chỉ vật lý là 0X300+0X200=0X500 P.EXE 0X3000 0X6000 JUMP JUMP (bound) 0X2000 0X5000 0X0000 0X3000 (base) HĐH Bộ nhớ vật lý Hình 4.4: Một ví dụ về chuyển đổi địa chỉ tương đối thành địa chỉ vật lý trong mô hình linker- loader Chương trình khi nạp vào bộ nhớ cho thực thi thì gọi là tiến trình, vậy trường hợp này các địa chỉ trong tiến trình là địa chỉ tuyệt đối, còn địa chỉ trong chương trình là địa chỉ tương đối. Nhận xét: + Vì việc chuyển đổi địa chỉ chỉ thực hiện vào lúc nạp nên sau khi nạp không thể di chuyển tiến trình trong bộ nhớ + Do không có cơ chế kiểm soát địa chỉ mà tiến trình truy cập, nên không thể bảo vệ một tiến trình bị một tiến trình khác truy xuất bộ nhớ của tiến trình một cách trái phép. 4.2.1.2 Mô hình Base & Limit Giống như mô hình Linker-Loader nhưng phần cứng cần cung cấp hai thanh ghi, một thanh ghi nền (base register) và một thanh ghi giới hạn (limit register). Khi một tiến trình được cấp phát vùng nhớ, hệ điều hành cất vào thanh ghi nền địa chỉ bắt đầu của vùng nhớ cấp phát cho tiến trình, và cất vào thanh ghi giới hạn kích thước của tiến trình. OPEN.PTIT.EDU.VN Hình 4.5: một ví dụ về mô hình base&limit Khi tiến trình thực thi, mỗi địa chỉ ảo (địa chỉ ảo cũng chính là địa chỉ tương đối) sẽ được MMU so sánh với thanh ghi giới hạn để bảo đảm tiến trình không truy xuất ngoài phạm vi vùng nhớ 104
5. được cấp cho nó. Sau đó địa chỉ ảo được cộng với giá trị trong thanh ghi nền để cho ra địa chỉ tuyệt đối trong bộ nhớ. Hình 4.6: cơ chế MMU trong mô hình base&limit Nhận xét: + Có thể di chuyển các chương trình trong bộ nhớ vì do tiến trình được nạp ở dạng địa chỉ ảo, khi tiến trình được di chuyển đến một vị trí mới, hệ điều hành chỉ cần nạp lại giá trị cho thanh ghi nền, và việc chuyển đổi địa chỉ được MMU thực hiện vào thời điểm xử lý. + Có thể có hiện tượng phân mảnh ngoại vi (external fragmentation ): tổng vùng nhớ trống đủ để thoả mãn yêu cầu, nhưng các vùng nhớ này lại không liên tục nên không đủ để cấp cho một tiến trình khác. Có thể áp dụng kỹ thuật “dồn bộ nhớ “ (memory compaction ) để kết hợp các mảnh bộ nhớ nhỏ rời rạc thành một vùng nhớ lớn liên tục, tuy nhiên kỹ thuật này đòi hỏi nhiều thời gian xử lý. Ví dụ về sự phân mảnh ngoại vi của bộ nhớ, các tiến trình liên tục vào ra bộ nhớ, sau một thời gian sẽ để lại các vùng nhớ nhỏ mà không thể chứa bất kỳ tiến trình nào. D D D D D C C E E E B B B B B B B A A A A A A F OS OS OS OS OS OS OS OS Hình 4.7: một ví dụ về sự phân mảnh ngoại vi trong mô hình cấp phát liên tục * Vấn đề nảy sinh khi kích thước của tiến trình tăng trưởng trong qúa trình xử lý mà không còn vùng nhớ trống gần kề để mở rộng vùng nhớ cho tiến trình. Có hai cách giải quyết: + Dời chỗ tiến trình: di chuyển tiến trình đến một vùng nhớ khác đủ lớn để thỏa mãn nhu cầu tăng trưởng của tiến trình. OPEN.PTIT.EDU.VN+ Cấp phát dư vùng nhớ cho tiến trình : cấp phát dự phòng cho tiến trình một vùng nhớ lớn hơn yêu cầu ban đầu của tiến trình. 105
6. Hình 4.8: dành chỗ trống để tiến trình có thể phát triển trong mô hình cấp phát liên tục + Tiến trình luôn được lưu trữ trong bộ nhớ suốt quá trình xử lý của nó nên tính đa chương của hệ điều hành sẽ bị hạn chế bởi kích thước bộ nhớ và kích thước của các tiến trình trong bộ nhớ. Cách giải quyết là khi tiến trình bị khóa (đợi tài nguyên, đợi một sự kiện, ) hoặc tiến trình sử dụng hết thời gian CPU dành cho nó, nó có thể được chuyển tạm thời ra bộ nhớ phụ (đĩa, ) và sau này được nạp trở lại vào bộ nhớ chính để tiếp tục xử lý (kỹ thuật swapping). Để tránh tình trạng bộ nhớ bị phân mảnh vì do phải cấp phát một vùng nhớ liên tục cho tiến trình, hệ điều hành có thể cấp phát cho tiến trình những vùng nhớ tự do bất kỳ, không cần liên tục. 4.2.2 Mô hình cấp phát không liên tục Có ba mô hình cấp phát bộ nhớ không liên tục là mô hình phân đoạn, mô hình phân trang và mô hình phân đoạn kết hợp phân trang. 4.2.2.1 Mô hình phân đoạn (Segmentation) Một chương trình được người lập trình chia thành nhiều phân đoạn, mỗi phân đoạn có ngữ nghĩa khác nhau và hệ điều hành có thể nạp các phân đọan vào bộ nhớ tại các vị trí không liên tục. Ví dụ: chương trình chia làm 5 phân đoạn (segment), mỗi phân đoạn được nạp vào vùng nhớ OPEN.PTIT.EDU.VNtrống có thể không liên tục. 106
7. Hình 4.9: mô hình phân đoạn trong kỹ thuật cấp phát bộ nhớ không liên tục * Cơ chế MMU trong kỹ thuật phân đoạn: Khi chương trình được nạp vào bộ nhớ, MMU ghi các vị trí lưu trữ và kích thước các phân đoạn vào bảng phân đoạn còn CPU làm nhiệm vụ chuyển đổi tất cả các địa chỉ tương đối trong chương trình thành địa chỉ ảo. Phần tử thứ s trong bảng phân đoạn gồm hai phần (base, limit), base là địa chỉ vật lý bắt đầu phân đoạn s, limit là chiều dài của phân đoạn s. Mỗi địa chỉ ảo gồm hai phần (s,d) với s là số hiệu phân đoạn , d là địa chỉ tương đối trong phân đoạn s. Để chuyển địa chỉ ảo (s,d) thành địa chỉ vật lý, MMU truy xuất phần tử thứ s trong bảng phân đoạn, lấy được giá trị limit và base của phân đoạn s, sau đó kiểm tra điều kiện (d<limit), nếu sai thì thông báo lỗi “ truy xuất địa chỉ không hợp lệ”, nếu đúng thì tính điạ chỉ vật lý theo công thức: đcvl =base + d. Theo ví dụ trên, giả sử tiến trình truy xuất địa chỉ ảo (s,d)=(4,1500) thì MMU sẽ thông báo lỗi!. Nếu tiến trình truy xuất địa chỉ ảo (4,100) thì MMU sẽ chuyển thành địa chỉ vât lý là 4700+100=4800. OPEN.PTIT.EDU.VN 107
8. Hình 4.10: cơ chế MMU trong mô hình phân đoạn * Cài đặt bảng phân đoạn: Có thể sử dụng các thanh ghi để lưu trữ bảng phân đoạn nếu có ít phân đoạn. Nếu chương trình có nhiều phân đoạn, bảng phân đoạn phải được lưu trong bộ nhớ chính. Phần cứng cần cung cấp một thanh ghi nền STBR (Segment Table Base Register) để lưu địa chỉ bắt đầu của bảng phân đoạn và một thanh ghi STLR lưu số phân đoạn (Segment Table Limit Register) mà chương trình sử dụng. Với một địa chỉ logic (s,d), trước tiên số hiệu phân đoạn s được kiểm tra tính hợp lệ (s<STLR). Kế tiếp, cộng giá trị s với STBR (STBR+s) để có được địa chỉ của phần tử thứ s trong bảng phân đoạn và điạ chỉ vật lý cuối cùng là (base + d) OPEN.PTIT.EDU.VN Hình 4.11: cơ chế MMU trong mô hình phân đoạn. sử dụng thanh ghi STLR và STBR * Bảo vệ phân đoạn 108
9. Vì mỗi phân đoạn do người lập trình xác định và người lập trình biết được một phân đoạn chứa những gì bên trong, do vậy họ có thể chỉ định các thuộc tính bảo vệ thích hợp cho mỗi phân đoạn. Khi đó mỗi phần tử của bảng phân đoạn cần có thêm một thành phần gọi là thuộc tính bảo vệ. MMU sẽ kiểm tra giá trị của thuộc tính này để ngăn chặn các thao tác xử lý bất hợp lệ đến phân đoạn. Giá trị của thuộc tính có thể là R (chỉ đọc), X (thực thi), W (ghi), Limit Base Attribute Hình 4.12: Cấu trúc một phần tử trong bảng phân đoạn có sử dụng thuộc tính bảo vệ * Chia sẻ phân đoạn Muốn hai tiến trình dùng chung một phân đoạn nào đó, MMU chỉ cần gán hai phần tử trong hai bảng phân đoạn của hai tiến trình cùng giá trị. Hình 4.13: hai tiến trình P1,P2 dùng chung phân đoạn 0 (phân đoạn editor) + Nhận xét Trong hệ thống sử dụng kỹ thuật phân đoạn , hiện tượng phân mảnh ngoại vi vẫn xảy ra khi các khối nhớ trống đều quá nhỏ, không đủ để chứa một phân đoạn. Ưu điểm của kỹ thuật phân đoạn là mã chương trình và dữ liệu được tách riêng thành những không gian địa chỉ độc lập nên dễ dàng bảo vệ mã chương trình và dễ dàng dùng chung dữ liệu hoặc hàm. 4.2.2.2 Mô hình phân trang (Paging) Bộ nhớ vật lý được chia thành các khối có kích thước cố định và bằng nhau gọi là khung trang OPEN.PTIT.EDU.VN(page frame). Không gian địa chỉ ảo cũng được chia thành các khối có cùng kích thước với khung trang và gọi là trang (page). Khi một tiến trình được đưa vào bộ nhớ để xử lý, các trang của tiến trình sẽ được cất vào những khung trang còn trống, như vậy một tiến trình kích thước N trang sẽ cần N khung trang trống. 109
10. Hình 4.14: không gian địa chỉ ảo đựoc chia thành nhiều trang và lưu vào các khung trang Ví dụ mỗi khung trang 1KB, một tiến trình 3.5KB sẽ được chia làm 4 trang. Gỉa sử trang 0 được cất ở khung trang 5, trang 1 ở khung trang 7, Page 3 7 Page 1 7168 3 2 Page 2 6 6144 2 0 Page 1 5 Page 0 5120 1 7 Page 0 4 4096 0 5 Không 3 3072 Bảng gian địa 2 Page 3 2048 trang chỉ ảo 1 1024 0 Page 2 0000 Không gian địa chỉ vật lý Hình 4.15: sử dụng bảng trang để lưu các số hiệu khung trang chứa trang. * Cấu trúc địa chỉ ảo: Để dễ dàng phân tích địa chỉ ảo thành số hiệu trang và địa chỉ tương đối, phần cứng qui định kích OPEN.PTIT.EDU.VNthước của trang là lũy thừa của 2n (9<=n<= 13). Nếu kích thước của không gian địa chỉ ảo là 2m (CPU dùng địa chỉ ảo m bít) và kích thước trang là 2n thì m-n bit cao của địa chỉ ảo sẽ biễu diễn số hiệu trang, và n bit thấp biễu diễn địa chỉ tương đối trong trang. Khi đó mỗi địa chỉ ảo m bit sẽ có dạng (p,d) với p chiếm m-n bit và p là số hiệu trang, d chiếm n bit và là địa chỉ tương đối trong trang p. địa chỉ ảo dạng (p,d) có m bit p là số hiệu trang và chiếm m-n bit cao d là địa chỉ tương đối trong trang và chiếm n bít thấp 110
11. Hình 4.16: cấu trúc địa chỉ ảo gồm hai phần: các bit cao lưu số hiệu trang, các bit thấp lưu địa chỉ tương đối trong trang. * Cơ chế MMU trong mô hình phân trang: Khi chương trình được nạp vào bộ nhớ, MMU ghi nhận lại số hiệu khung trang chứa trang vào bảng trang (pages table), còn CPU làm nhiệm vụ chuyển đổi tất cả các địa chỉ tương đối trong chương trình thành địa chỉ ảo. Phần tử thứ p trong bảng trang lưu số hiệu khung trang trong bộ nhớ vật lý đang chứa trang p. Để chuyển địa chỉ ảo (p,d) thành địa chỉ vật lý, MMU truy xuất phần tử thứ p trong bảng trang, lấy được giá trị f là số hiệu khung trang chứa trang p và từ đó tính được điạ chỉ vật lý = vị trí bắt đầu của khung trang f + d. Địa chỉ ảo Địa chỉ vật lý Bộ p d f d CPU nhớ vật lý p f Hình 4.17: cơ chế MMU trong mô hình phân trang Theo ví dụ trên, giả sử tiến trình truy xuất địa chỉ ảo (p,d) = (3,500), MMU sẽ truy xuất phần tử thứ 3 trong bảng trang và biết được trang 3 ở khung trang 2 và chuyển địa chỉ ảo thành địa chỉ vât lý là 2x 210 +500 = 2548 (2x 210 = 2048 là địa chỉ bắt đầu của khung trang 2). Trong thực tế, việc chuyển đổi địa chỉ ảo (p,d) được MMU thực hiện như sau: MMU truy xuất phần tử thứ p trong bảng trang, lấy được giá trị f là số hiệu khung trang chứa trang p và tính điạ chỉ vật lý bằng cách chép d vào n bit thấp của địa chỉ vật lý và chép f vào (m-n) bit cao của địa chỉ vật lý. Ví dụ: Một hệ thống có địa chỉ ảo 16 bit dạng (p,d) với p có 4 bít, d có 12 bít (hệ thống có 16 trang, mỗi trang 4 KB) . Bít Present/absent =1 nghĩa là trang hiện ở trong bộ nhớ và =0 là ở bộ nhớ phụ. Xét địa chỉ ảo 819610 = 0010.0000.0000.01002 => p = 00102 = 210 , d = 0000.0000.01002 = 410 . 12 Do trang p=2 ở khung trang f=1102 = 610 , nên địa chỉ vật lý là 0110.0000.0000.01002 = 6x2 + 4 OPEN.PTIT.EDU.VN= 24580 111
12. Hình 4.18: cơ chế chuyển đổi địa chỉ của MMU * Cài đặt bảng trang Nếu bảng trang có kích thước nhỏ có thể dùng một tập các thanh ghi để cài đặt bảng trang. Nếu bảng trang có kích thước lớn, cần phải được lưu trữ trong bộ nhớ chính, và phần cứng cung cấp một thanh ghi PTBR (Page Table Base Register) lưu địa chỉ bắt đầu của bảng trang và thanh ghi PTLR (Page Table Limit Register) lưu số phần tử trong bảng trang.Với một địa chỉ logic (p,d), trước tiên số hiệu trang p được kiểm tra tính hợp lệ (p<PTLR). Kế tiếp, cộng giá trị p với PTBR (PTBR+s) để có được địa chỉ của phần tử thứ p trong bảng phân đoạn và MMU truy xuất phần tử thứ p trong bảng trang, lấy được giá trị f là số hiệu khung trang chứa trang p và từ đó tính được điạ chỉ vật lý = vị trí bắt đầu của khung trang f + d. OPEN.PTIT.EDU.VN Hình 4.19: cơ chế MMU trong mô hình phân trang, sử dụng hai thanh ghi PTLR và PTBR 112
13. * Bộ nhớ kết hợp (Translation Lookaside Buffers:TLBs) Trong kỹ thuật phân trang, mỗi lần truy xuất đến dữ liệu hay chỉ thị đều cần hai lần truy xuất bộ nhớ: một cho truy xuất đến bảng trang để tìm số hiệu khung trang và một cho bản thân dữ liệu. Có thể giảm bớt việc truy xuất bộ nhớ hai lần bằng cách sử dụng thêm bộ nhớ kết hợp (TLBs). Bộ nhớ kết hợp có tốc độ truy xuất rất nhanh và cho phép tìm kiếm song song. Mỗi thanh ghi trong bộ nhớ kết hợp gồm một từ khóa và một giá trị, khi đưa đến bộ nhớ kết hợp một từ khoá cần tìm, từ khoá này sẽ được so sánh cùng lúc với các từ khóa trong bộ nhớ kết hợp để tìm ra giá trị tương ứng. Trong kỹ thuật phân trang, TLBs được sử dụng để lưu trữ các số hiệu trang được truy cập gần hiện tại nhất. Khi tiến trình truy xuất một địa chỉ ảo, số hiệu trang của địa chỉ sẽ được so sánh với các số hiệu trang trong TLBs, nếu tìm thấy thì sẽ xác định được ngay số hiệu khung trang tương ứng, nếu không có thì mới cần tìm kiếm trong bảng trang. Hình 4.20: cơ chế MMU trong mô hình phân trang có sử dụng bộ nhớ kết hợp. Hình 4.21: một ví dụ về bảng trang có thuộc tính bảo vệ (protection) và thuộc tính cập nhật (modified): 1 là mời đựoc cập nhật, 0 là chưa cập nhật. OPEN.PTIT.EDU.VNVí dụ một hệ thống máy tính 32 bit, có kích thước 1 khung trang là 4K. Hỏi hệ thống quản lý được tiến trình kích thước tối đa là bao nhiêu? HD: Máy tính 32 bit => địa chỉ ảo (p,d) có 32 bit => số bít của p + số bít của d = 32, mà 1 trang 4K=212 bytes => d có 12 bit =>p có 20 bit => 1 bảng trang có 220 phần tử => hệ thống quản lý được tiến trình có tối đa 220 trang => kích thước tiến trình lớn nhất là 220 x 212 byte = 232 byte =4 GB. Nhận xét: Máy tính n bit quản lý được tiến trình kích thước lớn nhất là 2n byte. 113
14. * Tổ chức bảng trang Thông thường hệ điều hành cấp cho mỗi tiến trình một bảng trang và phải dùng bảng trang kích thước đủ lớn để quản lý tiến trình lớn nhất nên rất tốn bộ nhớ. Có ba giải pháp cho vấn đề này là sử dụng phân trang đa cấp hoặc bảng trang băm hoặc bảng trang nghịch đảo. a/ Phân trang đa cấp Bản thân bảng trang cũng sẽ được phân trang. Xét trường hợp phân trang nhị cấp, khi đó bảng trang cấp 1 lưu số hiệu khung trang chứa bảng trang cấp 2, các bảng trang cấp 2 lưu số hiệu khung trang tiến trình sử dụng. Thông thường trong phân trang đa cấp mỗi bảng trang chiếm 1 khung trang, riêng bảng trang cấp 1 có thể lưu trữ trên đĩa và có thể có kích thước lớn hơn 1 khung trang. Hình 4.22: một ví dụ về phân trang nhị cấp. Nếu một máy tính 32 bít, với kích thước trang 4K thì địa chỉ logic có thể biểu diễn như sau: dùng p=20 bít lưu số hiệu trang, d=12 bít lưu vị trí tương đối trong trang. Nếu dùng bảng trang nhị cấp thì p được chia ra thành p1, p2 (p=p1+p2): p1=10 bít lưu chỉ mục của bảng trang cấp 1, p2=10 bít lưu chỉ mục của bảng trang cấp 2 (việc phân chia p1, p2 là bao nhiêu bít thì do phần cứng qui định). Ta có: BTC1[p1] lưu số hiệu khung trang chứa bảng trang cấp 2, BTC2[p2] lưu số hiệu khung trang chứa trang của tiến trình. page number page offset pi p2 d 10 10 12 p1 chỉ mục của bảng trang cấp một. p2 chỉ mục của bảng trang cấp 2 OPEN.PTIT.EDU.VN Hình 4.23: cấu trúc của một địa chỉ ảo trong phân trang nhị cấp Bảng trang cấp 1 114 Bảng trang cấp 2
15. Hình 4.24: cơ chế chuyển đổi địa chỉ trong bảng trang nhị cấp. b/ Bảng trang băm Khi không gian địa chỉ ảo lớn (> 32 bít) thường hệ điều hành dùng bảng băm để lưu trữ bảng trang. Gỉa sử trang p, lưu ở khung trang r, thì thông tin này được lưu trữ như sau: p được băm và lưu trữ trong một danh sách xung đột tương ứng của bảng băm. Ví dụ: Một máy tính 64 bít, có RAM 256MB, kích thước 1 khung trang là 4KB. Bảng trang thông thường phải có 252 mục, nếu dùng bảng trang băm có thể sử dụng bảng có số mục bằng số khung trang vật lý là 216 (<<232) với hàm băm là hasfunc(p)=p mod 216. Hình 4.25: sử dụng bảng băm để lưu trữ bảng trang Khi tìm khung trang chứa trang p, hệ điều hành dùng hàm băm tìm ra danh sách chứa trang p, sau đó tìm tuyến tính trên danh sách này để tìm ra khung trang chứa trang p. OPEN.PTIT.EDU.VN 115
16. Hình 4.26: cơ chế chuyển đổi địa chỉ khi sử dụng bảng trang băm c/ Bảng trang nghịch đảo Hệ điều hành có thể dùng một bảng trang duy nhất để quản lý bộ nhớ của tất cả các tiến trình và gọi là bảng trang nghịch đảo. Mỗi phần tử của bảng trang nghịch đảo là cặp (pid, p), pid là mã số của tiến trình, p là số hiệu trang và mỗi địa chỉ ảo là một bộ ba (pid, p, d). Khi một truy xuất bộ nhớ được phát sinh, một phần địa chỉ ảo là (pid, p) được đưa đến cho trình quản lý bộ nhớ để tìm phần tử tương ứng trong bảng trang nghịch đảo, nếu tìm thấy tại phần tử thứ i, thì i chính là số hiệu khung trang chứa trang p và địa chỉ vật lý tương ứng là (i,d). Trong các trường hợp khác, xem như đã truy xuất một địa chỉ bất hợp lệ. Nhận xét: số phần tử trong bảng trang nghịch đảo bằng với số khung trang vật lý Hình 4.27: cơ chế chuyển đổi địa chỉ khi sử dụng bảng trang nghịch đảo * Bảo vệ trang Cơ chế bảo vệ trong hệ thống phân trang được thực hiện với các bit bảo vệ (protection) được lưu trong mỗi phần tử của bảng trang, vì mỗi truy xuất đến bộ nhớ đều phải tham khảo đến bảng trang để phát sinh địa chỉ vật lý, khi đó, hệ thống có thể kiểm tra các thao tác truy xuất trên khung trang tương ứng có hợp lệ với thuộc tính bảo vệ của nó không. Ngoài ra, có thể thêm một số bít khác với các mục đích khác nhau. OPEN.PTIT.EDU.VN Hình 4.28: cấu trúc tổng quát của một phần tử trong bảng trang 116
17. Hình 4.29: một ví dụ về mô hình phân trang * Chia xẻ bộ nhớ: Trong kỹ thuật phân trang, hệ điều hành cũng có thể cho phép các tiến trình dùng chung một số khung trang, bằng cách ghi cùng số hiệu khung trang vào bảng trang của mỗi tiến trình. ví dụ: Hai tiến trình P1, P2 sinh ra từ chương trình word.exe có thể dùng chung đoạn code (gồm 3 trang) nhưng mỗi tiến trình có đoạn data riêng. 7 6 code3 3 data1 3 0 3 data2 3 4 5 2 code3 2 6 2 code3 2 6 4 data2 1 code2 1 3 1 code2 1 3 3 code2 0 code1 0 2 0 code1 0 2 2 code1 P1 Bảng trang P2 Bảng trang 1 P1 P2 0 data1 Bộ nhớ Vật lý Hình 4.30: hai tiến trình P1,P2 dùng chung ba trang 0,1,2 Nhận xét: + Kỹ thuật phân trang loại bỏ được hiện tượng phân mảnh ngoại vi vì mỗi khung trang đều có thể được cấp phát cho một tiến trình nào đó có yêu cầu. Tuy nhiên hiện tượng phân mảnh nội vi vẫn OPEN.PTIT.EDU.VNcó thể xảy ra khi kích thước của tiến trình không đúng bằng bội số của kích thước một trang, khi đó trang cuối cùng sẽ không được sử dụng hết. + Sự phân trang không phản ánh đúng cách thức người sử dụng cảm nhận về bộ nhớ. Kỹ thuật phân đoạn thỏa mãn được nhu cầu thể hiện cấu trúc logic của chương trình nhưng nó dẫn đến tình huống phải cấp phát các khối nhớ có kích thước khác nhau cho các phân đoạn. Điều này làm rắc rối vấn đề hơn rất nhiều so với việc cấp phát các trang có kích thước cố định và bằng nhau. Một 117
18. giải pháp dung hoà là kết hợp cả hai kỹ thuật phân trang và phân đoạn: chúng ta tiến hành phân trang các phân đoạn. 4.2.2.3 Mô hình phân đoạn kết hợp phân trang (Paged segmentation) Một tiến trình gồm nhiều phân đoạn, mỗi phân đoạn được chia thành nhiều trang, lưu trữ vào các khung trang có thể không liên tục. Hình 4.31: mô hình phân đoạn kết hợp phân trang * Cơ chế MMU trong mô hình phân đoạn kết hợp phân trang Mỗi địa chỉ logic là một bộ (s,d) với s là số hiệu phân đoạn, d là địa chỉ tương đối trong phân đoạn. Tách d thành p và d' (số bít của d = số bít của p + số bít của d’) với p là chỉ số trang, d' là địa chỉ tương đối trong trang (số bít của d' do phần cứng qui định). Để chuyển các địa chỉ ảo 2 chiều thành địa chỉ vật lý một chiều, MMU dùng một bảng phân đoạn, mỗi phân đoạn cần có một bảng phân trang tương ứng. Mỗi phần tử trong bảng phân đoạn gồm hai phần (base,limit), base lưu địa chỉ vật lý nơi bắt đầu của bảng trang của phân đoạn này, limit lưu chiều dài của phân đoạn. Hệ thống cần cung cấp một thanh ghi STBR lưu vị trí bắt đầu của bảng phân đoạn, khi tiến trình truy xuất một địa chỉ logic (s,d)=(s,p,d’), MMU lấy STBR cộng với s để truy xuất phần tử thứ s trong bảng phân đọan. Phần tử thứ s của bảng phân đoạn lưu hai gía trị (segment length, page-table base): segment length là kích thước phân đoạn, page-table base là vị trí lưu trữ bảng trang tương ứng với phân đoạn s. Nếu segment length <d thì thông báo “truy xuất địa chỉ không hợp lệ” ngược lại phân tích d thành p và d’ và cộng page-table base với p để truy xuất phần tử thứ p trong bảng phân trang lấy được giá trị f là số hiệu khung trang chứa trang OPEN.PTIT.EDU.VNp. Sau đó cộng f với d’ sẽ cho địa chỉ vật lý tương ứng. 118
19. Hình 4.32: cấu trúc một phần tử của bảng trang trong mô hình phân đoạn kết hợp phân trang. Hình 4.33: cơ chế chuyển đổi địa chỉ trong mô hình phân đoạn kết hợp phân trang Hình 4.34: hệ điều hành MULTICS dùng phân đoạn kết hợp phân trang và bộ nhớ kết hợp Nhận xét: + Tất cả các mô hình tổ chức bộ nhớ trên đây đều có khuynh hướng cấp phát cho tiến trình toàn bộ các trang yêu cầu trước khi thật sự xử lý. Vì bộ nhớ vật lý có kích thước rất giới hạn, điều này dẫn đến hai điểm bất tiện sau : OPEN.PTIT.EDU.VN+ Kích thước tiến trình bị giới hạn bởi kích thước của bộ nhớ vật lý. + Khó nâng cao mức độ đa chương của hệ thống. 4.3 BỘ NHỚ ẢO Bộ nhớ ảo là kỹ thuật dùng bộ nhớ phụ lưu trữ tiến trình, các phần của tiến trình được chuyển vào-ra giữa bộ nhớ chính và bộ nhớ phụ để cho phép thực thi một tiến trình mà không cần nạp 119
20. toàn bộ vào bộ nhớ vật lý. Với kỹ thuật bộ nhớ ảo, hệ điều hành sẽ tăng được mức độ đa chương của hệ thống, có thể thực thi được những chương trình kích thước rất lớn so với kích thước bộ nhớ vật lý và người lập trình không cần quan tâm máy tính có đủ RAM để thực thi chương trình hay không. Có hai phương pháp cài đặt kỹ thuật bộ nhớ ảo đó là phân trang theo yêu cầu (Demand paging) hoặc phân đoạn theo yêu cầu (Demand segmentation) 4.3.1 Phân trang theo yêu cầu (Demand paging) Một tiến trình được chia thành nhiều trang, thường trú trên bộ nhớ phụ (thường là đĩa cứng) và một trang chỉ được nạp vào bộ nhớ chính khi có yêu cầu. Vùng không gian đĩa dùng để lưu trữ tạm các trang gọi là không gian swapping. 4.3.1.1 Cấu trúc một phần tử trong bảng trang Mỗi phần tử trong bảng trang sẽ gồm hai trường: Một trường chứa bit "kiểm tra" có giá trị 1 (valid) là trang đang ở trong bộ nhớ chính , 0 (invalid) là trang đang được lưu trên bộ nhớ phụ hoặc trang không thuộc tiến trình, khởi đầu tất cả bit kiểm tra trong bảng trang đều bằng 0. Một trường chứa số hiệu khung trang (nếu bit kiểm tra là valid) hoặc chứa địa chỉ của trang trên bộ nhớ phụ (nếu bit kiểm tra là invalid). Hình 4.35: mô hình phân trang theo yêu cầu 4.3.1.2 Chuyển địa chỉ ảo (p,d) thành địa chỉ vật lý + Bước 1: MMU truy xuất phần tử thứ p trong bảng trang để lấy các thông tin cần thiết cho việc OPEN.PTIT.EDU.VNchuyển đổi địa chỉ. + Bước 2: Nếu phần tử thứ p có bit kiểm tra bằng 1 (valid), thì trang đang yêu cầu truy xuất hợp lệ, tức là có sẵn trong bộ nhớ, khi đó việc chuyển đổi địa chỉ ảo thành địa chỉ vật lý xảy ra bình thường, địa chỉ vật lý = số hiệu khung trang * kích thước của một khung + d. Nếu phần tử thứ p có bit kiểm tra bằng 0 (invalid), thì MMU sẽ phát sinh một ngắt để báo cho hệ điều hành có “lỗi 120
21. trang”. Khi đó hệ điều hành sẽ kiểm tra trang truy xuất có thuộc tiến trình không, nếu trang không thuộc tiến trình thì hệ điều hành kết thúc tiến trình, ngược lại chuyển đến bước 3 + Bước 3: Tìm vị trí trên đĩa chứa trang muốn truy xuất và tìm một khung trang trống trong bộ nhớ chính: nếu có khung trang trống thì đến bước 4, nếu không còn khung trang trống, chọn một khung trang "nạn nhân" (victim) và chuyển trang "nạn nhân " ra bộ nhớ phụ , rồi đến bước 4 + Bước 4: Chuyển trang muốn truy xuất từ bộ nhớ phụ vào khung trang trống đã chọn. + Bước 5: Cập nhật nội dung bảng trang. + Bước 6: Tái kích hoạt tiến trình người sử dụng. Hình 4.36: cơ chế chuyển đổi địa chỉ trong mô hình phân trang theo yêu cầu 4.3.1.3 Thay thế trang Nếu không có khung trang trống, thì mỗi khi xảy ra lỗi trang cần phải thực hiện hai thao tác chuyển trang : chuyển một trang ra bộ nhớ phụ và nạp một trang khác vào bộ nhớ chính. Có thể giảm bớt số lần chuyển trang bằng cách sử dụng thêm một bit "cập nhật" (dirty bit). Giá trị của bit được phần cứng đặt là 1 nếu nội dung trang có bị sửa đổi. Khi cần thay thế một trang, nếu bit cập nhật có giá trị là 1 thì trang này cần được lưu lại trên đĩa, ngược lại, nếu bit cập nhật là 0, nghĩa là trang không bị thay đổi, thì không cần lưu trữ trang trở lại đĩa. số hiệu khung trang chứa trang bit nhận diện trang có trong bộ bit nhận diện trang có hoặc địa chỉ trên đĩa của trang nhớ (bit valid-invalid) thay đổi (bit dirty) Hình 4.37: cấu trúc một phần tử của bảng trang trong kỹ thuật phân trang theo yêu cầu. 4.3.1.4 Thời gian thực hiện một yêu cầu truy xuất bộ nhớ Gọi xác suất xảy ra lỗi trang là p: 0 ≤ p ≤ 1.0, nếu p = 0 nghĩa là không có lỗi trang , nếu p = 1 OPEN.PTIT.EDU.VNnghĩa là mỗi lần truy xuất đều xảy ra lỗi. Memory access (ma) là thời gian một lần truy xuất bộ nhớ. Effective Access Time (EAT) là thời gian thực hiện một yêu cầu truy xuất bộ nhớ. Page fault overhead (pfo) là thời gian xử lý một lỗi trang. Swap page in (spi) là thời gian chuyển trang từ đĩa vào bộ nhớ. Swap page out (spo) là thời gian chuyển trang ra đĩa (swap page out có thể bằng 0). Restart overhead (ro) là thời gian tái khởi động lại việc truy xuất bộ nhớ. Ta có: 121
22. EAT = (1 – p) x ma+ p (pfo+ [spo]+ spi+ ro) Ví dụ: Giả sử thời gian một lần truy xuất bộ nhớ là 1 micro second và giả sử 40% trang được chọn đã thay đổi nội dung và thời gian hoán chuyển trang ra/vào là 10 mili second . Tính ETA. Ta có: ma=1 micro second spo= spin = 10 milisecond = 10000 micro second => EAT = (1 – p) + p (pfo+10000*0.4+10000+ro) micro second 4.3.1.5 Các thuật toán chọn trang nạn nhân Mục tiêu của các thuật tóan là chọn trang «nạn nhân» là trang mà sau khi thay thế sẽ gây ra ít lỗi trang nhất. Thông thường số lỗi trang tỉ lệ nghịch với số khung trang dành cho tiến trình (số khung trang tăng thì số lỗi trang giảm). Hình 4.38: biểu đồ minh họa số lỗi trang sẽ giảm khi số khung trang dành cho tiến trình tăng Có thể đánh giá thuật toán bằng cách xét một chuỗi các trang mà tiến trình sẽ lần lượt truy xuất với số khung trang cấp cho tiến trình đã biết và tính số lỗi trang phát sinh. Ví dụ tiến trình truy xuất các địa chỉ theo thứ tự : 0100, 0432, 0101, 0611. Nếu kích thước của một trang là 100 bytes thì có thể viết lại chuỗi địa chỉ thành chuỗi trang mà tiến trình truy xuất là 1, 4, 1, 6. 4.3.1.5.1 Thuật toán FIFO (First In First Out) Trang ở trong bộ nhớ lâu nhất sẽ được chọn làm trang nạn nhân (vào trước ra trước) Ví dụ: Một tiến trình được cấp 3 khung trang, ban đầu cả 3 khung đều trống, tiến trình lần lượt OPEN.PTIT.EDU.VNtruy xuất tới các trang theo thứ tự sau: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1. Tính số lỗi trang khi áp dụng thuật toán FIFO để chọn trang nạn nhân. 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 122
23. 7 7 7 2 2 2 24 4 4 0 0 00000777 0 0 0 0 3 3 3 2 2 2 2 21111100 1 1 1 1 0 0 0 3 3 3 3 3222221 * * * * * * * * * * * * * * * Kí hiệu * là có lỗi trang và có 15 lỗi trang Nhận xét: Không cần ghi nhận thời điểm trang được nạp vào bộ nhớ, mà chỉ cần quản lý các trang trong bộ nhớ bằng một danh sách FIFO, khi đó nếu có lỗi trang thì trang truy xuất được đưa vào cuối danh sách và nếu hết khung trang thì trang đầu danh sách sẽ được chọn làm trang nạn nhân. Thuật toán FIFO đơn giản, dễ cài đặt, nhưng nếu trang được chọn là trang thường xuyên được sử dụng, thì khi bị chuyển ra bộ nhớ phụ sẽ nhanh chóng gây ra lỗi trang. Số lượng lỗi trang có thể tăng lên khi số lượng khung trang sử dụng tăng, hiện tượng này gọi là nghịch lý Belady. Ví dụ: Xét tiến trình truy xuất chuỗi trang theo thứ tự sau: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 + Nếu sử dụng 3 khung trang, sẽ có 9 lỗi trang 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 4 4 4 5 5 5 5 5 5 2 2 2 1 1 1 1 1 3 3 3 3 3 3 2 2 2 2 2 4 4 * * * * * * * * * + Nếu sử dụng 4 khung trang, sẽ có 10 lỗi trang 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 1 1 1 5 5 5 5 4 4 2 2 2 2 2 2 1 1 1 1 5 3 3 3 3 3 3 2 2 2 2 OPEN.PTIT.EDU.VN 4 4 4 4 4 4 3 3 3 * * * * * * * * * * 4.3.1.5.2 Thuật toán tối ưu (Optimal Page Replacement Algorithm) Chọn trang lâu được sử dụng nhất trong tương lai. Ví dụ: 123
24. 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 * * * * * * * * * Nhận xét: Có 9 lỗi trang, FIFO 15 lỗi => tốt hơn FIFO nhiều. Thuật toán này bảo đảm số lượng lỗi trang phát sinh là thấp nhất, nó cũng không bị nghịch lý Belady, tuy nhiên đây là một thuật toán khó cài đặt vì thường không thể biết trước chuỗi truy xuất của tiến trình. Đối với các hệ điều hành cho thiết bị gia dụng, thường chỉ có một số tiến trình cố định thực thi nên có thể cho tiến trình chạy trước một lần, ghi nhận lại chuỗi trang truy xuất, các lần thực thi sau đó có thể sử dụng thuật toán tối ưu để chọn trang nạn nhân. 4.3.1.5.3 Thuật toán LRU ( Least-recently-used) Thuật toán FIFO sử dụng thời điểm nạp trang để chọn trang thay thế, thuật toán tối ưu dùng thời điểm trang sẽ được sử dụng gần nhất trong tương lai. Vì thời điểm này thường khó xác định trước nên thuật toán LRU sẽ dùng thời điểm cuối cùng trang được truy xuất (dùng quá khứ gần để dự đoán tương lai gần). Với mỗi trang, ghi nhận thời điểm cuối cùng trang được truy cập, trang được chọn để thay thế sẽ là trang lâu nhất chưa được truy xuất vì với suy nghĩ là trang này có khả năng ít được sử dụng nhất. Ví dụ: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 24 4 4 0 0 01111111 0 0 0 0 0 00 0 3 3 3 33300000 1 1 1 3 33 2 2 2 2 22222777 * * * * * * * * * * * * Nhận xét: OPEN.PTIT.EDU.VNCó 12 lỗi trang, FIFO 15 lỗi =>LRU tốt hơn FIFO. OPT và LRU có số lỗi trang không đổi khi nghịch đảo chuỗi địa chỉ truy xuất. * Cài đặt thuật toán LRU: có thể dùng hai kỹ thuật sau + Sử dụng bộ đếm: 124
25. Thêm vào cấu trúc của mỗi phần tử trong bảng trang một trường ghi nhận “thời điểm truy xuất gần nhất”, và thêm vào cấu trúc của CPU một thanh ghi đếm (counter). Mỗi lần thực hiện truy xuất đến một trang, giá trị của counter tăng lên 1 và ghi giá trị counter vào trường “thời điểm truy xuất gần nhất” của phần tử tương ứng với trang trong bảng trang. Khi đó trang “nạn nhân” là trang có giá trị trường “thời điểm truy xuất gần nhất” là nhỏ nhất. số hiệu khung trang chứa trang bit valid - bit dirty thời điểm truy xuất gần nhất hoặc địa chỉ trang trên đĩa invalid + Sử dụng danh sách liên kết : Dùng một một dslk lưu trữ các số hiệu trang, trang ở cuối danh sách là trang được truy xuất gần nhất, và trang ở đầu danh sách là trang lâu nhất chưa được sử dụng. Nếu có lỗi trang và nếu có khung trang trống thì thêm nút chứa số hiệu trang đang truy xuất vào cuối danh sách, nếu không có khung trống thì trang được chọn làm trang nạn nhân sẽ là trang ở đầu danh sách, khi đó hủy nút đầu và thêm nút chứa số hiệu trang đang truy xuất vào cuối danh sách. Nếu không có lỗi trang thì chuyển nút chứa số hiệu trang hiện hành xuống cuối danh sách. 4.3.1.5.4 Các thuật toán xấp xỉ LRU Có ít hệ thống được cung cấp đủ các phần cứng hỗ trợ để cài đặt thuật toán LRU thật sự. Tuy nhiên, nhiều hệ thống được trang bị thêm một bit tham khảo (reference). Mỗi phần tử trong bảng trang có thêm bit reference được khởi gán là 0 bởi hđh và được phần cứng gán là 1 mỗi lần trang tương ứng được truy cập. Sau mỗi chu kỳ qui định trước, phần cứng kiểm tra giá trị của các bit reference để xác định được trang nào đã được truy xuất đến và trang nào không, sau khi đã kiểm tra xong, các bit reference được phần cứng gán trở về 0. Với bit reference, có thể biết được trang nào đã được truy xuất, nhưng không biết được thứ tự truy xuất của các trang. Thông tin không đầy đủ này dẫn đến nhiều thuật toán xấp xỉ LRU khác nhau. số hiệu khung trang chứa trang hoặc bit valid-invalid bit dirty bit reference địa chỉ trang trên đĩa Hình 4.39: cấu trúc một phần tử của bảng trang trong thuật toán xấp xỉ LRU a/ Thuật toán với các bít history Mỗi trang sử dụng thêm 8 bit lịch sử (history). Sau từng khoảng thời gian nhất định (thường là 100 milliseconds), một ngắt đồng hồ được phát sinh và quyền điều khiển được chuyển cho hệ điều OPEN.PTIT.EDU.VNhành. Hệ điều hành sẽ cập nhật các bít history của mỗi trang bằng cách dịch các bit history sang phải 1 vị trí để loại bỏ bit thấp nhất và đặt bit reference của mỗi trang vào bit cao nhất trong 8 bit history của trang đó. 8 bit history sẽ lưu trữ tình hình truy xuất đến trang trong 8 chu kỳ cuối cùng. Nếu 8 bit history là 00000000 thì trang tương ứng có khả năng không được dùng trong 8 chu kỳ cuối, nếu 8 bit history là 11111111 thì trang tương ứng được dùng đến ít nhất 1 lần trong mỗi 8 chu kỳ cuối. Nếu xét 8 bit history như một số nguyên không dấu thì trang “nạn nhân” là trang có 125
26. giá trị history nhỏ nhất. Số lượng các bit history có thể thay đổi tùy theo phần cứng, số bít history nhiều thì việc chọn trang “nạn nhân” sẽ chính xác hơn. b/ Thuật toán cơ hội thứ hai Tìm một trang theo nguyên tắc FIFO, rồi kiểm tra bit reference của trang đó. Nếu bit reference là 0, chọn trang này, nếu bit reference là 1 thì gán lại là 0 rồi tìm trang FIFO tiếp theo (cho trang này một cơ hội thứ hai). Một trang đã được cho cơ hội thứ hai sẽ không bị thay thế cho tới khi tất cả những trang khác được thay thế hoặc được cho cơ hội thứ hai. Nếu trang thường xuyên được sử dụng, bit reference của nó sẽ duy trì được giá trị 1 và trang hầu như không bao giờ bị thay thế. Nếu tất cả các bít reference là 1 thì thuật toán trở thành FIFO. Thuật toán có thể cài đặt bằng dslk vòng. Hình 4.40: cơ chế chọn trang nạn nhân trong thuật toán chọn trang nạn nhân thứ hai. Ví dụ: 7 0 1 2 0 3 04 2 3 0 3 21201701 7 7 7 2 2 2 24 4 4 0 0 01111111 0 0 0 0 0 0 0 0 3 3 3 3 3 300000 1 1 1 3 3 3 2 2 2 2 22222777 * * * * * * * * * * * * OPEN.PTIT.EDU.VN Xem danh sách liên kết vòng của ví dụ trên 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7(1) 7(1) 7(1) 0(0) 1(0) 2(1) 2(1) 3(0) 0(0) 4(1) 2(0) 2(0) 0(1) 3(0) 3(0) 1(0) 2(1) 0(0) 1(0) 7(1) 126
27. 0(1) 0(1) 1(0) 2(1) 0(1) 3(1) 0(0) 4(1) 2(1) 3(0) 0(1) 3(1) 2(0) 1(0) 2(1) 0(1) 1(0) 7(1) 0(1) 1(1) 2(1) 0(1) 3(1) 0(1) 4(1) 2(1) 3(1) 0(1) 3(1) 2(1) 1(0) 2(1) 0(1) 1(1) 7(1) 0(1) 1(1) c/ Thuật toán cơ hội thứ hai nâng cao (Not Recently Used Page Replacement Algorithm: NRU) Xem các bit reference và dirty bit như một cặp có thứ tự và tạo thành 4 lớp sau : - Lớp 1 (0,0): gồm những trang có (ref,dirty)=(0,0). Những trang thuộc lớp này không được truy xuất gần đây và không bị sửa đổi, đây là những trang tốt nhất để thay thế. - Lớp 2 (0,1): trang không truy xuất gần đây nhưng đã bị sửa đổi. Trường hợp này không thật tốt, vì trang cần được lưu trữ lại trước khi thay thế. - Lớp 3 (1,0): trang được truy xuất gần đây, nhưng không bị sửa đổi. Trang có thể nhanh chóng được tiếp tục được sử dụng. - Lớp 4 (1,1): trang được truy xuất gần đây, và bị sửa đổi. Trang có thể nhanh chóng được tiếp tục được sử dụng và trước khi thay thế cần phải được lưu trữ lại. Lớp 1 có độ ưu tiên thấp nhất, và lớp 4 có độ ưu tiên cao nhất. Một trang sẽ thuộc về một trong bốn lớp trên và trang được chọn làm trang “nạn nhân” là trang đầu tiên tìm thấy trong lớp có độ ưu tiên thấp nhất. 4.3.1.5.5 Các thuật toán thống kê Sử dụng một biến đếm lưu số lần truy xuất đến một trang. + Thuật toán LFU (least frequently used): Thay thế trang có giá trị biến đếm nhỏ nhất, nghĩa là trang ít được sử dụng nhất. + Thuật toán MFU (most frequently used): Thay thế trang có giá trị biến đếm lớn nhất, nghĩa là trang được sử dụng nhiều nhất. 4.3.2 Cấp phát số lượng khung trang và thay thế trang Với mỗi tiến trình, cần phải cấp phát một số khung trang tối thiểu nào đó để tiến trình có thể hoạt động. Số khung trang tối thiểu này được quy định bởi kiến trúc của của một chỉ thị. Ví dụ máy IBM 370 để lệnh MOVE có thể thực hiện tối thiểu phải có hai trang: một trang from , một trang to. Khi một lỗi trang xảy ra trước khi chỉ thị hiện hành hoàn tất, chỉ thị đó cần được tái khởi động, lúc đó cần phải có đủ các khung trang để nạp tất cả các trang mà một chỉ thị cần sử dụng. Số khung trang tối thiểu được qui định bởi kiến trúc máy tính, trong khi số khung trang tối đa được xác định bởi dung lượng bộ nhớ vật lý có thể sử dụng. 4.3.2.1 Cấp phát số lượng khung trang OPEN.PTIT.EDU.VNCó ba cách cấp phát số lượng khung trang là: cấp phát ngang bằng, cấp phát theo tỉ lệ kích thước, cấp phát theo tỉ lệ độ ưu tiên. a/ Cấp phát ngang bằng: Nếu có m khung trang và n tiến trình, mỗi tiến trình được cấp m/n khung trang. Cấp phát này đơn giản nhưng không hiệu quả. 127
28. b/ Cấp phát theo tỷ lệ kích thước Tùy vào kích thước của tiến trình để cấp phát số khung trang. Gọi si là kích thước của tiến trình pi S = ∑si là tổng kích thước của tất cả tiến trình. m = số lượng khung trang có thể sử dụng Khi đó tiến trình pi sẽ được cấp phát ai khung trang S > m khung ai= si/ S x m si > ai =? ví dụ: có hai tiến trình, tiến trình 1= 10K, tiến trình 2=127K và có 62 khung trang trống. Khi đó có thể cấp cho tiến trình 1: 10/137 x 62 ~ 4 khung tiến trình 2: 127/137 x62 ~ 57 khung c/ Cấp phát theo tỷ lệ độ ưu tiên: Số lượng khung trang cấp cho tiến trình phụ thuộc vào độ ưu tiên của tiến trình. Tiến trình có độ ưu tiên cao sẽ được cấp nhiều khung hơn để tăng tốc độ thực hiện. 4.3.2.2 Thay thế trang Có hai cách thay thế trang: thay thế toàn cục và thay thế cục bộ a/ Thay thế toàn cục Chọn trang “ nạn nhân “ từ tập tất cả các khung trang trong hệ thống, khung trang đó có thể đang được cấp phát cho một tiến trình khác. Ví dụ có thể chọn trang của tiến trình có độ ưu tiên thấp hơn làm trang nạn nhân. Thuật toán thay thế toàn cục cho phép hệ thống có nhiều khả năng lựa chọn hơn, số khung trang cấp cho một tiến trình có thể thay đổi, nhưng các tiến trình không thể kiểm soát được tỷ lệ phát sinh lỗi trang của mình. b/ Thay thế cục bộ Chỉ chọn trang thay thế trong tập các khung trang được cấp cho tiến trình phát sinh lỗi trang, khi đó số khung trang cấp cho một tiến trình sẽ không thay đổi 4.3.3 Hệ thống trì trệ (thrashing) Khi tiến trình không có đủ các khung trang để chứa những trang cần thiết cho việc xử lý, thì nó sẽ thường xuyên phát sinh các lỗi trang, vì thế phải dùng đến rất nhiều thời gian sử dụng CPU để thực hiện thay thế trang. Hệ điều hành thấy hiệu quả sử dụng CPU thấp sẽ tăng mức độ đa OPEN.PTIT.EDU.VNchương, dẫn đến trì trệ toàn bộ hệ thống. Để ngăn cản tình trạng trì trệ này xảy ra, cần phải cấp cho tiến trình đủ các khung trang cần thiết để hoạt động. Vấn đề là làm sao biết được mỗi tiến trình cần bao nhiêu trang? 4.3.3.1 Mô hình tập làm việc (working set) 128
29. Tập làm việc của tiến trình tại thời điểm t là tập các trang được tiến trình truy xuất đến trong Δ lần truy cập cuối cùng tính tại thời điểm t. Hình 4.41: mô hình tập làm việc Gọi WSSi ( Δ , t) là số phần tử của tập working set của tiến trình Pi tại thời điểm t. m là số khung trang trống. D = ∑WSSi là tổng số khung trang yêu cầu cho toàn hệ thống . Hệ điều hành giám sát working set của mỗi tiến trình Pi và tại thời điểm t sẽ cấp phát cho tiến trình Pi số khung trang bằng với số phần tử trong tập làm việc (WSSi)(Δ, t-1). Nếu tổng số khung trang yêu cầu của các tiến trình trong hệ thống vượt quá các khung trang có thể sử dụng (D>m), thì sẽ xảy ra tình trạng hệ thống trì trệ. Khi đó hệ điều hành chọn một tiến trình để tạm dừng, giải phóng các khung trang của tiến trình đã chọn để các tiến trình khác có đủ khung trang hoàn tất công việc. 4.3.3.2 Cấu trúc chương trình Số lỗi trang có khi phụ thuộc vào ngôn ngữ lập trình, nên khi lập trình ta cần chú ý để chương trình có thể thực hiện nhanh hơn. Ví dụ: xét ct sau: int a[128][128]; for (i=0; i<128; i++) for (j=0; j<128; j++) a[i][j]=0; Gỉa sử trang có kích thước 128 bytes và tiến trình được cấp 2 khung trang: khung trang thứ nhất chưá mã tiến trình, khung trang còn lại được khởi động ở trạng thái trống . Trong Pascal, C mảng lưu theo hàng, mỗi hàng chiếm 1 trang bộ nhớ, nên số lỗi trang phát sinh là 128. Nhưng trong Fortran mảng lưu theo cột, do đó số lỗi trang sẽ là 128x128=1638. OPEN.PTIT.EDU.VN TÓM TẮT + Các vấn đề cần phải giải quyết khi quản lý bộ nhớ là việc chuyển đổi địa chỉ tương đối thành địa chỉ thực, quản lý bộ nhớ đã cấp phát và chưa cấp phát, các kỹ thuật cấp phát bộ nhớ. 129
30. + Việc chuyển đổi địa chỉ tương đối thành địa chỉ thực có thể xảy ra vào một trong những thời điểm sau: thời điểm biên dịch, thời điểm nạp, thời điểm xử lý. + Địa chỉ ảo là địa chỉ do bộ xử lý sinh ra, địa chỉ vật lý là địa chỉ thực trong bộ nhớ. Khi chương trình nạp vào bộ nhớ các địa chỉ tương đối trong chương trình được CPU chuyển thành địa chỉ ảo, khi thực thi, địa chỉ ảo được hệ điều hành kết hợp với phần cứng MMU chuyển thành địa chỉ vật lý . + Có hai phương pháp quản lý việc cấp phát bộ nhớ là sử dụng một dãy bit hoặc sử dụng một danh sách liên kết, mỗi nút của danh sách liên kết lưu thông tin một vùng nhớ chứa tiến trình hay vùng nhớ trống giữa hai tiến trình. + Để chọn một đoạn trống có thể sử dụng một trong các thuật toán sau :First-fit, Best-fit, Worst- fit + Có hai kỹ thuật dùng để cấp phát bộ nhớ cho một tiến trình là Cấp phát liên tục: tiến trình được nạp vào một vùng nhớ liên tục. Cấp phát không liên tục: tiến trình được nạp vào một vùng nhớ không liên tục + Có ba mô hình cấp phát bộ nhớ liên tục là mô hình Linker-Loader hoặc mô hình Base & Limit. Mô hình Linker-Loader: chương trình được nạp vào một vùng nhớ liên tục đủ lớn để chứa toàn bộ chương trình, hệ điều hành sẽ chuyển các địa chỉ tương đối về địa chỉ tuyệt đối ngay khi nạp chương trình. Mô hình Base & Limit giống như mô hình Linker-Loader nhưng phần cứng cần cung cấp hai thanh ghi, một thanh ghi nền và một thanh ghi giới hạn . Khi một tiến trình được cấp phát vùng nhớ, hệ điều hành cất vào thanh ghi nền địa chỉ bắt đầu của vùng nhớ cấp phát cho tiến trình, và cất vào thanh ghi giới hạn kích thước của tiến trình. + Có ba mô hình cấp phát bộ nhớ không liên tục là mô hình phân đoạn, mô hình phân trang và mô hình phân đoạn kết hợp phân trang. - Mô hình phân đoạn: một chương trình được người lập trình chia thành nhiều phân đoạn, mỗi phân đoạn có ngữ nghĩa khác nhau và hệ điều hành có thể nạp các phân đọan vào bộ nhớ tại các vị trí không liên tục và ghi các vị trí các phân đoạn vào bảng phân đoạn, đồng thời chuyển các địa chỉ tương đối trong chương trình thành các địa chỉ ảo. Mỗi địa chỉ ảo gồm hai phần (s,d): s là số hiệu phân đoạn , d là địa chỉ tương đối trong phân đoạn s. Mỗi phần tử trong bảng phân đoạn gồm hai phần (base, limit): base là địa chỉ vật lý bắt đầu phân đoạn, limit là chiều dài của phân đoạn. - Mô hình phân trang: Bộ nhớ vật lý được chia thành các khối có kích thước cố định và bằng nhau gọi là khung trang. Tiến trình cũng được chia thành các khối có cùng kích thước với khung trang và gọi là trang. Khi chương trình được nạp vào bộ nhớ, MMU ghi nhận lại số hiệu khung trang chứa trang vào bảng trang , CPU chuyển địa chỉ tương đối trong chương trình thành địa chỉ ảo. Mỗi địa chỉ ảo có dạng (p,d): p là số hiệu trang, d là địa chỉ tương đối trong trang p. Mỗi phần tử OPEN.PTIT.EDU.VNtrong bảng trang lưu số hiệu khung trang chứa trang. - Mô hình phân đoạn kết hợp phân trang: Một tiến trình gồm nhiều phân đoạn, mỗi phân đoạn được chia thành nhiều trang, lưu trữ vào các khung trang có thể không liên tục. + Bộ nhớ ảo là kỹ thuật dùng bộ nhớ phụ lưu trữ tiến trình, các phần của tiến trình được chuyển vào-ra giữa bộ nhớ chính và bộ nhớ phụ để cho phép thực thi một tiến trình mà không cần nạp 130
31. toàn bộ vào bộ nhớ vật lý. Có hai phương pháp cài đặt kỹ thuật bộ nhớ ảo đó là phân trang theo yêu cầu hoặc phân đoạn theo yêu cầu - Phân trang theo yêu cầu: Một tiến trình được chia thành nhiều trang, thường trú trên đĩa cứng và một trang chỉ được nạp vào bộ nhớ chính khi có yêu cầu. Nếu khi nạp trang mà không còn khung trang trống, chọn một khung trang "nạn nhân" và chuyển trang "nạn nhân " ra bộ nhớ phụ , rồi chuyển trang muốn truy xuất từ bộ nhớ phụ vào khung trang trống đã chọn. + Các thuật toán chọn trang nạn nhân: FIFO, tối ưu, LRU, các thuật toán xấp xỉ LRU CÂU HỎI VÀ BÀI TẬP 1. Giả sử có một hệ thống sử dụng kỹ thuật phân trang theo yêu cầu. Bảng trang được lưu trữ trong các thanh ghi. Để xử lý một lỗi trang tốn 8 miliseconds nếu có sẵn một khung trang trống, hoặc trang bị thay thế không bị sửa đổi nội dung, và tốn 20 miliseconds nếu trang bị thay thế bị sửa đổi nội dung. Mỗi truy xuất bộ nhớ tốn 100 nanoseconds. Giả sử trang bị thay thế có xác suất bị sửa đổi là 70%. Tỷ lệ phát sinh lỗi trang phải là bao nhiêu để có thể duy trì thời gian truy xuất bộ nhớ ( effective acess time) không vượt quá 200 nanoseconds? 2. Xét chương trình C sau : int A [100][100] ; for (i=0; i<100; i++) for (j=0; j<100; j++) A[i][j]= 0; Giả sử tiến trình được cấp 3 khung trang với kích thước một khung trang là 200 bytes, mã tiến trình luôn chiếm khung trang 1, khung trang 2 và 3 để lưu mảng A và khởi đầu khung 2, 3 là rỗng. Hỏi tiến trình có bao nhiêu lỗi trang khi sử dụng thuật toán thay thế LRU. Xét chương trình C sau với câu hỏi tương tự như trên int A [100][100] ; for (j=0; j<100; j++) for (i=0; i<100; i++) A[i][j]= 0; 3. Trong một hệ thống sử dụng kỹ thuật phân trang theo yêu cầu, kích thước mỗi trang là 2K , xét đoạn chương trình C sau đây: int n = 3*1024; int A[n], B[n]; for (i=0; i<n;i++) A[i]=i; for (i=0 ;i<n;i++) B[A[i]]=i; OPEN.PTIT.EDU.VNa) Nếu số khung cấp cho tiến trình là không hạn chế và giả sử khung trang thứ nhất luôn dùng để chưá tiến trình, các khung trang còn lại được khởi động ở trạng thái trống thì tiến trình có bao nhiêu lỗi trang. b) Nếu số khung cấp cho tiến trình là 2 khung và giả sử khung trang thứ nhất luôn dùng để chưá tiến trình, khung trang thứ hai được khởi động ở trạng thái trống thì tiến trình có bao nhiêu lỗi trang. 131
32. 4. Một máy tính có 4 khung trang. Thời điểm nạp, thời điểm truy cập cuối cùng, và các bit Reference (R), Dirty (D) của mỗi trang trong bộ nhớ được cho trong bảng sau : Trang Thời điểm Thời điểm R D nạp truy cập cuối cùng 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1 Trang nào sẽ được chọn thay thế theo : a) thuật toán NRU b) thuật toán FIFO c) thuật toán LRU d) thuật toán " cơ hội thứ 2" 5. Tính kích thước dãy bít dùng để quản lý RAM 512 MB, giả sử địa chỉ đánh theo byte. 6. Xét một không gian địa chỉ có 8 trang, mỗi trang có kích thước 1K, ánh xạ vào bộ nhớ vật lý có 32 khung trang. a) Địa chỉ logic gồm bao nhiêu bit ? b) Địa chỉ physic gồm bao nhiêu bit ? 7. Xét một hệ thống sử dụng kỹ thuật phân trang, với bảng trang được lưu trữ trong bộ nhớ chính. a) Nếu thời gian cho một lần truy xuất bộ nhớ bình thường là 200 nanoseconds, thì mất bao nhiêu thời gian cho một thao tác truy xuất bộ nhớ trong hệ thống này ? b) Nếu sử dụng TLBs với tỉ lệ tìm thấy (hit-ratio) là 75%, thời gian để tìm trong TLBs xem như bằng 0, tính thời gian truy xuất bộ nhớ trong hệ thống ( effective memory reference time) 8. Xét bảng phân đoạn sau: Segment Base Length OPEN.PTIT.EDU.VN1 2300 14 2 90 100 Cho biết địa chỉ vật lý tương ứng với các địa chỉ ảo sau đây : a. (1,10) b. (2,500) 132
33. 9. Một máy tính 32-bit địa chỉ, sử dụng một bảng trang nhị cấp. Địa chỉ ảo được phân bổ như sau: 9 bit dành cho bảng trang cấp 1, 11 bit cho bảng trang cấp 2, còn lại dành cho offset. Cho biết kích thước một trang trong hệ thống, và không gian địa chỉ ảo có bao nhiêu trang ? 10. Một máy tính có 48-bit địa chỉ ảo, và 32-bit địa chỉ vật lý, kích thước một trang là 8K. Có bao nhiêu phần tử trong một bảng trang thông thường và trong bảng trang nghịch đảo? 11. Giả sử có một máy tính đồ chơi sử dụng 7-bit địa chỉ, hệ thống sử dụng một bảng trang nhị cấp, dùng 2-bit làm chỉ mục đến bảng trang cấp 1, 2-bit làm chỉ mục đến bảng trang cấp 2. Xét một tiến trình sử dụng các địa chỉ ảo trong những phạm vi sau : 0 15, 21 29, 94 106, và 115 127. a) Vẽ chi tiết toàn bộ bảng trang cho tiến trình này b) Phải cấp phát cho tiến trình bao nhiêu khung trang, giả sử tất cả đều nằm trong bộ nhớ chính? c) Bao nhiêu bytes ứng với các vùng phân mảnh nội vi trong tiến trình này? d) Cần bao nhiêu bộ nhớ cho bảng trang của tiến trình này? 12. Giả sử có một máy tính sử dụng 16-bit địa chỉ. Bộ nhớ ảo được thực hiện với kỹ thuật phân đoạn kết hợp phân trang, kích thước tối đa của một phân đoạn là 4096 bytes. Bộ nhớ vật lý được phân thành các khung trang có kích thước 512 bytes. a) Thể hiện cách địa chỉ ảo được phân tích để phản ánh segment, page, offset b) Xét một tiến trình sử dụng các miền địa chỉ sau, xác định số hiệu segment và số hiệu page tương ứng trong segment mà chương trình truy cập đến : 350 1039, 3046 3904, 7100 9450, 33056 39200, 61230 63500 c) Bao nhiêu bytes ứng với các vùng phân mảnh nội vi trong tiến trình này? d) Cần bao nhiêu bộ nhớ cho bảng phân đoạn và bảng trang của tiến trình này ? TÀI LIỆU THAM KHẢO [1]. Gary J. Nutt, University of Colorado. Centralized And Distributed Operating Systems. Second Edition, 2000. [2]. Robert Switzer. Operating Systems, A Practical Approach. Prentice-Hall International, Inc. 1993. [3]. Andrew S. Tanenbaum. Modern Operating Systems. Prentice-Hall International, Inc. Second Edition, 2001. [4]. Abraham Silberschatz & Peter Baer Galvin. Operating System concepts. John Wiley & Sons, Inc. Fifth Edition, 1999. [5]. H. M. Deitel. Operating Systems. Addison-Wesley Inc. Second Edition, 1999. OPEN.PTIT.EDU.VN[6]. Trần Hạnh Nhi & Lê Khắc Nhiên Ân & Hoàng Kiếm. Giáo trình hệ điều hành (tập 1 & 2). ĐHKHTN 2000. 133
34. CHƯƠNG 5 QUẢN LÝ PROCESSOR Chương “QUẢN LÝ PROCESSOR" sẽ giới thiệu và giải thích các vấn đề sau: 5.1 Processor Vật lý và Processor logic 5.2 Ngắt và xử lý ngắt 5.3 Xử lý ngắt trong IBM-PC 5.1. PROCESSOR VẬT LÝ VÀ PROCESSOR LOGIC Trong lĩnh vực công nghệ thông tin, khái niệm bộ xử lý (processor) thường được gọi là đơn vị xử lý trung tâm (CPU-Central Processing Unit). CPU là một thành phần bên trong máy tính thực hiện công việc biên dịch các chỉ thị của máy tính và xử lý các dữ liệu bên trong các chương trình. Cùng với đơn vị lưu trữ chính, thiết bị nhập/xuất, CPU là thành phần cơ bản nhất không thể thiếu trong bất kỳ hệ thống máy tính nào. Để tăng tốc độ cho một hệ thống máy tính, ngoài việc sử dụng nhiều CPU, còn có một giải pháp khác – hyper threading (siêu phân luồng). Với kỹ thuật này, hệ điều hành sẽ nhìn thấy một processor vật lý thành hai processor logic. Processor vật lý là một thành phần phần cứng thực sự, thực hiện các thao tác do hệ điều hành và các chương trình đang thực thi trên máy tính ra lệnh. Trong khi đó, processor logic được tạo ra bởi các chương trình, tài nguyên hệ điều hành, hoặc là sự mô phỏng của processor vật lý. Một lý do khác để tạo ra processor logic là để tận dụng tối đa nguồn tài nguyên bên trong bộ xử lý đồng thời cho phép thực hiện tính toán cho nhiều tiểu trình hơn trong cùng một thời điểm. OPEN.PTIT.EDU.VNHình 5.1. Processor vật lý và processor logic Giả sử hệ thống có một CPU vật lý. Nếu CPU này không hỗ trợ kỹ thuật siêu phân luồng thì hệ điều hành chỉ nhìn thấy hệ thống có một CPU (vật lý) duy nhất. Ngược lại, nếu CPU này hỗ trợ kỹ thuật siêu phân luồng thì hệ điều hành sẽ cho rằng hệ thống này có hai CPU (logic). Hình 5.2 minh họa điều này khi thực hiện trên hai hệ thống được giả sử như trên. Khi đó, ở hình (b) ta sẽ 134
35. thấy có hai ô hình chữ nhật rời nhau để đo Performance cho từng CPU (logic). Trong khi đó, ở hình (a) chỉ có một CPU (vật lý) được đo Performance. Hình 5.2. Minh họa Performance của hệ thống có 1 CPU vật lý và hệ thống có 2 CPU logic 5.2. NGẮT VÀ XỬ LÝ NGẮT Ngắt là sự xảy ra của một điều kiện, sự kiện làm cho treo tạm thời chương trình trong khi đó điều kiện, sự kiện này được phục vụ bởi chương trình khác. Một hệ thống được điều khiển bằng ngắt cho ảo giác là nó thực hiện nhiều công việc đồng thời. Dĩ nhiên, CPU mỗi lần không thể thực thi nhiều hơn một lệnh; nhưng nó có thể tạm treo việc thực thi một chương trình để thực thi chương trình khác, rồi quay về chương trình thứ nhất. Cụ thể hơn, khi ngắt xảy ra, thì: + Hệ điều hành lấy được sự điều khiển. + Hệ điều hành lưu lại trạng thái của tiến trình bị ngắt. Trong nhiều hệ thống, các thông tin này được lưu trong khối điều khiển tiến trình của tiến trình bị ngắt. + Hệ điều hành phân tích ngắt và chuyển điều khiển đến một thủ tục tương ứng để thực hiện ngắt. + Thủ tục thực hiện ngắt tiến hành ngắt. OPEN.PTIT.EDU.VN+ Tiến trình bị ngắt được thực thi. 135
36. Địa chỉ Bộ nhớ 100 Chương trình CPU 101 chính Thủ tục ngắt: 102 - Xác định nguồn. - Cấm các ngắt khác? Input - Lưu lại nội dung các Ngắt A thanh ghi. - Link đến thủ tục ngắt. - Khôi phục lại các thanh ghi. 1000 Phục vụ ngắt A - Cho phép ngắt 1001 Các lệnh được thực - Quay lại chương hiện cho việc phục trình chính 1002 vụ ngắt A Quay lui Hình 5.3 Thủ tục ngắt Ngắt có thể được nạp từ một tiến trình đang thực thi, từ một sự cố có liên quan hoặc không liên quan đến tiến trình đang thực thi. Như ví dụ trong hình 5.11, CPU nhảy đến địa chỉ 1000 và thực thi chương trình ở đó. Và ở cuối thủ tục ngắt, một lệnh được khởi tạo để khôi phục lại trạng thái của các thanh ghi bị treo trong chương trình chính, nhờ đó nó cũng giúp khôi phục lại việc điều khiển cho chương trình gốc. Cấu trúc ngắt có thể khác nhau giữa các hệ thống, nhưng nhìn chung chúng đều thực hiện cùng một thủ tục ngắt như nhau. Dưới đây là một số yêu cầu mà một hệ thống ngắt phải đáp ứng được trước khi thực hiện ngắt: + Định nghĩa một tập các sự kiện có khả năng gây ra ngắt. + Có phương tiện để ghi lại các tình huống (ngữ cảnh) khi một ngắt xảy ra, thường là một hoặc một vài bit cờ (flag). + CPU phải thực hiện việc kiểm tra trạng thái ngắt theo thời gian định kỳ. Việc thiết lập và kiểm tra trạng thái các cờ ngắt thường được xử lý tự động bởi phần cứng với rất ít hoặc không có sự tham gia của CPU. + Hệ thống phải kiểm tra để xác định xem yêu cầu ngắt xuất phát từ đâu, và để quyết định có nên OPEN.PTIT.EDU.VNcấp CPU để đáp ứng yêu cầu ngắt đó hay không. + Xác định vị trí bên trong CPU, để lưu thông tin về nguyên nhân gây ra ngắt. + Nếu yêu cầu ngắt cần được đáp ứng, thì CPU phải nhảy đến chương trình hoặc thủ tục phục vụ ngắt tương ứng. + Bên trong hệ điều hành, các ngắt thường được sử dụng để truy xuất các dịch vụ của kernel (nhân của hệ điều hành). Việc thâm nhập vào kernel của một hệ điều hành có liên quan mật thiết 136
37. đến quá trình xử lý ngắt, một vài khả năng đáp ứng ngắt là yêu cầu tất yếu của kernel trong một hệ điều hành. Có ba loại ngắt được sử dụng trong một hệ điều hành như sau: a/ Ngắt giám sát (supervisor call interupt): là một loại ngắt đặc biệt, xảy ra khi một tiến trình phát ra một chỉ thị yêu cầu một thủ tục bên trong hệ điều hành. Sau đó, hệ điều hành có thể được xem như là một tập các chương trình hệ thống được liên kết với nhau để thực thi các tín hiệu ngắt. b/ Ngắt nội (internal interupt): hay còn gọi là ngắt mềm, được tạo ra bởi các sự kiện nào đó, bên trong bộ xử lý đang thực thi các sự kiện đó, chẳng hạn như khi một chương trình thực hiện sai chức năng (ví dụ như chương trình cố gắng chia một số cho 0). c/ Ngắt ngoại (external interupt): hay còn gọi là ngắt cứng, được tạo ra bên ngoài bộ xử lý đang xảy ra ngắt, thường là bởi các bộ xử lý khác hoặc các thiết bị nhập/xuất trong hệ thống. Mỗi loại ngắt có một thủ tục xử lý ngắt (interupt handler) để xử lý các yêu cầu ngắt tương ứng. Khi một thủ tục xử lý ngắt đọat được quyền điều khiển CPU, như minh họa trong hình 5.11, thông thường nó sẽ cấm tất cả các chỉ thị từ các ngắt khác cho đến khi nó đạt đến “điểm an toàn”. Điểm an toàn là vị trí mà thông tin trạng thái ngắt có thể được lưu và sẽ được khôi phục lại sau khi yêu cầu ngắt đã được đáp ứng. 5.2.1. Đồng hồ ngắt Để ngăn chặn những người sử dụng chiếm độc quyền hệ thống (chủ động hoặc bị động), hệ điều hành sẽ có các cơ chế để đòi lại CPU. Hệ điều hành cài một đồng hồ ngắt để ngắt các họat động chiếm giữ CPU trong một thời gian xác định. Khi CPU được trao cho một tiến trình, tiến trình đó được quyền điều khiển CPU cho đến khi nó chủ động trả lại CPU hoặc khi đồng hồ ngắt thực hiện ngắt. Nếu người sử dụng vẫn còn đang thực thi chương trình, và đồng hồ ngắt xảy ra việc ngắt giờ, thì việc ngắt này sẽ lấy quyền xử lý về lại cho hệ điều hành. Sau đó hệ điều hành sẽ quyết định tiến trình nào sẽ được nhận CPU tiếp theo. Đồng hồ ngắt giúp đảm bảo được thời gian hồi đáp hợp lý cho hệ thống đa người dùng, ngăn cản hệ thống bị treo khi có một người sử dụng đang thực thi một vòng lặp vô hạn. 5.2.2. Đa ngắt Những vấn đề chúng ta vừa nêu trên được áp dụng cho sự xuất hiện của một ngắt tại một thời điểm. Tuy nhiên, trong thực tế, một lúc có thể xảy ra nhiều ngắt. Chẳng hạn như, một chương trình có thể nhận dữ liệu từ bên ngoài vào và in ra kết quả tương ứng. Mỗi lần máy in chỉ thực hiện được một ngắt cho đến khi kết thúc hoạt động in. Bộ điều khiển bus sẽ thực hiện một ngắt mỗi khi có một đơn vị dữ liệu đến. Như vậy, ngắt điều khiển bus cho phép nhận dữ liệu sẽ xảy ra trong khi ngắt phục vụ in ấn đang thi hành. OPEN.PTIT.EDU.VN 137
38. Bộ điều khiểnngắtX Bộ điều khiểnngắtY Chương trình người dùng (a) Tiến hành ngắt tuần Bộ điều khiểnngắtX Bộ điều khiểnngắtY Chương trình người dùng (b) Tiến hành ngắt lồng (nested) Hình 5.4. Quy trình điều khiển đa ngắt * Có hai cách tiếp cận để giải quyết vấn đề đa ngắt: Cấm các ngắt họat động trong khi có một ngắt đang tiến hành. Nghĩa là CPU có thể và sẽ bỏ qua các tín hiệu yêu cầu ngắt. Nếu một ngắt xảy ra trong thời gian này thì nó sẽ bị treo và sẽ được kiểm tra sau khi bộ xử lý cho phép ngắt. Do đó, khi một chương trình của người sử dụng đang thực thi và một ngắt xảy ra thì các ngắt khác sẽ bị cấm ngay lập tức. Sau khi thủ tục phục vụ ngắt hoàn tất thì các ngắt được cho phép trước khi tái kích họat chương trình của người sử dụng và bộ xử lý sẽ kiểm tra xem có ngắt nào xảy ra nữa không. Cách tiếp cận này dễ và đơn giản vì các ngắt được điều khiển theo một thứ tự nghiêm ngặt. Minh hoạ trong hình 5.4(a) cho ta thấy cách xử lý ngắt trong hệ thống đa ngắt theo cách tiếp cận này. Ngắt X được phục vụ xong thì mới tời lượt ngắt Y được phục vụ. OPEN.PTIT.EDU.VNXác định thứ tự ưu tiên cho các ngắt và cho phép ngắt có thứ tự ưu tiên thấp hơn tự ngắt. Nghĩa là, trong khi một ngắt đang được phục vụ, nếu có ngắt khác xảy đến, thì hệ thống phải tiến hành kiểm tra thứ tự yêu tiên của các ngắt. Nếu ngắt đang được phục vụ có độ ưu tiên cao hơn thì ngắt đến sau sẽ bị bỏ qua. Ngược lại, nếu ngắt đang được phục vụ có độ ưu tiên thấp hơn, thì nó phải thực hiện viêc “tự ngắt” để cho phép ngắt đến sau thực hiện trước. Minh họa trong hình 5.4(b). Ngắt A 138
39. đang được phục vụ, giả sử ngắt B đến sau nhưng có độ ưu tiên cao hơn ngắt A, thì ngắt A phải tự ngắt để trao quyền điều khiển CPU cho ngắt B. Trở lại ví dụ ban đầu, giả sử một hệ thống có ba thiết bị nhập/xuất: một máy in, một ổ đĩa, và một đường liên lạc với các mức ưu tiên tăng dần tương ứng là 2, 4, và 5. Hình 5.5 mô tả một chuỗi các thao tác có thể xảy ra. Chương trình Phục vụ ngắt Phục vụ ngắt người dùng của máy in của việc liên t = 0 t = 15 t = 10 t = 25 t = 40 t = 25 Phục vụ ngắt của đĩa t = 35 Hình 5.5. Một ví dụ về xử lý ngắt có độ ưu tiên Một chương trình của người sử dụng bắt đầu tại thời điểm t=0. Tại thời điểm t=10, một ngắt cho máy in xảy ra; các thông tin của người sử dụng được lưu trong ngăn xếp của hệ thống và việc thực thi vẫn tiếp tục tại thủ tục phục vụ ngắt của máy in. Trong khi thủ tục này vẫn đang thực thi thì tại thời điểm t=15 một ngắt liên lạc xảy ra. Vì đường liên lạc có mức ưu tiên cao hơn máy in nên việc ngắt cho nó được ưu tiên trước Thủ tục phục vụ ngắt của máy in bị ngắt, trạng thái của nó lại được đưa vào ngăn xếp và việc thực thi vẫn được tiếp tục với thủ tục phục vụ ngắt của sự liên lạc. Trong khi thủ tục này đang thực thi thì một ngắt cho đĩa xảy ra (t=20). Vì ngắt này có mức ưu tiên thấp hơn nên nó phải chờ và thủ tục phục vụ ngắt của việc liên lạc vẫn hoạt động cho đến khi nó hoàn tất. OPEN.PTIT.EDU.VNKhi thủ tục phục vụ ngắt cho việc liên lạc kết thúc (t=25) thì trạng thái của bộ xử lý trước được khôi phục (trạng thái thực thi thủ tục phục vụ ngắt của máy in). Tuy nhiên, trước khi một lệnh trong thủ tục đó được thực thi thì bộ xử lý ưu tiên cho việc ngắt đĩa có mức ưu tiên cao hơn và sự điều khiển được chuyển cho thủ tục phục vụ ngắt của đĩa. Chỉ khi thủ tục này chấm dứt (t=35) thì thủ tục phục vụ ngắt của máy in mới được tái kích hoạt. Khi thủ tục đó kết thúc (t=40) thì sự điều khiển trở về chương trình của người sử dụng. 139
40. 5.3. Xử lý ngắt trong IBM-PC Trong phần này, chúng ta sẽ tìm hiểu một số ngắt cứng quan trọng và việc xử lý chúng như thế nào trong IBM-PC. Các thiết kế đầu tiên của IBM-PC dựa trên bộ xử lý 8088 và sử dụng bộ điều khiển ngắt 8259 cho phép tạo ra 8 tín hiệu ngắt đồng thời. Ngắt 00h: chia 0 8088 có hai lệnh chia (DIV và IDIV), chúng cho phép chia các số 16 bit và 32 bit cho các số 8 và 16 bit. Theo qui tắc toán học, thì phép chia cho 0 là không hợp lệ. Bởi vậy, 8088 cấm các phép chia có thương số là 0. Nếu xuất hiện phép chia cho 0, bộ bộ xử lý sẽ gọi ngắt 00h để thực hiện một thủ tục xử lý tương ứng (hiển thị thông báo “Division by Zero”). Ngắt 01h: thực hiện từng lệnh CPU gọi ngắt này khi bit TRAP của thanh ghi cờ bằng 1. Ngắt sẽ được gọi sau mỗi lệnh máy. Ngắt này cho phép người sử dụng theo dõi việc thực hiện từng lệnh của một chương trình ngôn ngữ máy. Để không xảy ra việc gọi đệ quy ngắt này, bộ xử lý sẽ đặt bit TRAP bằng 0 khi vào ngắt này. Nó cất thanh ghi cờ vào ngăn xếp, có nghĩa là cả bit TRAP. Nếu thủ tục xử lý ngắt được kết thúc bằng lệnh IRET, thì thanh ghi cờ (chứa bit TRAP) được tự động khôi phục từ ngăn xếp. sau khi thực hiện xong lệnh tiếp theo, ngắt 01h lại được gọi. sau khi nguời lập trình đã nhận đủ thông tin về chương trình, thì bit TRAP có thể bị xóa. Tuy nhiên, chương trình đang được kiểm tra không hề biết rằng nó đang được thực hiện từng lệnh, và nó không có lệnh nào để xóa bit TRAP trong thanh ghi cờ. Tuy nhiên, ngắt 01h rất ít khi được sử dụng bởi chương trình. Ngắt 02h: NMI (ngắt không che) Ngắt không che (Non-Maskable Interupt) được gọi như vậy bởi lẻ người dùng không thể ngăn cản nó. Người dùng có thể ngăn cản các ngắt khác bằng lệnh CLI, nhưng đối với ngắt 02h thì không thể. NMI thông báo cho người sử dụng biết rằng có lỗi trong RAM. Lỗi này có thể xuất hiện do hỏng một chip RAM nào đấy.Vì chip RAM hỏng có thể làm này sinh những ảnh hưởng nghiêm trọng cho hệ thống, nên ngắt này có độ ưu tiên cao nhất. Ngắt 03h: Điểm dừng Ngắt này được sử dụng trong các chương trình tiện ích. Khác với các ngắt khác, là các ngắt được gọi bởi một lệnh máy dài 2 bytes, ngắt này được gọi bởi một lệnh máy dài 1 byte. Ngắt này rất hữu ích để kiểm tra một chương trình chạy tới một điểm nào đó. Ngắt 03h dừng việc chạy chương trình, và cho phép người sử dụng kiểm tra nội dung các thanh ghi của bộ xử lý. Ngắt 04h: Lỗi tràn Ngắt này có thể được gọi bởi một lệnh. Đó là lệnh INTO (Interupt of Overflow), lệnh này chỉ gọi ngắt 04h khi bit tràn của thanh ghi cờ bằng 1. Điều này có thể xảy ra sau một thao tác toán học, nếu như kết quả của thao tác này không chứa nổi trong một số bit đã đặt. Ngắt 05h: Copy cứng OPEN.PTIT.EDU.VNKhi ấn phím PrtScr, ngắt này sẽ được gọi. Ngắt này gửi toàn bộ nội dung màn hình ra máy in. Ngắt 06h-07h: không sử dụng (dành cho các ứng dụng về sau). Ngắt 08h -0Fh: Các ngắt này do bộ điều khiển ngắt 8259 tạo ra. Bộ điều khiển ngắt này nhận tất cả các yêu cầu ngắt của hệ thống. Nó xác định mức ưu tiên của các yêu cầu ngắt. Có đến 8 nguồn sinh ngắt (thiết bị) có thể được nối tới 8259, mỗi thiết bị được gán một mức ưu tiên. Thông qua các bit của thanh ghi cờ, CPU có thể cấm tất cả các ngắt của 8259 (trừ ngắt 02h và NMI). 140
41. Ta cũng có thể cấm ngắt từ một thiết bị nào đó, bằng cách đặt bit ngắt tương ứng của thanh ghi che ngắt thuộc 8259 bằng 1. Thanh ghi này được truy nhập thông qua cổng 21h. 8 bit của thanh ghi này tuơng ứng với 8 thiết bị sinh ngắt. Bit 0 tương ứng với thiết bị số 0, bit 7 tương ứng với thiết bị số 7. Nếu bit có giá trị 0, thì CPU sẽ nhận được ngắt do thiết bị tương ứng sinh ra. Nếu ngắt bằng 1, yêu cầu ngắt sẽ bị bỏ qua. Nếu đồng thời có nhiều yêu cầu ngắt, yêu cầu ngắt số 0 sẽ có mức ưu tiên cao nhất, yêu cầu ngắt số 7 có mức ưu tiên thấp nhất. Nếu yêu cầu ngắt mức cao được xử lý xong, thì yêu cầu ngắt tiếp theo sẽ được 8259 chuyển tới CPU. Hình 6.14 mô tả các yêu cầu ngắt của các thiết bị và mức ưu tiên của chúng trên PC. Trong hình này, các bit 2 và 5 không được sử dụng. Bit 2 được sử dụng bởi bộ điều khiển ngắt thứ hai (trong các máy AT). Bit 5 chưa dùng do trước đây nó được IBM dành riêng cho cổng song song LPT2, nhưng vì có quá ít người dùng sử dụng cổng LPT2 nên IBM không tiếp tục phát triển ngắt này nữa (tuy nhiên, card âm thanh có thể sẽ sử dụng nó). Do vậy, sau này trên các dòng máy XT thì bit 5 được dùng để phục vụ cho ngắt của đĩa cứng. Chiều tăng của mức ưu 7654 3210 Bộ điều khiển ngắt (địa chỉ Bộ thời gian Bàn phím COM 2 COM 1 Đĩa mềm Máy in song song Hình 5.6. Các yêu cầu ngắt và mức yêu tiên trên PC Ngắt 08h: bộ thời gian (bit 0) Cứ sau 65.536 nhịp tín hiệu (khỏang 18,2 lần/giây), ngắt 08h lại được gọi. bộ điều khiển ngắt 8259 sẽ chuyển yêu cầu ngắt này tới CPU. Vì sự xuất hiện ngắt này không phụ thuộc tần số nhịp của hệ thống, nên nó có thể dùng để đo thời gian. Sau 18,2 lần gọi ngắt, thì có nghĩa là đã trôi qua một giây. Ngắt 09h: ngắt bàn phím (bit 1) Bàn phím được hỗ trợ bởi bộ xử lý Intel 8048(PC/XT) hoặc 8042 (AT). Bộ xử lý này kiểm soát và ghi nhận phím bị ấn, nhả hoặc bị ấn và giữ liên tục. Nó gửi tín hiệu yêu cầu ngắt tới 8259, bộ này lại yêu cầu CPU gọi ngắt số 09h (trong trường hợp đồng thời đang có một ngắt khác có mức ưu tiên cao hơn). Ngắt 0Ah -0Ch: thay đổi OPEN.PTIT.EDU.VNCác ngắt này thay đổi tùy theo từng máy. Ngắt 0Dh: đĩa cứng (bit 5) Ngắt này được gọi khi kết thúc các thao tác đọc, ghi đĩa cứng. Ngắt 0Eh: đĩa mềm (bit 6) Ngắt này được gọi khi kết thúc các thao tác đọc, ghi đĩa mềm hoặc khi có lỗi xuất hiện. Ngắt 0Fh: máy in (bit 7) 141
42. Máy in song song gọi ngắt này thông qua 8259 khi nó cần sự phục vụ của CPU. 5.3.1. Thanh ghi ngắt 8259 biết được khi nào một yêu cầu ngắt đã được xử lý xong là do thanh ghi chỉ thị ngắt ở địa chỉ 20h. Khi một ngắt của 8259 kết thúc, nó thực hiện lệnh OUT giá trị 20h (EOI = End Of Interupt) tới cổng 20h. Lệnh này thông báo cho 8259 biết rằng việc xử lý ngắt đã kết thúc, và 8259 có thể chấp nhận yêu cầu ngắt tiếp theo. Việc định nghĩa các bit cuả thanh ghi che ngắt là khác nhau, tùy loại PC. Có thể coi rằng, thiết bị tương ứng bit 0 của thanh ghi she ngắt sẽ gọi ngắt 08h. Thiết bị tương ứng bit 1 sẽ gọi ngắt 09h Ngắt 0Fh, ngắt cuối cùng của 8259, sẽ được kích họat bởi thiết bị tương ứng bit 7 của thanh ghi che ngắt. Tổng quát, 8 ngắt trên có các ký hiệu là IRQ0, IRQ1, IRQ có nghĩa là Interupt Request (yêu cầu ngắt). 5.3.2. Các bộ điều khiển ngắt của máy AT AT có hai bộ điều khiển ngắt 8259, và nó có thể xử lý tới 16 yêu cầu ngắt (nguồn sinh ngắt). Các ngắt của bộ điều khiển ngắt thứ hai có tên là IRQ8, , IRQ15. Nếu xuất hiện một yêu cầu ngắt của bộ điều khiển ngắt thứ 2, thì nó được coi như là yêu cầu ngắt số 2 của bộ điều khiển ngắt thứ nhất. Bởi vậy các yêu cầu ngắt của bộ điều khiển ngắt thứ hai có độ ưu tiên cao hơn các yêu cầu ngắt từ 3 đến 7 của bộ điều khiển ngắt thứ nhất. Ta cũng có thể che các yêu cầu ngắt của bộ điều khiển ngắt thứ hai, bằng cách thao tác các bit của thanh ghi che ngắt thuộc 8259 thứ hai. Thanh ghi này có địa chỉ cổng A0h. ta phải gửi lệnh EOI tới cả hai bộ điều khiển ngắt sau khi kết thúc việc xử lý một yêu cầu ngắt của bộ điều khiển ngắt thứ hai. Đó là vì hai bộ điều khiển này được nối với nhau, mỗi yêu cầu ngắt của bộ thứ hai đều làm xuất hiện yêu cầu ngắt số 2 của bộ thứ nhất. Các hình sau đây cho thấy các yêu cầu ngắt của các thiết bị và mức ưu tiên của chúng. Chiều tăng của mức ưu 7654 3210 Bộ điều khiển ngắt (địa chỉ 7654 3210 Đồng xử lý toán học Thời gian thực Chiều tăng của mức ưu OPEN.PTIT.EDU.VN Hình 5.7. Các yêu cầu ngắt và mức yêu tiên trên máy AT 5.3.3. Các ngắt của AT Vì có thêm bộ xử lý ngắt thứ hai, nên AT có nhiềuu ngắt cứng hơn PC và XT. Bộ điều khiển ngắt thứ hai có thể gọi các ngắt từ 70h tới 77h. Thiết bị tương ứng yêu cầu ngắt số 0 sẽ gọi ngắt 70h, thiết bị tương ứng yêu cầu ngắt số 1 gọi ngắt 71h, 142
43. Chỉ có các ngắt 70h và 75h là được bộ điều khiển ngắt gọi, bởi lẽ chỉ có hai thiết bị nối với 8259 này. Tuy nhiên, các vector ngắt 71h-74h và 76h-77h có thể được đổi hướng cho các mục đích khác. Hình 5.15 mô tả chi tiết một số yêu cầu ngắt và mức độ ưu tiên của chúng trên máy AT. Ngắt 70h: đồng hồ thời gian thực Ngắt 70h được gọi khi đến thời điểm báo chuông, thời gian vừa được cập nhật, hoặc vừa xảy ra một ngắt chu kỳ. ngắt này thường được một thủ tục của BIOS xử lý. Ngắt 75h: bộ đồng xử lý tóan học Ngắt 75h thông báo cho CPU biết là bộ đồng xử lý toán học yêu cầu phục vụ (thì dụ, nó đã thực hiện xong một phép tính nào đó). TÓM TẮT Trong lĩnh vực công nghệ thông tin, khái niệm bộ xử lý (processor) thường được gọi là đơn vị xử lý trung tâm (CPU-Central Processing Unit). CPU là một thành phần bên trong máy tính thực hiện công việc biên dịch các chỉ thị của máy tính và xử lý các dữ liệu bên trong các chương trình. Cùng với đơn vị lưu trữ chính, thiết bị nhập/xuất, CPU là thành phần cơ bản nhất không thể thiếu trong bất kỳ hệ thống máy tính nào. Để tăng tốc độ cho một hệ thống máy tính, ngoài việc sử dụng nhiều CPU, còn có một giải pháp khác – hyper threading (siêu phân luồng). Với kỹ thuật này, hệ điều hành sẽ nhìn thấy một processor vật lý thành hai processor logic. Processor vật lý là một thành phần phần cứng thực sự, thực hiện các thao tác do hệ điều hành và các chương trình đang thực thi trên máy tính ra lệnh. Trong khi đó, processor logic được tạo ra bởi các chương trình, tài nguyên hệ điều hành, hoặc là sự mô phỏng của processor vật lý. Một lý do khác để tạo ra processor logic là để tận dụng tối đa nguồn tài nguyên bên trong bộ xử lý đồng thời cho phép thực hiện tính toán cho nhiều tiểu trình hơn trong cùng một thời điểm. CÂU HỎI VÀ BÀI TẬP 1. Phân biệt giữa CPU vật lý và CPU logic. Mục tiêu của CPU logic là gì? 2. Kỹ thuật siêu phân luồng và Dual core có tương tự nhau không? Hãy phân biệt bản chất của chúng. 3. Tại sao ngắt được xem là mức điều khiển cao nhất trong một bộ xử lý? 4. Định nghĩa và phân loại một vài loại ngắt cứng, ngắt mềm. Chỉ ra mục đích của ngắt mềm. 5. Điểm an tòan trong quá trình thực thi một chương trình là gì? Đồng hồ ngắt có mục đích gì trong hệ thống? OPEN.PTIT.EDU.VN TÀI LIỆU THAM KHẢO [1]. Gary J. Nutt, University of Colorado. Centralized And Distributed Operating Systems. Second Edition, 2000. [2]. Robert Switzer. Operating Systems, A Practical Approach. Prentice-Hall International, Inc. 1993. [3]. Andrew S. Tanenbaum. Modern Operating Systems. Prentice-Hall International, Inc. Second Edition, 2001. 143
44. CHƯƠNG 6 HỆ ĐIỀU HÀNH NHIỀU BỘ VI XỬ LÝ Chương “HỆ ĐIỀU HÀNH NHIỀU BỘ VI XỬ LÝ" sẽ giới thiệu và giải thích các vấn đề sau: 6.1 Cấu hình nhiều processor 6.2 Các loại hệ điều hành hỗ trợ nhiều bộ vi xử lý 6.3 Đồng bộ trong hệ thống đa xử lý 6.4 Điều phối trong hệ thống đa xử lý 6.1. CẤU HÌNH NHIỀU PROCESSOR Mặc dù tốc độ máy tính ngày càng được cải thiện nhờ vào các công nghệ mới, nhưng nhu cầu của con người vẫn chưa được thỏa mãn. Một trong các cách tiếp cận nhằm mục đích tăng tốc độ của máy tính đó là sử dụng nhiều bộ xử lý trên một máy. Mỗi bộ xử lý chỉ cần hoạt động ở tốc độ bình thường cũng đã cung cấp cho hệ thống khả năng tính toán tốt hơn rất nhiều so với hệ thống chỉ có một bộ xử lý. Hệ thống có nhiều bộ xử lý có thể chia làm 3 loại chính như sau: + Đa xử lý dùng bộ nhớ chia sẻ. + Đa xử lý dùng bộ nhớ riêng. + Đa xử lý phân tán. Đối với mô hình thứ nhất, các CPU truyền thông với nhau để thực hiện một hoặc một số công việc nào đó thông qua việc sử dụng chung một bộ nhớ (bộ nhớ chia sẻ). Trong mô hình này, các CPU đều có quyền như nhau để truy xuất vào bộ nhớ vật lý. Đối với mô hình thứ hai, hệ thống gồm nhiều cặp CPU-bộ nhớ được kết nối với nhau thông qua các đường kết nối tốc độ cao. Trong mô hình này, bộ nhớ là cục bộ đối với mỗi CPU và chỉ có thể được truy xuất bởi CPU đó. Còn trong mô hình thứ ba, hệ thống cũng gồm nhiều cặp CPU-bộ nhớ, nhưng chúng kết nối với nhau thông qua mạng diện rộng, chẳng hạn như Internet, và hình thành nên một hệ thống phân tán. Trong mô hình này, việc truyền thông giữa các cặp CPU-bộ nhớ này cũng sử dụng cách chuyển thông điệp (message passing), giống như trong mô hình thứ hai. Tuy nhiên, sự khác nhau giữa hai hệ thống này đó là độ trễ. Độ trễ để truyền thông điệp giữa các cặp CPU-bộ nhớ trong mô hình thứ hai là thấp hơn rất nhiều so với độ trễ trong mô hình thứ 3. Một hệ thống đa xử lý dùng bộ nhớ chia sẻ (shared-memory multiprocessor, hoặc đôi khi người ta chỉ gọi multiprocessor) là một hệ thống có hai hoặc nhiều hơn hai CPU cùng chia sẻ một bộ nhớ RAM. Một chương trình chạy trên bất kỳ CPU nào cũng đều có khả năng nhìn thấy cùng một không gian địa chỉ ảo như nhau (nói cách khác, chúng được phân trang như trong hệ thống có một bộ xử lý). Tuy nhiên, điều khác biệt trong hệ thống đa xử lý thể hiện ở chỗ, một CPU có thể ghi vào một từ nhớ nào đó một giá trị là a nhưng khi đọc ra có thể sẽ mang giá trị khác a (bởi vì một OPEN.PTIT.EDU.VNCPU khác đã làm thay đổi giá trị này). Điều này tạo nên đặc tính cơ bản của việc truyền thông giữa các tiến trình với nhau trong hệ thống có nhiều bộ xử lý – một CPU ghi dữ liệu vào trong bộ nhớ và một CPU khác sẽ đọc để lấy dữ liệu đó ra. Nói chung, hệ điều hành dùng cho hệ thống đa xử lý cũng tương tự như hệ điều hành trong hệ thống đơn xử lý. Nó cũng xử lý các lời gọi hệ thống, thực hiện việc quản lý bộ nhớ, cung cấp cơ chế quản lý tập tin cũng như các cơ chế quản lý vào ra. Tuy nhiên, có một số vấn đề mới mà chúng ta cần quan tâm khi nghiên cứu một hệ điều 144
45. hành dùng trong hệ thống đa xử lý. Chẳng hạn như: việc quản lý tài nguyên, việc đồng bộ tiến trình, cũng như việc điều phối tiến trình trong nhiều bộ xử lý khác nhau. Trong giới hạn của giáo trình này, chúng tôi chỉ cung cấp cho bạn đọc chi tiết về cấu hình phần cứng cũng như các vấn đề liên quan về hệ điều hành cho hệ thống đa xử lý dùng bộ nhớ chia sẻ. Phần tương tự cho hai hệ thống còn lại, bạn đọc có thể tham khảo thêm trong các tài liệu khác về hệ điều hành khác. Mặc dù các hệ thống có nhiều bộ xử lý đều cho phép mọi CPU có thể truy xuất đến bộ nhớ của hệ thống, nhưng một vài hệ thống có thêm một đặc tính nữa, đó là nó cho phép mọi từ nhớ có thể được đọc ra với cùng một tốc độ. Những hệ thống này được gọi là hệ thống đa xử lý UMA (Uniform Memory Access Multiprocessor). Ngựơc lại, hệ thống nào không có khả năng trên thì được gọi là NUMA (NonUniform Memory Access Multiprocessor). Vì sao có sự khác biệt này chúng ta sẽ tìm hiểu ở phần sau, còn bây giờ chúng ta sẽ lần lượt tìm hiểu từng loại hệ thống một. 6.1.1. Hệ thống đa xử lý UMA dùng mô hình Bus Các hệ thống có nhiều bộ xử lý đơn giản nhất đều dựa trên một bus chung, được minh họa trong hình 6-1(a). Hai hoặc nhiều CPU và một hoặc nhiều bộ nhớ, tất cả sử dụng một tuyến bus để truyền thông. Khi một CPU muốn đọc một từ nhớ, trước tiên nó phải kiểm tra xem bus có rỗi không. Nếu trạng thái bus là rỗi, CPU sẽ gởi địa chỉ của từ nhớ mà nó muốn đọc dữ liệu lên trên bus, kiểm tra một vài tín hiệu điều khiển, và đợi cho đến khi bộ nhớ đặt từ nhớ được yêu cầu lên lên bus. Hình 6.1: Các hệ thống đa xử lý dùng mô hình Bus: (a) Không có cache. (b) Có cache. (c) Có cache và các bộ nhớ riêng. Còn nếu bus bận khi một CPU muốn đọc hoặc ghi bộ nhớ, CPU phải đợi đến khi bus trở về trạng thái rỗi. Đối với hệ thống có 2 hoặc 3 CPU, việc cạnh tranh bus là có thể quản lý được. Tuy nhiên nếu hệ thống có số lượng CPU lớn hơn (ví dụ 32, hoặc 64 CPU), điều này là không thể. Hệ thống bị hạn chế hoàn toàn bởi băng thông cho phép của bus, và vì vậy hầu hết các CPU sẽ rỗi trong phần lớn thời gian. Giải pháp cho vấn đề này là thêm bộ nhớ cache cho mỗi CPU như chỉ ra trong hình 6-1(b). Bộ OPEN.PTIT.EDU.VNnhớ cache có thể nằm bên trong chip của CPU, nằm kế bên, nằm trên bo mạch của CPU, hoặc được kết hợp từ các cách trên. Điều này thực sự làm giảm bớt tải cho bus chung. Và vì vậy hệ thống có thể hỗ trợ nhiều CPU hơn. Nói chung, caching không thực hiện trên một đơn vị nhớ riêng nào, mà nó dựa trên khối các byte (thường là các khối 32-byte hoặc 64-byte). Khi một từ nhớ được tham chiếu đến, thì toàn bộ khối (block) chứa từ nhớ đó sẽ được nạp vào trong cache của CPU yêu cầu. 145
46. Mỗi block dữ liệu trong cache hoặc là read-only (trong trường hợp nó hiện diện trong nhiều cache ở cùng một thời điểm), hoặc là read-write (trong trường hợp nó không hiện diện trong các cache khác). Nếu một CPU cố gắng ghi một từ nhớ đang hiện diện bên trong một hoặc một vài cache khác, một tín hiệu sẽ được phần cứng phát lên trên bus để thông báo cho các cache khác biết việc ghi này. Nếu các cache này có một bản sao (giống như bản gốc trong bộ nhớ), thì chúng sẽ chỉ hủy bỏ những bản sao này và cho phép CPU nạp block dữ liệu từ bộ nhớ vào cache. Đối với một vài cache có một bản sao đã được thay đổi, thì nó phải hoặc là được ghi ngược lại ra bộ nhớ trước khi việc ghi được thực hiện, hoặc được truyền trực tiếp đến CPU có nhu cầu ghi thông qua bus. Một khả năng khác có thể được thiết kế như trong hình 6-1(c). Trong mô hình này, mỗi CPU không chỉ có cache mà còn có bộ nhớ riêng được truy xuất thông qua một bus riêng. Để sử dụng tối ưu cấu hình này, trình biên dịch nên đặt tất cả các chương trình text, chuỗi, hằng số và những dữ liệu chỉ đọc, ngăn xếp, và các biến cục bộ vào trong các bộ nhớ riêng này. Bộ nhớ chia sẻ dùng chung chỉ được sử dụng cho các biến chia sẻ. Trong hầu hết các trường hợp, việc làm này sẽ giảm đáng kể lưu lượng cho bus chung, tuy nhiên điều này cũng đòi hỏi sự tích cực hợp tác từ trình biên dịch. 6.1.2. Hệ thống đa xử lý UMA dùng mô hình chuyển mạch chéo (Crossbar Switch) Ngay cả khi hệ thống được hỗ trợ nhiều CPU với bộ nhớ cache, thì việc sử dụng một tuyến bus duy nhất cũng chỉ cho phép tối đa 16 hoặc 32 CPU trong một hệ thống đa xử lý UMA. Nhằm năng cao hơn nữa khả năng đáp ứng cho hệ thống, cần thay đổi cách kết nối các CPU. Một cách kết nối đơn giản giữa n CPU và k bộ nhớ để hình thành một mô hình kết nối chéo được thể hiện trong hình 6-2. Mô hình này đã được ứng dụng cách đây nhiều thập kỷ trong các tổng đài chuyển mạch điện thoại để kết nối một nhóm các line vào và một tập các line ra. Trạng thái của mỗi giao điểm (crosspoint), điểm giao nhau giữa đường ngang (line vào) và đường dọc (line ra), là đóng hay mở tùy thuộc vào trạng thái kết nối hay không kết nối của đường ngang và đường dọc này. Trong hình 6-2(a), 3 crosspoint đóng đồng thời, cho phép 3 kết nối giữa CPU và bộ nhớ được hình thành cùng lúc. Đó là các cặp (001, 000), (101, 101), và (110, 010). Đương nhiên là nhiều sự kết hợp khác cũng đều có khả năng như vậy. Mô hình này có thể hỗ trợ tối đa nxk sự kết hợp có thể có giữa n CPU và k bộ nhớ. Một trong những đặc điểm nổi bật của mô hình này là nó đảm bảo hệ thống không bị nghẽn. Nghĩa là sẽ không có trường hợp một CPU nào đó không có bộ nhớ để làm việc chỉ vì một vài điểm crosspoint đã bị sử dụng. Ngoài ra, hệ thống cũng không cần phải lập ra kế hoạch phân phối tài nguyên cho CPU trước. Ngay cả khi những kết nối bất kỳ giữa CPU và bộ nhớ đã được thiết lập, hệ thống đều có khả năng cho phép thực hiện kết nối các CPU và bộ nhớ còn lại với nhau. Một trong những yếu điểm lớn nhất của mô hình này là số lượng crosspoint rất lớn khi số CPU và bộ nhớ tăng lên. Với 1000 CPU và 1000 bộ nhớ thì hệ thống sẽ có 1000000 crosspoint. Một mô hình kết nối lớn như thế là không khả thi. Tuy nhiên, đối với các hệ thống với kích thước nhỏ hơn, OPEN.PTIT.EDU.VNthì đây là một mô hình tuyệt vời. 146
47. Hình 6.2. (a) Chuyển mạch chéo 8x8. (b) Giao điểm mở. (c) Giao điểm đóng. 6.1.3. Hệ thống đa xử lý UMA dùng mô hình mạng chuyển mạch đa tầng (Multistage Switching Network) Một thiết kế hoàn toàn khác cho hệ thống đa xử lý dựa trên chuyển mạch 2x2 được trình bày trong hình 6-3(a). Chuyển mạch này có 2 ngỏ vào và 2 ngỏ ra. Các message có thể đến bất kỳ một trong hai ngỏ vào và được chuyển ra theo một trong hai ngỏ ra. Theo đó, mỗi message sẽ gồm 4 phần, như trong hình 6-3(b). Trong hình này, trường Module cho biết vùng nhớ nào được sử dụng. Trường Address cho biết địa chỉ nào trong vùng nhớ đó. Trường Opcode cho biết họat động gì sẽ được thực hiện (đọc (READ) hay ghi (WRITE)). Và trường Value là trường tùy chọn, cho biết toán hạng nào sẽ được dùng vào việc đọc hoặc ghi (chẳng hạn như một từ 32-bit sẽ được đọc hoặc ghi). Chuyển mạch (switch) sẽ kiểm tra trường Module và dùng nó để xác định xem message nên đi ra ngỏ nào, X hay Y. Hình 6.3. (a) Chuyển mạch 2x2. (b) Định dạng của Message. OPEN.PTIT.EDU.VN Các chuyển mạch 2x2 có thể được sắp xếp theo nhiều cách để tạo nên một mạng chuyển mạch đa tầng (multistage switching network). Một kiến trúc điển hình cho lọai này được trình bày trong hình 6-4. Ở đây, 8 CPU được kết nối với 8 bộ nhớ sử dụng 12 switch. Một cách tổng quát, với n CPU và n bộ nhớ, chúng ta cần log2n tầng (stage) với n/2 switch cho mỗi tầng. Nghĩa là, tổng cộng hệ thống cần (n/1)log2n switch. Điều này rõ ràng là tốt hơn nhiều so với hệ thống đa xử lý UMA dùng chuyển mạch chéo, cần tới n2 crosspoint, đặc biệt là khi n mang giá trị lớn. 147
48. Hình 6.3. Mạng chuyển mạch Omega Xét mạng chuyển mạch Omega như trong hình 6-4, giả sử CPU 011 muốn đọc một từ nhớ (word) từ bộ nhớ 110. CPU gởi message READ đến chuyển mạch 1D chứa giá trị 110 trong trường Module. Switch lấy bit đầu tiên (bên trái nhất) của 110 và dùng nó cho việc định tuyến. Nếu bit này có giá trị 0, switch sẽ chọn lên ngỏ ra phía trên, ngược lại, nếu bit này có giá trị 1, thì switch sẽ chọn tuyến bên dưới. Như vậy, trong trường hợp này, bit đầu tiên có giá trị 1, nên message được đưa đến ngỏ ra bên dưới để đi đến switch 2D. Tất cả các switch ở tầng thứ 2, bao gồm switch 2D, bit thứ 2 (từ trái sang) sẽ được dùng vào việc định tuyến. Và trong trường hợp này, bit thứ 2 có giá trị 1, nên message cũng được chuyển đến ngỏ ra bên dưới đến switch 3D. Tại đây, bit thứ 3 từ trái sang sẽ được kiểm tra, và vì nó mang giá trị 0 nên message sẽ được chuyển đến ngỏ ra bên trên và đi đến bộ nhớ 110. Kết quả là message sẽ đi theo con đường được đánh dấu bằng ký tự a trong hình 6-4. Giả sử tại cùng thời điểm diễn ra những việc trên, CPU 001 muốn ghi một word đến bộ nhớ 001. Một tiến tình tương tự như vậy cũng xảy ra, ở đó, message được định tuyến thông qua các cổng theo thứ tự như sau: message đến ngỏ vào trên của switch 1B và đi ra ở ngỏ ra trên của 1B, sau đó đến switch 2C, và đi ra ở ngỏ ra trên của 2C để đến switch 3A, sau cùng thì message sẽ đi ra ở ngỏ ra dưới của switch 3A để đến bộ nhớ 001. Kết quả là message sẽ đi theo con đường được đánh dấu bằng ký tự b trong hình 6-4. Bởi vì 2 yêu cầu này sử dụng các switch, kết nối và bộ nhớ khác nhau, nên không xảy ra bất kỳ sự đụng độ nào, chúng có thể thực hiện công việc một cách đồng thời. Tuy nhiên, điều gì sẽ xảy ra nếu CPU 000 đồng thời muốn truy xuất bộ nhớ 000. Yêu cầu của nó sẽ đụng độ với nhu cầu của CPU 001 tại switch 3A. Một trong hai yêu cầu này phải đợi. Không giống như cơ chế chuyển mạch chéo, mạng Omega là một mạng có khả năng xảy ra nghẽn. Không phải mọi yêu cầu đều có thể được xử lý đồng thời. Đụng độ có thể xảy ra do việc sử dụng chung OPEN.PTIT.EDU.VNkết nối, switch hoặc bộ nhớ mà các yêu cầu truy xuất đến. Từ hệ thống này, người ta mong đợi có một hệ thống được cải tiến hơn bằng cách cho phép các word liên tục được lưu trong các bộ nhớ khác nhau. Điều này cho phép hệ thống truy xuất đến bộ nhớ nhanh hơn. Ngòai ra, tình trạng nghẽn mạng cũng có thể được khắc phục bằng cách cung cấp nhiều đường đi từ một CPU này đến một bộ nhớ bất kỳ, khi đó tốc độ truy xuất bộ nhớ cũng được cải thiện đáng kể. 148
49. 6.1.4. Hệ thống đa xử lý NUMA Các hệ thống đa xử lý UMA dùng bus thường bị giới hạn tối đa khoảng vài tá CPU, còn các hệ thống dùng chuyển mạch chéo hoặc chuyển mạch đa tầng thì cần nhiều phần cứng hỗ trợ. Để cho phép một hệ thống có thể hỗ trợ tốt với trên 100 CPU, người ta đưa ra một cách tiếp cận khác. Với cách tiếp cận này, việc truy xuất bộ nhớ cục bộ sẽ nhanh hơn việc truy xuất bộ nhớ ở xa. Như vậy, các chương trình hỗ trợ UMA sẽ chạy tốt trên các máy hỗ trợ NUMA mà không có sự thay đổi nào. Trong khi đó, các chương chương trình được hỗ trợ NUMA sẽ giảm hiệu suất thực thi khi chạy trên các máy hỗ trợ UMA ở cùng một tốc độ đồng hồ. Các máy NUMA có 3 đặc điểm chính có thể phân biệt với các hệ thống đa xử lý khác, đó là: Có một không gian địa chỉ duy nhất có thể nhìn thấy bởi tất cả các CPU. Truy xuất bộ nhớ ở xa thông qua hai lệnh LOAD và STORE. Truy xuất bộ nhớ ở xa chậm hơn truy xuất bộ nhớ cục bộ. Khi thời gian truy xuất bộ nhớ ở xa có sự khác biệt lớn so với thời gian truy xuất bộ nhớ cục bộ (bởi vì không có cơ chế caching) thì hệ thống được gọi là NC-NUMA (NonCaching NUMA). Ngược lại, khi có các bộ nhớ cache, thì hệ thống được gọi là CC-NUMA (Cache Coherent NUMA). Hình 6.4. (a) Hệ thống đa xử lý sử dụng Directory – 256 node. (b) Phân chia địa chỉ ô nhớ 32-bit thành các trường. (c) Cấu trúc Directory của node 36. Cách tiếp cận phổ biến nhất để xây dựng một hệ thống đa xử lý CC-NUMA hiện nay là sử dụng một cơ sở dữ liệu để lưu vị trí của các khối cache và trạng thái của chúng. Khi một khối cache được tham chiếu, cơ sở dữ liệu được yêu cầu được truy vấn để tìm ra vị trí và trạng thái của nó là nguyên bản hay đã bị sửa đổi. Vì cơ sở dữ liệu này phải được truy vấn bởi mọi chỉ thị lệnh tham OPEN.PTIT.EDU.VNchiếu đến bộ nhớ, nên nó phải được lưu giữ trong một thiết bị phần cứng đặc biệt hỗ trợ tốc độ truy xuất cực nhanh. Để làm rõ hơn ý tưởng của hệ thống này, chúng ta xét ví dụ đơn giản được mô tả như trong hình 6-5. Một hệ thống gồm 256 node, mỗi node gồm một CPU và 16MB bộ nhớ RAM được kết nối đến CPU thông qua một bus cục bộ. Tổng bộ nhớ là 232 byte, được chia làm 226 khối cache, mỗi khối 64 byte. Bộ nhớ được định vị cố định tại mỗi node, với 0-16MB cho node 0, 16MB–32MB 149
50. cho node 1 Các node được kết nối với nhau như trong hình 6-5(a). Ngoài ra, mỗi node cũng lưu giữ các thực thể (entry) trong thư mục (directory) cho 218 khối cache 64-byte (hình thành bộ nhớ 224 byte) tương ứng. Để thấy rõ cơ chế làm việc của hệ thống này, thực hiện theo vết lệnh LOAD từ CPU 20 như sau. Đầu tiên, CPU sẽ phát chỉ thị lệnh đến đơn vị quản lý bộ nhớ của nó (MMU), đơn vị này sẽ chuyển chỉ thỉ lệnh đó sang một địa chỉ vật lý (giả sử là 0x24000108). MMU tiếp tục chia địa chỉ này thành 3 phần như trong hình 6-5(b). Giả sử 3 phần này lần lượt có giá trị là node 36, khối cache 4 và offset 8. Như vậy, MMU nhận thấy rằng, word được tham chiếu là từ node 36, không phải node 20, do vậy nó gởi một message yêu cầu đến node 36, là node quản lý khối cache 4, hỏi xem khối 4 có được cache hay không, nếu có thì nó được cache ở đâu. Khi yêu cầu này đến node 36, nó sẽ được chuyển đến phần cứng Directory. Phần cứng này sẽ dò trong bảng gồm 218 thực thể của nó để tìm ra thực thể 4. Từ hình 6-5(c), chúng ta thấy rằng khối 4 không được cache, do vậy phần cứng sẽ nạp dòng 4 từ bộ nhớ RAM cục bộ và gởi ngược lại node 20, đồng thời cập nhật Directory ở thực thể 4 và chỉ ra rằng khối này bây giờ được cache ở node 20. Bây giờ, chúng ta xem xét một yêu cầu khác, lần này node 20 hỏi về khối cache 2 của node 36. Từ hình 6-5(c), chúng ta thấy rằng khối này được cache tại node 82. Như vậy, phần cứng phải cập nhật thực thể 2 trong Directory để chỉ ra rằng khối này đang được cache ở node 20 đồng thời vô hiệu hóa cache của nó. 6.2. CÁC LOẠI HỆ ĐIỀU HÀNH HỖ TRỢ NHIỀU BỘ XỬ LÝ Trong phần này chúng ta chuyển từ phần cứng sang tìm hiểu về phần mềm, cụ thể là chúng ta sẽ tìm hiểu về các hệ điều hành hỗ trợ cho các hệ thống có nhiều bộ xử lý. Có rất nhiều loại, tuy nhiên, ở đây chúng ta sẽ tìm hiểu 3 trong số các loại đó. 6.2.1. Mỗi CPU có riêng một hệ điều hành OPEN.PTIT.EDU.VNHình 6.5. Phân chia bộ nhớ cho các CPU trong hệ thống đa xử lý, nhưng cùng chia sẻ chung tập lệnh của hệ điều hành. Dữ liệu cũng được lưu trữ riêng cho từng CPU. Cách đơn giản nhất để tổ chức một hệ điều hành hỗ trợ nhiều bộ xử lý là phân chia cố định bộ nhớ thành nhiều phần tương ứng với số lượng CPU mà hệ thống hỗ trợ. Mỗi CPU được cấp một bộ nhớ riêng và sở hữu một bản sao riêng của hệ điều hành. Kết quả là, n CPU sau đó sẽ họat động như là n máy tính độc lập. Một mô hình tối ưu như được trình bày trong hình 6-6, ở đó, hệ thống 150
51. cho phép các CPU chia sẻ code của hệ điều hành trong khi dữ liệu thì được lưu trữ riêng tại các vùng nhớ đã dành riêng cho chúng. Sơ đồ này vẫn tốt hơn trường hợp hệ thống có nhiều máy tính tách biệt bởi vì nó cho phép các CPU có thể chia sẻ một tập các tài nguyên đĩa và các thiết bị nhập/xuất khác, đồng thời nó cũng cho phép bộ nhớ được chia sẻ một cách linh họat hơn. Thí dụ, nếu một ngày đẹp trời nào đó, một chương trình có kích thước lớn bất thường cần được thực thi, thì một trong các CPU vẫn có thể được cung cấp một phần bộ nhớ đủ lớn để thực thi chương trình đó. Ngòai ra, các tiến trình còn có thể truyền thông với nhau một cách hiệu quả, chẳng hạn như một producer có thể ghi dữ liệu vào bộ nhớ đồng thời một consumer lấy dữ liệu đó ra từ nơi mà producer ghi vào. Tuy nhiên, thiết kế này vẫn cho thấy một số nhược điểm sau: Thứ nhất, khi một tiến trình tạo một lời gọi hệ thống, thì lời gọi hệ thống này sẽ được thực thi trên chính CPU của tiến trình đó sử dụng các cấu trúc dữ liệu trong các bảng của cùng hệ điều hành dành CPU đó. Thứ hai, vì mỗi hệ điều hành đều có một tập các tiến trình được điều phối bởi chính nó. Cho nên, sẽ không có việc chia sẻ tiến trình ở đây. Nếu một user làm việc với CPU 1 thì tất cả các tiến trình của user này chỉ chạy trên CPU 1. Kết quả là, CPU1 quá tải trong khi các CPU khác thì rảnh rỗi. Thứ ba, không có việc chia sẻ trang nhớ ở đây. Chẳng hạn như, trong khi CPU 1 có nhiều trang nhớ dư thừa, thì CPU 2 vẫn phải thực hiện phân trang liên tục. Không có cách nào để CPU 2 có thể mượn một vài trang nhớ từ CPU 1 bởi vì bộ nhớ đã được chia cố định. Thứ tư và cũng là nhược điểm lớn nhất. Nếu mỗi hệ điều hành của từng CPU lưu giữ một vùng nhớ cache của các khối đĩa mới sử dụng gần đây, thì mỗi hệ điều hành sẽ thao tác trên khối dữ liệu này một cách độc lập với các hệ điều hành khác. Vì vậy, có thể sẽ xảy ra trường hợp là các khối đĩa này trở thành một phần riêng và chỉ bị thay đổi bởi một CPU tương ứng tại một thời điểm. Điều này dẫn đến những kết quả mâu thuẫn nhau. Chỉ có một cách duy nhất để loại bỏ vấn đề này là loại bỏ các vùng nhớ cache. Điều này không có gì khó, nhưng vấn đề là nó sẽ làm giảm đáng kể hiệu suất làm việc của hệ thống. Vì những lý do đó mà mô hình này không còn được sử dụng nữa. Một mô hình thứ hai được đề cập trong phần tiếp theo là hệ điều hành hỗ trợ nhiều bộ xử lý hoạt động theo cơ chế Chủ-Tớ (Master-Slave). 6.2.2. Hệ điều hành cho nhiều bộ xử lý họat động theo cơ chế Chủ-Tớ (Master-Slave) Trong mô hình này, được trình bày trong hình 6-7, một bản sao của hệ điều hành được lưu giữ trên CPU 1, các CPU khác không có tính năng này. Khi đó, tất cả các lời gọi hệ thống đều được chuyển đến CPU 1 để được xử lý ở đây. Ngoài ra, CPU 1 cũng có thể chạy các tiến trình người dùng nếu nó có dư thời gian. Mô hình này được gọi là “Chủ-Tớ” với CPU 1 là “chủ” còn các CPU khác đóng vai trò là “tớ”. Mô hình Chủ-Tớ này giải quyết hầu hết các vấn đề trong mô hình thứ nhất. Có một cấu trúc dữ OPEN.PTIT.EDU.VNliệu duy nhất (thí dụ như một danh sách hoặc một tập các danh sách được sắp thứ tự ưu tiên) để theo vết các tiến trình sẵn sàng. Khi một CPU muốn đi vào trạng thái rỗi, nó sẽ yêu cầu hệ điều hành gán cho nó một tiến trình để thực thi. Nếu được gán thì nó tiếp tục làm việc, nếu không nó mới đi vào trạng thái rỗi. Như vậy, sẽ không bao giờ xảy ra trường hợp một CPU rỗi trong khi một CPU khác quá tải. Tương tự thế, các trang nhớ cũng có thể được phân phối cho tất cả các tiến trình một cách linh động. Ngoài ra, mô hình này chỉ hỗ trợ một vùng nhớ cache nên sẽ không bao giờ xảy ra việc có những kết quả mâu thuẫn nhau. 151
52. Hình 6.6. Mô hình hệ điều hành Chủ-Tớ trong hệ thống đa xử lý Vấn đề trong mô hình này là hệ thống có thể xảy ra tình trạng nghẽn cổ chai tại CPU “chủ” nếu có quá nhiều CPU trong hệ thống. Nghĩa là CPU “chủ” phải giải quyết tất cả các lời gọi hệ thống từ các CPU “tớ”. Giả sử có 10% tổng thời gian được dùng vào việc xử lý các lời gọi hệ thống thì với hệ thống có 10 CPU nó sẽ làm tràn ngập CPU “chủ”. Còn nếu hệ thống có 20 CPU thì nó sẽ bị quá tải. Vì vậy mô hình này là đơn giản và chỉ có thể làm việc được cho các hệ thống đa xử lý với số lượng nhỏ các CPU. 6.2.3. Hệ điều hành cho hệ thống có nhiều bộ xử lý đối xứng (Symmetric multiprocessors) Trong mô hình này, chỉ có một bản sao của hệ điều hành trong bộ nhớ, nhưng bất kỳ CPU nào cũng có khả năng sử dụng nó. Khi một lời gọi hệ thống được tạo ra cho một CPU nào đó, thì CPU này sẽ thực hiện truy xuất đến kernel của hệ điều hành và tiến hành xử lý lời gọi hệ thống đó. Mô hình này được thể hiện trong hình 6-8. Hình 6.7. Mô hình hệ điều hành cho hệ thống đa xử lý đối xứng OPEN.PTIT.EDU.VN Mô hình này làm cân bằng quá trình xử lý và phân phối bộ nhớ một cách linh hoạt trong hệ thống vì nó chỉ hỗ trợ duy nhất một tập các bảng của hệ điều hành trên cùng một phần cứng. Ngoài ra, nó còn loại bỏ được vấn đề nghẽn cổ chai trong mô hình “chủ-tớ” vì nó không có CPU nào đóng vai trò “chủ” trong hệ thống cả. Tuy nhiên nó vẫn có vấn đề của riêng nó. Nếu có hai hoặc nhiều CPU đang thực thi cùng lúc các đoạn code của hệ điều hành, vấn đề nghiêm trọng sẽ xảy ra. Điều gì sẽ xảy ra nếu có hai CPU chọn cùng tiến trình để thực thi và yêu cầu cùng trang nhớ rỗi? Cách 152
53. đơn giản nhất để giải quyết vấn đề này là sử dụng biến mutex để cho phép khi nào thì một CPU được đi vào miền găng để thực thi tiến trình và sử dụng trang nhớ mà nó cần. Khi một CPU muốn thực thi đoạn code của hệ điều hành, trước tiên nó phải giành được mutex. Nếu mutex bị khóa, nó phải đợi. Theo cách này, bất kỳ CPU nào cũng có thể thực thi code của hệ điều hành, nhưng chỉ tại một thời điểm chỉ có một CPU được thực thi. Tuy nhiên hiệu suất thực hiện của mô hình này cũng không khá hơn mô hình “chủ-tớ” nhiều. Giả sử rằng 10% tổng thời gian được dành cho hệ điều hành xử lý tương tranh, nếu hệ thống hỗ trợ 20 CPU thì cần phải có một hàng đợi CPU khá dài để các CPU lần lượt được phục vụ. Tuy thế, trong mô hình này, điều này được cải thiện dễ dàng hơn. Vì rằng, nhiều phần trong một hệ điều hành là độc lập với một vài phần khác. Chẳng hạn như, sẽ chẳng có vấn đề gì nếu một CPU đang thực thi việc điều phối trong khi một CPU thứ hai khác đang giải quyết một lời gọi hệ thống về tập tin và một CPU thứ ba thì lại đang xử lý vấn đề lỗi trang. Từ nhận xét này, chúng ta thấy rõ rằng hệ thống có thể được chia thành nhiều miền găng độc lập, các miền găng này không thực hiện bất kỳ một sự tương tác nào với nhau. Mỗi miền găng được bảo vệ bởi một biến mutex của nó, và như vậy chỉ có một CPU có thể thực thi code của hệ điều hành tại một thời điểm. Tương tự như trong trường hợp một bảng nào đó trong hệ điều hành có thể được sử dụng bởi nhiều miền găng, và mỗi bảng như thế cũng cần có một biến mutex của chính nó để quản lý việc tương tranh. Theo cách này, mỗi miền găng có thể được thực thi bởi một CPU tại một thời điểm và mỗi bảng (được bảo vệ bởi miền găng) cùng có thể được truy xuất chỉ bời một CPU ở một thời điểm. Hầu hết các hệ thống có nhiều bộ xử lý đều sử dụng mô hình này. Cái khó trong cách tiếp cận này không nằm ở chỗ viết code như thế nào cho khác với một hệ điều hành thông thường trước đây. Mà cái khó ở đây là việc chia nó thành nhiều miền găng để có thể thực thi code của hệ điều hành một cách đồng thời bởi nhiều CPU mà không bị ảnh hưởng bởi bất kỳ một CPU nào khác. Bên cạnh đó, tất cả các bảng được sử dụng bởi hai hoặc nhiều miền găng phải được bảo vệ bằng một biến mutex và các đoạn code đang sử dụng bảng này cũng phải sử dụng biến muxtex một cách phù hợp. Ngoài ra, vấn đề “khóa chết” (deadlocks) cũng phải được quan tâm. Nếu cả hai miền găng đều cần dùng bảng A và bảng B, và một trong hai miền găng này yêu cầu bảng A trước trong khi miền găng kia lại yêu cầu bảng B trước. Vì vậy, trước sau gì thì deadlock cũng sẽ xảy ra và không miền găng nào biết được lý do tại sao. Theo lý thuyết thì tất cả các bảng nên được gán các giá trị nguyên, và các miền găng cũng cần giành được các bảng theo thứ tự tăng dần. Chiến lược này sẽ tránh deadlocks nhưng nó đòi hỏi người lập trình phải suy nghĩ rất cẩn thận để chọn ra bảng nào mà mỗi miền găng cần giành được theo đúng thứ tự. Khi code đã được phát triển sau một thời gian thực thi, một miền găng có thể cần một bảng mới mà nó chưa bao giờ cần trước đây. Nếu một lập trình viên chưa có kinh nghiệm và chưa hiều rỏ về họat động logic của hệ thống thì sẽ dễ dàng thực hiện việc chọn ra một mutex cho bảng mà miền găng cần và sau đó giải phòng nó đi khi không còn cần đến nữa. Điều này dễ dẩn đến deadlocks. Vì vậy, việc sử dụng biến mutex đã OPEN.PTIT.EDU.VNkhông dễ thì việc giữ nó làm việc đúng trong suốt quá trình họat động của hệ thống là điều cực hơn đối với các lập trình viên. 153