Tổng hợp câu hỏi và trả lời từ bài 1 đến bài 8 môn HĐH.

BÀI 1
Câu 1: Mục tiêu, ý nghĩa,cấu trúc môn học
Ý nghĩa:
 Hiểu sâu nguyên lý hoạt động của Phần cứng và Phần mềm máy tính.
 Học phương pháp phân tích, thiết kế và lập trình một hệ thống lớn để áp dụng cho công tác nghiệp vụ sau này.
Mục tiêu: Cung cấp các khái niệm cơ bản về cấu trúc và hoạt động của HĐH.
Cấu trúc môn học:
 Mô tả vắn tắt:
- Khái niệm chung, Lịch sử, Phân loại HĐH.
- Nguyên lý và hoạt động các khối chức năng.
- Giới thiệu dòng HĐH Windows NT/2000/XP/2003
 Gồm 8 chương:
Chương 1: Giới thiệu Hệ điều hành
Định nghĩa hệ điều hành
Lịch sử hệ điều hành
Phân loại hệ điều hành
Chương 2: Cấu trúc máy tính
Hoạt động của máy tính
Cấu trúc nhập xuất (I/O Structure)
Cấu trúc bộ nhớ
Phân cấp bộ nhớ.
Chương 3: Cấu trúc hệ điều hành
Các thành phần hệ thống
Các dịch vụ hệ thống
Các lời gọi hệ thống
Các chương trình hệ thống
Cấu trúc hệ thống
Thiết kế và thi công (Design & Implementation)
Sản sinh hệ thống.
Chương 4: Quản lý tiến trình
Khái niệm tiến trình (Process Concept)
Điều phối tiến trình (Process Scheduling)
Thao tác với tiến trình (Operations on Process)
Cộng tác giữa các tiến trình (Cooperation Process)
Liên lạc giữa các tiến trình (Interprocess Communications)
Liên lạc trong hệ thống Khách – Chủ ( Communications in Client – Server)
Chương 5: Đa luồng
Khái niệm chung
Chuẩn Pthreads
Đa luồng trong windows
Chương 6: Điều phối CPU
Khái niệm chung
Tiêu chí điều phối (Scheduling Criteria)
Các thuật giải điều phối (Scheduling Algorithms).
Chương 7: Đồng bộ hóa tiến trình
Khái niệm chung
Vấn đề đoạn tương tranh (Critical-Section Problem)
Đèn hiệu (Semaphores)
Bài toán Hiền triết cùng ăn.
Chương 8: Deadlocks
Mô hình hệ thống (System Model)
Bản chất của deadlocks
Các phương thức xử trí deadlocks
Ngăn chặn deadlocks
Tránh deadlocks
Câu 2: Phân tích Định nghĩa “Hệ điều hành là Máy tính mở rộng (Extended Machine) hay Máy tính ảo (Virtual Machine)”
 Ẩn các chi tiết của phần cứng để máy tính dễ sử dụng hơn.
 Người sử dụng và người lập trình được cung cấp một giao diện đơn giản, dễ hiểu và không phụ thuộc vào thiết bị cụ thể.
 Thực tế, HĐH là một hệ thống bao gồm nhiều máy tính trừu tượng xếp thành nhiều lớp chồng lên nhau. Máy tính mức dưới phục vụ cho máy tính mức trên.
 Bản thân chương trình ứng dụng cũng là một máy tính trừu tượng và phải dễ sử dụng nhất.
 Công việc của người lập trình là liên tục xây dựng các máy tính trừu tượng như vậy (cho người khác sử dụng và cho cả chính mình).
Câu 3: Phân tích Định nghĩa “Hệ điều hành là bộ quản lý tài nguyên (Resource Manager)”.
 Đáp ứng các yêu cầu sử dụng tài nguyên thiết bị như: CPU, Bộ nhớ trong, ổ đĩa, ổ băng, Máy in, Card mạng, ...
 Trong trường hợp nhiều chương trình, nhiều người dùng cùng chia sẻ các tài nguyên chung như vậy, HĐH phải giải quyết tranh chấp có thể xảy ra và đứng ra làm trung gian điều phối sao cho tài nguyên được sử dụng đúng thứ tự, dùng xong lại được cấp cho đối tượng khác sử dụng.
 Hình dung tình huống: 3 chương trình cùng in ra một máy in duy nhất. Khó chấp nhận trường hợp 1 trang in xen kẽ nhiều kết quả từ nhiều nguồn khác nhau. HĐH giải quyết bằng cách đưa kết quả in của mỗi chương trình tạm thời ra đĩa cứng, sau đó lần lượt in từ đĩa vào thời điểm thích hợp.
Câu 4: Phân biệt HĐH đa xử lý và HĐH gom cụm
Hệ điều hành đa xử lý và hệ điều hành gom cụm giống nhau là đều tập hợp nhiều CPU với nhau để thực hiện công việc tính toán
Hệ điều hành gom cụm khác hệ điều hành đa xử lý ở điểm chúng được hợp thành từ hai hay nhiều hệ thống đơn được kết hợp với nhau.
a. Hệ điều hành đa xử lý
Các hệ hỗ trợ nhiều CPU, còn gọi là các hệ song song (Parallel Systems)
Ích lợi:
 Tăng thông suất : tăng số tác vụ hoàn tất trong 1 đơn vị thời gian, bằng cách tăng số lượng bộ xử lý, chúng ta hy vọng thực hiện nhiều công việc hơn với thời gian ít hơn.
 Tiết kiệm: Nhiều CPU nhưng chung bộ nhớ và các thiết bị ngoài. Ví dụ: Nếu nhiều chương trình điều hành trên cùng tập hợp dữ liệu thì lưu trữ dữ liệu đó trên một đĩa và tất cả bộ xử lý chia sẻ chúng sẽ rẻ hơn là có nhiều máy tính với đĩa cục bộ và nhiều bản sao dữ liệu.
 Tăng độ tin cậy: Nếu 1 CPU gặp sự cố, hệ vẫn chạy tuy có chậm hơn. Ví dụ: Nếu chúng ta có 10 bộ xử lý và có 1 bộ xử lý bị sự cố thì mỗi bộ xử lý trong 9 bộ xử lý còn lại phải chia sẻ của công việc của bộ xử lý bị lỗi. Do đó, toàn bộ hệ thống chỉ giảm 10% năng lực hơn là dừng hoạt động. Các hệ thống được thiết kế như thế được gọi là hệ thống có khả năng chịu lỗi (fault tolerant).
