Giáo trình Nguyên Lý Hệ Điều Hành Phần 2: Điều Khiển và Quản Lý Bộ Nhớ

Giáo trình nghiên cứu nguyên lý các hệ điều hành phần 2, trình bày lý thuyết rõ ràng, minh họa ví dụ thực tế, phù hợp sinh viên ., phục vụ nghiên cứu và ứng dụng thực tiễn

• Trường học: Không rõ
• Chuyên ngành: Hệ điều hành
• Đề tài: Quản Lý Bộ Nhớ
• Loại tài liệu: Bài giảng
• Năm xuất bản: Không rõ
• Địa điểm: Không rõ

Mục lục chi tiết

• 3. CHƯƠNG 3: ĐIỀU KHIỂN BỘ NHỚ
• 3.1. Một số khái niệm liên quan đến bộ nhớ
• 3.2. Quản lý phân phối bộ nhớ. Vấn đề bảo vệ bộ nhớ
• 3.3. Điều khiển bộ nhớ trong chế độ đơn chương trình
• 3.4. Điều khiển bộ nhớ liên tục theo đa bài toán
• 3.5. Giới thiệu
• 3.6. Điều khiển bộ nhớ theo cận thay đổi
• 3.7. Quản lý bộ nhớ rỗi

Tóm tắt

I. Khám phá vai trò của quản lý bộ nhớ trong hệ điều hành

Quản lý bộ nhớ là một trong những chức năng cốt lõi và phức tạp nhất của mọi hệ điều hành hiện đại. Nhiệm vụ chính của nó là điều phối và phân bổ tài nguyên bộ nhớ chính một cách hiệu quả cho nhiều tiến trình đang chạy đồng thời. Nếu không có một cơ chế quản lý chặt chẽ, các chương trình có thể ghi đè lên dữ liệu của nhau, gây ra lỗi hệ thống và làm giảm hiệu suất tổng thể. Mục tiêu cơ bản của quản lý bộ nhớ là đảm bảo mỗi tiến trình có không gian riêng để hoạt động, bảo vệ không gian đó khỏi sự truy cập trái phép, và tối ưu hóa việc sử dụng dung lượng bộ nhớ vật lý có hạn. Để làm được điều này, hệ điều hành phải theo dõi trạng thái của từng vùng nhớ, quyết định cấp phát cho tiến trình nào, và thu hồi khi tiến trình kết thúc. Nền tảng của quá trình này là sự phân biệt rõ ràng giữa không gian địa chỉ mà chương trình "nhìn thấy" và không gian địa chỉ thực tế trên phần cứng, một khái niệm sẽ được làm rõ trong các phần tiếp theo.

1.1. Mục tiêu và nhiệm vụ cốt lõi của quản lý bộ nhớ

Bài toán cơ bản của điều phối bộ nhớ là giải quyết ba yêu cầu chính. Thứ nhất là phân phối các vùng nhớ cho chương trình và dữ liệu để chúng có thể thực thi một cách chính xác. Thứ hai là bảo vệ chương trình và dữ liệu không bị xóa hoặc chồng chéo bởi các tiến trình khác. Cuối cùng là sử dụng bộ nhớ hiệu quả nhất có thể. Để đạt được các mục tiêu này, hệ điều hành phải có khả năng phân rã không gian địa chỉ để tránh xung đột, đồng thời cho phép chia sẻ bộ nhớ khi cần thiết. Ví dụ, nhiều tiến trình người dùng có thể cần truy cập vào cùng một thư viện hệ thống. Cơ chế quản lý bộ nhớ phải hỗ trợ việc dùng chung này một cách an toàn, đảm bảo tính toàn vẹn của cả hệ thống và các ứng dụng.

1.2. Phân biệt không gian địa chỉ logic và địa chỉ vật lý

Một khái niệm nền tảng trong quản lý bộ nhớ là sự tách biệt giữa hai loại không gian địa chỉ. Không gian địa chỉ logic (hay địa chỉ ảo) là tập hợp các địa chỉ được tạo ra bởi CPU trong quá trình một chương trình thực thi. Chương trình và lập trình viên làm việc với không gian này mà không cần biết về cấu trúc vật lý của bộ nhớ. Ngược lại, không gian địa chỉ vật lý là tập hợp các địa chỉ thực tế trong bộ nhớ chính (RAM). Địa chỉ vật lý là địa chỉ mà bộ điều khiển bộ nhớ "nhìn thấy". Việc ánh xạ từ địa chỉ logic sang địa chỉ vật lý là nhiệm vụ quan trọng, thường được thực hiện bởi phần cứng chuyên dụng.

1.3. Vai trò của MMU trong việc ánh xạ và bảo vệ bộ nhớ

Bộ quản lý bộ nhớ, hay MMU (Memory Management Unit), là một thành phần phần cứng thiết yếu nằm giữa CPU và bộ nhớ chính. Chức năng chính của MMU là chuyển đổi nhanh chóng các địa chỉ logic do CPU tạo ra thành các địa chỉ vật lý tương ứng. Quá trình này được gọi là "Binding địa chỉ lúc thực thi" (Execution time binding). MMU sử dụng các thanh ghi cơ sở và thanh ghi giới hạn để thực hiện việc ánh xạ. Ngoài ra, MMU còn đóng vai trò quan trọng trong việc bảo vệ bộ nhớ. Nó kiểm tra mọi địa chỉ do người dùng tạo ra, đảm bảo rằng địa chỉ đó nằm trong phạm vi hợp lệ đã được cấp phát cho tiến trình, từ đó ngăn chặn các truy cập trái phép vào không gian bộ nhớ của hệ điều hành hoặc của các tiến trình khác.

II. Phân mảnh Thách thức lớn nhất trong quản lý bộ nhớ

