Giáo trình Nguyên lý hệ điều hành

BỘ LAO ĐỘNG – THƯƠNG BINH VÀ XÃ HỘI
TỔNG CỤC DẠY NGHỀ
GIÁO TRÌNH
Môn học: Nguyên lý hệ điều hành
NGHỀ: QUẢN TRỊ MẠNG
TRÌNH ĐỘ: CAO ĐẲNG NGHỀ
(Ban hành kèm theo Quyết định số:120/QĐ-TCDN ngày 25/02/2013 
của Tổng cục trưởng Tổng cục dạy nghề)
Hà Nội, năm 2013
TUYÊN BỐ BẢN QUYỀN: 
	Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể được phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham khảo.
	Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh doanh thiếu lành mạnh sẽ bị nghiêm cấm.
MÃ TÀI LIỆU: MH 10
LỜI GIỚI THIỆU
	Trong hệ thống kiến thức chuyên ngành trang bị cho sinh viên nghề Quản trị mạng máy tính, môn học Nguyên lý hệ điều hành góp phần cung cấp những nội dung liên quan đến việc mô tả các phương pháp giải quyết các bài toán điều khiển hoạt động của hệ thống máy tính
	Các nội dung chính được trình bày trong tài liệu này gồm các chương:
 	-Giới thiệu chung về hệ điều hành
	- Điều khiển dữ liệu
	- Điều khiển bộ nhớ
	- Điều khiển CPU và Tiến trình
	- Hệ điều hành đa xử lý
Mặc dầu có rất nhiều cố gắng, nhưng không tránh khỏi những khiếm khuyết, rất mong nhận được sự đóng góp ý kiến của độc giả để giáo trình được hoàn thiện hơn.
 Hà Nội, ngày 25 tháng 02 năm 2013
Tham gia biên soạn
 1. Chủ biên Ths. Nguyễn Văn Hưng
 2. CN Trương Văn Hiền
MỤC LỤC
NGUYÊN LÝ HỆ ĐIỀU HÀNH
Mã môn học:MH 10
Vị trí, tính chất, ý nghĩa và vai trò môn học:
Vị trí: Môn học được bố trí sau khi sinh viên học xong các môn học chung, trước các môn học, mô đun đào tạo chuyên môn nghề.
Tính chất: Là môn học cơ sở.
Ý nghĩa và vai trò: Đây là môn học cơ sở ngành của các ngành liên quan đến công nghệ thông tin, cung cấp cho sinh viên các kiến thức cơ bản về hệ điều hành để làm nền tản cho việc lập trình giải quyết các vấn đề cần thiết, tối ưu hóa hệ thống máy tính.
Mục tiêu của môn học:
Hiểu vai trò và chức năng của hệ điều hành trong hệ thống máy tính;
Biết các giai đoạn phát triển của hệ điều hành;
Hiểu các nguyên lý thiết kế, thực hiện của hệ điều hành;
Hiểu cách giải quyết các vấn đề phát sinh trong hệ điều hành.
Bố trí làm việc khoa học đảm bảo an toàn cho người và phương tiện học tập.
Nội dung chính của môn học (danh sách các chương mục...):
Số
TT
Tên chương, mục
Thời gian 
Tổng số
Lý thuyết
Thực hành
Kiểm tra* (LT hoặc TH)
I
Tổng quan về hệ điều hành
5
5
0
0
Khái niệm về hệ điều hành 
2
2
0
0
Phân loại hệ điều hành 
2
2
0
0
Sơ lược lịch sử phát triển của HĐH 
1
1
0
0
II
Điều khiển dữ liệu
15
9
5
1
Các phương pháp tổ chức và truy nhập dữ liệu
5
3
2
0
Bản ghi và khối
2
1
1
0
Điều khiển buffer 
2
1
1
0
Quy trình chung điều khiển vào – ra 
2
2
0
0
Tổ chức lưu trữ dữ liệu trên bộ nhớ ngoài 
4
2
1
1
III
Điều khiển bộ nhớ
20
10
9
1
Quản lý và bảo vệ bộ nhớ
2
2
0
0
Điều khiển bộ nhớ liên tục theo đa bài toán
8
3
5
0
Điều khiển bộ nhớ gián đoạn
10
4
5
1
IV
Điều khiển CPU, Điều khiển quá trình
25
12
12
1
Các khái niệm cơ bản 
2
2
0
0
Trạng thái của quá trình 
5
2
3
0
Điều phối quá trình 
3
1
2
0
Các thuật toán lập lịch 
10
4
6
0
Hệ thống ngắt 
1
1
0
0
Hiện tượng bế tắc 
4
2
1
1
V
Hệ điều hành đa xử lý
10
7
2
1
Hệ điều hành đa xử lý tập trung 
5
3
2
0
Hệ điều hành đa xử lý phân tán 
5
3
1
1
Cộng
75
43
28
4
CHƯƠNG 1:GIỚI THIỆU CHUNG VỀ HỆ ĐIỀU HÀNH
 Mã chương: MH10-01
Mục tiêu: 
Nắm được yêu cầu cần có hệ điều hành;
Nắm được khái niệm hệ điều hành, chức năng, phân loại và các thành phần cơ bản trong hệ điều hành;
 - Thực hiện các thao tác an toàn với máy tính.