Phân loại:
 Đa xử lý đối xứng (symmetric multiprocessing-SMP). Trong hệ thống này mỗi bộ xử lý chạy bản sao của hệ điều hành và những bản sao này giao tiếp với các bản sao khác khi cần.
o Các CPU chung bộ nhớ và thiết bị
o Các CPU ngang hàng về chức năng
Ví dụ: Windows 2000 professional : 2CPU ; Windows 2000 Server : 4 CPU
 Đa xử lý bất đối xứng (asymmetric multiprocessing).
o Các CPU chung bộ nhớ và thiết bị
o Các CPU được ấn định chức năng riêng: Cơ chế này định nghĩa mối quan hệ chủ-tớ. Bộ xử lý chính lập thời biểu và cấp phát công việc tới các bộ xử lý tớ.
 Có CPU chủ (Master): kiểm soát toàn hệ thống
 Các CPU khác đóng vai trò phụ thuộc (Slaves), chuyên trách công việc nào đó. (chờ bộ xử lý chủ ra chỉ thị hoặc có những tác vụ được định nghĩa trước)
Ví dụ: Hệ điều hành SunOS 4.x
b. Hệ điều hành gom cụm
Nhiều máy nối mạng để cùng thực hiệc công việc chung
Phân loại :
 Gom cụm đối xứng (Symmetric Clustering): các máy ngang hàng về chức năng. Mỗi máy thực hiện phần việc của mình và giám sát lẫn nhau. Ví dụ: Trong hệ thống mạng gồm nhiều máy chủ chạy song song và chúng đang kiểm soát lẫn nhau.
 Gom cụm phi đối xứng (Asymmetric Clustering): Một máy chạy trong Hot Standby Mode, nghĩa là chỉ giám sát công việc các máy khác nhưng sẽ đảm đương công việc của máy gặp sự cố. Ví dụ: Hệ thống mạng gồm hai máy server chạy song song, trong đó một máy ở trong chế độ dự phòng (hot standby). Máy dự phòng không là gì cả ngoại trừ theo dõi server hoạt động. Nếu server đó bị lỗi, máy chủ dự phòng nóng trở thành server hoạt động.
Câu 5: So sánh các hệ Batch System
 Hệ xử lý lô (Batch System)
Mỗi thời điểm chỉ có một tác vụ trong bộ nhớ
 Hệ đa chương (Multiprogramming System)
Nhiều tác vụ (tiến trình) cùng một lúc trong bộ nhớ
Khi một tác vụ không cần đến CPU (do phải thực hiện I/O với thiết bị ngoài), tác vụ khác được thi hành.
 Hệ chia thời gian (Time-Sharing System)
Là hệ đa chương
Mỗi tác vụ chỉ được dùng CPU trong một khoảng thời gian ngắn (ví dụ với thời lượng là 20ms), sau đó bị ngắt, chuyển sang tác vụ khác, cứ thế xoay vòng.
Mỗi người dùng đều có cảm giác là máy tính chỉ phục vụ cho mình là duy nhất.
Ví dụ: Trong nhà hàng, người bồi bàn (CPU) phục vụ mỗi bàn ăn (chương trình người dùng) trong một khoảng thời gian ngắn (chẳng hạn trong 10 giây), sau đó chuyển sang bàn khác.
BÀI 2
CẤU 1: Trình bày nguyên tắc xử lý ngắt của hệ điều hành.
 Hai loại ngắt chính:
 Tín hiệu ngắt (Interrupt Signal) từ các thiết bị (Ngắt cứng) truyền qua System Bus.
 Tín hiệu ngắt từ chương trình người dùng (Ngắt mềm) nhờ Lời gọi hệ thống (System Call hay Monitor Call). Lệnh đặc biệt này ( ví dụ có tên INT hoặc SysCall )cơ chế để tiến trình người dùng yêu cầu một dịch vụ của HĐH (ví dụ, yêu cầu thực hiện lệnh I/O).
 Với mỗi loại ngắt, có đoạn mã riêng của HĐH dùng để xử lý.
 Các HĐH hiện đại được dẫn dắt bởi các sự kiện. Nếu không có tiến trình nào vận hành, không có thiết bị I/O nào làm việc, HĐH im lặng chờ và theo dõi.
 Thông thường, mỗi loại ngắt tương ứng với 1 dòng trong bảng (Véc-tơ ngắt) chứa con trỏ (Pointer) tới chương trình xử lý loại ngắt đó. Bảng này nằm ở vùng thấp của RAM (ví dụ: 100 bytes đầu tiên).
 Cơ chế xử lý ngắt phải có trách nhiệm ghi lại địa chỉ lệnh bị ngắt để sau đó có thể quay lại. Địa chỉ này cùng với nhiều thông tin khác có thể được ghi vào Ngăn xếp hệ thống (System Stack) với nguyên tắc làm việc LIFO ( Last-In, First-Out )