Một trong những vấn đề cố hữu và khó giải quyết nhất khi quản lý bộ nhớ là hiện tượng phân mảnh. Phân mảnh xảy ra khi các vùng nhớ trống không liên tục với nhau, bị xé lẻ thành nhiều mảnh nhỏ nằm rải rác. Mặc dù tổng dung lượng bộ nhớ trống có thể đủ lớn để đáp ứng một yêu cầu cấp phát, nhưng không có một vùng trống liên tục nào đủ lớn. Điều này dẫn đến lãng phí tài nguyên và suy giảm hiệu năng hệ thống. Hệ điều hành phải đối mặt với hai loại phân mảnh chính là phân mảnh nội và phân mảnh ngoại. Việc hiểu rõ bản chất và nguyên nhân gây ra chúng là bước đầu tiên để tìm ra các chiến lược cấp phát và kỹ thuật quản lý bộ nhớ hiệu quả hơn, nhằm giảm thiểu tác động tiêu cực của hiện tượng này.

2.1. Cấp phát bộ nhớ liên tục và nguyên nhân gây phân mảnh

Trong kỹ thuật cấp phát bộ nhớ liên tục, mỗi tiến trình khi được nạp vào sẽ chiếm một khối bộ nhớ duy nhất và liền kề. Kỹ thuật này đơn giản trong việc quản lý nhưng lại là nguyên nhân chính gây ra phân mảnh bộ nhớ. Khi các tiến trình được nạp vào và giải phóng khỏi bộ nhớ theo thời gian, chúng sẽ để lại các "lỗ hổng" (vùng trống) có kích thước khác nhau. Các lỗ hổng này nằm xen kẽ với các vùng đã được cấp phát. Khi một tiến trình mới cần bộ nhớ, hệ điều hành phải tìm một lỗ hổng đủ lớn. Quá trình này, lặp đi lặp lại, sẽ làm cho các vùng trống ngày càng bị chia nhỏ, dẫn đến phân mảnh.

2.2. Phân biệt phân mảnh nội và phân mảnh ngoại là gì

Có hai loại phân mảnh chính. Phân mảnh ngoại (External Fragmentation) xảy ra khi tổng dung lượng bộ nhớ trống đủ cho một yêu cầu nhưng không liên tục. Các vùng trống bị phân tán thành nhiều mảnh nhỏ, không có mảnh nào đủ lớn để chứa tiến trình mới. Đây là vấn đề của các hệ thống dùng cấp phát liên tục. Ngược lại, phân mảnh nội (Internal Fragmentation) xảy ra khi vùng nhớ được cấp phát cho một tiến trình lớn hơn so với nhu cầu thực tế của nó. Phần bộ nhớ dư thừa bên trong khối đã cấp phát này bị lãng phí vì không thể cấp cho tiến trình khác. Vấn đề này thường xuất hiện trong các hệ thống chia bộ nhớ thành các khối có kích thước cố định, ví dụ như trong kỹ thuật phân trang.

2.3. Các chiến lược cấp phát First fit Best fit và Worst fit

Để cấp phát bộ nhớ từ danh sách các vùng trống, hệ điều hành sử dụng các chiến lược khác nhau. Chiến lược "chọn cái đầu tiên" (First-fit) sẽ duyệt danh sách và chọn vùng trống đầu tiên đủ lớn. Chiến lược này nhanh nhưng có thể để lại nhiều mảnh vụn nhỏ. Chiến lược "chọn cái tốt nhất" (Best-fit) duyệt toàn bộ danh sách để tìm vùng trống nhỏ nhất mà vẫn đủ lớn. Cách này giảm lãng phí nhưng tốn thời gian tìm kiếm. Cuối cùng, Worst-fit chọn vùng trống lớn nhất, với hy vọng phần còn lại sẽ đủ lớn cho các yêu cầu sau này. Tuy nhiên, mỗi chiến lược đều có ưu nhược điểm riêng và không có giải pháp nào loại bỏ hoàn toàn được phân mảnh ngoại.

III. Phương pháp phân trang Giải pháp quản lý bộ nhớ tối ưu

Để khắc phục triệt để vấn đề phân mảnh ngoại do cấp phát liên tục gây ra, kỹ thuật phân trang (Paging) đã ra đời. Đây là một trong những phương pháp quản lý bộ nhớ phổ biến và hiệu quả nhất trong các hệ điều hành hiện đại. Ý tưởng cốt lõi của phân trang là cho phép không gian địa chỉ vật lý của một tiến trình có thể không liên tục. Thay vì cấp một khối nhớ lớn duy nhất, hệ điều hành chia bộ nhớ vật lý thành các khối có kích thước cố định gọi là khung trang (frame), và chia không gian địa chỉ logic của tiến trình thành các khối cùng kích thước gọi là trang (page). Bằng cách này, một tiến trình có thể được nạp vào các khung trang rải rác bất kỳ trong bộ nhớ, loại bỏ hoàn toàn phân mảnh ngoại. Tuy nhiên, nó lại có thể gây ra phân mảnh nội ở trang cuối cùng của tiến trình.

3.1. Cơ chế hoạt động của kỹ thuật phân trang Paging

Khi một tiến trình cần thực thi, các trang của nó sẽ được nạp vào các khung trang (Page Frame) còn trống trong bộ nhớ chính. Hệ điều hành duy trì một bảng trang (Page Table) cho mỗi tiến trình để theo dõi việc ánh xạ này. Địa chỉ logic do CPU tạo ra được chia làm hai phần: số hiệu trang (p) và độ dời trong trang (d). Số hiệu trang (p) được dùng làm chỉ số để tra cứu trong bảng trang, tìm ra địa chỉ cơ sở của khung trang tương ứng trong bộ nhớ vật lý. Địa chỉ vật lý cuối cùng được tính bằng cách cộng địa chỉ cơ sở của khung trang với độ dời (d). Cơ chế này cho phép các trang của một chương trình nằm rải rác, tạo ra sự linh hoạt tối đa trong việc sử dụng bộ nhớ.