1. Khái niệm về hệ điều hành
Mục tiêu: Nắm được yêu cầu cần có hệ điều hành;
 Nắm được khái niệm hệ điều hành.
 1.1. Tài nguyên hệ thống
	Tài nguyên của một trung tâm máy tính được tổng hợp từ ba thành tố, đó là tài nguyên về phần cứng, tài nguyên về phần mềm và tài nguyên về nguồn nhân lực của trung tâm máy tính đó.
	Trong các tài liệu giới thiệu về một trung tâm máy tính bất kỳ, các số liệu thống kê về phần cứng (số lượng và chủng loại máy tính, hệ thống thiết bị ngoại vi, khả năng liên kết với môi trường ngoài v.v) luôn là những yếu tố được quan tâm sớm nhất và là thành tố dễ nhận biết nhất về sức mạnh của trung tâm máy tính đó.
	Tài nguyên về phần mềm cũng được chú ý thông qua các thông tin về hệ điều hành được sử dụng, về các phần mềm ứng dụng đã có tại cơ sở tính toán đó. Hiện nay, tại những trung tâm tính toán mạnh, giá trị (tính theo tiền) thực sự của tài nguyên phần mềm lại cao hơn và vượt trội nhiều so với giá trị của tài nguyên phần cứng.
	Tài nguyên về nguồn nhân lực cũng được chú ý, tuy rằng trong một số trường hợp, thành tố này lại khó nhận biết và khó đánh giá hơn so hai loại tài nguyên đã nói ở trên. Năng lực về nguồn nhân lực trong hệ thống nhằm đảm bảo việc thực hiện chức năng bảo trì, phục vụ và phát triển hệ thống (kỹ sư hệ thống, kỹ thuật viên, thao tác viên v.v) thực sự lại đánh giá hơn rất nhiều so với phần cứng và phần mềm.
	Tuy nhiên, trong giáo trình này, chúng ta hạn chế trong một phạm vi tiếp cận là mọi công việc của hệ điều hành bắt đầu từ hệ thống phần cứng có sẵn và hệ điều hành cần phải hoạt động nhằm phát huy cao nhất năng lực của hệ thống phần cứng đó và vì vậy chúng ta chỉ đề cập đến tài nguyên về phần cứng (có thể kể tới một phần về tài nguyên phần mềm) và định hướng tới vấn đề phát huy hiệu quả khai thác các tài nguyên đó.
	Để định hướng tới mục tiêu phát huy hiệu quả các thành phần trong tài nguyên phần cứng, cần xem xét một số đặc trưng cơ bản và đánh giá giá trị của mỗi thành phần trong hệ thống phần cứng, hướng tới mục đích đưa ra được các chiến lược ưu tiên thích đáng (hoặc khả dụng) đối với mỗi thành phần khi xây dựng hệ thống các chương trình điều khiển sự hoạt động của máy tính.
Theo cách tiếp cận của hệ điều hành, các tài nguyên điển hình thuộc phần cứng bao gồm: thiết bị xử lý trung tâm (CPU), bộ nhớ trong, và hệ thống vào – ra (kênh, thiết bị điều khiển thiết bị vào ra và thiết bị vào ra, bộ nhớ ngoài v.v). CPU và bộ nhớ trong thuộc và khu vực trung tâm còn hệ thống vào – ra thường được xếp vào khu vực ngoại vi của hệ thống máy tính.
	Trong các thiết bị nói trên, đáng chú ý nhất phải kể đến là CPU và bộ nhớ trong.
Bộ xử lý trung tâm (Central Processing Unit-CPU)
	Trước hết chúng ta xem xét về các đặc trưng liên quan đến CPU. Việc đánh giá tài nguyên CPU về cơ bản cũng dựa trên các đặc trưng này: tốc độ xử lý, độ dài từ máy, phương pháp thiết kế hệ lệnh máy trong CPU.
	Tốc độ xử lý là thông số thể hiện mức độ làm việc nhanh chậm của CPU dựa trên các đơn vị biểu diễn tốc độ. Tốc độ xử lý của CPU thường được tính theo tần số đồng hồ nhịp (với đơn vị là MHz-triệu nhịp trong 1 giây) khi xem xét tần số đồng hồ nhịp hoặc số lượng phép tính cơ bản được thực hiện trong một giây (với đơn vị là MIPS – Million Instruction Per Second – triệu phép tính cơ bản trong một giây) khi xem xét theo tốc độ thực hiện phép tính (phép cộng tĩnh – không dấu của một CPU thường được coi là phép tính cơ bản của CPU đó). Thông thường, đơn vị đo MHz được dùng cho một CPU cụ thể hoặc một máy vi tính còn đơn vị đo MIPS được dùng cho một hệ thống CPU của một máy tính lớn.
	Độ dài từ máy: Từ máy là lượng thông tin đồng thời mà CPU xử lý trong một nhịp làm việc. Độ dài từ máy chính là số lượng bit nhị phân của toán hạng đối số trong phép tính cơ bản của CPU. Trong thời gian gần đây, chúng ta đã quen thuộc với các CPU 8 bit, 16 bit, 32 bit, 64 bit, và số lượng bit nói trên chính là độ dài từ máy. 