Câu 2: Trình bày Tuyến thời gian của một tiến trình có nhiều yêu cầu tới thiết bị ngoại vi.
Câu 3: Phân biệt hai phương thức I/O đồng bộ và không đồng bộ
- Synchronous I/O: Sau khi phát ra lệnh Nhập/Xuất, tiến trình chuyển sang trạng thái chờ đến
khi Nhập/Xuất hoàn tất rồi mới chạy tiếp (thực hiện lệnh kế tiếp)
Ví dụ: Khi ta tạo mới một tài liệu nhập dữ liệu từ bàn phím, khi muốn lưu lại ta phải chọn Save, sau đó đặt tên file, và chọn nơi lưu trữ. Các tiến trình đó ở trạng thái chờ tiến trình trước nhập
xuất hoàn tất đã.
- ASynchronous I/O: Sau khi phát ra lệnh Nhập/Xuất, tiến trình không chờ Nhập/Xuất hoàn tất mà thực hiện ngay lệnh kế tiếp. Như vậy, tiến trình vận hành song song với công việc Nhập/Xuất. Ví dụ: Khi ta nhập dữ liệu mới hoặc thêm vào tài liệu đã có, khi ta muốn lưu thì ta chọn Save và lúc này tiến trình vận hành song song với việc phát ra lệnh từ Save.
Câu 4: Phân tích vai trò phân cấp các loại bộ nhớ trong máy tính
Một sự phân cấp bộ nhớ kiểu mẫu được chỉ ra ở hình trên. Khi chúng ta đi từ trên xuống trong sơ đồ phân cấp này, những sự kiện sau sẽ xảy ra: Giảm phí tổn cho một bit Tăng dung lượng Tăng thời gian truy cập Giảm tần số truy cập bộ nhớ bởi CPU
Do vậy bộ nhớ nhỏ hơn, nhanh hơn, đắt tiền hơn được phụ trợ bởi bộ nhớ lớn hơn, chậm hơn, rẻ hơn. Chìa khóa cho sự thành công trong cách tổ chức này là yếu tố cuối cùng, tức là giảm thiểu tần số truy cập.
Câu 5: Nguyên lý lưu gần
 Là nguyên tắc quan trọng của hệ thống máy tính.
 Thông tin từ RAM có thể được cơ chế phần cứng đưa vào bộ nhớ nhanh hơn gọi là Cache. Khi CPU cần chính thông tin đó, không cần phải truy xuất RAM, mà lấy ngay từ Cache.
 Loại bộ nhớ này không do HĐH quản lý và cấp phát.
 Thực tế, RAM (Bộ nhớ Sơ cấp) là loại Cache nhanh so với đĩa cứng (Bộ nhớ thứ cấp) và HĐH có chức năng quản lý sự lưu chuyển dữ liệu giữa 2 loại bộ nhớ này
Câu 6: Nguyên lý bảo vệ bộ nhớ chính bằng thanh ghi cơ sở và thanh ghi giớ hạn
 Để tiến trình người dùng không can thiệp được vào vùng nhớ của hệ điều hành và các tiến trình khác, thường sử dụng hai thanh ghi :
o Thanh ghi Cơ sở (Base register): được dùng để lưu trữ địa chỉ ô nhớ hợp lệ nhỏ nhất
o Thanh ghi Giới hạn (Limit register): lưu trữ kích thước của cả ô nhớ.
Ví dụ, nếu thanh ghi base lưu trữ giá trị 300040 và thanh ghi limit lưu trữ giá trị là 120900 thì chương trình sẽ có thể truy cập hợp lệ vào các địa chỉ ô nhớ trong khoảng từ 300040 cho đến 420940.
 Chỉ có HĐH mới có thể sửa được nội dung hai thanh ghi này. Vì thanh ghi base và limit chỉ có thể được nạp bởi hệ điều hành
BÀI 2
CẤU 1: Trình bày nguyên tắc xử lý ngắt của hệ điều hành.
 Hai loại ngắt chính:
 Tín hiệu ngắt (Interrupt Signal) từ các thiết bị (Ngắt cứng) truyền qua System Bus.
 Tín hiệu ngắt từ chương trình người dùng (Ngắt mềm) nhờ Lời gọi hệ thống (System Call hay Monitor Call). Lệnh đặc biệt này ( ví dụ có tên INT hoặc SysCall )cơ chế để tiến trình người dùng yêu cầu một dịch vụ của HĐH (ví dụ, yêu cầu thực hiện lệnh I/O).
 Với mỗi loại ngắt, có đoạn mã riêng của HĐH dùng để xử lý.
 Các HĐH hiện đại được dẫn dắt bởi các sự kiện. Nếu không có tiến trình nào vận hành, không có thiết bị I/O nào làm việc, HĐH im lặng chờ và theo dõi.
 Thông thường, mỗi loại ngắt tương ứng với 1 dòng trong bảng (Véc-tơ ngắt) chứa con trỏ (Pointer) tới chương trình xử lý loại ngắt đó. Bảng này nằm ở vùng thấp của RAM (ví dụ: 100 bytes đầu tiên).
 Cơ chế xử lý ngắt phải có trách nhiệm ghi lại địa chỉ lệnh bị ngắt để sau đó có thể quay lại. Địa chỉ này cùng với nhiều thông tin khác có thể được ghi vào Ngăn xếp hệ thống (System Stack) với nguyên tắc làm việc LIFO ( Last-In, First-Out )