3.2. Cấu trúc và chức năng của bảng trang Page Table

Mỗi tiến trình có một bảng trang riêng, lưu trữ ánh xạ giữa các trang logic và các khung trang vật lý. Mỗi phần tử trong bảng trang chứa số hiệu của khung trang vật lý nơi trang logic tương ứng được lưu trữ. Ngoài ra, mỗi phần tử còn có thể chứa các bit thông tin bổ sung như bit hợp lệ/không hợp lệ (valid/invalid bit) để bảo vệ, bit truy cập (access bit), và bit sửa đổi (dirty bit). Bảng trang được lưu trong bộ nhớ chính. Hệ điều hành sử dụng một thanh ghi đặc biệt (Page Table Base Register - PTBR) để trỏ đến vị trí bắt đầu của bảng trang của tiến trình đang chạy. Việc truy cập bộ nhớ trong cơ chế phân trang đòi hỏi hai lần truy cập: một lần để lấy thông tin từ bảng trang và một lần để truy cập dữ liệu thực sự.

3.3. Tăng tốc độ truy cập với bộ đệm TLB Cache

Việc phải truy cập bộ nhớ chính hai lần cho mỗi tham chiếu làm chậm đáng kể hệ thống. Để giải quyết vấn đề này, các hệ thống hiện đại sử dụng một bộ nhớ đệm phần cứng đặc biệt, tốc độ cao gọi là TLB (Translation Lookaside Buffer). TLB hoạt động như một bộ nhớ cache cho bảng trang, lưu trữ các cặp (số hiệu trang, số hiệu khung trang) được truy cập gần đây. Khi CPU tạo ra một địa chỉ logic, số hiệu trang sẽ được tìm kiếm song song trong TLB. Nếu tìm thấy (TLB hit), số hiệu khung trang được lấy ra ngay lập tức và địa chỉ vật lý được hình thành. Nếu không tìm thấy (TLB miss), hệ thống phải truy cập bảng trang trong bộ nhớ chính, và sau đó cập nhật mục mới vào TLB. Tỉ lệ TLB hit cao giúp giảm đáng kể thời gian truy cập bộ nhớ.

IV. Cách quản lý bộ nhớ ảo và kỹ thuật phân đoạn hiệu quả

Bên cạnh phân trang, phân đoạn (Segmentation) và bộ nhớ ảo (Virtual Memory) là hai khái niệm nâng cao giúp hệ điều hành quản lý bộ nhớ một cách linh hoạt và mạnh mẽ hơn. Phân đoạn cung cấp một góc nhìn logic hơn về bộ nhớ cho người lập trình, trong khi bộ nhớ ảo phá vỡ giới hạn của bộ nhớ vật lý, cho phép chạy các chương trình lớn hơn nhiều so với dung lượng RAM thực có. Bộ nhớ ảo là một kỹ thuật cho phép tách biệt bộ nhớ logic của người dùng khỏi bộ nhớ vật lý. Điều này không chỉ cho phép không gian địa chỉ logic có thể lớn hơn rất nhiều so với không gian địa chỉ vật lý mà còn giúp chia sẻ tệp và thư viện hiệu quả hơn, cũng như hỗ trợ tạo tiến trình hiệu quả. Các kỹ thuật này thường được kết hợp với phân trang để tạo ra các hệ thống quản lý bộ nhớ phức tạp và tinh vi.

4.1. Kỹ thuật phân đoạn Segmentation và ưu nhược điểm

Kỹ thuật phân đoạn (Segmentation) chia bộ nhớ theo góc nhìn của người dùng. Một chương trình được xem là một tập hợp các đoạn logic (segment) như: đoạn mã chính, thủ tục, hàm, biến toàn cục, stack... Mỗi đoạn có kích thước thay đổi. Địa chỉ logic bao gồm hai phần: số hiệu đoạn và độ dời trong đoạn. Hệ thống sử dụng một bảng đoạn (Segment Table) để ánh xạ. Ưu điểm của phân đoạn là hỗ trợ chia sẻ và bảo vệ bộ nhớ theo cấu trúc logic của chương trình. Tuy nhiên, nhược điểm lớn của nó là kích thước đoạn thay đổi gây ra phân mảnh ngoại, một vấn đề mà phân trang đã giải quyết. Nhiều hệ thống hiện đại kết hợp cả phân trang và phân đoạn để tận dụng ưu điểm của cả hai.

4.2. Khái niệm bộ nhớ ảo Virtual Memory và các lợi ích

Bộ nhớ ảo là một kỹ thuật cho phép thực thi một tiến trình mà không cần nạp toàn bộ nó vào bộ nhớ vật lý. Chỉ những phần cần thiết của chương trình mới được đưa vào bộ nhớ. Lợi ích chính là chương trình không còn bị giới hạn bởi dung lượng RAM. Nó cũng cho phép nhiều tiến trình chạy đồng thời hơn, tăng hiệu suất CPU. Hơn nữa, bộ nhớ ảo đơn giản hóa việc lập trình, vì lập trình viên không cần lo lắng về việc quản lý không gian bộ nhớ hạn chế. Cơ chế này thường được hiện thực hóa bằng phân trang theo yêu cầu (Demand Paging), kết hợp với kỹ thuật hoán đổi (Swapping) để đưa các trang ra/vào giữa bộ nhớ chính và bộ nhớ phụ (đĩa cứng).

4.3. Xử lý lỗi trang Page Fault và phân trang theo yêu cầu

