Đề cương nguyên lý hệ điều hành

hiệu ngắt I/O hoàn thành. CPU sẽ trong trạng thái chờ cho đến khi có một ngắt tiếp. - Mỗi thời điểm chỉ có 1 yêu cầu I/O được giải quyết, ko xử lý đồng thời. - Không có sự chồng chéo trong xử lý I/O. Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 9  như vậy: tiến trình đang chạy, nếu gặp ngắt thì dừng lại, k xử lý nữa để nhận tín hiệu từ I/O. I/O hoàn thành thì tiến trình lại chạy tiếp. Các tiến trình chờ được xử lý xếp hàng thành dòng đợi. Không đồng bộ (asynchronous): Sau khi I/O bắt đầu, điều khiển được chuyển tới chương trình của người sử dụng mà không chờ I/O hoàn thành. - System call là một yêu cầu của user chuyển tới hệ điều hành đòi hỏi đáp ứng I/O. - I/O không đồng bộ cho phép I/O đồng thời.  như vậy: khi tiến trình đang chạy, HĐH vẫn có thể nhận I/O bên ngoài mà không cần dừng vì có nhiều luồng (thread) để xử lý các ngắt khác nhau. Bảng trạng thái (device-status table) chứa các entry của mỗi thiết bị I/O ghi kiểu, địa chỉ và trạng thái. (bảng xem trong slide) Hệ điều hành tra cứu vào bảng thiết bị I/O để xác định trạng thái thiết bị và sửa đổi bảng nhập vào bao gồm thêm thông tin ngắt I/O mới. Sơ đồ: Câu 5: Giải thích lược đồ các thiết bị lưu trữ, phân tích nguyên lý hoạt động và đặc tính của từng loại thiết bị lưu trữ? Trình bày nguyên lý và hoạt động của kỹ thuật caching? Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 10 Lược đồ các thiết bị lưu trữ Giải thích lược đồ Từ trên xuống dung lượng lưu trữ tăng dần còn tốc độ xử lý giảm dần. ⌂ Registers: thanh ghi. ⌂ Cache: bộ nhớ đệm. ⌂ Main memory: bộ nhớ chính. ⌂ Electronic disk: bộ nhớ thứ cấp ⌂ Magnetic disk: đĩa từ ⌂ Optical disk: đĩa quang ⌂ Magnetic tapes: băng từ Nguyên lý hoạt động và đặc tính của từng loại: ⌂ Registers: - Nguyên lý hoạt động -> dữ liệu được chuyển từ bộ nhớ chính vào các thanh ghi, tính toán trên chúng, sau đó chuyển kết quả vào bộ nhớ chính. - Đặc tính: tốc độ truy xuât nhanh, bộ nhớ dung lượng nhỏ Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 11 ⌂ Cache: - Nguyên lý hoạt động -> khi 1 chương trình cần truy xuất dữ liệu từ ổ đĩa: đầu tiên bộ nhớ cache được kiểm tra Nếu có, dữ liệu được lấy trực tiếp từ cache. Không có, dữ liệu đc sao tới cache và đc sử dụng. - Đặc tính: tốc độ truy xuất nhanh, bộ nhớ dung lượng nhỏ ⌂ Main memory: - Nguyên lý hoạt động: ->khi CPU thực thi 1 chỉ thị trước tiên nó đọc các chỉ thị từ bộ nhớ và nạp vào bộ nhớ chính sau đó nó đọc và viết dữ liệu từ bộ nhớ chính trong chu kỳ lấy dữ liệu. - Đặc tính: tốc độ truy xuất nhanh CPU có thể truy xuất trực tiếp, bộ nhớ dung lượng lớn. ⌂ Electronic disk: - Nguyên lý hoạt đông ->theo cơ chế đọc ghi dữ liệu nhanh chóng bằng một tập hợp các phần tử từ hóa trên các đĩa quay. - Đặc tính: tốc độ truy xuất trung bình là thiết bị lưu trữ mở rộng cung cấp khả năng lưu trữ lớn và lâu dài. ⌂ Magnetic disk: - Nguyên lý hoạt động ->theo cơ chế di chuyển đầu đọc (ghi) đến trực tiếp vị trí lưu trữ dữ liệu. - Đặc tính: kim loại cứng hoặc khối phủ các vật liệu ghi từ tính tốc độ truy xuất chậm, Khả năng lưu trữ lớn. ⌂ Optical disk: - Nguyên lý hoạt động ->đọc ghi dữ liệu trên nguyên tắc quang học, dùng tia sáng laser. - Đặc tính: lưu trữ dữ liệu dạng số dùng phương tiện quang học để lưu thông tin tốc độ truy xuất chậm, khả năng lưu trữ lớn. ⌂ Magnetic tapes: - Nguyên lý hoạt động ->theo cơ chế đọc ghi tuần tự phải đợi để băng từ quay đến phần cần đọc hoặc ghi dữ liêu. - Đặc tính: dải nhựa tổng hợp hẹp đc phủ các vật liệu ghi từ tính, tốc độ truy xuât chậm, lưu trữ lớn, đc sử dụng rộng rãi. Caching: kỹ thuật làm tăng tốc độ xử lý của hệ thống bằng cách: Thực hiện copy thông tin tới thiết bị nhớ nhanh hơn để tăng tốc độ xử lý của hệ thống. Giữ lại các dữ liệu mới được truy nhập trong thiết bị tốc độ cao đó. Yêu cầu: dữ liệu phải được lưu trữ đồng bộ trong nhiều mực hệ thống nhớ để nhất quán (consistent). Vì dung lượng cach có hạn, yêu cầu có sự quản lý cach (cache management) để tăng hiệu năng. Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 12 Đọc để hiểu bản chất // Cache là tên gọi của bộ nhớ đệm – nơi lưu trữ các dữ liệu nằm chờ các ứng dụng hay phần cứng xử lý. Mục đích của nó là để tăng tốc độ xử lý (có sẵn xài liền không cần tốn thời gian đi lùng sục tìm kéo về). việc truy xuất 1 byte dữ liệu trong bộ nhớ RAM có thể nhanh hơn hàng ngàn lần nếu truy xuất từ một ổ đĩa cứng. Nói một cách bài bản, cache là một cơ chế lưu trữ tốc độ cao đặc biệt. Nó có thể là một vùng lưu trữ của bộ nhớ chính hay một thiết bị lưu trữ tốc độ cao độc lập.Có hai dạng lưu trữ cache được dùng phổ biến trong máy tính cá nhân là memory caching (bộ nhớ cache hay bộ nhớ truy xuất nhanh) và disk caching (bộ nhớ đệm đĩa).// Nguyên lý hoạt động: +) khi 1 chương trình cần truy xuất dữ liệu từ ổ đĩa: đầu tiên bộ nhớ cache được kiểm tra *) nếu có, dữ liệu được lấy trực tiếp từ cache. *) ko có, dữ liệu đc sao tới cache và đc sử dụng. Câu 6: Trình bày cấu trúc phân lớp của hệ điều hành OS/2. Sơ đồ: Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 13 Trong sơ đồ trên ta thấy hệ điều hành được chia thành các lớp (bậc) mỗi lớp được xây dựng trên 1 lớp bên dưới.Lớp dưới cùng(lớp 0) là phần cứng ,lớp cao nhất là giao tiếp người sử dụng.Với Khả năng mô đun hóa ,các lớp được chon 1 số thao tác và được phục vụ bởi chỉ lớp bậc dưới của nó. Các ứng dụng của người sử dụng giao tiếp với hệ điều hành thông qua lớp giao tiếp các chương trình ứng dụng đã được lập trình sẵn,ngoài ra hệ điều hành còn cung cấp thư viện API (giao diện lập trình ứng dụng)được thiết kế theo kiểu hướng đối tượng và là giao tiếp cho người lập trình.Kế đó là các hệ thống con. Dưới các hệ thống con là phần nhân của hệ thống,phần này gồm quản li bộ nhớ,gửi các tác vụ,quản lí thiết bị.Lớp dưới cùng là phần cứng nó cũng được chia thành các mô đun độc lập.Do cấu trúc phân lớp nên khi các chương trình ứng dụng được gửi xuống hệ điều hành nó trở thành các chương trình độc lập điều này làm cho hệ điều hành có tính đa nhiệm. Sự khác biệt cơ bản giữa OS/2 với Unix là: OS/2 có cấu trúc phân lớp còn Unix có cấu trúc đơn giản chỉ gồm 2 phần là các chương trình hệ thống và phần nhân. Trong Unix người sử dụng dùng các chương trình ứng dụng dựa trên các chương trình con có sẵn của hệ điều hành,người sử dụng gử các yêu cầu tới shell, shell biên dịch chung sau đó gửi tới nhân. Trong Unix các chương trình con nằm ngoài nhân do vậy người dung có thể thêm bớt các chương trình con. Unix hướng tới hệ thống lớn đa người dùng. Câu7: Hãy trình bày cấu trúc phân lớp của hệ điều hành UNIX. Sự khác biệt cơ bản về cấu trúc của 2 loại hệ điều hành OS2 là gi? Trong cấu trúc phân lớp hãy chỉ ra thành phần làm cho hệ điều hành này trở thành hệ điều hành đa người dùng. UNIX giống như các hệ điều hành khác nó là lớp nằm giữa phần cứng và ứng dụng. Nó có chức năng quản lý phần cứng và quản lý các ứng dụng thực thi. Cấu trúc cơ bản của hệ điều hành UNIX như sau: Các chương trình hệ thống Kernel Bao gồm tất cả các thành phần bên dưới giao tiếp lời gọi hệ thống và trên lớp phần cứng Cung cấp hệ thống tệp tin, lập lịch CPU, quản trị bộ nhớ và các chức năng điều hành hệ thống khác. Một số lượng lớn các chức năng được tập hợp trong một lớp Ta có thể hiển thị hệ điều hành UNIX truyền thống khi nó được phân tầng như sau: Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 14 Sự khác biệt cơ bản giữa cấu trúc HĐH UNIX và cấu trúc HĐH OS2 là UNIX Nó chứa 2 phần có thể tách rời nhau: nhân và các chương trình hệ thống Bao gồm tất cả các thành phần bên dưới giao tiếp lời gọi hệ thống và trên lớp phần cứng Lời gọi hệ thống định nghĩa giao diện lập trình ứng dụng cho UNIX Tập hợp các chương trình hệ thống thường dùng sẵn định nghĩa giao diện người dùng Người lập trình và giao diện người dùng định nghĩa ngữ cảnh mà nhân phải hỗ trợ Những ấn bản mới của UNIX được thiết kế để dùng phần cứng tiên tiến hơn : Các hệ điều hành có thể giữ lại việc điều khiển lớn hơn qua các máy tính và qua các ứng dụng thực hiện việc sử dụng máy tính đó Những người cài đặt thoải mái hơn trong việc thực hiệ n việc sử dụng máy tính Việc chia toàn bộ các chức năng và đặc điểm thành các thành phần cho phép người lập trình che giấu thông tin, họ tự do cài đặt các thủ tục cấp thấp… OS/2 Cài đặt phân tầng nên có khuynh hướng ít hiệu quả hơn các loại khác Tại mỗi tầng , các tham số có thể hiệu chỉnh, dữ liệu có thể được truyền Mỗi tầng thêm chi phí cho lời gọi hệ thống, kết quả thực sự là lời gọi hệ thống mất thời gian lâu hơn khi chúng thực hiện trên hệ thống không phân tầng Bổ sung thêm tính năng đa tác vụ và điều hành hai chế độ cùng một số đặc điểm mới. Câu 8: Các kỹ thuật quản lý các khối còn trống, các khối bị hỏng trên bộ nhớ lưu trữ ngoài. Quản lý theo bit vecto( bit map). Không gian nhớ được chia thành các khối và được đánh số từ 0..max. Mỗi khối sử dụng một bit để đánh dấu trạng thái. Khối đĩa nào đã sử dụng có giá trị là 1, khối nào chưa sử dụng có giá trị 0. Đọc thông tin trên bitmap ta có thể xác định được không gian nhớ tự do của bộ lưu trữ( đĩa từ). Ưu điểm: quản lý dễ dàng, đơn giản dễ tìm kiếm. Nhược điểm: tốn không gian lưu trữ dành cho bitmap. Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 15 Quản lý theo phương pháp liệt kê: Sử dụng một danh sách móc nối để liệt kê các khối đĩa tự do. Con trỏ đầu trong danh sách chỉ tới khối đĩa tự do đầu tiên, mỗi khối có một con trỏ để trỏ tới khối kế tiếp. Quản lý theo phương pháp lập nhóm: Hệ thống nhóm các khối đĩa tự do liên tiếp thành nhóm. Khối đĩa tự do đầu tiên trong nhóm lưu giữ địa chỉ của các khối đĩa tự do trong nhóm. Khối đĩa tự do cuối cùng trong nhóm lưu trữ địa chỉ của khối tự do đầu tiên trong nhóm tiếp theo. Quản lý theo phương pháp đếm: Giống như phương pháp lập nhóm. Hệ thống lập danh sách quản lý địa chỉ của các khối tự do đầu tiên và số lượng các khối tự do liên tục kế tiếp các khối đĩa đó. Câu 9: Các phương pháp quản lý tệp trên bộ lưu trữ ngoài: Định vị liên tục: mỗi tệp chiếm một tập hợp liên tục các khối trên đĩa. Để định vị tệp cần biết địa chỉ bắt đầu và số lượng các khối( block) trên file. Sử dụng việc truy cập ngẫu nhiên. Ưu điểm: không gian tự do còn lại lớn. Nhược điểm: không lưu trữ được các tệp lớn. Định vị liên kết. Sử dụng hai con trỏ: con trỏ đến địa chỉ đầu tiên của khối đầu tiên và một con trỏ đến địa chỉ của khối cuối cùng. Và sử dụng một con trỏ tới địa chỉ khối kế tiếp. Ưu điểm: tận dụng được không gian trống. Nhược điểm: không truy cập ngẫu nhiên và tốn không gian vì phải cung cấp không gian cho việc lưu trữ các con trỏ. Định vị theo mục lục: Cung cấp một khối lưu chỉ số chứa địa chỉ của các khối đã cấp phát khi đó ta chỉ cần cập nhật khối chỉ số của file. Ưu điểm: có thể truy cập trực tiếp Nhược điểm: lãng phí không gian nhớ. Câu 10: Hệ điều hành UNIX và MSDOS sử dụng phương pháp nào để định vị tệp, mô tả bằng sơ đồ. I.MS-DOS MS-DOS sử dụng bảng FAT (File Allocation Table), lưu giữ tất cả không gian trên đĩa theo phương pháp danh sách liên kết có chỉ mục. Thông thường có từ hai FAT trở lên để phòng hờ. Mỗi entry của FAT quản lý một khối (còn gọi là Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 16 cluster được đánh số bắt đầu từ 2) trên đĩa. Kích thước khối được lưu trong bootsector thông thường từ 1 đến 8 sector. Có hai loại FAT là FAT 12 và FAT 16. FAT 12 có thể quản lý được 4096 khối còn FAT 16 có thể quản lý 64 K khối trên một partition. Giá trị trong mỗi phần tử (entry) có ý nghĩa như sau : 0 Cluster còn trống (0)002 - (F)FEF Cluster chứa dữ liệu của các tập tin (F)FF0 - (F)FF6 Dành riêng, không dùng (F)FF7 Cluster hỏng (F)FF8 - (F)FFF Cluster cuối cùng của chuỗi Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 17 Có một ánh xạ một một giữa entry và khối ngoại trừ hai entry đầu tiên, dùng cho đĩa. Khi hệ thống mở một tập tin, MS-DOS tìm trong bảng mô tả tập tin trong PSP, sau đó kiểm tra tên tập tin xem có phải là con, lpt, ... tiếp theo kiểm tra các đường dẫn để xác định vị trí trong bảng thư mục. Tên tập tin (8bytes) Phần mở rộng (3bytes) Thuộc tính (1 byte) A-D-V-S-H-R Dành riêng (10bytes) Giờ (2bytes) Ngày (2bytes) Khối đầu tiên (2bytes) Kích thước tập tin (4bytes) Hình 10.2 Một entry thư mục trong MS-DOS Bảng thư mục nằm ngay sau FAT, và mỗi entry là 32 byte. Mười một byte đầu tiên mô tả tên và phần mở rộng(không lưu trữ dấu chấm phân cách). Sau đó là byte thuộc tính, với giá trị : 1 : tập tin chỉ đọc 2 : tập tin ẩn 4 : tập tin hệ thống 8 : nhãn đĩa 16 : thư mục con 32 : tập tin chưa backup Byte thuộc tính có thể được đọc ghi trong quá trình sử dụng. Tiếp theo là 10 byte trống dàng riêng sử dụng sau này. Sau đó là 4 byte lưu trữ giờ, ngày với 6 bit cho giây, 4 bit cho giờ, 5 bit cho ngày, 4 bit cho tháng và 7 bit cho năm (từ 1980). Hai byte kế tiếp chứa số hiệu của khối đầu tiên (khối trong MS-DOS còn được gọi là cluster) và bốn byte sau cùng lưu trữ kích thước của tập tin. Hệ thống tập tin của Unix: Có hai cách mô tả tên tập tin trong UNIX. Cách thứ nhất là dùng đường dẫn tuyệt đối, tập tin được truy cập từ thư mục gốc. Thứ hai là dùng khái niệm thư mục làm việc hay thư mục hiện hành trong đường dẫn tương đối. UNIX cung cấp đặc tính LINK, cho phép nhiều người sử dụng cùng dùng chung một tập tin, hay còn gọi là chia xẻ tập tin. Ví dụ như hình sau, fred và lisa cùng Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 18 làm việc trong cùng một đề án, họ cần truy cập tập tin lẫn nhau. Giả sử fred cần truy cập tập tin x của lisa, anh ta sẽ tạo một entry mới trong thư mục của anh ta và sau đó có thể dùng x với nghĩa là /usr/lisa/x. Ngoài ra UNIX cho phép một đĩa có thể được mount thành một thành phần của hệ thống cây thư mục của một đĩa khác. Một đặc tính thú vị khác của hệ thống tập tin của UNIX là khóa ( locking). Trong một số ứng dụng, một số tiến trình có thể sử dụng cùng một tập tin cùng lúc. Có hai loại khóa là chia xẻ hay loại trừ. Nếu tập tin đã chứa khóa chia xẻ thì có thể đặt thêm một khóa chia xẻ nữa, nhưng không thể đặt một khoá loại trừ nhưng nếu đã được đặt khóa loại trừ thì không thể đặt thêm khóa nữa. Vùng khóa có thể được ghi chồng. Hệ thống tập tin của UNIX thông thường được cài đặt trên đĩa như ở hình sau : Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 19 Khối 0 thường chứa mã khởi động của hệ thống. Khối 1 gọi là khối đặc biệt (super block), nó lưu giữ các thông tin quan trọng về toàn bộ hệ thống tập tin, bao gồm: Kích thước của toàn bộ hệ thống tập tin. Địa chỉ của khối dữ liệu đầu tiên. Số lượng và danh sách các khối còn trống. Số lượng và danh sách các I-node còn trống. Ngày super block được cập nhật cuối cùng. Tên của hệ thống tập tin. Nếu khối này bị hỏng, hệ thống tập tin sẽ không truy cập được. Có rất nhiều trình ứng dụng sử dụng thông tin lưu trữ trong super block. Vì vậy một bản sao super block của hệ thống tập tin gốc được đặt trong RAM để tăng tốc độ truy xuất đĩa. Việc cập nhật super block sẽ được thực hiện ngay trong RAM và sau đó mới ghi xuống đĩa. Sau khối đặc biệt là các I-node, được đánh số từ một cho tới tối đa. Mỗi I-node có độ dài là 64 byte và mô tả cho một tập tin duy nhất (chứa thuộc tính và địa chỉ khối lưu trữ trên đĩa của tập tin). Sau phần I-node là các khối dữ liệu. Tất cả tập tin và thư mục đều được lưu trữ ở đây. Một entry của directory có 16 byte, trong đó 14 byte là tên của tập tin và 2 byte là địa chỉ của I-node. Để mở một tập tin trong thư mục làm việc, hệ thống chỉ đọc thư mục, so sánh tên được tìm thấy trong mỗi entry cho đến khi tìm được, từ đó xác định được chỉ số I-node và đưa vào bộ nhớ để truy xuất. Tập tin được tạo hay tăng kích thước bằng cách sử dụng thêm các khối từ danh sách các khối còn trống. Ngược lại, khối được giải phóng sẽ trả về danh sách khối trống khi xóa tập tin. Super block sẽ chứa địa chỉ của 50 khối trống. Trong đó địa chỉ cuối cùng chứa địa chỉ của một khối chứa địa chỉ của 50 khối trống kế tiếp và cứ tiếp tục như thế. Unix sử dụng khối trống trong super block trước. Khi khối trống cuối cùng trong super block được sử dụng, 50 khối trống kế tiếp sẽ được đọc vào trong super block. Ngược lại, khi một khối được giải phóng, địa chỉ của nó sẽ được thêm vào danh sách của super block. Khi đã đủ 50 địa chỉ trong super block, khối trống kế tiếp sẽ được dùng để lưu trữ 50 địa chỉ khối trống đang đặt trong super block thay cho super block. Câu 11: Ý nghĩa của các chế độ thực thi chương trình: User Mode và Kernel Mode? Lời gọi hệ thống (System Call)? Nêu khái niệm và các đặc điểm của Tiến trình (Process). Vẽ và giải thích Sơ đồ trạng thái của tiến trình. Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 20 Ý nghĩa của chế độ thực thi chương trình user mode và kernel mode: Để bảo vệ hệ điều hành tránh sự truy cập và/hoặc thay đổi bất hợp lệ của các chương trình ứng dụng của người sử dụng, hệ điều hành phân ra hai chế độ xử lý truy cập: Kernel mode và User mode. Các chương trình ứng dụng của người sử dụng chạy trong user mode, trong khi đó các dịch vụ hệ thống và các chương trình điều khiển thiết bị của hệ điều hành chạy trong kernel mode. Kernel mode chỉ đến một chế độ của việc thực hiện trong processor mà ở đó nó có toàn quyền truy cập đến tất cả hệ thống bộ nhớ và tất cả các chỉ thị của CPU. Trong cấu trúc này phần mềm hệ điều hành được cung cấp một mức đặc quyền cao hơn so với mức đặc quyền của các chương trình ứng dụng của người sử dụng. Processor cung cấp các cơ sở cần thiết để người thiết kế hệ điều hành đảm bảo rằng các ứng dụng không thể phá vỡ trạng thái ổn định của hệ thống và làm hỏng nó. Lời gọi hệ thống (system call) – Cung cấp giao tiếp giữa tiến trình và HĐH. Có 2 dạng: • Cấp thấp: các lệnh hợp ngữ • Cấp cao: các hàm/thủ tục thiết kế bằng NNLT cấp cao. – Trong các NLT cấp cao, user không quan tâm đến chi tiết mà chỉ cần thông qua các hàm hay các lệnh để gọi thực hiện – Có 3 phương pháp chuyển tham số cho HĐH: thanh ghi, ngăn xếp hoặc cấu trúc bảng – Các loại lời gọi hệ thống: kiểm soát tiến trình, tao tác tập tin, thao tác thiết bị, truyền thông điệp. Tiến trình (process). – Tiến trình là một loạt các công việc được thi hành (proram, batch processing, spooling, connecting…) – Tiến trình sử dụng tài nguyên máy tính (CPU, bộ nhớ, tập tin, thiết bị…) để phục vụ công việc của nó – Khi tiến trình khởi tạo, nó đòi hỏi nhiều tài nguyên hệ thống. – Khi tiến trình kết thúc, HĐH phải thu hồi hoặc tái tạo tài nguyên để có thể dùng lại cho các tiến trình khác – Tiến trình được biên dịch thành các tập tin thụ động trên đĩa – Khi tiến trình được kích hoạt, HĐH sẽ khởi tạo tài nguyên ban đầu theo yêu cầu, nạp tập chỉ thị vào bộ nhớ và thi hành theo cơ chế tuần tự. Tiến trình chuyển sang hoạt. Sơ đồ trạng thái của tiến trình Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 21 Giải thích: 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ý Bocked: 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ý . 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 cs 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 1 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ờ 1 sự kiện hay 1 thao tác nhập/ xuất. Bộ điều phối chọn 1 tiến trình khác để cho xử lý Tài nguyên mà tiến trình yêu cầu trở nên sẵn sàng để cấp phát, hay sự kiện hoặc thao tác nhập/ xuất tiến trình đang đợi hoàn tất. Câu 12: Hãy trình bày cấu trúc phân lớp của hệ điều hành Windows XP. Trong cấu trúc phân lớp hãy chỉ ra các thành phần làm cho hệ điều hành này trở thành hệ điều hành tương thích với các ứng dụng của một số hệ điều hành khác?. Cấu trúc phân lớp của hệ điều hành của hệ điều hành Windows XP Hệ thống phân lớp là: Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 22 Hệ thống được xây dựng bởi nhiều lớp. Mỗi lớp được xây dựng dựa vào các lớp bên trong. Lớp trong cùng (lớp 0): phần cứng (hardware) Lớp ngoài cùng (lớp n): giao diện với người dùng. Mỗi lớp là một đối tượng trừu tượng (dữ liệu + thao tác xử lý dữ liệu). Mỗi lớp có thể gọi các thủ tục của các lớp bên trong. Windows XP là một hệ điều hành phân lớp với hoạt động được chia làm 2 chế độ chính là: Chế độ bảo vệ (Protected mode): HAL (hardware abstrction layer – lớp phần cứng trừu tượng), kernel (thực hiện các thủ tục của HĐH – system call), executive (các trình quản lý). Chế độ người dùng (User mode): thực hiện các chương trình của người dùng, là tập hợp của các tiểu hệ thống (subsystems). Trong đó: - Các tiểu hệ thống môi trường (Environmental subsystems) giả lập các hệ thống khác nhau. - Các tiểu hệ thống bảo vệ (Protection subsystems) cung cấp các chức năng bảo vệ. Từ 2 chế độ này phân thành nhiều lớp (layer) con. Các thành phần làm cho hệ điều hành Windows XP trở thành hệ điều hành tương thích với các ứng dụng của một số hệ điều hành khác Các tiến trình trong user-mode được phân lớp dựa trên các dịch vụ thực thi của XP, cho phép XP chạy các chương trình được phát triển cho các hệ điều hành khác. XP dùng tiểu hệ thống Win32 (Win32 subsystem) làm môi trường điều hành chính; Win32 được dùng để khởi động tất cả các tiến trình. Môi trường MS-DOS được cung cấp bởi một ứng dụng Win32 được gọi là máy ảo DOS (Virtual DOS Machine – VDM), một tiến trình trong user- mode được phân trang và giải quyết giống như bất kỳ c ác luồng (thread) của XP. Môi trường Windows 16bit: - Được cung cấp bởi một VDM mà VDM đó tổ chức thành Windows on Windows. - Cung cấp các thủ tục và thủ tục con của trong nhân của Windows 3.1 cho trình quản lý cửa sổ (window manager) và các chức năng GDI. Tiểu hệ thống POSIX được thiết kế để chạy các ứng dụng POSIX theo tiêu chuẩn POSIX.1 dựa trên nền tảng UNIX. Tiểu hệ thống OS/2 dùng để chạy các ứng dụng OS/2 Tiểu hệ thống đăng nhập và bảo mật (Logon and sercurity) xác nhận người dùng đăng nhập vào hệ thống. - Yêu cầu người dùng phải có tên tài khoản và mật khẩu. - Gói xác nhận sẽ xác nhận người dùng bất cứ khi nào họ cố gắng truy cập vào một đối tượng trong hệ thống. Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 23 Câu 13. Hãy trình bày các phương pháp bảo vệ CPU, I/O và bộ nhớ chủ từ cấu trúc phần cứng của máy tính? Để bảo đảm quyền điều hành hệ thống của Hệ điều hành người ta đã sử dụng kĩ thuật nào? Trả lời Phương pháp bảo vệ CPU: Timer - đồng hồ ngắt giờ để đảm bảo quyền điều khiển của hệ điều hành Đồng hồ ngắt sẽ giảm đều đặn theo một chu kì nhất định Khi đồng hồ ngắt giờ giảm đến giá trị 0 thì một số ngắt xảy ra, ngắt này trả lại quyền điều khiển cho OS Timer thông thường được sử dụng cho những OS chia sẻ thời gian Timer cũng còn được sử dụng cho các máy tính thời gian thực Load-timer là một privikeged instruction Phương pháp bảo vệ I/O: Tất cả các chỉ thị I/O là chỉ thị đặc quyền Phải chắc chắn một chương trình của user không bao giờ giành được điều khiển của máy tính trong monitor mode ( chẳng hạn nó không bao giờ có thể thay đổi địa chỉ trong vecto ngắt). Bảo vệ bộ nhớ chủ: Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 24 Bảo vệ vécto ngắt và chương trình con phục vụ ngắt Thêm hai thanh ghi xác định vùng địa chỉ mà chương trình được phép truy nhập: - Base register – lưu trữ địa chỉ vật lý nhỏ nhất được phép truy nhập - Limit register - chứa kích thước của giới hạn Phần bên ngoài bộ nhớ của vùng đuợc định nghĩa là đã được bảo vệ Phần cứng bảo vệ: khi thực hiện trong monitor mode, hệ điều hành sẽ không bị hạn chế truy nhập tới vùng nhớ của cả monitor và user chỉ thị truy nhập địa chỉ vượt quá giá trị của thanh ghi base và limit la chỉ thị đặc quyền (privileged instruction) sơ đồ phần cứng bảo vệ địa chỉ Để bảo đảm quyền điều hành hệ thống của Hệ điều hành người ta đã sử dụng kĩ thuật timer Câu 14. Hãy trình bày khái niệm về các hàng đợi của tiến trình trong quá trình hoạt động? Trình bày mô hình lập lịch và các tiêu chuẩn dùng cho lập lịch tiến trình? Trả lời Khái niệm về các hàng đợi của tiến trình trong quá trình hoạt động Có 3 loại hàng đợi cơ bản: - Hàng đợi công việc: tập tất cả các tiến trình trong hệ thống. - Hàng đợi sẵn sàng: tập tất cả các tiến trình đã nạp trong bộ nhớ, sẵn sàng và chờ thực hiện. Hàng đợi sẵn sàng bao gồm các hàng đợi khác nhau (hàng đợi đa cấp), phân loại: + hàng đợi tương tác (interactive) Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 25 + hàng dợi nền (batch) Mỗi hàng đợi có 1 giải thuật lập lịch riêng: + hàng đợi tương tác – RR + hàng đợi nền – FCFS. - Hàng đợi thiết bị: tập tất cả các tiến trình chờ thiết bị nhập xuất Các tiến trình sẽ di chuyển giữa các hàng đợi khác nhau; sự “lão hóa” có thể thực hiện bằng phương pháp này. Mô hình lập lịch và các tiêu chuẩn dùng cho lập lịch tiến trình a) Mô hình lập lịch tiến trình Bộ lập lịch gồm: + Bộ lập lịch ngắn hạn (lập lịch CPU): lựa chọn 1 trong các tiến trình đã sẵn sàng để chuyển giao đến CPU thực thi. Bộ lập lịch ngắn hạn được thực hiện rất thường xuyên với chu kỳ mili giây và phải quyết định rất nhanh. Bộ lập lịch CPU quyết định vị trí của tiến trình khi tiến trình đó: 1. Chuyển từ trạng thái chạy sang chờ 2. Chuyển từ trạng thái chạy sang sẵn sàng 3. Chuyển từ trạng thái chờ sang sẵn sàng 4. Kết thúc Trường hợp 1 và 4 là không được lựa chọn. Các trường hợp khác là được lựa chọn. + Bộ lập lịch dài hạn( lập lịch công việc): lựa chọn các chương trình từ thiết bị nhớ để nạp và thực thi. Bộ lập lịch này cũng thực hiện thường xuyên nhưng với tần số chậm hơn (giây, phút) và có thể chạy chậm hơn. Bộ lập lịch dài hạn điều khiển ở mức độ đa chương. b) Tiêu chuẩn dùng cho lập lịch tiến trình - độ sử dụng CPU - giữ CPU luôn hoạt động. - thông lượng – số lượng tiến trình hoàn thành sự thực hiện theo đơn vị thời gian. - thời gian xoay vòng – tổng số thời gian để thực hiện từng tiến trình. - thời gian chờ - tổng số thời gian 1 tiến trình phải chờ trong hàng đợi sẵn sàng. - thời gian đáp ứng – tổng thời gian từ khi 1 yêu cầu được gửi đi đến khi sự đáp ứng đầu tiên được thực hiện (khong dùng với hệ thống time-sharing). Tối ưu hóa các tiêu chuẩn: - cực đại hóa độ sử dụng CPU - cực đại hóa thông lượng - cực tiểu hóa thời gian xoay vòng - cực tiểu hóa thời gian chờ - cực tiểu hóa thời gian đáp ứng CÂU 15: Khái niệm không gian địa chỉ logic và không gian địa chỉ vật lý? Chức năng và mô hình của bộ quản lý bộ nhớ MMU? Trả lời: Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 26 Không gian địa chỉ logic (Logical Address Spaces): Một địa chỉ được tạo ra bởi CPU được gọi là địa chỉ logic (logical address), nó chính là địa chỉ ảo ( virtual address). Tập hợp tất cả địa chỉ logic là không gian địa chỉ logic. Không gian điạ chỉ vật lý (Physical Address Spaces): Một địa chỉ được nạp vào thanh ghi địa chỉ bộ nhớ được gọi là địa chỉ vật lý (physical address), nó là địa chỉ thật trong bộ nhớ. Tập hợp tất cả địa chỉ vật lý tương ứng với mỗi địa chỉ logic là không gian địa chỉ vật lý. Chức năng của bộ quản lý bộ nhớ - MMU (Memory Management Unit): - Bộ quản lý bộ nhớ MMU là thiết bị phần cứng làm nhiệm vụ ánh xạ địa chỉ ảo tới địa chỉ vật lý. - MU thay thế địa chỉ logic phát ra từ chương trình của người sử dụng bằng địa chỉ thật trước khi nó được gử tới bộ nhớ. Để ánh xạ nó dùng thanh ghi tái định vị (relocation register). - Chương trình của người sử dung là địa chỉ logic, không bao giờ dung địa chỉ vật lý thật. - Mô hình: Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 27 Câu 16. Hãy trình bày mô hình quản lý bộ nhớ theo kiểu phân trang? Trình bày lược đồ chuyển đổi địa chỉ trong kĩ thuật phân trang? Trả lời Mô hình quản lý bộ nhớ theo kiểu phân trang Trong mô hình này, bộ nhớ vật lý được phân thành các khối có kích thước cố định bằng nhau, được đánh số địa chỉ bắt đầu từ 0 và được gọi là các khung trang (Page Frame ). Không gian địa chỉ của các tiến trình cũng được chia thành các phần có kích thước bằng nhau và bằng kích thước của 1 khung trang, được gọi là các trang (page) của tiến trình. Khi một tiến trình được nạp vào bộ nhớ thì các trang của tiến trình được nạp vào các khung trang còn trống bất kì (có thể không liên tiếp nhau) của bộ nhớ. Trên bộ nhớ có thể tồn tại các trang của nhiều tiến trình khác nhau. Khi 1 tiến trình bị swap – out thì các khung trang mà tiến trình các khung trang mà tiến trình này chiếm giữ sẽ được giải phóng để hệ điều hành có thể nạp các trang tiến trình khác vào. Trong kỹ thuật này, HĐH phải đưa ra các cơ chế thích hợp để theo dõi trạng thái của các khung trang (còn trống hay đã cấp phát) trên bộ nhớ và các khung trang đang chứa các trang của 1 tiến trình của các tiến trình khác nhau trên bộ nhớ. HĐH sử dụng 1 danh sách để ghi số hiệu của các khung trang còn trống trên bộ nhớ, HĐH dựa vào danh sách này để tìm các khung trang trống trước khi quyết định nạp một tiến trình vào bộ nhớ, danh sách này được cập nhật ngay sau khi HĐH nạp 1 tiến trình vào bộ nhớ, được kết thúc hoặc bị swap – out ra bên ngoài. Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 28 HĐH sử dụng bảng trang (pages table) để theo dõi vị trí các trang tiến trình trên bộ nhớ, mỗi tiến trình có 1 bảng trang riêng. Bảng trang bao gồm nhiều phần tử, thường là bằng số lượng trang của 1 tiến trình mà bảng trang này theo dõi, các phần tử được đánh số bắt đầu từ 0. Lược đồ chuyển đổi địa chỉ trong kĩ thuật phân trang: Trong kĩ thuật phân trang, khi cần truy xuất bộ nhớ địa chỉ CPU phát ra gồm: - số hiệu (p) – chỉ số trong bảng trang chứa địa chỉ cơ sở của nó trong bộ nhớ vật lý. - Vị trí trang (d) – tổ hợp với địa chỉ cơ sở để xác định địa chỉ vật lý và được gửi tới bộ nhớ. Kích thước của mỗi trang hay khung trang do phần cứng quy định và thường là lũy thừa của 2, biến đổi từ 512 byte đến 8192 byte. Nếu kích thước của không gian địa chỉ là 2m và kích thước của trang là 2n thì m-n bít cao của địa chỉ logic là số hiệu trang (p) và n bít còn lại là địa chỉ tương đối trong trang (d). Việc chuyển từ địa chỉ logic sang địa chỉ vật lý được thực hiện theo các bước : - Trích ra m-n bit trái nhất (thấp nhất) của địa chỉ logic để xác định số hiệu trang cần truy xuất. - Sử dụng số hiệu trang ở trên để chỉ đến phần tử tương ứng trong bảng trang của tiến trình, để xác định khung trang tương ứng, vd là k. Địa chỉ vật lý bắt đầu của khung trang là k*2n, và địa chỉ vật lý của byte cần truy xuất là số hiệu trang cộng với giá trị địa chỉ tương đối trong trang (d). Địa chỉ vật lý không cần tính toán, nó có được bằng cách nối số hiệu khung trang với địa chỉ tương đối của trang (d). Câu 17. Hãy trình bày khái niệm chia sẻ bộ nhớ dùng chung trong mô hình phân trang? Trình bày lược đồ chuyển đổi địa chỉ trong kĩ thuật sử dụng bảng phân trang dịch chuyển? Trả lời: Khái niệm chia sẻ bộ nhớ dùng chung trong mô hình phân trang: Chia sẻ code: một bản sao code chỉ đọc được chia sẻ giữa các tiến trình (chẳng hạn bộ soạn thảo văn bản, bộ dịch, hệ thống cửa sổ…) code được chia sẻ phải đặt ở cùng vị trí trong không gian địa chỉ logic của tất cả các tiến trình code và dữ liệu không chia sẻ mỗi tiến trình lưu trữ một bản sao code và dữ liêu phân biệt các trang code và dữ liệu dùng riêng có thể đặt ở bất cứ vị trí nào trong không gian địa chỉ logic Bảng phân trang dịch chuyển: Một điểm truy cập cho mỗi trang thực của bộ nhớ Điểm truy nhập chứa địa chỉ ảo của trang được lưu trữ tại vị trí địa chỉ thật trong bảng trangvà tên tiến trình đang sở hữu bảng trang này Bộ nhớ dành cho bảng trang tăng lên, nhưng thời gian tìm kiếm giảm đi sử dụng bảng băm để giới hạn tìm kiếm một hoặc một vài điểm truy nhập Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 29 Lược đồ chuyển đổi địa chỉ trong kĩ thuật sử dụng bảng phân trang dịch chuyển: (xem và trình bày theo sơ đồ) Câu 18: Hãy trình bày mô hình quản lý bộ nhớ theo kiểu phân đoạn? Trình bày lược đồ chuyển đổi địa chỉ trong mô hình phân đoạn? Trả lời Tóm lược: Kỹ thuật phân đoạn bộ nhớ là chia bộ nhớ thành những đoạn nhỏ, mỗi đoạn có số hiệu đoạn, nhờ vào các thanh ghi đoạn limit và thanh ghi nền base để biết đoạn nhớ nào trong bộ nhớ vật lý. Để xác định ô nhớ trong đoạn nhớ nào thì phải nhờ vào địa chỉ tương đối của mỗi đoạn đó là địa chỉ offset (độ lệch) là địa chỉ tương đối cho mỗi đoạn. Mỗi chương trình có thể có nhiều phân đọan, bây giờ được kết hợp thành bảng phân đọan thay bảng trang. Bảng phân đọan đơn giản là tập hợp những cặp cơ sở cho mỗi phân đọan. Trong quá trình phân đoạn bộ nhớ ta phải giải quyết 2 vấn đề đó là chuyển đổi địa chỉ và cài đặt bằng phân đoạn. Bảo vệ các đoạn nhớ: ngăn chặn sự xâm nhập trái phép giữa 2 đoạn nhớ nhờ vào 2 thanh ghi offset và base. Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 30 Chia sẻ phân đoạn: kỹ thuật phân đoạn có ưu điểm là khả năng chia sẻ với từng phần chương trình, các tiến trình có thể chia sẻ với nhau, với từng phần chương trình không nhất thiết phải chia sẻ toàn bộ chương trình như kỹ thuật phân trang. Phân đoạn có thể gây ra sự phân mảnh, khi tất cả khối bộ nhớ trống là quá nhỏ để chứa một phân đoạn. Thông thường, nếu kích thước phân đoạn trung bình là nhỏ, phân mảnh ngoài cũng sẽ nhỏ. Kỹ thuật phân đoạn chỉ áp dụng ở hệ điều hành đa nhiệm. Chi tiết: Bộ nhớ là trung tâm để điều hành hệ thống máy tính hiện đại. Bộ nhớ chứa một mảng lớn các từ (words) hay các bytes, mỗi phần tử với địa chỉ của chính nó. CPU lấy các chỉ thị từ bộ nhớ dựa theo giá trị của thanh đếm chương trình. Các chỉ thị này có thể gây việc nạp bổ sung các từ và lưu trữ tới các địa chỉ bộ nhớ xác định. Phân đoạn là một cơ chế quản lý bộ nhớ hỗ trợ tầm nhìn bộ nhớ của người dùng. Không gian địa chỉ logic là tập hợp các phân đoạn. Mỗi phân đoạn có tên và chiều dài. Các địa chỉ xác định tên phân đoạn và độ dời trong phân đoạn. Do đó, người dùng xác định mỗi địa chỉ bằng hai lượng: tên phân đoạn và độ dời. (tương phản cơ chế này với cơ chế phân trang, trong đó người dùng chỉ xác định một địa chỉ đơn, được chia bởi phần cứng thành số trang và độ dời, tất cả không thể nhìn thấy đối với người lập trình). Để đơn giản việc cài đặt, các phân đoạn được đánh số và được tham chiếu tới bởi số phân đoạn, hơn là bởi tên phân đoạn. Do đó, địa chỉ logic chứa một bộ hai: Thông thường, chương trình người dùng được biên dịch, và trình biên dịch tự động tạo ra các phân đoạn phản ánh chương trình nhập. Một trình biên dịch có thể tạo một phân đoạn riêng cho mỗi khối chung. Các mảng có thể được gán các phân đoạn riêng. Bộ nạp có thể mang tất cả phân đoạn này và gán chúng số phân đoạn. Mặc dù người dùng có thể tham chiếu tới các đối tượng trong chương trình bởi một địa chỉ hai chiều, bộ nhớ vật lý là chuỗi một chiều các byte. Do đó, chúng ta phải xác định việc cài đặt để ánh xạ địa chỉ hai chiều được định nghĩa bởi người dùng vào địa chỉ vật lý một chiều. Ánh xạ này được tác động bởi một bảng phân đoạn. Mỗi mục từ của bảng phân đoạn có một nền phân đoạn (segment base) và giới hạn phân đoạn (segment limit). Nền phân đoạn chứa địa chỉ vật lý bắt đầu, nơi phân đoạn định vị trong bộ nhớ, ngược lại giới hạn phân đoạn xác định chiều dài của phân đoạn. Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 31 Lược đồ chuyển đổi địa chỉ Sử dụng bảng phân đoạn được hiển thị như hình trên. Một địa chỉ logic có hai phần: số phân đoạn s và độ dời phân đoạn d. Số phân đoạn được dùng như chỉ mục trong bảng đoạn. Độ dời d của địa chỉ logic phải ở trong khoảng từ 0 tới giới hạn đoạn. Nếu không chúng ta sẽ trap tới hệ điều hành (địa chỉ vật lý vượt qua điểm cuối của phân đoạn). Nếu độ dời này là hợp lệ thì nó được cộng thêm giá trị nền của phân đoạn để tạo ra địa chỉ trong bộ nhớ vật lý của byte mong muốn. Do đó, bảng phân đoạn là một mảng của cặp thanh ghi nền và giới hạn. Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 32 Xét trường hợp như hình trên. Chúng ta có năm phân đoạn được đánh số từ 0 đến 4. Các phân đoạn được lưu trong bộ nhớ vật lý như được hiển thị. Bảng phân đoạn có một mục từ riêng cho mỗi phân đoạn, cho địa chỉ bắt đầu của phân đoạn trong bộ nhớ vật lý (hay nền) và chiều dài của phân đoạn đó (hay giới hạn). Thí dụ, phân đoạn 2 dài 400 bytes và bắt đầu tại vị trí 4300. Do đó, một tham chiếu byte 53 của phân đoạn 2 được ánh xạ tới vị trí 4300 + 53 = 4353. Một tham chiếu tới phân đoạn 3, byte 852, được ánh xạ tới 3200 (giá trị nền của phân đoạn 3) +852=4052. Một tham chiếu tới byte 1222 của phân đoạn 0 dẫn đến một trap tới hệ điều hành, khi phân đoạn này chỉ dài 1000 byte. Câu 19. Định nghĩa hệ điều hành. Lấy ví dụ thực tế để minh họa cho các đặc điểm trong định nghĩa. Trình bày sơ đồ phân lớp của hệ thống máy tính? Ý nghĩa của sự phân lớp? Trả lời Hệ điều hành: - Là một tập hợp các phần mềm hệ thống điều khiển mọi hoạt động của máy tính và tạo môi trường giao diện giữa người sử dụng và máy tính. - Là tài nguyên quản lý các tài nguyên khác. - Là trung gian điều khiển các chương trình ngăn ngừa lỗi và sự sử dụng không thích hợp. Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 33 - Làm trung gian giữa những mâu thuẫn về hiệu năng của tài nguyên và việc sử dụng một cách thuận tiện. Ví dụ: Trong một công ty các trưởng phòng là một hệ thống điều khiển mọi hoạt động của công ty và là trung gian giữa nhân viên làm việc và giám đốc công ty. - Các trưởng phòng quản lý các nhân viên trong công ty. - Các hoạt động hay công tác của nhân viên đều do người trưởng phòng quản lý và điều hành. Ngăn các lỗi hay các việc làm không đúng của nhân viên . - Làm trung gian giải quyết các vấn đề mâu thuẫn giữa người làm việc và công ty. Phân lớp của hệ thống máy tính: Gồm có 4 lớp: Phần cứng. Hệ điều hành. Các chương trình ứng dụng. Người sử dụng. Ý nghĩa của việc phân lớp: - Tạo ra môi trường làm việc thuận tiện cho người sử dụng, cho phép người sử dụng đưa ra các lệnh điều khiển hoạt động của hệ thống. - Tạo môi trường hoạt động cho các chương trình ứng dụng bằng các hệ điều hành. - Quản lý các tài nguyên hệ thống một cách hiệu quả và khai thác được hết các khả năng của các thiết bị, cung cấp cho người dùng tài nguyên của phần cứng khi có yêu cầu. Câu 20: dead . Phần cứng. Hệ điều hành Các chương trình ứng dụng. Người sử dụng Người sử dụng Người sử dụng Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 34 Trả lời: : . . : - . . - . L . . . /O. : : ) = 12; . - Bây giờ chúng ta xem giao thức sau để ngăn chặn deadlock: mỗi quá trình có thể yêu cầu tài nguyên chỉ trong thứ tự tăng của số lượng. Nghĩa là, một quá trình ban đầu có thể yêu cầu bất cứ số lượng thể hiện của một loại tài nguyên Ri. Sau đó, một quá trình có thể yêu cầu các thể hiện của loại tài nguyên Rj nếu và chỉ nếu F(Rj) > F(Ri). Nếu một số thể hiện của cùng loại tài nguyên được yêu cầu, thì một yêu cầu cho tất cả thể hiện phải được cấp phát. Thí dụ, sử dụng hàm được định nghĩa trước đó, một quá trình muốn dùng ổ băng từ và máy in tại cùng một lúc trước tiên phải yêu cầu ổ băng từ và sau đó yêu cầu máy in. - Nói một cách khác, chúng ta yêu cầu rằng, bất cứ khi nào một quá trình yêu cầu một thể hiện của loại tài nguyên Rj, nó giải phóng bất cứ tài nguyên Ri sao cho F(Ri) ≥F(Rj). Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 35 - Nếu có hai giao thức được dùng thì điều kiện tồn tại chu trình không thể xảy ra. - Chúng ta có thể giải thích điều này bằng cách cho rằng tồn tại chu trình trong đồ thị cấp phát tài nguyên tồn tại. Gọi tập hợp các quá trình chứa tồn tại chu trình trong đồ thị cấp phát tài nguyên là {P0, P1, … , Pn}, ở đây Pi đang chờ một tài nguyên Ri, mà Ri được giữ bởi quá trình Pi+1. Vì sau đó quá trình Pi+1 đang giữ tài nguyên Ri trong khi yêu cầu tài nguyên Ri+1, nên chúng ta có F(Ri) < F(Ri+1) cho tất cả i. Nhưng điều kiện này có nghĩa là F(R0) < F(R1) < …< F(Rn) < F(R0). Bằng qui tắc bắt cầu F(R0) < F(R0), điều này là không thể. Do đó, không thể có chờ chu trình. Chú ý rằng hàm F nên được định nghĩa dựa theo thứ tự tự nhiên của việc sử dụng tài nguyên trong hệ thống. Thí dụ, vì ổ băng từ thường được yêu cầu trước máy min nên có thể hợp lý để định nghĩa F( ổ băng từ) < F(máy in). sử dụng thiết bị chậm và thông lượng hệ thống bị giảm Một phương pháp khác để tránh deadlock là yêu cầu thông tin bổ sung về cách tài nguyên được yêu cầu. Thí dụ, trong một hệ thống với một ổ băng từ và một máy in, chúng ta có thể bảo rằng quá trình P sẽ yêu cầu ổ băng từ trước và sau đó máy in trước khi giải phóng cả hai tài nguyên. Trái lại, quá trình Q sẽ yêu cầu máy in trước và sau đó ổ băng từ. Với kiến thức về thứ tự hoàn thành của yêu cầu và giải phóng cho mỗi quá trình, chúng ta có thể quyết định cho mỗi yêu cầu của quá trình sẽ chờ hay không. Mỗi yêu cầu đòi hỏi hệ thống xem tài nguyên hiện có, tài nguyên hiện được cấp tới mỗi quá trình, và các yêu cầu và giải phóng tương lai của mỗi quá trình, để yêu cầu của quá trình hiện tại có thể được thoả mãn hay phải chờ để tránh khả năng xảy ra deadlock. Câu 21. ? . Trả lời Trạng thái an toàn của hệ thống tại một thời điểm nếu dãy tiến trình song hành tại thời điểm đó có thể được sắp xếp thành một dãy an toàn. Một trạng thái an toàn là một trạng thái không có bế tắc( deadlock). Cách điều khiển phân phối tài nguyên cho một dãy an toàn: Một dãy P1, P2, …, Pn là một dãy an toàn nếu với mọi tiến trình Pi, tài nguyên mà Pi cần có thể được thỏa mãn bởi tài nguyên của hệ thống. Tài nguyên mà Pi đòi hỏi có thể thỏa mãn bởi tài nguyên còn tự do và tài nguyên bị giữ bởi Pj với j>i. - Nếu Pi không có tài nguyên ngay tức thì Pi có thể chờ cho đến khi các Pj kết thúc. - Khi Pj kết thúc thì Pi thu được tài nguyên mà nó cần, thực hiện và khi kết thúc sẽ trả lại tài nguyên cho hệ thống. - Khi Pi kết thúc thì tiến trình Pi+1 sẽ được thu được tài nguyên mà nó cần. Ví dụ: Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 36 Cho dãy hệ thống gồm có 12 ổ băng trong đó Tiến trình yêu cầu hiện có P0 10 5 P1 4 2 P2 9 2 Khi đó hệ thống còn là 3 ổ băng nó sẽ phân cho tiến trình P1 thêm 2 ổ băng. Sau khi thực hiện xong tiến trình P1 thì có 5 ổ băng tự do. Khi đó tiến trình P0 sẽ được thực hiện vì có đủ tài nguyên cần thiết.. Sau đó tiến trình P2 sẽ được thực hiện. Câu 22. ? Trả lời Deadlock là quá trình yêu cầu tài nguyên không sẵn dùng tại thời điểm đó.quá trình vào trạng thái chờ.Quá trình chờ có thể không chuyển trạng thái trở lại vì tài nguyên chúng yêu cầu bị giữ bởi những quá trình đang chờ khác.Trường hợp này gọi là deadlock Phương phát điều khiển khoá chết : - Ngăn ngừa - Thoát khỏi - Phát hiện - Khôi phục - Tổ hợp các biện pháp Trạng thái an toàn: nếu hệ thống có thể cấp phát tài nguyên tới mỗi tiến trình trong một thứ tự và vẫn tránh deadlock Hệ thống ở trạng thái an toàn nếu nó tồn tại dãy an toàn của tất cả các tiến trình Dãy là an toàn nếu mỗi pi các tài nguyên mà vẫn đòi hỏi có thể thoả mãn bởi tài nguyên tự do và tài nguyên bị giữ bởi bởi tất cả các pj,với j<i : pi chờ,nhận ,kết thúc(trả) Trình bày giải thuật kiểm tra sự an toàn của hệ thống: Ta di tìm hiểu 3 giải thuật dẫn đén sự an toàn hê thống Giải thuật về phân phối tài nguyên Giải thuật ông chủ nhà hàng Giải thuật an toàn 1:Giải thuật đồ thị phân phối tài nguyên: - pi→rj:cung mong muốn - rj→pi:cung yêu cầu - tài nguyên được báo trước trong yêu cầu hệ thống 2:giải thuật ông chủ ngân hàng : - tiến trình báo trước nhu cầu tối đa về tài nguyên - tiến trình yêu cầu có thể phải chờ - tiến trình lấy được tài nguyên trả lại chúng ngay khi kết thúc *AVAILABLE:vecto độ dài m availlable[j]=k có đơn vị thuộc về kiểu tài nguyên còn được tự do.Vi dụ availlable[j]=5 Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 37 *MAX:ma trận n*m.nếu MAX[ i,j]=k:tiến trình yêu cầu k đơn vị thuộc kiểu tài nguyên j *ALLOCATION:ma trận n*m.nếu ALLOCATION[ i,j]=k tức là tiến trình nhiều nhất là k đơn vị thuộc kiểu tài nguyên rj NEED:ma trận n*m.Nếu NEED[ i,j]=k túc la tiến trình cần k đơn vị cua rj NEED[ i,j]=MAX[ i,j]-ALLOCATION[ i,j] 3:Giải thuật an toàn: B1:đặt Work và Finish là các vecto lần lượt có độ dài m,n.Khởi động Work= AVAILABLE Finish[i]=false với i=1,2,3,…,n B2: tìm pi thỏa mãn cả hai điều kiện: Finish[i]=false Needi≤Work Nếu không tìm thấy i chuyển tới B4 B3:Work=Work+ALLOCATION Finish[i]=true Chuyển sang B2 B4 :Nếu Finish[i]=true với mọi i,thì hệ thống trong trạng thái an toàn Ví dụ:cho tiến trình từ p0 dên p4 co 3 kiểu tài nguyên A(10 đơn vị), B(5 đơn vị),C(3 đơn vị) Trạng thái tại thời điểm T0 ALLOCATION MAX AVAILABLE A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 2 1 2 2 2 P4 0 0 2 4 3 3 Ma trận NEED :NEED[ i,j]=MAX[ i,j]-ALLOCATION[ i,j] NEED A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 Hệ thống trong trạng thái an toàn nếu xuất hiện dãy thỏa mãn tính chất an toàn vì Need p0>Work→chuyển sang tiến trình p1 Need p1<Work→ tiến trìnhp1 thực hiện rồi trả lại tài nguyên cho tiến trình tiếp theo p2 (chuyển sang b3 ) Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 38 Need p2>Work=Work+ALLOCATION1 →chuyển sang tiến trình p3.p2 chưa thực hiện Need p3<Work=Work+ALLOCATION1 tiến trình p3 hiện rồi trả lại tài nguyên cho tiến trình tiếp theo p4 (chuyển sang b3 ) Need p4 < Work=Work+ALLOCATION3 tiến trình p4 hiện rồi trả lại tài nguyên cho tiến trình tiếp theo p0 (chuyển sang b3 ) Need p0>Work=Work+ALLOCATION4 →chuyển sang tiến trình p2 Need p2<Work=Work+ALLOCATION4 tiến trình p2 hiện rồi trả lại tài nguyên cho tiến trình tiếp theo p0 (chuyển sang b3 ).Cuối cùng p0 thực hiện Câu 23: Trình bày giải thuật “ông chủ ngân hàng “ về phân phối tài nguyên của hệ thống? Cho ví dụ minh họa. Trả lời Cài đặt giải thuật : - N = số tiến trình ( nút p1->pn) - M = số kiểu tài nguyên hệ thống ( r1->rm) Ta xây dựng CTDL như sau: - Available : mảng 1 chiều có m phần tử -> gọi là 1 vecto có độ dài m. - Available [j] = k ,tức là kiểu tài nguyên Rj có k đơn vị còn tự do. - Max: Ma trận n*m. Nếu Max [i,j] = k , tức là tiến trình Pi cần tối đa k đơn vị của tài nguyên Rj. Allocation: Ma trận n*m . Nếu Allocation [i,j] = k, tức là tiến trình Pi đã được cấp k tài nguyên Rj . Need: Ma trận n*m. Nếu Need [i,j] = k, tức là tiến trình Pi còn cần thêm k đơn vị của Rj để hoàn thành nhiệm vụ. Need [i,j] = Max [i,j] - Allocation [i,j]. Ví dụ: 5 tiến trình từ P0->P4; 3 kiểu tài nguyên A(10 đơn vị), B(5 đơn vị), C(7đơn vị). Trạng thái tại thời điểm T0: Tiến trình Allocation Max Available Need ABC ABC ABC ABC P0 010 753 332 743 P1 200 322 122 P2 302 902 600 P3 221 222 011 P4 002 433 431 Giải thích Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 39 Tại tiến trình P0 ta có: Available ABC 332 Available :Tức là cái trong kho có RA=3; RB=3; RC=2; Max ABC 753 Max: yêu cầu tối đa .Có Max[0,A]=7, Max[0,B]=5, Max[0,C]=3; Allocation ABC 010 Allocation: cái được cấp phát . Tại thời điểm P0 : A,C không được cấp phát ,B được cấp phát Allocation[0,B] = 1=> cái còn cần là: Need [i,j] = Max [i,j] - Allocation [i,j]. Need ABC 743 Làm tương tự đối với P1,P2,P3,P4 ta sẽ được kết quả như ở cột 5. Minh họa: Một ông chủ ngân hàng X ,ông ta có 10 tỉ đồng. Tại 1 thời điểm nào đó có 1 đối tượng Y tới vay tiền, yêu cầu tối đa là Y được vay 5 tỉ, nhưng ngân hàng mới cấp cho ông ta được 3 tỉ. Vậy là số tiền ông ta còn cần là : Need = 5 – 3 = 2 (tỉ). Câu 24:Trình bày giải thuật phát hiện khóa chết? ví dụ minh họa. Trả lời: Giải thuật phát hiện khóa chết: Ta có: A là một vecto có độ dài m xác định số tài nguyên có thể sử dụng. B là một ma trận nx m xác định số tài nguyên đã phân bố cho các tiến trình. R là một ma trận nx m xác định các yêu cầu hiện tại của mỗi tiến trình.  Bước 1: đặt w, f là các vecto có độ dài m, n lần w= A. for i=1, 2, 3, …, n. if B ≠0 then f[i] = false else f[i] = true. Đề cương Nguyên lý Hệ điều hành K57C – CNTT wWw.K57C.cOm 40  Bước 2: tìm một chỉ số I thỏa mã 2 điều kiện sau: f[ i] =false. R≤ w. Nếu không tìm thấy, chuyển đến bước 4.  Bước 3: w:= w + B(i) f( i):= true chuyển đến bước 2.  Bước 4: nếu f[ i] = false thì hệ thống bế tắc. Ví dụ: Cho 3 tiến trình và 2 kiểu tài nguyên ở trạng thái sau: Process B R A D E D E D E P0 3 0 7 0 3 3 P1 2 1 9 2 P2 2 1 2 5