Câu 2: Trình bày Tuyến thời gian của một tiến trình có nhiều yêu cầu tới thiết bị ngoại vi.
Câu 3: Phân biệt hai phương thức I/O đồng bộ và không đồng bộ
- Synchronous I/O: Sau khi phát ra lệnh Nhập/Xuất, tiến trình chuyển sang trạng thái chờ đến
khi Nhập/Xuất hoàn tất rồi mới chạy tiếp (thực hiện lệnh kế tiếp)
Ví dụ: Khi ta tạo mới một tài liệu nhập dữ liệu từ bàn phím, khi muốn lưu lại ta phải chọn Save, sau đó đặt tên file, và chọn nơi lưu trữ. Các tiến trình đó ở trạng thái chờ tiến trình trước nhập
xuất hoàn tất đã.
- ASynchronous I/O: Sau khi phát ra lệnh Nhập/Xuất, tiến trình không chờ Nhập/Xuất hoàn tất mà thực hiện ngay lệnh kế tiếp. Như vậy, tiến trình vận hành song song với công việc Nhập/Xuất. Ví dụ: Khi ta nhập dữ liệu mới hoặc thêm vào tài liệu đã có, khi ta muốn lưu thì ta chọn Save và lúc này tiến trình vận hành song song với việc phát ra lệnh từ Save.
Câu 4: Phân tích vai trò phân cấp các loại bộ nhớ trong máy tính
Một sự phân cấp bộ nhớ kiểu mẫu được chỉ ra ở hình trên. Khi chúng ta đi từ trên xuống trong sơ đồ phân cấp này, những sự kiện sau sẽ xảy ra: Giảm phí tổn cho một bit Tăng dung lượng Tăng thời gian truy cập Giảm tần số truy cập bộ nhớ bởi CPU
Do vậy bộ nhớ nhỏ hơn, nhanh hơn, đắt tiền hơn được phụ trợ bởi bộ nhớ lớn hơn, chậm hơn, rẻ hơn. Chìa khóa cho sự thành công trong cách tổ chức này là yếu tố cuối cùng, tức là giảm thiểu tần số truy cập.
Câu 5: Nguyên lý lưu gần
 Là nguyên tắc quan trọng của hệ thống máy tính.
 Thông tin từ RAM có thể được cơ chế phần cứng đưa vào bộ nhớ nhanh hơn gọi là Cache. Khi CPU cần chính thông tin đó, không cần phải truy xuất RAM, mà lấy ngay từ Cache.
 Loại bộ nhớ này không do HĐH quản lý và cấp phát.
 Thực tế, RAM (Bộ nhớ Sơ cấp) là loại Cache nhanh so với đĩa cứng (Bộ nhớ thứ cấp) và HĐH có chức năng quản lý sự lưu chuyển dữ liệu giữa 2 loại bộ nhớ này
Câu 6: Nguyên lý bảo vệ bộ nhớ chính bằng thanh ghi cơ sở và thanh ghi giớ hạn
 Để tiến trình người dùng không can thiệp được vào vùng nhớ của hệ điều hành và các tiến trình khác, thường sử dụng hai thanh ghi :
o Thanh ghi Cơ sở (Base register): được dùng để lưu trữ địa chỉ ô nhớ hợp lệ nhỏ nhất
o Thanh ghi Giới hạn (Limit register): lưu trữ kích thước của cả ô nhớ.
Ví dụ, nếu thanh ghi base lưu trữ giá trị 300040 và thanh ghi limit lưu trữ giá trị là 120900 thì chương trình sẽ có thể truy cập hợp lệ vào các địa chỉ ô nhớ trong khoảng từ 300040 cho đến 420940.
 Chỉ có HĐH mới có thể sửa được nội dung hai thanh ghi này. Vì thanh ghi base và limit chỉ có thể được nạp bởi hệ điều hành
BÀI 4
Câu 1: Trình bày mô hình chuyển trạng thái của tiến trình
New : tiến trình đang được tạo lập.
Running : các chỉ thị của tiến trình đang được xử lý.
Blocked : tiến trình chờ được cấp phát một tài nguyên, hay chờ một sự kiện xảy ra .
Ready : tiến trình chờ được cấp phát CPU để xử lý.
Kết thúc : tiến trình hoàn tất xử lý.
Tại một thời điểm, chỉ có một tiến trình có thể nhận trạng thái running trên một bộ xử lý
bất kỳ. Trong khi đó, nhiều tiến trình có thể ở trạng thái blocked hay ready.
Các cung chuyển tiếp trong sơ đồ trạng thái biễu diễn sáu sự chuyển trạng thái có thể xảy
ra trong các điều kiện sau :
 Tiến trình mới tạo được đưa vào hệ thống
 Bộ điều phối cấp phát cho tiến trình một khoảng thời gian sử dụng CPU
 Tiến trình kết thúc
 Tiến trình yêu cầu một tài nguyên nhưng chưa được đáp ứng vì tài nguyên chưa sẵn
sàng để cấp phát tại thời điểm đó ; hoặc tiến trình phải chờ một sự kiện hay thao tác
nhập/xuất.
 Bộ điều phối chọn một tiến trình khác để cho xử lý .
 Tài nguyên mà tiến trình yêu cầu trở nên sẵn sàng để cấp phát ; hay sự kiện hoặc thao
tác nhập/xuất tiến trình đang đợi hoàn tất.
Tiến trình P1: vào hàng đợi Job-Queue ở trạng thái New, sẽ đợi 1 khoảng thời gian của quá trình điều phối chậm (Scheduler Long Term) của hệ điều hành(HĐH) để chọn tiến trình, sau khi được O.S chọn, P1 chuyển sang hàng đợi reday quueue và ở trạng thái Ready. Lúc này P1 chỉ đợi cấp CPU và running. Sau một khỏang thời gian running, tiến trình P2 xuất hiện. Lúc này, hệ điều hành sẽ ghi lại thông tin của P1 vào thanh PCB1 bao gồm những thông tin: con trỏ, trạng thái của P1, số hiệu của tiến trình P1, Bộ đếm P1, nội dung của P1…Và chuyển P1 sang hàng đợi Waiting và chuyển trạng thái Ready. Lúc này, P2 sẽ được cấp CPU và running. Và sau một khỏang thời gian running, P2 cũng sẽ chuyển sang hàng đợi waiting và chuyển trạng thái ready, lúc này HĐH cũng ghi lại thông tin vào thanh ghi PCB2 như đã làm ở P1. Sau đó, HĐH sẽ load lại thông tin của PCB1 và P1 sẽ tiếp tục running. Quá trình này cũng sẽ lập lại cho P2. Đển khi P1 và P2 kết thúc.
Câu 2: Phân tích vai trò của khối kiểm soát tiến trình
Khối kiểm soát tiến trình (Process Control Block - PCB ) - Bảng thông tin về môi trường và trạng thái hoạt động của tiến trình:
Chứa các thông tin ứng với mỗi process. Process ID, parent process ID
 Credentials (user ID, group ID, effective ID,...)
 Trạng thái process : new, ready, running, waiting…
 Program counter: địa chỉ của lệnh kế tiếp sẽ thực thi
 Các thanh ghi CPU
 Thông tin dùng để định thời CPU: priority,...
 Thông tin bộ nhớ: base/limit register, page tables…
 Thông tin thống kê: CPU time, time limits…
 Thông tin trạng thái I/O: danh sách thiết bị I/O được cấp phát, danh sách các file đang mở,...
 Con trỏ (pointer) đến PCBs khác.