Độ dài của từ máy có quan hệ với tốc độ xử lý. Khi nói đến năng lực hoạt động (tốc độ xử lý thông tin) thực sự của một CPU mà chỉ nói đến tốc độ xử lý mà không nói kèm theo độ dài từ máy là chưa hoàn toàn đầy đủ. Điều đó có thể được diễn giải theo phát biểu như sau “năng lực hoạt động thực sự củaCPU được đánh giá thông qua tốc độ xử lý và độ dài từ máy”.
Bộ nhớ trong (Operative Memory-OM) có một số đặc trưng tiêu biểu như sau:
	Dung lượng bộ nhớ: Khả năng đồng thời lưu trữ thông tin của bộ nhớ trong. Hiện tại dung lượng của bộ nhớ trong từ vài MB đến vài GB.
	Đặc trưng tiếp theo của bộ nhớ trong phù hợp với nguyên lý thứ hai theo Von Neumann là: Bộ nhớ được địa chỉ hóa để truy nhập. Đa số các máy tính được địa chỉ hóa theo byte và trong một số trường hợp lại được địa chỉ hóa theo từ máy.
	Địa chỉ đầu tiên trong bộ nhớ là địa chỉ 0. Lý do của việc chọn địa chỉ đầu tiên là 0 liên quan đến tính chia hết, bởi số 0 chia hết cho mọi số. Khi phân phối bộ nhớ trong cho một đối tượng, trong nhiều trường hợp, địa chỉ vùng bộ nhớ trong của đối tượng phải chia hết cho độ dài vùng bộ nhớ dành cho đối tượng đó hoặc chia hết cho số nào đó (ví dụ, phân phối cho một chương trình trong MS-DOS được bắt đầu bởi địa chỉ đoạn là địa chỉ chia hết cho 16).
	Một đặc trưng (hay cũng vậy là một yêu cầu) mang tính bản chất đối với bộ nhớ trong là: Thời gian truy cập bộ nhớ trong tới mọi địa chỉ nhớ phải đồng nhất; không thể có sự khác biệt giữa thời gian truy cập tới địa chỉ cao với thời gian truy cập tới địa chỉ thấp. Từ đặc trưng này dẫn đến việc đặt ra một yêu cầu là phải tổ chức bộ nhớ trong theo các khối phân cấp để cục bộ dần và việc cục bộ dần như vậy sẽ làm cho việc truy nhập được cân bằng. Nguồn gốc của yêu cầu này liên quan đến tính xác định của thuật toán, hay nói cách khác đi, yêu cầu này nhằm mục tiêu đảm bảo độ tin cậy của hệ thống máy tính. Chúng ta thường thấy bộ nhớ được cấu trúc từ các “ thanh bộ nhớ”, mỗi thanh bộ nhớ lại có thể được phân nhỏ hơn và việc truy nhập bộ nhớ theo cách phân cấp dần theo từng thanh, trong mỗi thanh lại theo từng bộ phận nhỏ hơn có trong thanh đó v.v cho đến khi truy nhập tuần tự trong phần nhỏ nhất chỉ có sai khác thời gian không đáng kể.
	Để tăng tốc độ truy nhập của CPU đối với bộ nhớ trong, người ta thường gắn CPU với bộ nhớ tạm thời của CPU (được gọi là bộ nhớ cache của CPU). Bộ nhớ cache là thiết bị nhớ đặc biệt với tốc độ truy cập của CPU tới cache của nó cao hơn rất nhiều so với tốc độ truy cập vào bộ nhớ trong. Trong cache chứa một phần nội dung của bộ nhớ trong thường là phần bộ nhớ hiện thời (chương trình và dữ liệu) được CPU đang hướng tới. Quá trình hướng truy nhập bộ nhớ (theo địa chỉ) của CPU được bắt đầu từ việc hướng tới cache, nếu cache chứa phần bộ nhớ đó thì việc hướng địa chỉ kết thúc và thực hiện công việc, ngược lại thực hiện việc hướng tới bộ nhớ trong theo quy tắc thông thường.
	Chương trình chỉ chạy được khi chương trình và dữ liệu tương ứng của chương trình đó phải có mặt tại bộ nhớ trong (chính xác hơn là chỉ cần bộ phận hiện thời của chương trình và dữ liệu liên quan đến bộ phận đó nằm trong bộ nhớ trong). Cách thức sử dụng bộ nhớ trong đóng vai trò quan trọng nhằm đảm bảo chất lượng hoạt động của hệ thống và vì vậy, bài toán điều khiển bộ nhớ trong có độ ưu tiên cao chỉ sau bài toán điều khiển CPU.
Hệ thống ngoại vi
	Hệ thống ngoại vi đảm bảo việc chuyển đổi thông tin giữa môi trường ngoài và khu vực trung tâm. Có sự phân cấp trong hệ thống ngoại vi: gần khu vực trung tâm nhất là kênh, sau đó là thiết bị điều khiển thiết bị ngoại vi và ngoài cùng là thiết bị ngoại vi. 