Demand Paging (Phân trang theo yêu cầu) là một kỹ thuật cốt lõi của bộ nhớ ảo. Theo đó, một trang chỉ được nạp vào bộ nhớ khi nó thực sự được tham chiếu đến. Khi một tiến trình cố gắng truy cập một trang chưa có trong bộ nhớ (được đánh dấu là không hợp lệ trong bảng trang), một ngắt đặc biệt gọi là Page Fault sẽ xảy ra. Hệ điều hành sẽ xử lý ngắt này bằng cách: tìm trang yêu cầu trên đĩa, tìm một khung trang trống trong bộ nhớ (hoặc giải phóng một khung trang đang dùng), nạp trang từ đĩa vào khung trang đó, và cập nhật lại bảng trang. Sau đó, lệnh gây ra lỗi sẽ được thực thi lại. Quá trình này diễn ra một cách trong suốt đối với tiến trình.

V. Top các thuật toán thay thế trang trong quản lý bộ nhớ

Khi sử dụng bộ nhớ ảo và phân trang theo yêu cầu, một tình huống tất yếu sẽ xảy ra: bộ nhớ chính bị đầy nhưng hệ thống lại cần nạp một trang mới từ đĩa vào. Lúc này, hệ điều hành phải quyết định "hy sinh" một trang nào đó hiện có trong bộ nhớ để giải phóng khung trang. Việc lựa chọn trang nào để thay thế có ảnh hưởng lớn đến hiệu suất hệ thống. Một thuật toán tốt sẽ chọn trang ít có khả năng được sử dụng trong tương lai gần nhất, nhằm giảm thiểu số lần xảy ra Page Fault. Có nhiều thuật toán thay thế trang đã được đề xuất, mỗi thuật toán có sự cân bằng khác nhau giữa độ phức tạp và hiệu quả. Việc lựa chọn thuật toán phù hợp phụ thuộc vào yêu cầu cụ thể của hệ điều hành.

5.1. Thuật toán FIFO Đơn giản nhưng có thể kém hiệu quả

Thuật toán FIFO (First-In, First-Out) là thuật toán đơn giản nhất. Nó hoạt động giống như một hàng đợi: trang nào được nạp vào bộ nhớ sớm nhất sẽ là trang đầu tiên bị thay thế. Để cài đặt, hệ điều hành chỉ cần duy trì một danh sách các trang theo thứ tự thời gian chúng được nạp vào. Mặc dù dễ cài đặt, FIFO có thể hoạt động không tốt. Nó có thể loại bỏ một trang quan trọng đã được nạp vào từ lâu và vẫn đang được sử dụng thường xuyên. Trong một số trường hợp, việc tăng số khung trang có sẵn cho một tiến trình thậm chí có thể làm tăng số lỗi trang, một hiện tượng dị thường gọi là "Anomalous Belady".

5.2. Thuật toán LRU Tối ưu dựa trên tần suất sử dụng

Thuật toán LRU (Least Recently Used) hoạt động dựa trên nguyên tắc: trang nào không được sử dụng trong một khoảng thời gian dài nhất thì ít có khả năng được sử dụng trong tương lai gần. Do đó, LRU sẽ chọn trang ít được sử dụng gần đây nhất để thay thế. Về mặt lý thuyết, LRU cho hiệu suất rất tốt và không bị Anomalous Belady. Tuy nhiên, việc cài đặt LRU một cách chính xác đòi hỏi sự hỗ trợ phần cứng đáng kể để theo dõi thời điểm cuối cùng mỗi trang được truy cập. Các phương pháp cài đặt phổ biến bao gồm sử dụng bộ đếm thời gian cho mỗi mục trong bảng trang hoặc sử dụng một ngăn xếp để duy trì thứ tự truy cập. Do sự phức tạp này, nhiều hệ thống sử dụng các thuật toán xấp xỉ LRU.

Nội dung chính

GIÁO TRÌNH NGUYÊN LÝ CÁC HỆ ĐIỀU HÀNH

• Tác giả: PGS. Hà Quang Thụy
• Nhà xuất bản: Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội
• Thông tin xuất bản: Chịu trách nhiệm xuất bản: TS. Phạm Văn Diễn; Biên tập: ThS. Nguyễn Huy Tiến; Sửa bài: Ngọc Linh; Trình bày bìa: Xuân Dũng. Xuất bản và nộp lưu chiểu Quý III năm 2009. Khổ sách: $16 \times 24\text{ cm}$.

---

1. Tổng quan về giáo trình

Giáo trình Nguyên lý các Hệ điều hành do PGS. Hà Quang Thụy biên soạn là tài liệu học tập chính quy dành cho sinh viên và học viên chuyên ngành Công nghệ Thông tin và Khoa học Máy tính tại các trường đại học, học viện. Trong khung chương trình đào tạo kỹ sư và cử nhân công nghệ thông tin, học phần này giữ vị trí kiến thức cơ sở ngành bắt buộc, làm cầu nối trung gian giữa khối kiến thức phần cứng (Kiến trúc máy tính, Kỹ thuật vi xử lý) và khối kiến thức phần mềm ứng dụng, hệ thống thông tin.

Mục tiêu học tập của giáo trình nhằm trang bị cho người học:

1. Bản chất và các nguyên lý cơ bản điều khiển tài nguyên của hệ thống máy tính (bộ nhớ trong, bộ xử lý trung tâm, thiết bị ngoại vi, tệp tin).
2. Các cấu trúc dữ liệu hệ thống cùng thuật toán điều phối quá trình, quản lý bộ nhớ thực và bộ nhớ ảo, cơ chế phân xử tranh chấp và kiểm soát bế tắc (Deadlock).
3. Cơ chế hoạt động của các hệ điều hành đơn chương trình, đa chương trình, hệ thống đa xử lý tập trung và phân tán.