PCB đơn giản phục vụ như kho chứa cho bất cứ thông tin khác nhau từ quá trình này tới quá trình khác.
Câu 3: Trình bày mô hình luân chuyển CPU giữa hai tiến trình
Câu 4: Phân biệt các loại trình điều phối
Điều phối chậm (Long-term scheduler (or job scheduler)) :
 Chọn process nào sẽ được đưa vào ready queue (từ New chuyển sang Ready)
 Kiểm soát Độ đa chương
 Do có nhiều thời gian (tới vài phút), loại scheduler này có điều kiện để lựa chọn kỹ càng nhằm phối hợp cân đối 2 loại tiến trình
o Hướng CPU: tính toán nhiều, ít I/O. Ví dụ: Công ty có một chiếc ô tô (CPU), nhiều nhân viên cần đi công tác (nhiều tiến trình) phải sử dụng ô tô. Do đó, ô tô (CPU) phải bận (phục vụ) cho nhiều người (nhiều tiến trình).
o Hướng I/O: tính toán ít, nhiều I/O
Ví dụ: Công ty có một chiếc ô tô (CPU), các nhân viên trong công ty chỉ ngồi nghiên cứu (I/O), không sử dụng đến ô tô. Vậy quá lãng phí ô tô (CPU)
 Mục đích cân bằng tải
Điều phối nhanh (Short-term scheduler (or CPU scheduler)) :
 Còn gọi là Điều phối CPU.
 Chọn tiến trình từ Ready Queue để cấp CPU.
 Có tần suất công việc cao. Thường cứ 100 ms lại tốn 10 ms để xác định tiến trình kế tiếp, như vậy 10/(100+10)=9% thời gian CPU được dùng để điều phối công việc.
Điều phối vừa (Medium-term scheduler) :
 Là Short-Term Scheduler được thêm chức năng rút các tiến trình khỏi bộ nhớ, dẫn đến làm giảm Độ đa chương, sau đó đưa lại chúng vào bộ nhớ vào thời điểm thích hợp để tiếp tục thực hiện từ vị trí bị tạm ngừng trước đó.
 Nhờ cách điều phối này, hỗn hợp các tiến trình trong Ready Queue có tính tối ưu hơn.
Ví dụ: Phòng thực hành nhỏ, nhưng nhiều bạn đi học thực hành (nhiều tiến trình). Thầy (HĐH) sẽ đẩy một số bạn ra khỏi lớp (rút tiến trình ra khỏi bộ nhớ). Sau khi nhóm trong phòng học xong Thầy sẽ đẩy các bạn bên ngoài vào phòng học (đưa tiến trình vào bộ nhớ vào thời điểm thích hợp).
Câu 5: Trình bày những lý do cộng tác giữa các tiến trình
 Chia sẻ thông tin (Information Sharing): Một tiến trình sử dụng thông tin do tiến trình khác cung cấp. Ví dụ: các bạn trong lớp chia nhóm học. Nhóm một nghiên cứu chương 1, nhóm hai nghiên cứu chương 2. Sau đó, hai nhóm trao đổi thông tin cho nhau. Kết quả hai nhóm mau chóng tìm hiểu hết hai chương.
 Tăng tốc tính toán (Computation Speedup): Các tiến trình cùng làm việc song song trên 1 hoặc nhiều máy để giải quyết bài toán chung.
 Đảm bảo tính đơn thể (Modularity): Chương trình được chia thành các đơn thể chức năng vận hành trong các tiến trình hoặc luồng khác nhau. Ví dụ: mỗi bạn học một bài, đảm bảo tính đơn thể.
 Đảm bảo tính tiện dụng (Convenience): Người dùng có nhu cầu làm nhiều việc một lúc: Soạn thảo, In ấn, Duyệt Web, Lấy file về, Biên dịch chương trình, Kiểm tra chính tả,...
Câu 6: Phát biểu bài toán sản xuất tiêu thụ với thuật giải phù hợp. (Trình bày giải thuật)
Phát biểu bài toán:
 Giả sử có Bộ nhớ đệm (Buffer) bao gồm nhiều khoang (Items) được tiến trình Producer lần lượt đưa các sản phẩm S1, S2,... vào.
 Tiến trình Consumer lần lượt lấy sản phẩm ra theo đúng thứ tự.
 Công việc của Producer phải đồng bộ với Consumer: Không được đưa sản phẩm vào khi Buffer đầy, Không được lấy ra khi chưa có.
Trình bày giải thuật:
Câu 7: Truyền thông điệp trong windows (Message-Passing in Windows)
Các hàm API dùng để Gửi/Nhận thông điệp
– SendMessage - Gửi có chờ
– PostMessage - Gửi không chờ
– SendMessageTimeout- Gửi có chờ nhưng với thời hạn
– WaitMessage - Chờ thông điệp đến
– GetMessage - Nhận có chờ
– PeekMessage - Nhận không chờ
Câu 1: Phân biệt khái niện luồng với tiến trình. Và trình bày những lợi ích của công nghệ đa luồng
Phân biệt khái niệm luồng với tiến trình
 Luồng: là tiến trình nhẹ (LWP - Light Weight Process), một đơn vị cơ bản sử dụng CPU. Luồng cũng có thông tin trạng thái như của tiến trình hệ thống (HWP - Heavy Weight Process) Ví dụ: Lớp học là một tiến trình. Trong lớp sẽ có một giáo viên(đơn luồng) và các học viên (đa luồng)
 Tiến trình: là chương trình trong thời gian thực hiện (đặt dưới sự quản lý của hệ điều hành). Có sự phân biệt Tiến trình hệ thống (của Hệ điều hành) với Tiến trình người dùng. Ví dụ: Lớp HCTH102C đang học là một tiến trình