1.2. Khái niệm hệ điều hành
	Hệ thống máy tính là hệ thống kết hợp giữa thiết bị phần cứng và vấn đề điều khiển phân phối công việc trong toàn hệ thống. Để giải quyết bài toán này, không thể dùng phương pháp thủ công mà cần có cơ chế tự động hóa, tức cần có một chương trình điều khiển hoạt động của hệ thống máy tính. Chương trình đó gọi là hệ điều hành, đây là thành phần quan trọng của hệ thống máy tính.
	-Xét về phía người sử dụng thì hệ điều hành cần phải tạo được môi trường giao diện giữa người sử dụng và máy tính.Thông qua môi trường này cho phép người sử dụng đưa ra các lệnh, chỉ thị điều khiển hoạt động của máy tính.
	-Về phía các chương trình ứng dụng thì hệ điều hành phải tạo môi trường để các chương trình hoạt động, cung cấp các cơ chế cho phép kích hoạt hoặc loại bỏ các chương trình ứng dụng.
	-Về phía phần cứng thì hệ điều hành phải quản lý các thiết bị một cách có hiệu quả, khai thác được hết các khả năng của thiết bị, cung cấp cho các chương trình và người sử dụng các tài nguyên phần cứng khi có yêu cầu, thu hồi khi cần thiết.
Hình 1.1 Mô hình trừu tượng của hệ thống máy tính
Vì vậy, hệ điều hành là một tập hợp các chương trình hệ thống có chức năng tạo môi trường giao diện cho người dùng, tạo môi trường hoạt động cho các chương trình ứng dụng, quản lý và khai thác hiệu quả các thiết bị phần cứng.
2. Phân loại hệ điều hành 
Mục tiêu: Nắm được chức năng, phân loại và các thành phần cơ bản trong hệ điều hành.
 	 Nắm được cách thức tải hệ điều hành. 
 2.1. Các thành phần của hệ điều hành
	Theo định nghĩa trên đây, hệ điều hành là một tập hợp các chương trình đã được cài đặt sẵn, mỗi chương trình đảm nhận một chức năng nào đó trong hệ thống chức năng của hệ điều hành. Một trong những nguyên tắc phổ biến nhất để nhận biết các thành phần của hệ điều hành là dựa theo chức năng của các chương trình có trong thành phần đó. Theo nguyên tắc này thì các thành phần cơ bản của hệ điều hành là thành phần điều khiển (control programs), thành phần ứng dụng (application programs, còn gọi thành phần xử lý) và các chương trình tiện ích (utilities).
Thành phần điều khiển
	Thành phần điều khiển liên quan đến chức năng điều khiển, phân phối công việc của hệ điều hành. Khi một chương trình điều khiển hoạt động, nó không cho ra một sản phẩm mới (sản phẩm ở đây là các File trên đĩa từ, một kết quả được in ra) mà cho tác động đối với sự điều khiển hoạt động của máy tính. Dưới đây liệt kê một số môdun chương trình điển hình thuộc vào thành phần điều khiển:
	-Chương trình dẫn dắt (điều phối chính, monitor, chương trình giải thích lệnh): Tiếp nhận các nhiệm vụ ( yêu cầu của người dùng) từ dòng vào các nhiệm vụ, sắp xếp phân phối lịch thực hiện v.vđối với từng nhiệm vụ, sau đó trả lại kết quả cho người dùng.
	-Điều khiển quá trình (bài toán): Thực hiện luân phiên các quá trình (process; bài toán –task) đang tồn tại trong bộ nhớ, mỗi bài toán có các khối chứa thông tin liên quan để chuyển việc thực hiện từ quá trình này sang quá trình khác sao cho việc sử dụng CPU đạt hiệu quả.
	-Điều khiển dữ liệu: Tổ chức lưu trữ dữ liệu trên vật dẫn ngoài và đảm bảo truy nhập dữ liệu theo yêu cầu của chương trình người dùng. Công việc vào – ra giữa bộ nhớ ngoài và bộ nhớ trong cũng như do liên quan đến một hệ thống thiết bị ngoại vi đa dạng và phong phú nên điều khiển dữ liệu cũng rất đa dạng.
	-Môdun chương trình tải (loader): Đảm bảo việc đưa các môdun chương trình từ bộ nhớ ngoài vào bộ nhớ trong tại một địa chỉ trong bộ nhớ trong. Trong nhiều trường hợp, môdun chương trình tải còn đảm bảo việc chuyển điều khiển để thực hiện (execute) chương trình được tải vào;
	-và nhiều thành phần khác
Thành phần ứng dụng
	Thành phần ứng dụng có trong hệ điều hành bao gồm những chương trình mà khi được thực hiện sẽ tạo ra một sản phẩm mới. Các bộ dịch ngôn ngữ lập trình (compiler), các chương trình tính toán, các chương trình soạn thảo v.vđược các hệ điều hành cung cấp nhằm giúp cho người sử dụng có thể chọn lựa phần mềm thích hợp trong lĩnh vực khai thác máy tính của mình. Thành phần ứng dụng rất đa dạng do tính chất đa dạng của yêu cầu người dùng.
	Thành phần điều khiển hướng đích là sự hiệu quả khai thác máy tính; còn thành phần ứ ...  xảy ra bế tắc. Có một số thuật toán dựa vào các danh sách đã liệt kê ở trên để đoán nhận được bế tắc có thể xảy ra để loại bỏ .