Cấu trúc giáo trình tiếp cận từ nguyên lý trừu tượng đến hiện thực hóa kỹ thuật thông qua các cấu trúc dữ liệu cụ thể (như bảng mô tả phân khu PDT, khối điều khiển bộ nhớ MCB, khối điều khiển quá trình PCB). Điểm đặc sắc của công trình là sự gắn kết giữa lý thuyết hệ điều hành với việc mô hình hóa toán học (đồ thị định hướng phi chu trình DAG cho thuật toán song song) và cấu phần nghiên cứu tình huống (Case-study) thiết kế nhân hệ điều hành thực nghiệm KMOS.

---

2. Nội dung kiến thức cốt lõi

                             KIẾN TRÚC NỘI DUNG GIÁO TRÌNH

Các chương và chủ đề chính

• Chương 3: Điều khiển bộ nhớ
  Khảo sát toàn diện các phương thức quản lý không gian địa chỉ vật lý và bộ nhớ ảo. Nội dung bắt đầu từ các khái niệm địa chỉ tuyệt đối và địa chỉ tương đối (sử dụng thanh ghi cơ sở CS, DS, SS, ES và thanh ghi chỉ số trong chế độ địa chỉ [BX+SI+4]), quản lý bộ nhớ đơn chương trình thông qua khối MCB (Memory Control Block) trong vùng nhớ TPA (Transient Program Area) của MS-DOS/PC-DOS. Tiếp đó, chương phân tích các chiến lược phân phối bộ nhớ liên tục theo cơ chế giới hạn tĩnh (MFT với bảng PDT) và giới hạn động (MVT); giải thuật quản lý vùng nhớ rỗi bằng phương pháp kề cận nhị phân (Buddy system) và kề cận tổng quát Fibonacci; các kỹ thuật Overlay, Swapping; kết thúc bằng cơ chế quản lý bộ nhớ gián đoạn thông qua phân đoạn (Segmentation), phân trang (Paging với các giải thuật thay thế trang FIFO, LRU, LFU) và cơ chế trộn Segment - Trang với bộ ba chỉ số $(s, p, i)$.

• Chương 4: Điều khiển CPU, điều khiển quá trình
  Trình bày bản chất của quá trình (Process) theo quan niệm của D. Parnas (1974), phân biệt giữa chương trình tĩnh và quá trình động, giữa trạng thái CPU bài toán (User mode) và trạng thái kiểm tác (Supervisor mode). Chương mô tả mô hình 3 trạng thái cơ bản của quá trình (Sử dụng/Running, Chuẩn bị/Ready, Chờ đợi/Blocked), cấu trúc khối điều khiển quá trình PCB (Process Control Block) hoặc TCB (Task Control Block). Phân định rõ chức năng giữa bộ điều phối chính (khởi tạo, kết thúc, quản lý CPU ảo) và bộ điều phối mức dưới (cấp phát CPU thực). Phân tích các nguyên tắc điều phối như FCFS (First-Come First-Served), cơ chế đồng bộ hóa tiến trình bằng biến Semaphore với các toán tử nguyên tử $P$ và $V$; các điều kiện sinh ra bế tắc (Deadlock), phương pháp phòng ngừa, phát hiện và bẻ gãy bế tắc dựa trên các ma trận $ALLOCATED$, $AVAILABLE$, $REQUESTED$.

• Chương 5: Hệ điều hành đa xử lý
  Phân loại hệ thống đa xử lý theo vị trí địa lý (tập trung và phân tán) và theo phân loại Flynn (SISD, SIMD, MISD, MIMD; mở rộng sang SPMD, MPSD, MPMD trong tính toán cụm Cluster Computing). Phân tích các mô hình phần cứng điển hình: ILLIAC-IV ($64$ bộ xử lý cấu trúc ma trận $8 \times 8$ điều khiển bởi máy tính B6500) và CRAY-1 (xử lý vector dây chuyền tốc độ $80\text{--}140\text{ MIPS}$). Trình bày lý thuyết thuật toán song song thông qua mô hình đồ thị định hướng phi chu trình (DAG), phương pháp sắp xếp tô-pô, xác định chiều cao (thời gian tính toán) và bề rộng (số CPU tối thiểu). Chương cũng mở rộng sang hệ điều hành phân tán với mô hình Client/Server, vấn đề bảo đảm tính nhất quán dữ liệu và cơ chế lưu trữ kép.

• Progression logic (Logic phát triển nội dung):
  Giáo trình xây dựng tiến trình nhận thức đi từ mức vi mô đến vĩ mô: từ quản lý không gian nhớ của một tiến trình đơn nhiệm $\rightarrow$ phân phối đa nhiệm trên hệ thống đơn xử lý $\rightarrow$ điều phối thời gian CPU và giải quyết tranh chấp tài nguyên giữa nhiều tiến trình $\rightarrow$ mở rộng lên kiến trúc song song đa CPU tập trung và hệ thống phân tán diện rộng.

Kiến thức nền tảng được xây dựng

• Lý thuyết không gian địa chỉ và ánh xạ địa chỉ: Hệ thống hóa quá trình chuyển dịch từ Không gian tên logic $\rightarrow$ Không gian địa chỉ ảo (do trình dịch thiết lập) $\rightarrow$ Không gian địa chỉ thực vật lý (do hệ điều hành và phần cứng ánh xạ).
• Lý thuyết quá trình và chuyển trạng thái: Mô hình hóa vòng đời tiến trình, phân biệt vai trò giữa CPU thực và CPU ảo, quản trị ngữ cảnh thông qua cấu trúc PCB.
• Nguyên lý đồng bộ hóa và điều khiển tài nguyên: Nền tảng toán học về miền tương hỗ loại trừ, cấu trúc Semaphore của Dijkstra, giải thuật đồ thị và ma trận trạng thái để kiểm soát hiện tượng bế tắc hệ thống.
• Lý thuyết tính toán song song: Biểu diễn thuật toán dưới dạng cấu trúc đa tầng, xác định quan hệ phụ thuộc dữ liệu và giới hạn tối ưu của việc song song hóa thuật toán số học (như biến đổi Fourier nhanh FFT, nhân ma trận).