Những ích lợi của công nghệ đa luồng
 Khả năng đáp ứng (Responsiveness) tốt hơn: Trong khi một luồng bị ách hoặc quá bận, luồng khác vẫn vận hành bình thường (Luồng chính của trình duyệt vẫn tương tác với người dùng trong khi dữ liệu được lấy về).
Ví dụ: Các cô ở tổng đài 108 là các luồng. Khi khách hàng điện thoại hỏi 108, thì một trong các cô (cô thứ 1) sẽ trả lời. Nếu trong thời điểm đó khách hàng thứ hai gọi 108, thì một trong các cô (cô thứ 2) còn lại sẽ trả lời cho khách hàng.
 Chia sẻ tài nguyên (Resource Sharing): Theo mặc định, các luồng có thể dùng chung bộ nhớ và tài nguyên của luồng cha. Vài luồng cùng vận hành trong 1 vùng địa chỉ, do đó dễ dùng chung tài nguyên hơn so với trường hợp đa tiến trình.
Ví dụ: Trong nhà ta có kệ sách, tivi, xe gắn máy, ... mọi người trong nhà có thể dùng chung sách, tivi, xe máy.
 Tiết kiệm (Economy): Cấp phát bộ nhớ và tài nguyên cho tiến trình là công việc tốn kém. Do luồng chung tài nguyên với cha và các luồng khác, việc tạo lập và chuyển ngữ cảnh cũng nhanh hơn (Solaris 2: Tạo tiến trình chậm hơn 30 lần, Chuyển ngữ cảnh chậm hơn 5 lần). Ví dụ: Các bạn trong lớp là các luồng đang dùng chung một cái bảng, ai cần ghi thi ghi, ai cần thì chụp hình về xem
 Tận dụng được thế mạnh của kiến trúc đa xử lý: Đa luồng làm tăng tính song song trên hệ máy nhiều CPU. Mỗi luồng có thể chạy bởi CPU riêng.
Câu 2: Trình bày nguyên lý tập nguồn và cho ví dụ minh họa
Tập luồng (Thread Pools):
 Tiến trình cha tạo lập sẵn một tập luồng khi khởi động.
 Các luồng trong tập luồng luôn sẵn sàng chờ công việc.
 Khi tiến trình cha (ví dụ Web Server) nhận thêm một yêu cầu, một luồng được đánh thức và đưa vào vận hành.
 Phục vụ xong, luồng được đưa trả về tập luồng.
 Nếu số yêu cầu lớn hơn số luồng trong tập, tiến trình cha chờ đến khi có luồng được giải phóng.
Ví dụ:
Trong một doanh trai quân đội sẽ có một tướng lĩnh (tiến trình cha) và sẽ có một đội binh (tập luồng).
Đội binh này sẽ sẳn sàng chiến đầu khi có mệnh lệnh (sẵn sàng chờ công việc).
Khi có một tên địch đột nhập, Tướng lĩnh sẽ điều binh sĩ 1 (một luồng) đi bắt tên địch (một luồng được đánh thức và đưa vào vận hành).
Trong khi đó, lại có thêm một tên địch khác đột nhập (nhận thêm một yêu cầu), Tướng lĩnh sẽ điều binh sĩ 2 (một luồng) đi bắt địch (một luồng khác được đánh thức và đưa vào vận hành).
Sau khi bắt địch xong, binh sĩ sẽ trở về doanh trại (luồng được trả về tập luồng)
Câu 3: Lập trình đa luồng trong windows
 Windows sử dụng các hàm trong thư viện Win32 API.
 Ứng dụng Windows vận hành như một tiến trình với 1 hoặc nhiều luồng.
 Bài toán Sản xuất-Tiêu thụ có thể được thực thi bằng Ứng dụng đa luồng (Visual C++ 6.0).
 Nhận độ ưu tiên của luồng bằng hàm: int GetThreadPriority (HANDLE threadHandle)
 Thay đổi độ ưu tiên của luồng bằng hàm:BOOL SetThreadPriority (HANDLE threadHandle, int priority)
Với độ ưu tiên priority:
THREAD_PRIORITY_LOWEST ( -2)
THREAD_PRIORITY_BELOW_NORMAL ( -1)
THREAD_PRIORITY_NORMAL ( 0 )
THREAD_PRIORITY_ABOVE_NORMAL (+1)
THREAD_PRIORITY_HIGHEST (+2)
 Có thể lập trình đa luồng với Visual Basic 6.0:
Sản xuất – Tiêu thụ
Animations
Colors
Câu 1: 4 tình huống ra quyết định của trình điều phối. Và phân biệt điều phối không tiếm quyền và điều phối có tiếm quyền
Bốn tình huống ra quyết định của trình điều phối:
1. Khi tiến trình chuyển từ Running sang Waiting (chờ I/O, chờ tiến trình con)
2. Khi tiến trình chuyển từ Running sang Ready (do ngắt xảy ra)
3. Khi tiến trình chuyển từ Waiting sang Ready (khi kết thúc I/O)
4. Khi tiến trình kết thúc công việc.
Phân biệt điều phối không tiếm quyền và điều phối có tiếm quyền
Điều phối Không tiếm quyền (Non-Preemptive): sơ đồ điều phối chỉ tiến hành trong tình huống 1 và 4. Tiến trình giữ CPU cho đến khi kết thúc bình thường hoặc khi chuyển sang trạng thái Waiting (cách làm trong Windows 3.1 và Macintosh OS). Dùng khi máy không có Timer.
Điều phối Có tiếm quyền (Preemptive): sơ đồ điều phối tiến hành trong cả 4 tình huống được
Câu 4: Phân biệt thuật giải MQS với thuật giải MFQS
Điều phối hàng chờ nhiều mức (Multilevel Queue Scheduling - MQS)
 Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau, ví dụ: Mức các tiến trình tương tác (Interactive) chạy ở mặt trước ( Foreground ) có độ ưu tiên cao nhất và Mức các tiến trình lô ( Batch ) vận hành trong hậu trường (Background ) .
 Mỗi hàng chờ có thuật giải điều phối riêng, ví dụ: Foreground dùng RRS, Background dùng FCFS.
 Quan hệ giữa các mức:
 Ưu tiên cố định: Xong hết các tiến trình mức trên rồi mới chuyển xuống mức dưới. Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mới mức cao hơn, tiến trình mức dưới sẽ bị tiếm quyền cho tiến trình mới có độ ưu tiên cao hơn ( Hệ Solaris 2 dùng cách này ) .
 Phân bổ theo tỉ lệ thời lượng, ví dụ: 80% thời lượng CPU dành cho Foreground, 20 % cho Background.