6.4. Xử lý bế tắc
Đình chỉ hoạt động của các tiến trình liên quan
Cách tiếp cận này dựa trên việc thu hồi lại các tài nguyên của những tiến trình bị kết thúc. Có thể sử dụng một trong hai phương pháp sau :
Đình chỉ tất cả các tiến trình trong tình trạng tắc nghẽn 
Đình chỉ từng tiến trình liên quan cho đến khi không còn chu trình gây tắc nghẽn : để chọn được tiến trình thích hợp bị đình chỉ, phải dựa vào các yếu tố như độ ưu tiên, thời gian đã xử lý, số lượng tài nguyên đang chiếm giữ , số lượng tài nguyên yêu cầu...
Thu hồi tài nguyên
Có thể hiệu chỉnh tắc nghẽn bằng cách thu hồi một số tài nguyên từ các tiến trình và cấp phát các tài nguyên này cho những tiến trình khác cho đến khi loại bỏ được chu trình tắc nghẽn. Cần giải quyết 3 vấn đề sau:
Chọn lựa một nạn nhân: tiến trình nào sẽ bị thu hồi tài nguyên ? và thu hồi những tài nguyên nào ?
Trở lại trạng thái trước tắc nghẽn: khi thu hồi tài nguyên của một tiến trình, cần phải phục hồi trạng thái của tiến trình trở lại trạng thái gần nhất trước đó mà không xảy ra tắc nghẽn.
Tình trạng « đói tài nguyên »: làm sao bảo đảm rằng không có một tiến trình luôn luôn bị thu hồi tài nguyên ?
 6.5. Kết luận chung về phòng tránh bế tắc
Trạng thái deadlock xảy ra khi hai hay nhiều quá trình đang chờ không xác định một sự kiện mà có thể được gây ra chỉ bởi một trong những quá trình đang chờ. Về nguyên tắc, có ba phương pháp giải quyết deadlock:
•	Sử dụng một số giao thức để ngăn chặn hay tránh deadlock, đảm bảo rằng hệ thống sẽ không bao giờ đi vào trạng thái deadlock.
•	Cho phép hệ thống đi vào trạng thái deadlock, phát hiện và sau đó phục hồi.
•	Bỏ qua vấn đề deadlock và giả vờ deadlock chưa bao giờ xảy ra trong hệ thống. Giải pháp này là một giải pháp được dùng bởi hầu hết các hệ điều hành bao gồm UNIX.
Trường hợp deadlock có thể xảy ra nếu và chỉ nếu bốn điều kiện cần xảy ra cùng một lúc trong hệ thống: loại trừ hỗ tương, giữ và chờ cấp thêm tài nguyên,
không đòi lại tài nguyên, và tồn tại chu trình trong đồ thị cấp phát tài nguyên. Để ngăn chặn deadlock, chúng ta đảm bảo rằng ít nhất một điều kiện cần không bao giờ xảy ra.
Một phương pháp để tránh deadlock mà ít nghiêm ngặt hơn giải thuật ngăn chặn deadlock là có thông tin trước về mỗi quá trình sẽ đang dùng tài nguyên như thế nào. Thí dụ, giải thuật Banker cần biết số lượng tối đa của mỗi lớp tài nguyên có thể được
yêu cầu bởi mỗi quá trình. Sử dụng thông tin này chúng ta có thể định nghĩa giải thuật tránh deadlock.
Nếu hệ thống không thực hiện một giao thức để đảm bảo rằng deadlock sẽ không bao giờ xảy ra thì lược đồ phát hiện và phục hồi phải được thực hiện. Giải thuật phát hiện deadlock phải được nạp lên để xác định deadlock có thể xảy ra hay không. Nếu deadlock được phát hiện hệ thống phải phục hồi bằng cách kết thúc một số quá trình bị deadlock hay đòi lại tài nguyên từ một số quá trình bị deadlock.
Trong một hệ thống mà nó chọn các nạn nhân để phụv hồi về trạng thái trước đó chủ yếu dựa trên cơ sở yếu tố chi phí, việc đói tài nguyên có thể xảy ra. Kết quả là quá trình được chọn không bao giờ hoàn thành tác vụ được chỉ định của nó.
CÂU HỎI VÀ BÀI TẬP
Nêu khái niệm quá trình (tiến trình). Phân biệt quá trình với chương trình.
Vẽ sơ đồ không gian trạng thái. Nêu ý nghĩa các trạng thái của một quá trình.
Thế nào là lập lịch dài kỳ và lập lịch ngắn kỳ.
Khái niệm ngắt và qui trình xử lý ngắt.
Nêu các tiêu chuẩn lập lịch cho CPU.
Cho các quá trình với thời gian thực hiện tương ứng như sau:
Quá trình (process) tthực hiện
	P1 10
	P2 	 2
	P3	 7
	P4	 1
	P5	 5