Kỹ năng phát triển

• Kỹ năng kỹ thuật (Technical skills): Nắm vững quy trình chuyển đổi địa chỉ ảo sang địa chỉ thực trên các kiến trúc phân đoạn, phân trang và kết hợp; giải mã và thao tác trên cấu trúc bảng mô tả hệ thống (PDT, MCB, bản đồ trang/đoạn).
• Kỹ năng phân tích (Analytical skills): Đo lường và đánh giá hiệu năng của các giải thuật thay thế trang bộ nhớ ảo (so sánh số lần lỗi trang giữa FIFO và LRU); phân tích định lượng thời gian chờ trung bình của các thuật toán điều phối CPU; phát hiện khả năng bế tắc thông qua các điều kiện ràng buộc tài nguyên.
• Năng lực thực tế (Practical competencies): Vận dụng ngôn ngữ lập trình cấp cao (như Pascal, C) và Hợp ngữ để mô phỏng cơ chế cấp phát bộ nhớ rỗi; lập trình đồng bộ tiến trình thông qua biến cờ/Semaphore; tiếp cận quy trình thiết kế mã nguồn cho nhân hệ điều hành đa nhiệm thực nghiệm KMOS.

---

3. Phương pháp giảng dạy và học tập

                         KHUNG THỜI LƯỢNG GIẢNG DẠY

Giáo trình được thiết kế tương thích với khung thời lượng đào tạo chuẩn gồm 30 đến 33 tiết giảng dạy lý thuyết trên lớp và 01 đơn vị học trình dành riêng cho hoạt động thực hành, nghiên cứu trường hợp riêng (Case-study).

Phương pháp tiếp cận sư phạm kết hợp giữa thuyết giảng nguyên lý và thảo luận chuyên đề:

• Tổ chức nghiên cứu tình huống (Case-study):
  Hoạt động được tiến hành trong 3 đến 4 buổi học. Sinh viên thành lập nhóm từ 2 đến 3 người, chủ động lựa chọn hoặc được phân công các chủ đề chuyên sâu trích xuất từ các tài liệu kinh điển quốc tế:

  • Khảo sát kiến trúc hệ điều hành MS-DOS (dựa theo Chương 8 tài liệu Modern Operating Systems).
  • Khảo sát kiến trúc hệ điều hành UNIX (dựa theo Chương 7 tài liệu Modern Operating Systems).
  • Quy trình thiết kế và hoàn thiện nhân hệ điều hành đa bài toán KMOS (Kernel for Multiprogramming Operating System - Chương 11 tài liệu Operating System: Concepts and Design). Nhiệm vụ của mỗi nhóm bao gồm dịch thuật tài liệu, biên tập nội dung, thuyết trình trước lớp và bảo vệ quan điểm học thuật thông qua giải đáp câu hỏi của giảng viên cùng tập thể sinh viên.

• Hệ thống bài tập thực hành (Practical exercises):
  Cuối mỗi chương, giáo trình cung cấp hệ thống bài tập đa dạng nhằm củng cố năng lực tính toán và lập trình:

  • Bài tập lập trình: Viết chương trình Pascal quản lý mảng $2^n$ bit nhị phân để mô phỏng thuật toán cấp phát và phân phối vùng nhớ rỗi cho một tiến trình; lập trình quản lý khối nhớ Overlay.
  • Bài tập vết giải thuật: Thực hiện mô phỏng quá trình chuyển dịch địa chỉ ảo $(s, d)$ sang địa chỉ vật lý dựa trên bảng Segment tổng thể; tính toán chính xác số lần tráo đổi trang của các giải thuật FIFO và LRU dựa trên chuỗi truy cập trang bộ nhớ cho trước.
  • Bài tập phân tích cơ chế: Mô tả chi tiết biến trạng thái Semaphore và hoạt động của hàng đợi tiến trình kết khối qua chuỗi 14 trạng thái đồng bộ; giải thích cơ chế ngắt Ctrl-Break trong môi trường MS-DOS.

• Phương pháp đánh giá và hướng dẫn tự học:
  Đánh giá kết quả học tập của sinh viên dựa trên tổng hòa các điểm số: bài tập tính toán định lượng cá nhân, chất lượng bản báo cáo biên tập và năng lực thuyết trình của nhóm trong các buổi hội thảo Case-study, cùng bài thi kết thúc học phần. Người học được hướng dẫn tự nghiên cứu bằng cách đối chiếu mã nguồn hệ thống mẫu, vẽ sơ đồ chuyển trạng thái và tự cài đặt lại các cấu trúc dữ liệu quản lý bộ nhớ rỗi trên môi trường máy vi tính.

---

4. Điểm nổi bật và cập nhật

• Minh họa trên các hệ thống phần cứng và hệ điều hành thực tế:
  Giáo trình phân tích cấu trúc bộ nhớ và cơ chế điều khiển của các hệ thống máy tính thực: từ kiến trúc máy vi tính 16-bit (phân đoạn địa chỉ Segment/Offset với các thanh ghi CS, DS, SS, ES), vi xử lý Intel 80386 trở đi cho phép vận hành chế độ bảo vệ đa nhiệm (Protected mode), đến việc phân định xử lý giữa CPU chính 80x86 và bộ đồng xử lý toán học dấu phẩy động 80x87.