Điều phối hàng chờ nhiều mức có điều tiết ( Multilevel Feedback Queue Scheduling - MFQS )
 Như MQS nhưng cho phép Điều tiết tiến trình sang mức khc, ví dụ: những tiến trình hướng CPU được đưa xuống mức dưới, trong khi tiến trình hướng I/O hoặc chờ lâu được chuyển lên trên.
 MFQS đặc trưng bởi các thông số:
Số mức ( số hàng chờ )
Thuật giải điều phối cho mỗi mức
Phương thức nâng cấp tiến trình
Phương thức hạ cấp tiến trình
Phương thức chọn hàng chờ ( chọn mức ) cho tiến trình mới
BÀI 7:
Câu 1: Những lý do đồng bộ hóa công việc tiến trình. Cho ví dụ minh họa
 Đảm bảo tính nhất quán của tài nguyên dùng chung.
 Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình) .
VD: một trường học chỉ có 1 phòng lab (tài nguyên dùng chung) , lớp có giờ học trước thì được vào phòng lab học, các lớp còn lại phải chờ đến khi lớp học trước đó hết giờ mới được vào phòng lab
Câu 2: Khái niện đoạn tương tranh và loại trừ lẫn nhau. Cho ví dụ minh họa.
 Đoạn tương tranh :Xét một hệ có n tiến trình P0,P1, ...,Pn, mỗi tiến trình có một đoạn mã lệnh, nếu như trong đoạn mã này các tiến trình thao tác trên các biến chung,đọc ghi file... (tổng quát: thao tác trên dữ liệu chung) thì đoạn mã lệnh đó là đoạn tương tranh.
 Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.
 Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).
Ví dụ minh họa :
ĐƠN XIN VIỆC Kính gửi: Giám đốc công ty x Tôi tên là: Lê Văn Ba ..........(nội dung đơn)............. TP Hồ Chí Minh, ngày 5 tháng 5 năm 2011 Người làm đơn ....(chữ ký).... Lê Văn Ba
. Nội dung đơn này phải được đảm bảo tính toàn vẹn (Integrity), ví dụ: Phía trên là Lê Văn Ba thì phía dưới cũng phải là Lê Văn Ba.
. Nếu vài tiến trình (hơn 1) cùng sửa đơn trên một lúc (không đảm bảo được tính Loại trừ lẫn nhau) thì nội dung của nó có thể không đúng. Ví dụ, giả sử tiến trình P1 (nhà sản xuất) sửa Lê Văn Ba phía trên thành Lê Văn Bàng, trong khi P2 (nhà sản xuất khác) sửa Lê Văn Ba phía dưới thành Lê Văn Bá, mà có tiến trình P3 (nhà tiêu thụ) nào đó "lấy" đơn về dùng (để in ra) thì kết quả sẽ không nhất quán như sau:
ĐƠN XIN VIỆC Kính gửi: Giám đốc công ty x Tôi tên là: Lê Văn Bàng ..........(nội dung đơn)............. TP Hồ Chí Minh, ngày 5 tháng 5 năm 2011 Người làm đơn ....(chữ ký).... Lê Văn Bá
Câu 3: Khái niệm đèn hiệu (Semaphores).Và 2 ứng dụng của đèn hiệu.
Khái niệm đèn hiệu
 Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
 Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu): typedef int semaphore; // Định nghĩa kiểu Đèn hiệu wait (semaphore S) { while ( S <= 0 ); // Chờ bận nếu S<=0 S --; // Giảm S đi 1 } signal (semaphore S) { S ++; // Tăng S lên 1 }
 Việc kiểm tra S <= 0 và giảm S (trong Wait) hoặc tăng S (trong Signal) phải được thực hiện trọn vẹn (không xảy ra ngắt trong thời gian thi hành), do đó Wait và Signal được gọi là các tác nguyên (Atomic Operations).
Hai ứng dụng của đèn hiệu:
Câu 4: Thực thi đèn hiệu trong windows
Câu 5: Thực thi bài toán sản xuất và tiêu thụ được đồng bộ bằng ba đèn hiệu
HANDLE semEmpty, semFull; //hai đèn hiệu
CRITICAL_SECTION critSec;//Biến kiểu Mutex
void Producer(void * p)
{
while (1)
{
// ... Sản xuất (nextProduced)
// Chờ đến khi có chỗ trống
WaitForSingleObject(semEmpty, INFINITE);
EnterCriticalSection(&critSec);
//…Sắp sản phẩm vào Buffer
// Tăng (semFull) lên 1
ReleaseSemaphore(semFull, 1, NULL);
LeaveCriticalSection(&critSec);
SuspendThread(GetCurrentThread());
}
}
void Consumer()
{
int nextConsumed;
while (1)
{
// Chờ đến khi có sản phẩm
WaitForSingleObject(semFull, INFINITE);
EnterCriticalSection(&critSec);
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE;
// Tăng (semEmpty) lên 1
ReleaseSemaphore (semEmpty, 1, NULL);
LeaveCriticalSection(&critSec);
// ... Tiêu thụ (nextConsumed)
SuspendThread(GetCurrentThread());
}
}
- Biến semEmpty dùng để chứa mục quản của đèn hiệu quản lý số vùng trống trong bộ đệm.
- Biến semFull dùng để chứa mục quản của đèn hiệu quản lý số sản phẩm trong bộ đệm.
- CritSec là đối tượng đèn hiệu kiểu mutex dùng để bảo vệ đoạn tương tranh để đảm bảo tính loại trừ lẫn nhau trong công việc của các tiến trình với tài nguyên dùng chung.
BÀI 7:
Câu 1: Những lý do đồng bộ hóa công việc tiến trình. Cho ví dụ minh họa
 Đảm bảo tính nhất quán của tài nguyên dùng chung.
 Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình) .