Tính thời gian chờ đợi trung bình của các quá trình trong các chiến lược FCFS, SJN, RR (với lượng tử thời gian là 2).
Nêu khái niệm về bế tắc và các điều kiện xảy ra bế tắc trong hệ thống.
HƯỚNG DẪN TRẢ LỜI
Tiến trình là một đoạn chương trình hay đoạn dữ liệu chương trình được đưa vào CPU để xử lý. Dựa vào khái niệm chương trình và tiến trình để phân biệt.
Vẽ sơ đồ. Nêu lên khi nào thì quá trình ở các trạng thái trong sơ đồ.
Nêu ở phần lập lịch dài kỳ và lập lịch ngắn kỳ.
Ở phần ngắt và các bước xử lý ngắt trong giáo trình
Xem xét số tiến trình vào xử lý trong CPU, thời gian chờ của các tiến trình.
Áp dụng và xem ví dụ các chiến lược FCFS, SJN,RR nói ở trên để giải.
Ở phần bế tắc và các điều khiện xảy ra bế tắc.
CHƯƠNG 5: HỆ ĐIỀU HÀNH ĐA XỬ LÝ
Mã chương: MH10-05
Mục tiêu:
Sau khi học xong bài học này, sinh viên có khả năng:
- Hiểu khái quát được xu thế sử dụng hệ thống đa xử lý hiện nay, hiểu được những nét cơ bản về hệ điều hành đa xử lý nhằm trang bị khả năng tự nghiên cứu trong tương lai.
1. Hệ điều hành đa xử lý tập trung
Mục tiêu: Hiểu khái quát được xu thế sử dụng hệ thống đa xử lý
1.1 Hệ thống đa xử lý 
a. Hệ thống nhiều CPU
	Hiện nay, từ sự phát triển với tốc độ nhanh của công nghệ, máy tính ngày càng được phổ dụng trong xã hội. Mức độ thâm nhập của máy tính vào cuộc sống càng cao thì yêu cầu nâng cao năng lực của máy tính lại ngày càng trở nên cấp thiết. Bộ nhớ chính ngày càng rộng lớn; đĩa từ có dung lượng càng rộng, tốc độ truy nhập ngày càng cao; hệ thống thiết bị ngoại vi càng phong phú, hình thức giao tiếp người – máy ngày càng đa dạng. Như đã nói, CPU là một tài nguyên thể hiện chủ yếu nhất năng lực của hệ thống máy tính, vì vậy một trong những vấn đề trọng tâm nhất để tăng cường năng lực của hệ thống là tăng cường năng lực của CPU. Về vấn đề này, nảy sinh giải pháp theo hai hướng:
	Giải pháp tăng cường năng lực của một CPU riêng cho từng máy máy tính: công nghệ vi mạch ngày càng phát triển vì vậy năng lực của từng CPU cũng ngày nâng cao, các dự án các vi mạch VLSI với hàng triệu, hàng chục triệu transitor. Tuy nhiên giải pháp này cũng nảy sinh những hạn chế về kĩ thuật: tốc độ truyền thông tin không vượt qua tốc độ ánh sáng; khoảng cách gần nhất giữa hai thành phần không thể giảm thiểu quá nhỏ v.v
	Song song với giải pháp tăng cường năng lực của CPU là giải pháp liên kết nhiều CPU để tạo ra một hệ thống chung có năng lực đáng kể: việc đưa xử lý song song tạo ra nhiều lợi điểm. Thứ nhất, chia các phần nhỏ công việc cho mỗi CPU đảm nhận, năng suất tăng không chỉ theo tỷ lệ thuận với một hệ số nhân mà còn cao hơn do không mất thời gian phải thực hiện những công việc trung gian.
	Giải pháp này còn có lợi điểm tích hợp các hệ thống máy đã có để tạo ra một hệ thống mới với sức mạnh tăng gấp bội.
	Trong chương này, xem xét việc chọn giải pháp đa xử lý theo nghĩa một hệ thống tính toán được tổ hợp không chỉ một CPU mà nhiều CPU trong một máy tính hoặc nhiều máy tính trong một hệ thống thống nhất. Gọi chung các hệ có nhiều CPU như vậy là hệ đa xử lý.
b.Phân loại các hệ đa xử lý
	Có một số cách phân loại các hệ đa xử lý:
	Ví dụ về hệ đa xử lý tập trung là tập các xử lý trong một siêu máy tính (supercomputer). Đặc trưng của hệ thống này là các CPU được liên kết với nhau trong một máy tính duy nhất;
	Ví dụ về hệ đa xử lý phân tán là các mạng máy tính: mạng gồm nhiều máy tính liên kết và được đặt ở những vị trí khác nhau, với một khoảng cách có thể coi là xa tùy ý.
	Phân loại theo đặc tính của các CPU thành phần: hệ đã xử lý thuần nhất hoặc hệ đa xử lý không thuần nhất v.v
	Một ví dụ dễ quen thuộc là trong các máy vi tính từ 80486 trở đi trong đó có hai CPU (80x86 và 80x87) là hai CPU không thuần nhất.
	Siêu máy tính ILLIAC-IV gồm nhiều CPU có đặc trưng giống nhau là một ví dụ về thuần nhất.
	Phân loại theo cách các CPU thành phần tiếp nhận và xử lý dữ liệu. Trong cách phân loại này bao gồm cả những máy tính đơn xử lý thông thường:
Đơn câu lệnh, đơn dữ liệu (SISD: single data single instruction) được thể hiện trong máy tính thông thường; Mỗi lần làm việc, CPU chỉ xử lý “một dữ liệu” và chỉ có một câu lệnh được thực hiện.
Đơn câu lệnh, đa dữ liệu (SIMD: single instruction multiple data):
	Các bộ xử lý trong cùng một nhịp thời gian chỉ thực hiện cùng một câu lệnh. Có thể lấy ví dụ từ việc cộng hai vector cho trước: Các CPU thành phần đều thực hiện các phép cộng; đổi số tương ứng đã có từng CPU; sau đó, chọn tiếp lệnh (chỉ thị) mới để điều khiển công việc này. Thông thường có một hệ chọn câu lệnh chung và mọi CPU thành phần cùng thực hiện: siêu máy tính ILLIAC-IV sử dụng cách thức này, có một máy tính con có tác dụng lưu giữ hệ điều hành để điều khiển ILLIAC.IV (bộ xử lý ma trận).
Đa câu lệnh, đơn dữ liệu (MISD: multiple instruction single data)
	Trong các máy tính thuộc loại này, hệ thống gồm nhiều CPU, các CPU liên kết nhau một cách tuần tự: output của bộ xử lý này là input của bộ xử lý tiếp theo (ví dụ CRAY-1: Bộ xử lý vector). Các CPU kết nối theo kiểu này được gọi là kết nối “dây chuyền”.
Đa dữ liệu, đa câu lệnh (MIMD)
	Mỗi bộ xử lý có bộ phân tích chương trình riêng; câu lệnh và dữ liệu do chính mỗi CPU phải đảm nhận; có thể hình dung các CPU này hoạt động hoàn toàn “độc lập nhau”. Các hệ điều hành mạng, hệ điều hành phân tán là những ví dụ về đa dữ liệu, đa câu lệnh.
	Trong nội dung ở chương này, xem xét cách phân loại dạng tập trung/phân tán song thực chất chỉ quan tâm đến hệ đa xử lý tập trung còn với hệ đa xử lý phân tán, sẽ có những chuyên đề riêng đáp ứng.
	Chú ý, một xu thế nghiên cứu và triển khai các hệ thống tính toán đa xử lý thời sự là nghiên cứu về tính toán cụm trong đó các mô hình SIMD, MISD và MIMD tương ứng được phát triển.
1.2. Hệ điều hành đa xử lý tập trung
	Hệ đa xử lý tập trung hoạt động trên các máy tính có nhiều CPU mà điển hình là các siêu máy tính: CRAY-1,ILLIAC-IV, Hitachi và các máy tính nhiều xử lý hiện nay (máy tính của khoa CNTT, trường ĐHKHTN-ĐHQGHN có hai bộ xử lý). Các tài nguyên khác CPU có thể được phân chia cho các CPU. Trong các hệ điều hành đa xử lý, hai bài toán lớn nhất có thể kể đến là phân phối bộ nhớ và phân phối CPU.
a.Phân phối bộ nhớ
	Các quá trình xuất hiện trong bộ nhớ chung. Việc phân phối bộ nhớ được tiến hành cho quá trình theo các chế độ điều khiển bộ nhớ đã cài đặt: phân phối theo chế độ mẻ hay phân phối gián đoạn.
	Để tăng tốc độ làm việc với bộ nhớ (bài toán xử lý con trỏ ngoài v.v.) có thể gắn với mỗi CPU một cache nhớ. Phân ra hai loại thâm nhập cache: tĩnh và động. Thâm nhập tĩnh: mỗi CPU chỉ thâm nhập cache tương ứng, không thâm nhập dữ liệu tại vùng cache của các CPU khác. Thâm nhập động cho phép CPU của máy này có thể thâm nhập các cache của CPU khác.
b.Bài toán điều khiển CPU
	Có nhiều CPU, việc điều khiển CPU được phân ra một số cách như sau:
	Toàn bộ các CPU dành cho một quá trình : một quá trình được phân phối CPU, song tự quá trình nói trên nảy sinh các quá trình con; mỗi quá trình con được giải quyết trên mỗi CPU. Các quá trình con có thể được coi như một tính toán hết sức đơn giản nào đó: Máy tính đa xử lý vector chia các công đoạn của quá trình và mỗi CPU thực hiện một quá trình con (một công đoạn) trong quá trình đó. Máy tính đa xử lý ma trận cho phép mọi CPU cùng thực hiện một thao tác.
	Về dòng xếp hàng có thể xem xét theo hai mô hình dưới đây:
	Mô hình tĩnh: Hoặc mỗi CPU có một dòng xếp hàng riêng; mỗi bài toán được gắn với từng dòng xếp hàng, việc điều khiển mỗi dòng xếp hàng như đã được chỉ ra độc lập với các dòng xếp hàng khác, mỗi quá trình được phát sinh gắn với một dòng xếp hàng nào đó;
	Mô hình động: toàn bộ hệ thống gồm một hay một vài dòng xếp hàng, các quá trình được xếp lên các CPU khi rỗi (có thể sử dụng kiểu dữ liệu semaphore nhiều giá trị để phân phối CPU cho các quá trình này).