• Tích hợp các trường phái siêu máy tính và tính toán hiệu năng cao:
  Bên cạnh các hệ điều hành thông dụng (PC-DOS, MS-DOS, UNIX), giáo trình đưa vào phân tích chuyên sâu kiến trúc tính toán của các siêu máy tính kinh điển:

  • ILLIAC-IV: Hệ thống SIMD gồm 64 bộ xử lý 64-bit sắp xếp theo ma trận $8 \times 8$, mỗi bộ xử lý có 2048 từ nhớ riêng, đạt hiệu năng 100–200 MIPS dưới sự điều phối của máy chủ Burroughs B6500.
  • CRAY-1: Hệ thống MISD/Vector đạt hiệu năng 80–140 MIPS với 12 thiết bị chức năng trung tâm làm việc đồng thời theo nguyên lý dây chuyền.
  • Xu hướng tính toán cụm (Cluster Computing): Khái quát hóa các mô hình SPMD, MPSD, MPMD phục vụ xử lý song song các bài toán khoa học kỹ thuật quy mô lớn.

• Khai thác hệ thống tài liệu tham khảo chuẩn quốc tế:
  Nội dung giáo trình được biên soạn dựa trên sự tổng hợp có chọn lọc từ các giáo trình và công trình nghiên cứu uy tín trên thế giới:

  • Modern Operating Systems của Andrew S. Tanenbaum.
  • Distributed Operating Systems and Algorithms của Randy Chow và Theodore Johnson (1997).
  • Operating System: Concepts and Design của Milan Milenković.
  • Giáo trình chuẩn mã môn CS260: Operating Systems của Khoa Khoa học Máy tính - Đại học RMIT (1997).
  • Chương trình đào tạo ngành Khoa học Thông tin và Máy tính niên khóa 1998–1999 của Đại học California, Irvine (UC Irvine).

---

5. Đối tượng sử dụng giáo trình

• Sinh viên chuyên ngành:
  Giáo trình được thiết kế cho sinh viên đại học năm thứ hai hoặc năm thứ ba thuộc các ngành: Công nghệ Thông tin, Khoa học Máy tính, Kỹ thuật Phần mềm, Mạng máy tính và Truyền thông dữ liệu, Hệ thống Thông tin. Ngoài ra, học viên cao học chuyên ngành Khoa học Máy tính có thể sử dụng cuốn sách làm tài liệu ôn tập và đào sâu các mô hình lý thuyết tính toán song song, phân tán.

• Yêu cầu kiến thức nền tảng (Prerequisites):
  Để tiếp thu tốt nội dung giáo trình, người học cần hoàn thành các học phần tiên quyết:

  • Kiến trúc máy tính & Hợp ngữ (Assembly): Hiểu rõ cấu trúc thanh ghi, chu kỳ lệnh, ngăn xếp (Stack), địa chỉ hóa bộ nhớ và các cơ chế ngắt phần cứng.
  • Cấu trúc dữ liệu và Giải thuật: Nắm vững các cấu trúc danh sách liên kết, mảng, ngăn xếp, hàng đợi và các thuật toán đồ thị cơ bản.
  • Kỹ năng lập trình cơ sở: Thành thạo một ngôn ngữ lập trình có cấu trúc (như C hoặc Pascal) để thực hiện các bài tập lập trình mô phỏng.

• Ứng dụng đối với giảng viên:
  Tài liệu cung cấp đề cương bài giảng lý thuyết chi tiết theo từng đề mục chuẩn mực, đi kèm hệ thống câu hỏi, sơ đồ kỹ thuật và định hướng phân chia nhóm sinh viên thực hiện bài tập lớn/Case-study trong 3–4 buổi seminar chuyên đề.

• Tham khảo tự học và nghiên cứu:
  Kỹ sư phát triển phần mềm nhúng, lập trình viên hệ thống và các nhà nghiên cứu cần tra cứu nguyên lý cấu trúc phân vùng bộ nhớ, giải thuật điều phối hàng đợi và cơ chế phân chia tài nguyên trong các hệ thống tính toán lớn.

---

6. Câu hỏi thường gặp

1. Giáo trình này phù hợp với đối tượng nào?

Giáo trình phục vụ giảng dạy chính quy cho sinh viên đại học, học viên cao học ngành Công nghệ Thông tin, Khoa học Máy tính và các kỹ sư phần mềm cần nắm vững nguyên lý hoạt động của hệ điều hành.

2. Cần trang bị những kiến thức nền tảng nào trước khi học?

Người học cần có kiến thức cơ bản về Kiến trúc máy tính, ngôn ngữ Hợp ngữ (đặc biệt là chế độ địa chỉ trên dòng vi xử lý Intel x86), Cấu trúc dữ liệu và Giải thuật, cùng kỹ năng lập trình bằng ngôn ngữ C hoặc Pascal.

3. Điểm khác biệt của giáo trình này so với các tài liệu khác là gì?

Tài liệu kết hợp chặt chẽ giữa việc mô tả cấu trúc dữ liệu cụ thể (như bản ghi MCB 16-byte, bảng PDT, cấu trúc 3 trường của bảng Segment) với việc mô hình hóa toán học cho tính toán song song (đồ thị DAG, sắp xếp tô-pô) và dành trọn 01 đơn vị học trình cho hoạt động nghiên cứu trường hợp thiết kế nhân KMOS.

4. Phương pháp tự học giáo trình như thế nào để đạt hiệu quả cao?

Người học nên đọc song song lý thuyết từng chương với việc giải các bài tập vết giải thuật (thuật toán thay thế trang FIFO/LRU, chuyển đổi địa chỉ), đồng thời tự viết mã nguồn mô phỏng các giải thuật phân phối bộ nhớ rỗi và quản lý Semaphore bằng ngôn ngữ lập trình bậc cao.

5. Có tài liệu bổ trợ nào kèm theo giáo trình?