VD: một trường học chỉ có 1 phòng lab (tài nguyên dùng chung) , lớp có giờ học trước thì được vào phòng lab học, các lớp còn lại phải chờ đến khi lớp học trước đó hết giờ mới được vào phòng lab
Câu 2: Khái niện đoạn tương tranh và loại trừ lẫn nhau. Cho ví dụ minh họa.
 Đoạn tương tranh :Xét một hệ có n tiến trình P0,P1, ...,Pn, mỗi tiến trình có một đoạn mã lệnh, nếu như trong đoạn mã này các tiến trình thao tác trên các biến chung,đọc ghi file... (tổng quát: thao tác trên dữ liệu chung) thì đoạn mã lệnh đó là đoạn tương tranh.
 Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.
 Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).
Ví dụ minh họa :
ĐƠN XIN VIỆC Kính gửi: Giám đốc công ty x Tôi tên là: Lê Văn Ba ..........(nội dung đơn)............. TP Hồ Chí Minh, ngày 5 tháng 5 năm 2011 Người làm đơn ....(chữ ký).... Lê Văn Ba
. Nội dung đơn này phải được đảm bảo tính toàn vẹn (Integrity), ví dụ: Phía trên là Lê Văn Ba thì phía dưới cũng phải là Lê Văn Ba.
. Nếu vài tiến trình (hơn 1) cùng sửa đơn trên một lúc (không đảm bảo được tính Loại trừ lẫn nhau) thì nội dung của nó có thể không đúng. Ví dụ, giả sử tiến trình P1 (nhà sản xuất) sửa Lê Văn Ba phía trên thành Lê Văn Bàng, trong khi P2 (nhà sản xuất khác) sửa Lê Văn Ba phía dưới thành Lê Văn Bá, mà có tiến trình P3 (nhà tiêu thụ) nào đó "lấy" đơn về dùng (để in ra) thì kết quả sẽ không nhất quán như sau:
ĐƠN XIN VIỆC Kính gửi: Giám đốc công ty x Tôi tên là: Lê Văn Bàng ..........(nội dung đơn)............. TP Hồ Chí Minh, ngày 5 tháng 5 năm 2011 Người làm đơn ....(chữ ký).... Lê Văn Bá
Câu 3: Khái niệm đèn hiệu (Semaphores).Và 2 ứng dụng của đèn hiệu.
Khái niệm đèn hiệu
 Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
 Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu): typedef int semaphore; // Định nghĩa kiểu Đèn hiệu wait (semaphore S) { while ( S <= 0 ); // Chờ bận nếu S<=0 S --; // Giảm S đi 1 } signal (semaphore S) { S ++; // Tăng S lên 1 }
 Việc kiểm tra S <= 0 và giảm S (trong Wait) hoặc tăng S (trong Signal) phải được thực hiện trọn vẹn (không xảy ra ngắt trong thời gian thi hành), do đó Wait và Signal được gọi là các tác nguyên (Atomic Operations).
Hai ứng dụng của đèn hiệu:
Câu 4: Thực thi đèn hiệu trong windows
Câu 5: Thực thi bài toán sản xuất và tiêu thụ được đồng bộ bằng ba đèn hiệu
HANDLE semEmpty, semFull; //hai đèn hiệu
CRITICAL_SECTION critSec;//Biến kiểu Mutex
void Producer(void * p)
{
while (1)
{
// ... Sản xuất (nextProduced)
// Chờ đến khi có chỗ trống
WaitForSingleObject(semEmpty, INFINITE);
EnterCriticalSection(&critSec);
//…Sắp sản phẩm vào Buffer
// Tăng (semFull) lên 1
ReleaseSemaphore(semFull, 1, NULL);
LeaveCriticalSection(&critSec);
SuspendThread(GetCurrentThread());
}
}
void Consumer()
{
int nextConsumed;
while (1)
{
// Chờ đến khi có sản phẩm
WaitForSingleObject(semFull, INFINITE);
EnterCriticalSection(&critSec);
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE;
// Tăng (semEmpty) lên 1
ReleaseSemaphore (semEmpty, 1, NULL);
LeaveCriticalSection(&critSec);
// ... Tiêu thụ (nextConsumed)
SuspendThread(GetCurrentThread());
}
}
- Biến semEmpty dùng để chứa mục quản của đèn hiệu quản lý số vùng trống trong bộ đệm.
- Biến semFull dùng để chứa mục quản của đèn hiệu quản lý số sản phẩm trong bộ đệm.
- CritSec là đối tượng đèn hiệu kiểu mutex dùng để bảo vệ đoạn tương tranh để đảm bảo tính loại trừ lẫn nhau trong công việc của các tiến trình với tài nguyên dùng chung.

Cảm ơn bạn Thanh nhiều, đã tổng hợp cho lớp nhiều tài liệu quý giá

Cám ơn bạn rất nhiều nghe , tài liệu thật bổ ích .

Cảm ơn bạn nhiều, vì đã tập hợp được rất nhiều câu hỏi rất hay và nhiều vấn đề trong bài giảng của thầy.
Nhưng mình thấy vẫn còn một số hạn chế thế này này : Các câu hỏi vẫn còn thiếu và vẫn còn lặp lại phần trình bày : ví dụ các câu hỏi và trả lời của bài 2 bạn viết lặp lại 2 lần luôn đó
Bạn sửa lại và bổ sung nha

Cám ơn bạn rất nhiều vì bài viết! Nhưng mình thấy còn có một số câu hỏi có phần trả lời chưa đầy đủ lắm.