2. Hệ điều hành đa xử lý phân tán
Mục tiêu: hiểu được những nét cơ bản về hệ điều hành đa xử lý phân tán nhằm trang bị khả năng tự nghiên cứu trong tương lai.
2.1. Giới thiệu hệ phân tán
	Trong phần phân loại hệ thống đa xử lý, chú ý cách phân loại theo vị trí đặt các CPU (tập trung và phân tán) thì hệ phân tán được xây dựng từ các “ máy tính” rời rạc nhau: mỗi vị trí là một máy tính nguyên vẹn, có đầy đủ chức năng xử lý, lưu trữ và truyền dữ liệu.
	Hệ tập trung cho phép xử lý song song theo thao tác hoặc theo quá trình, trong khi đó, hệ phân tán chỉ có thể xử lý song song theo quá trình: các quá trình con được xử lý trên các máy tính khác nhau. Việc phân chia quá trình cho các CPU thành phần hoặc theo chức năng của CPU đó (server/client) hoặc theoo một lịch được phân công của một hệ thống chung.
	Do phân tán nên vấn đề truyền dẫn dữ liệu đóng vai trò quan trọng trong các hệ phân tán. Đây cũng là một trong những lí do điển hình nhất để cách thức xử lý song song trên các hệ phân tán là theo quá trình mà không phải theo phép toán.
2.2. Đặc điểm hệ phân tán
	Hệ thống phân tán (kéo theo sự hình thành các hệ điều hành phân tán) được phát sinh do các nhu cầu hết sức tự nhiên về việc nâng cao năng lực tài nguyên hệ thống (sức mạnh của hệ thống tính toán và cơ sở dữ liệu chung v.v..). Giải pháp phân tán có tác dụng phát huy năng lực chung của toàn bộ hệ thống khi giải quyết bài toán với kích thước bài toán tăng lên và vẫn đảm bảo hoạt động bình thường của các máy tính thành viên. Hệ thống phân tán được thiết lập hoặc là một hệ thống mới hoàn toàn được thiết kế theo mô hình phân tán hoặc xây dựng một hệ phân tán dựa trên các tài nguyên địa phương (máy tính, cơ sở dữ liệu) sẵn có.
	Một trong các trường hợp điển hình, các hệ phân tán được dùng để quản trị các hệ thống cơ sở dữ liệu lớn. Trong các hệ cơ sở dữ liệu phân tán, tính dư thừa thông tin lại được quan tâm chú ý không chỉ tới khía cạnh gây khó khăn khi tính đến tính nhất quán dữ liệu mà còn tới khía cạnh thuận lợi về vần đề an toàn: lưu trữ kép (ngoài bản chính còn một số bản sao) để có thể phục hồi khi xảy ra sự cố đối với hệ thống. Để đảm bảo tính nhất quán của hệ thống định kỳ “làm tươi” các thông tin do hệ thống quản lý.
	Như đã biết, bài toán lập lịch cho hệ thống chung là phức tạp ngay cả đối với máy tính với một CPU, vì vậy trong các hệ phân tán, bài toán nói trên là hết sức phức tạp (ngay cả các hệ đồng nhất) cho nên người ta thường chọn các phương án đơn giản nhất.
	Các nội dung kiến thức về hệ thống phân tán được trình bày chi tiết hơn trong giáo trình chuyên đề” mạng và các hệ phân tán”. Bản chất của hệ điều hành trong các mô hình phân tán là một hệ điều hành đa chương trình. Do tính chất không thuần nhất của các máy tính địa phương và có liên quan chặt chẽ đến đường truyền thông, bài toán lập lịch và các hệ thống chương trình điều khiển là phức tạp. Các thuật toán điều khiển được chọn lựa là đủ đơn giản và vẫn luôn là bài toán thời sự đang được nghiên cứu.
CÂU HỎI VÀ BÀI TẬP
Trình bày mục đích của hệ nhiều CPU.
Hệ phân tán là gì?
Đặc điểm hệ phân tán.
HƯỚNG DẪN TRẢ LỜI
1. Tăng cường năng lực của CPU là giải pháp liên kết nhiều CPU để tạo ra một hệ thống chung có năng lực đáng kể: việc đưa xử lý song song tạo ra nhiều lợi điểm.
2. Hệ phân tán tập hợp các máy tính ghép nối với nhau bằng đường truyền theo một tiêu chuẩn qui định trước.
3. Đặc điểm hệ phân tán: tạo khả năng làm việc phân tán, nâng cao việc khai thác và xử lý dữ liệu, tăng độ tin cậy của hệ thống, chia sẻ tài nguyên.
TÀI LIỆU THAM KHẢO
[1]. TS Hà Quang Thụy, Giáo trình Nguyên lý các hệ điều hành , NXB KH & KT, 2005. 
[2]. Trần Hồ Thủy Tiên, Nguyên lý hệ điều hành, Đại học Đà Nẵng, Năm 2007.
[3]. Đặng Vũ Tùng, Giáo trình Nguyên lý hệ điều hành,Nhà xuất bản Hà Nội, 2005.
 [4]. James R.Pinkert, Operating systems, California State University.