Giáo trình dẫn chiếu trực tiếp đến các tài liệu nghiên cứu chuyên sâu gồm: tài liệu thiết kế nhân KMOS (Operating System: Concepts and Design), các chương tình huống về MS-DOS/UNIX trong Modern Operating Systems, giáo trình chuyên đề Mạng và các hệ phân tán, cùng các chương trình môn học chuẩn từ Đại học RMIT và UC Irvine.

---

7. Kết luận

Giáo trình Nguyên lý các Hệ điều hành của PGS. Hà Quang Thụy cung cấp nền tảng tri thức toàn diện về kiến trúc và cơ chế điều hành tài nguyên hệ thống máy tính. Toàn bộ nội dung được trình bày tường minh thông qua hệ thống định nghĩa chuẩn mực, cấu trúc dữ liệu cụ thể, sơ đồ khối kỹ thuật và mô hình toán học giải thuật.

Lộ trình học tập đề xuất:

1. Nắm vững bản chất quản lý bộ nhớ thực và ảo (Chương 3).
2. Làm chủ nguyên lý điều phối tiến trình và kiểm soát bế tắc (Chương 4).
3. Thực hành thiết kế nhân hệ điều hành thực nghiệm KMOS và phân tích trường hợp MS-DOS/UNIX.
4. Mở rộng nghiên cứu sang kiến trúc tính toán song song và hệ điều hành phân tán (Chương 5).

Để mở rộng kiến thức, người học nên tiếp tục tham khảo giáo trình chuyên đề Mạng và các hệ phân tán cùng các công trình học thuật chuẩn quốc tế của Randy Chow, Theodore Johnson và Andrew S. Tanenbaum.

Trích đoạn nội dung tài liệu

chương I) và cần cơ chế để bảo vệ các chương trình hệ thống với chương trình người dùng. Đến chế độ đa chương trình thực sự thì vấn đề bảo vệ bộ nhớ không chỉ xảy ra giữa chương trình người dùng với chương trình hệ thống mà còn giữa các chương trình người dùng lẫn nhau. Như đã biết, việc phân chương bộ nhớ góp phần đảm bảo cho việc bảo vệ bộ nhớ. Ngoài ra, thường có một cơ chế kỹ thuật sử dụng các thanh ghi: thanh ghi cơ sở và thanh ghi bảo vệ; và hơn thế nữa, có thể kể đến việc đưa ra những thuộc tính của bộ nhớ và thuộc tính của chương trình về quyền thâm nhập đến bộ nhớ.

Một bài toán cơ bản là số lượng và kích cỡ của các chương bộ nhớ được phân. Người ta phân ra 2 lớp các bài toán mà các chương trình xử lý: tính toán nhiều và vào/ra nhiều. Theo một số thống kê, để bộ xử lý đạt hiệu quả 90%, thường đồng thời có 4 hoặc 5 chương trình trong bộ nhớ. Tồn tại chiến lược giới hạn tĩnh (cận cố định) và chiến lược giới hạn động (cận thay đổi).

Chiến lược giới hạn tĩnh (cận cố định) Một trong những phương pháp điển hình phân phối bộ nhớ liên tục là chiến lược giới hạn tĩnh còn gọi là chiến lược phân chương (tương ứng với chế độ MET của hệ điều hành). Bộ nhớ được chia thành các chương: gán tên chương, địa chỉ, dung lượng trong quá trình khởi tạo hệ điều hành.4 cho một hình ảnh phân chương bộ nhớ và việc phân phối bộ nhớ cho một số chương trình. 184K P4 112K P3 72K P2 32K 0K PO Dia chi Chương bộ nhớ Hình 3. Bộ nhớ được phân chương.

NGUYÊN LÝ CÁC HỆ ĐIỀU HÀNH 7 Đối với ví dụ theo hình vẽ 3.4, bộ nhớ được phân ra thành 5 chương: PO (32K), PI (40K), P2 (40K), P3 (72K), P4 (72K). Chương P0 được dành cho nhân, mỗi chương còn lại đã có một chương trình được tải (load). Kích cỡ (dung lượng) trung bình của mỗi chương phụ thuộc vào dung lượng của bộ nhớ và số lượng chương. Các chương trình được gán số hiệu để chỉ có thể tải vào những chương nhất định.

Nảy sinh trường hợp có thể có những chương rỗi mà không tải được chương trình: lớp gắn với nó bị bận hoặc độ rộng của chương không đủ để tải. Lúc đó hoặc hệ thống hoặc thao tác viên thực hiện việc thay đổi lớp gắn cho chương trình hoặc thay đổi số lượng chương, kích cỡ chương song phổ biến là thao tác viên dùng lệnh để thực hiện công việc đó. Tuy điều đó xem ra có vẻ thủ công song tránh được sự phức tạp cho chương trình điều khiển. Để quản lý bộ nhớ trong trường hợp này, sử dụng bảng mô tả chương (partition đescription table : PDT), có dạng: Số hiệu chương Địa chỉ Độ dài Tình trạng 0 0K 32K đã load 1 32K 40K đã load 2 72K 40K đã load 112K 72K đã load 3 184K 72K đã load 4 nhớ, chiến lược Đối với một bài toán, nó được gắn với một vài chương bộ phối nhanh nhất phân phối bộ nhớ cho nó có thể được kể làm hai hướng: phân tối ưu (chọn chương với (gặp chương được gắn, đủ độ rộng đầu tiên), phân phối nhớ: vùng nhớ dừ thừa là ít nhất).

Trở lại vấn đẻ vướng mắc khi phân phối bộ trình; - Không có chương nào đủ để phân phối cho chương - Mọi chương đã được tải; 78 CHƯƠNG 3. ĐIỀU KHIỂN BỘ NHỚ - Một số chương rỗi, mỗi chương rỗi không đủ chứa bài toán song nối vài chương rỗi tạo ra một vùng bộ nhớ đủ đẻ tải bài toán.