Nguyên tắc thay thế trang địa phương (local replacement) là gì?
HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
III.1. Giới thiệu chung
Nắm lại được một số khái niêm căn bản Hiểu nguyên tắc cấp phát tổ chức quản lý khác nhau bộ nhớ trong, Hiểu cách tiếp cận quản lý bộ phân trang, phân đoạn và các thuật toán cấp phát bộ nhớ liên tục cho các tiến trình
III.1.1 Các khái niệm cơ bản
III.1.2. Hoán chuyển (Swapping) Phủ lắp cho phép nạp một tiến trình lớn hơn dung lượng bộ nhớ cấp phát cho nó bới một phần của tiến trình nằm ở bộ nhớ ngoài, hoán chuyển thì cho phép chuyển một tiến trình đã được cấp phát bộ nhớ xếp tạm ra bộ nhớ ngoài để giải phóng bộ nhớ nạp tiến trình khác. HĐH sẽ dùng một vùng nhớ ngoài nhanh nhất thường là đĩa cứng và gọi là Backing Store. Tiến trình hoán chuyển ra là tiến trình đang không được thực thi.
III.1.3. Cấp phát bộ nhớ (Memory Allocation) Bộ nhớ trong thường được chia thành 2 vùng riêng biệt, một cho HĐH và một cho các tiến trình.
Mỗi tiến trình chỉ được cấp một vùng nhớ và tuần tự. Bộ nhớ vì vậy được chia thành các vùng. Vùng nhớ được cấp phát có thể bằng nhưng cũng có thể lớn hơn so với nhu cầu của tiến trình. Phân vùng cố định hoặc phân vùng động.
Mỗi tiến trình sẽ được cấp nhiều hơn một vùng nhớ và không liền nhau. Bộ nhớ trong được chia thành các vùng có độ lớn bằng nhau (gọi là trang mà thực chất là khung trang), cũng có thể thành các độan có độ lớn khác nhau. Tiến trình được cấp một số các khung trang và/hoặc các đoạn đó. III.1.4. Phân mảnh (Fragmantation) Hiện tượng phân mảnh là có không gian nhớ rảnh chưa cấp phát cho tiến trình nào nhưng không thể cấp cho tiến trình mặc dù tổng dung lượng không gian nhớ rảnh này lớn hơn nhu cầu cần cấp phát cho tiến trình.
HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
III.2. Cấp phát bộ nhớ liên tục (Contigous Allocation)
Hiểu nguyên tắc tổ chức và cấp phát lien tục bộ nhớ trong, Nắm được, hướng tới viết chương trình dựa trên các thuật toán cấp phát bộ nhớ liên tục cho các tiến trình
Cấp phát bộ nhớ liên tục (Contigous Memory Allocation) Cấp phát liên tục tức là cấp cho tiến trình vùng nhớ có địa chỉ liền nhau. III.2.1. Phân vùng cố định (Fixed Partistioning) Chia bộ nhớ chính thành nhiều phần không trùng lấp gọi là các phân hoạch có kích thước bằng nhau hoặc khác nhau. Tiến trình nào có kích thước nhỏ hơn hoặc bằng kích thước của một phân họach thì có thể nạp vào phân hoạch đó. Nếu chương trình có kích thước lớn hơn một phân hoạch thì phải dùng cơ chế phủ lấp (overlay). Nếu tất cả các phân hoạch đều đã đầy thì hệ điều hành sẽ tiến hành hoán chuyển (swap) các tiến trình. III.2.2. Phân vùng động (Dynamic Partistioning) Số lượng phân hoạch (partition) không cố định và phân hoạch có kích thước khác nhau, độ lớn quyết định bởi dung lượng tiến trình. Mỗi tiến trình được cấp phát chính xác dung lượng bộ nhớ cần thiết. Chúng ta sẽ nghiên cứu kỹ hơn thuật toán cấp phát bộ nhớ ở mục phía sau. III.2.3. Cấp phát bộ nhớ phân vùng động (Dynamic Partition Allocation) Tiến trình được cấp phát không gian nhớ liên tục và đúng bằng dung lượng yêu cầu. Sau một khoảng thời gian các tiến trình của hệ thống được kích hoạt rồi kết thúc, bộ nhớ trong của máy sẽ xuất hiện các vùng nhớ rảnh (rỗng) bên cạnh các phân hoạch được chiếm dụng bởi các tiến trình khác nhau. Các khoảng trống chưa bị chiếm dụng đó gọi là hole, vấn đề đặt ra là sẽ cấp cho tiến trình mới vào hole nào trong số đó. Hole dùng để cấp phát phải có dung lượng bằng hoặc lớn hơn nhu cầu của tiến trình.
Chọn vùng nhớ trống lớn nhất nhưng đủ lớn Nếu không còn vùng nhớ trống đủ lớn?
Bài 1. Máy tính sử dụng partition để quản lí bộ nhớ, và tại một thời điểm bộ nhớ vật lí của máy đang được sử dụng như sau: 1,5M rỗng, 0.5M P1, 0.5M rỗng, 1.2M P2, 1.6M rỗng, 1.0M P3, 1.2M rỗng, 1.8M P4, 1.7M rỗng, 2.6M P5, 3.5M rỗng. Các tiến trình mới xuất hiện và kết thúc theo thứ tự sau: P6: 1.1M, P7: 1.5M, P4 kết thúc, P8: 1.7M, P9: 1.3M, P2 kết thúc, P10: 1.7M, P11: 1,2M, P1 kết thúc, P12: 0.9M, P6 kết thuc. Hãy giải thích và vẽ sơ đồ bộ nhớ vật lí ứng với các thuật toán cấp phát bộ nhớ chính (First Fit, Best Fit và Worst Fit) sau khi tiến trình P6 kết thúc: First Fit, Best Fit, Worst Fit Bài 2: Máy tính sử dụng partition để quản lí bộ nhớ, và tại một thời điểm bộ nhớ vật lí của máy đang được sử dụng như sau: 1,1M rỗng, 0.5M P1, 0.8M rỗng, 1.2M P2, 0.6M rỗng, 1.0M P3, 1.2M rỗng, 1.1M P4, 1.1M rỗng, 1.2M P5, 2.5M rỗng. Các tiến trình mới xuất hiện và kết thúc theo thứ tự sau: P6: 0.6M, P7: 1.5M, P4 kết thúc, P8: 0.7M, P9: 1.3M, P2 kết thúc, P10: 1.1M, P11: 0,5M, P1 kết thúc, P12: 0.9M, P6 kết thuc. Hãy giải thích và vẽ sơ đồ bộ nhớ vật lí ứng với các thuật toán cấp phát bộ nhớ chính (First Fit, Best Fit và Worst Fit) sau khi tiến trình P6 kết thúc: First Fit, Best Fit, Worst Fit
HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
III.3. Cấp phát bộ nhớ không liên tục (None-contigous Allocation)
III.3.1. Phân trang (Paging) Kỹ thuật phân trang sẽ cho phép không gian địa chỉ vật lý cấp cho một tiến trình không cần phải là liên tục.
III.3.2. Phân đoạn (Segmentation) Trong thực tế, dưới góc nhìn của người sử dụng, một chương trình cấu thành từ nhiều phân đoạn (segment). Mỗi phân đoạn là một đơn vị logic như: main program, procedure, function, local variables, global variables, stack, symbol table, … Kỹ thuật phân đoạn: Chia không gian địa chỉ ảo thành một tập các phân đoạn (segment), mỗi phân đoạn có tên và kích thước riêng. Một địa chỉ logic được định vị bằng tên phân đoạn và độ dời (offset) bên trong phân đoạn đó. Khác với phân trang khi mà độ lớn trang là bằng nhau thì đọ lớn mỗi đoạn không bắt buộc điều này. Địa chỉ logic là một cặp giá trị: base – chứa địa chỉ khởi đầu của phân đoạn trong bộ nhớ limit – xác định kích thước của phân đoạn
III.3.3. Phân đoạn kết hợp với phân trang. Phân trang và phân đoạn có điểm chung và điểm riêng; phân trang và phân đoạn có ưu và nhược điểm khác nhau. Có thể kết hợp đồng thời phân trang với phân đoạn khi mà một đoạn có thể được phân thành các trang.
HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
III.4. Bộ nhớ ảo
Hiểu được kỹ thuật bộ nhớ ảo, mục đích và ý nghĩa việc ứng dụng kỹ thuật bộ nhớ ảo; Đồng thời nắm được các thuật toán xử lý lỗi trang, hướng tới lập trình mô phỏng các thuật toán này.
III.4.1. Khái niệm chung (Background):
III.4.2. Phân trang theo yêu cầu (Demand Paging):
III.4.3. Thay thế trang (Page Replacement) hay Xử lý lỗi trang Khi xảy ra page fault, hệ điều hành thực hiện các bước sau
III.4.3.1. Thuật toán FIFO vào trước ra trước (First In First out) Chọn trang swap out là trang đã được swap in đầu tiên (trong số nhứng trang đang nằm trong bộ nhớ cơ sở) Nêu ví dụ với bài toán cấp 3 khung trang và bài toán cấp 4 khung trang, tính số lỗi trang III.4.3.2. Thuật toán tối ưu OPT (Optimal Replacement) Nhằm hạn chế tối đa lỗi trang, sẽ tìm trang để thay thế là trang lâu được thực hiện nhất tức là để lại những trang sắp được thực hiện. (Thảo luận tính khả thi) Nêu ví dụ bài toán cấp phát mỗi tiến trình 4 khung trang, tính số lỗi trang III.4.3.3. Thuật toán lâu nhất chưa sử dụng LRU (Least Recently Used) Thay thế trang nằm trong bộ nhớ nhưng đã lâu nhất chưa được sử dụng/ thực hiện. Nêu ví dụ với bài toán cấp cho tiến trình 4 khung trang, tính số lỗi trang.
Bài 1. Trong các hệ thống áp dụng kỹ thuật Bộ nhớ ảo, mỗi tiến trình được cấp phát hạn chế số lượng “khung trang” trong khi số lượng trang thực tế tiến trình yêu cầu có thể nhiều hơn nhiều. Hãy giải thích ngắn gọn các thuật toán “Thay thế trang” và tính số lượng lỗi trang với mỗi thuật toán tương ứng đối với Tiến trình có yêu cầu truy nhập theo trình tự các trang sau: 1, 2, 3, 7, 8, 2, 2, 4, 5, 7, 1, 2, 3, 7, 8, 4, 1, 5, 6, 7,1 với trường hợp số lượng khung trang được cấp là 4. Bài 2. Trong các hệ thống áp dụng kỹ thuật Bộ nhớ ảo, mỗi tiến trình được cấp phát hạn chế số lượng “khung trang” trong khi số lượng trang thực tế tiến trình yêu cầu có thể nhiều hơn nhiều. Hãy giải thích ngắn gọn các thuật toán “Thay thế trang” và tính số lượng lỗi trang với mỗi thuật toán tương ứng đối với Tiến trình có yêu cầu truy nhập theo trình tự các trang sau: 1, 2, 3, 5, 7, 8, 4 , 2, 3, 4, 7, 4, 2, 3, 8, 4, 8, 5, 6, 7, 1 với trường hợp số khung trang được cấp là 4.
Chia sẻ với bạn bè của bạn:
Page 2
HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
II.1. Tiến trình
II.1.1. Khái niệm, định nghĩa tiến trình (Process). Tiến trình là một chương trình hoặc một phần của chương trình đã được nạp vào bộ nhớ chính, đang trong quá trình thực hiện (nhưng không nhất thiết là luôn luôn được cấp CPU). Chương trình là thực thể thụ động, tiến trình là thực thể chủ động của chương trình và có thời gian sống nhất định (life cycle). Trong một số tài liệu tiếng Anh có sử dụng khái niệm job hay task: công việc hay chức năng, có thể hiểu là tiến trình giống như process, và một số tài liệu tiếng Việt dịch process là quá trình. II.1.2. Các trạng thái của tiến trình
II.1.3. Khối điều khiển tiến trinh PCB (Process Control Block) Mỗi một tiến trình được quản lý trong HĐH bởi một PCB. Khối điều khiển tiến trình là một cấu trúc dữ liệu gồm các thông tin quan trọng sau: 1. Danh định cho tiến trình (PID) 2. Trạng thái của tiến trình 3. Bộ đếm chương trình – chứa địa chỉ của lệnh tiếp theo 4. Vùng lưu giá trị thanh ghi CPU 5. Độ ưu tiên của tiến trình 6. Thông tin định vị bộ nhớ tiến trình 7. Thông tin bảo mật 8. Con trỏ đến các tiến trình cha, con 9.Bộ vi xử lý mà tiến trình đang sử dụng (trong các hệ đa bộ xử lý) 10. Danh sách các tài nguyên mà tiến trình đang sử dụng II.1.4. Mô hình tiến trình, các loại tiến trình (Process Models) Các hệ thống khác nhau có thể tổ chức để các tiến trình có thể thực thi tuần tự hoặc song hành. Ở hệ thống các tiến trình song hành có thể chia làm nhiều dạng (mô hình) khác nhau:
II.1.5. Chuyển CPU giữa các tiến trình (Context Switch) Giả sử có 2 tiến trình P0, P1. P0 đang chạy thì xuất hiện ngắt và P0 dừng lại, khi đó toàn bộ thông tin về P0 từ các thanh ghi được ghi ra thực thể PCB0 trong bộ nhớ chính. Sau đó các thông tin của P1 từ PCB1 trong bộ nhớ chính được nạp vào các thanh ghi và thực thi P1…. II.1.6. Lập thời biểu tiến trình (Process Scheduling) Trong hệ thống có nhiều tiến trình song hành, các tiến trình chuyển từ trạng thái này sang trạng thái khác và CPU chuyển từ việc cấp cho tiến trình này sang tiến trình khác. CPU tại một thời điểm cụ thể chỉ có thể thực hiện một chỉ lệnh của một tiến trình, vì vậy các tiến trình khác sẽ phải chờ trong các hang đợi khác nhau.
HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
II.2. Luồng (Thread)
II.2.1 Khái niệm Luồng hay còn được sử dụng với khái niệm tiểu trình hay thiết trình. Luồng được xem như một phiên bản đơn giản của tiến trình mà đã được bỏ đi nhiều đặc tính. Truyền thống, một tiến trình sẽ có một luồng thực hiện công việc. Nhưng một tiến trình có thể chứa đựng nhiều luồng. Một tiến trình bao gồm: thread id, program counter, tập thanh ghi register, và một ngăn xếp stack. Luồng sẽ chia sẻ với các luồng trong cùng một tiến trình phần mã (code ssection), phần dữ liệu (data section), và các tài nguyên của HĐH mà được dùng bởi tiến trình. II.2.2. Lợi ích của việc sử dụng luồng
Tiến trình đa luồng (multithreaded process) là tiến trình thực thi trong nhiều luồng. Các thread trong cùng một process chia sẻ code section, data section và tài nguyên khác (các file đang mở,...) của process. II.2.3. Các mô hình đa luồng:
HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
II.3. Lập lich cho CPU (CPU Scheduling)
Nắm được các khái niệm liên quan tới lập lịch bao gồm lập licgh cho CPU, nắm sâu hơn vấn đề song hành của các tiến trình và việc thực hiện chúng. Hiểu và vận dụng được các thuật toán lập lịch cho CPU, hướng tới viết được các modul chương trình quản lý cấp phát CPU
II.3.1. Các khái niệm cơ bản (Basic Concepts)
II.3.2. Các tiêu chí lập lịch Đánh giá bộ lập lích dựa trên các tiêu chí trung dưới đây; với các hệ thống và yêu cầu khác nhau các tiêu chí có thể đóng vai trò quan trọng khác nhau:
II.2.3. Các thuật toán định thời (Scheduling Algorythms) Thuật toán định thời áp dụng để chọn tiến trình đang trongb hàng đợi sẵn sang để cấp CPU
Đây là giải thuật đơn giản nhất khi mà tiến trình nào vào hàng đợi sẵn sang trước sẽ được lựa chọn phục vụ trước tức là được chọn để cấp CPU. Thuật toán này sẽ cấp CPU cho tiến trình cho đến khi CPU được giải phỏng, như vậy FCFS là định thời không trưng dụng hay định thời tự nguyện.
Trong thực tế các HĐH có thể kết hợp, lồng ghép các thuật toán trên hay các giải thuạt phát triển từ các thuật toán trên như định thời với hàng đợi nhiều cấp, định thời hàng đợi phản hồi đa cấp. Đánh giá các giải thuật
Câu 1: Có các tiến trình P0, P1, P2, P3, P4 và P5 đã đang sẵn sàng chờ được cấp phát CPU. Đánh giá các thuật toán lựa chọn tiến trình để cấp phát (thuật toán lập lịch cho CPU). Các tiến trình có thời gian cần CPU (CPU burst time) và có thời gian đến (vào hàng đợi Ready) được cho trong bảng dưới đây:
Đối với mô hình Time-sharing, Quantum time hay Time slice = 10ms Câu 2: Có các tiến trình P0, P1, P2, P3, P4 và P5 đã đang sẵn sàng chờ được cấp phát CPU. Đánh giá các thuật toán lựa chọn tiến trình để cấp phát (thuật toán lập lịch cho CPU). Các tiến trình có thời gian cần CPU (CPU burst time) và có thời gian đến (vào hàng đợi Ready) được cho trong bảng dưới đây:
. HỌC VIỆN KỸ THẬT QUÂN SỰKHOA CÔNG NGHỆ THÔNG TIN Page 3HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
III.1. Giới thiệu chung
Nắm lại được một số khái niêm căn bản Hiểu nguyên tắc cấp phát tổ chức quản lý khác nhau bộ nhớ trong, Hiểu cách tiếp cận quản lý bộ phân trang, phân đoạn và các thuật toán cấp phát bộ nhớ liên tục cho các tiến trình
III.1.1 Các khái niệm cơ bản
III.1.2. Hoán chuyển (Swapping) Phủ lắp cho phép nạp một tiến trình lớn hơn dung lượng bộ nhớ cấp phát cho nó bới một phần của tiến trình nằm ở bộ nhớ ngoài, hoán chuyển thì cho phép chuyển một tiến trình đã được cấp phát bộ nhớ xếp tạm ra bộ nhớ ngoài để giải phóng bộ nhớ nạp tiến trình khác. HĐH sẽ dùng một vùng nhớ ngoài nhanh nhất thường là đĩa cứng và gọi là Backing Store. Tiến trình hoán chuyển ra là tiến trình đang không được thực thi.
III.1.3. Cấp phát bộ nhớ (Memory Allocation) Bộ nhớ trong thường được chia thành 2 vùng riêng biệt, một cho HĐH và một cho các tiến trình.
Mỗi tiến trình chỉ được cấp một vùng nhớ và tuần tự. Bộ nhớ vì vậy được chia thành các vùng. Vùng nhớ được cấp phát có thể bằng nhưng cũng có thể lớn hơn so với nhu cầu của tiến trình. Phân vùng cố định hoặc phân vùng động.
Mỗi tiến trình sẽ được cấp nhiều hơn một vùng nhớ và không liền nhau. Bộ nhớ trong được chia thành các vùng có độ lớn bằng nhau (gọi là trang mà thực chất là khung trang), cũng có thể thành các độan có độ lớn khác nhau. Tiến trình được cấp một số các khung trang và/hoặc các đoạn đó. III.1.4. Phân mảnh (Fragmantation) Hiện tượng phân mảnh là có không gian nhớ rảnh chưa cấp phát cho tiến trình nào nhưng không thể cấp cho tiến trình mặc dù tổng dung lượng không gian nhớ rảnh này lớn hơn nhu cầu cần cấp phát cho tiến trình.
HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
III.2. Cấp phát bộ nhớ liên tục (Contigous Allocation)
Hiểu nguyên tắc tổ chức và cấp phát lien tục bộ nhớ trong, Nắm được, hướng tới viết chương trình dựa trên các thuật toán cấp phát bộ nhớ liên tục cho các tiến trình
Cấp phát bộ nhớ liên tục (Contigous Memory Allocation) Cấp phát liên tục tức là cấp cho tiến trình vùng nhớ có địa chỉ liền nhau. III.2.1. Phân vùng cố định (Fixed Partistioning) Chia bộ nhớ chính thành nhiều phần không trùng lấp gọi là các phân hoạch có kích thước bằng nhau hoặc khác nhau. Tiến trình nào có kích thước nhỏ hơn hoặc bằng kích thước của một phân họach thì có thể nạp vào phân hoạch đó. Nếu chương trình có kích thước lớn hơn một phân hoạch thì phải dùng cơ chế phủ lấp (overlay). Nếu tất cả các phân hoạch đều đã đầy thì hệ điều hành sẽ tiến hành hoán chuyển (swap) các tiến trình. III.2.2. Phân vùng động (Dynamic Partistioning) Số lượng phân hoạch (partition) không cố định và phân hoạch có kích thước khác nhau, độ lớn quyết định bởi dung lượng tiến trình. Mỗi tiến trình được cấp phát chính xác dung lượng bộ nhớ cần thiết. Chúng ta sẽ nghiên cứu kỹ hơn thuật toán cấp phát bộ nhớ ở mục phía sau. III.2.3. Cấp phát bộ nhớ phân vùng động (Dynamic Partition Allocation) Tiến trình được cấp phát không gian nhớ liên tục và đúng bằng dung lượng yêu cầu. Sau một khoảng thời gian các tiến trình của hệ thống được kích hoạt rồi kết thúc, bộ nhớ trong của máy sẽ xuất hiện các vùng nhớ rảnh (rỗng) bên cạnh các phân hoạch được chiếm dụng bởi các tiến trình khác nhau. Các khoảng trống chưa bị chiếm dụng đó gọi là hole, vấn đề đặt ra là sẽ cấp cho tiến trình mới vào hole nào trong số đó. Hole dùng để cấp phát phải có dung lượng bằng hoặc lớn hơn nhu cầu của tiến trình.
Chọn vùng nhớ trống lớn nhất nhưng đủ lớn Nếu không còn vùng nhớ trống đủ lớn?
Bài 1. Máy tính sử dụng partition để quản lí bộ nhớ, và tại một thời điểm bộ nhớ vật lí của máy đang được sử dụng như sau: 1,5M rỗng, 0.5M P1, 0.5M rỗng, 1.2M P2, 1.6M rỗng, 1.0M P3, 1.2M rỗng, 1.8M P4, 1.7M rỗng, 2.6M P5, 3.5M rỗng. Các tiến trình mới xuất hiện và kết thúc theo thứ tự sau: P6: 1.1M, P7: 1.5M, P4 kết thúc, P8: 1.7M, P9: 1.3M, P2 kết thúc, P10: 1.7M, P11: 1,2M, P1 kết thúc, P12: 0.9M, P6 kết thuc. Hãy giải thích và vẽ sơ đồ bộ nhớ vật lí ứng với các thuật toán cấp phát bộ nhớ chính (First Fit, Best Fit và Worst Fit) sau khi tiến trình P6 kết thúc: First Fit, Best Fit, Worst Fit Bài 2: Máy tính sử dụng partition để quản lí bộ nhớ, và tại một thời điểm bộ nhớ vật lí của máy đang được sử dụng như sau: 1,1M rỗng, 0.5M P1, 0.8M rỗng, 1.2M P2, 0.6M rỗng, 1.0M P3, 1.2M rỗng, 1.1M P4, 1.1M rỗng, 1.2M P5, 2.5M rỗng. Các tiến trình mới xuất hiện và kết thúc theo thứ tự sau: P6: 0.6M, P7: 1.5M, P4 kết thúc, P8: 0.7M, P9: 1.3M, P2 kết thúc, P10: 1.1M, P11: 0,5M, P1 kết thúc, P12: 0.9M, P6 kết thuc. Hãy giải thích và vẽ sơ đồ bộ nhớ vật lí ứng với các thuật toán cấp phát bộ nhớ chính (First Fit, Best Fit và Worst Fit) sau khi tiến trình P6 kết thúc: First Fit, Best Fit, Worst Fit
HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
III.3. Cấp phát bộ nhớ không liên tục (None-contigous Allocation)
III.3.1. Phân trang (Paging) Kỹ thuật phân trang sẽ cho phép không gian địa chỉ vật lý cấp cho một tiến trình không cần phải là liên tục.
III.3.2. Phân đoạn (Segmentation) Trong thực tế, dưới góc nhìn của người sử dụng, một chương trình cấu thành từ nhiều phân đoạn (segment). Mỗi phân đoạn là một đơn vị logic như: main program, procedure, function, local variables, global variables, stack, symbol table, … Kỹ thuật phân đoạn: Chia không gian địa chỉ ảo thành một tập các phân đoạn (segment), mỗi phân đoạn có tên và kích thước riêng. Một địa chỉ logic được định vị bằng tên phân đoạn và độ dời (offset) bên trong phân đoạn đó. Khác với phân trang khi mà độ lớn trang là bằng nhau thì đọ lớn mỗi đoạn không bắt buộc điều này. Địa chỉ logic là một cặp giá trị: base – chứa địa chỉ khởi đầu của phân đoạn trong bộ nhớ limit – xác định kích thước của phân đoạn
III.3.3. Phân đoạn kết hợp với phân trang. Phân trang và phân đoạn có điểm chung và điểm riêng; phân trang và phân đoạn có ưu và nhược điểm khác nhau. Có thể kết hợp đồng thời phân trang với phân đoạn khi mà một đoạn có thể được phân thành các trang.
HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
III.4. Bộ nhớ ảo
Hiểu được kỹ thuật bộ nhớ ảo, mục đích và ý nghĩa việc ứng dụng kỹ thuật bộ nhớ ảo; Đồng thời nắm được các thuật toán xử lý lỗi trang, hướng tới lập trình mô phỏng các thuật toán này.
III.4.1. Khái niệm chung (Background):
III.4.2. Phân trang theo yêu cầu (Demand Paging):
III.4.3. Thay thế trang (Page Replacement) hay Xử lý lỗi trang Khi xảy ra page fault, hệ điều hành thực hiện các bước sau
III.4.3.1. Thuật toán FIFO vào trước ra trước (First In First out) Chọn trang swap out là trang đã được swap in đầu tiên (trong số nhứng trang đang nằm trong bộ nhớ cơ sở) Nêu ví dụ với bài toán cấp 3 khung trang và bài toán cấp 4 khung trang, tính số lỗi trang III.4.3.2. Thuật toán tối ưu OPT (Optimal Replacement) Nhằm hạn chế tối đa lỗi trang, sẽ tìm trang để thay thế là trang lâu được thực hiện nhất tức là để lại những trang sắp được thực hiện. (Thảo luận tính khả thi) Nêu ví dụ bài toán cấp phát mỗi tiến trình 4 khung trang, tính số lỗi trang III.4.3.3. Thuật toán lâu nhất chưa sử dụng LRU (Least Recently Used) Thay thế trang nằm trong bộ nhớ nhưng đã lâu nhất chưa được sử dụng/ thực hiện. Nêu ví dụ với bài toán cấp cho tiến trình 4 khung trang, tính số lỗi trang.
Bài 1. Trong các hệ thống áp dụng kỹ thuật Bộ nhớ ảo, mỗi tiến trình được cấp phát hạn chế số lượng “khung trang” trong khi số lượng trang thực tế tiến trình yêu cầu có thể nhiều hơn nhiều. Hãy giải thích ngắn gọn các thuật toán “Thay thế trang” và tính số lượng lỗi trang với mỗi thuật toán tương ứng đối với Tiến trình có yêu cầu truy nhập theo trình tự các trang sau: 1, 2, 3, 7, 8, 2, 2, 4, 5, 7, 1, 2, 3, 7, 8, 4, 1, 5, 6, 7,1 với trường hợp số lượng khung trang được cấp là 4. Bài 2. Trong các hệ thống áp dụng kỹ thuật Bộ nhớ ảo, mỗi tiến trình được cấp phát hạn chế số lượng “khung trang” trong khi số lượng trang thực tế tiến trình yêu cầu có thể nhiều hơn nhiều. Hãy giải thích ngắn gọn các thuật toán “Thay thế trang” và tính số lượng lỗi trang với mỗi thuật toán tương ứng đối với Tiến trình có yêu cầu truy nhập theo trình tự các trang sau: 1, 2, 3, 5, 7, 8, 4 , 2, 3, 4, 7, 4, 2, 3, 8, 4, 8, 5, 6, 7, 1 với trường hợp số khung trang được cấp là 4.
Chia sẻ với bạn bè của bạn:
Page 4HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
IV.1. Tổng quan Hề thống xuất nhập và Thiết bị ngoại vi
Hiểu được cơ sở của phần cứng xuất nhập Nắm được các dịch vụ do HĐH cung cấp và chức năng cầu nối của HĐH giữa ứng dụng với phần cứng Nắm được nguyên lý thiết kế HĐH để cải tiến năng lực xuất nhập
IV.1.1 Các khái niêm cơ bản Một trong những quan tâm chính của người thiết kế HĐH là điều khiển ngoại vi. Điều khiển ngoại vi bao gồm cả phần cứng lẫn phần mềm, hơn nữa ngoại vi lại rất phong phú, rất khác nhau giữa các chủng loại. Công nghệ thiết bị ngoại vi song hành hai xu hướng trái ngược nhau, bên cạnh việc chuẩn hóa phần mềm cùng với giao diện phần cứng là sự tăng sự đa dạng của thiết bị. Một số khái niệm:
IV.1.2 Phần cứng xuất nhập Có rất nhiều và rất đa dạng thiết bị ngoại vi. Ngoài các thiết bị phổ biến knhưng cũng rất phong phú, kết nói với máy tính nói chung như bàn phím, màn hình, con chuột, thiết bị lưu trữ, máy in … rồi tới thiết bị nối mạng, loa, mỉco, máy vẽ, máy chiếu hay thẻ nhớ ngoài….còn phải kể đến các ngoại vi đặc chủng như bộ phận đếm và trả tiền của máy ATM, kênh đóng mở van cấp nhiệt của hệ thống điều khiển nhiệt hay đơn giản là một máy cắt gọt cơ khí của hệ thống máy tiện chính xác điều khiển bằng vi tính … Một máy tính có thể kết nối với nhiều ngoại. Chúng ta không nghiên cứu cái thiết bị hoạt động như thế nào mà tìm hiểu máy tính làm việc với thiết bị ngoại vi ra sao.
IV.1.3 Giao diện xuất nhập ứng dụng (Application I/O Interface) Phần này sẽ tìm hiểu kỹ hơn các kỹ thuật cấu trúc và giao diện của HĐH sao cho các thiết bị xuất nhập được nhìn nhận một cách thống nhất và chuẩn hóa.
IV.1.3.1 Thiết bị ký tự và thiết bi khối (Block and Character Devices)
IV.1.3.2 Nhập xuất khóa và nhập xuất không khóa (Blocking and Nonblocking I/O) Một khía cạnh khác của giao thức lời gọi hệ thống liên quan tới việc chọn giữa xuất nhập chặn (blocking I/O) và xuất nhập không chặn (nonblocking I/O) hay còn được gọi là không đồng bộ (asynchronous). Khi ứng dụng gặp lời gọi hệ thống chặn thì việc chạy ứng dụng tạm dừng, ứng dụng sẽ được chuyển sang hàng đợi “chờ” (wait queue). Sau khi lời gọi hệ thống hoàn thành, tiến trình được chuyển vào hàng đợi sẵn sàng để chờ được cấp CPU thực hiện tiếp. Ở một góc khác chúng ta nhận có những hành động vật lý được thực hiện bởi thiết bị ngoại vi diễn ra không đồng bộ. Một số tiến trình ở mức người sử dụng cần các xuất nhập không chặn này, chẳng hạn như giao tiếp người sử dụng nhận ký tự từ bàn phím và đầu vào con chuột trong khi đang xử lý và hiển thị dữ liệu trên màn hình. Có một số khái niệm và vấn đề liên quan cần nghiên cứu:
IV.1.4 Hiệu năng hệ thống (Performance) Tất cả các cấu thành của hệ thống tác động tới hiệu năng của nó; và hệ thống xuất nhập cũng là một yếu tố quan trọng.
HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
IV.2 Thiết bị lưu trữ
Nắm được và phân biệt các loại thiết bị lưu trữ ngoài, đặc biệt là đĩa cứng Nắm được các thuật toán căn bản lập lịch cho đầu từ đĩa cứng, hướng tới lập trình mô phỏng dịch chuyển đầu từ.
IV.3.1 Giới thiệu chung về thiết bị lưu trữ
IV.3.2 Lập lịch cho đầu từ (Arm Scheduling) Một nhiệm vụ quan trọng của HĐH là khai thác phần cứng hiệu quả. Đối với đĩa cứng đó chính là thời gian truy cập nhanh và lưu trữ được nhiều trên đĩa nhất. Thời gian truy cập bao gồm hai thành phần: Thời gian dịch chuyển đầu từ và thời gian trễ vòng quay, trong đó thời gian trễ vòng quay có thể nói là xác định và phụ thuộc phần cứng, trong khi thời gian định vị đầu từ tới các rãnh chứa thông tin cần truy cập của tệp tin trên đĩa là tổng thời gian đầu từ dịch chuyển tới tất cả các rãnh chứa thông tin. Bới vậy việc dịch chuyển đầu từ tới rãnh nào trước, rãnh nào sau có ảnh hưởng rất lớn tới thời gian truy cập.
Nội dung thảo luận Đọc mở rộng và nâng cao về RAID, các loại thẻ nhớ và flash disk (thường gọi là USB)
HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
IV.3: Tắc nghẽn (Deadlocks)
Hiểu mô hình hệ thống với vấn đề tắc nghẽn, các đặc điểm của chúng Nắm được các phương pháp quản lý, ngăn chặn và tránh tắc nghẽn Hiểu được cách phát hiện và phục hồi từ tắc nghẽn
IV.2.1 Tắc nghẽn Trong môi trường đa trình đa nhiệm, khi có nhiều tiến trình cùng đồng hành lại yêu cầu một số lượng hữu hạn tài nguyên phần cứng, đặc biệt là các ngoại vi khá chậm (một cách tương đối), chúng xung đột với nhau. Một tiến trình khi yêu cầu các tài nguyên, nếu tài nguyên đó không thể đáp ứng tài thời điểm hiện thời thì tiến trình sẽ phải chuyển sang trạng thái chờ. Các tiến trình có thể chờ mãi mãi bởi vì tài nguyên mà nó yêu cầu bị giữ bởi một tiến trình khác chưa thể giải phóng trong khi tiến trình này lại cũng đang chờ tài nguyên. Tắc nghẽn thường xảy ra do xung đột về tài nguyên thuộc dạng không chia sẻ, tuy nhiên trong một số ít trường hợp tắc nghẽn vẫn có thể xảy ra với tài nguyên chia sẻ được. IV.2.2. Mô hình hệ thống Hệ thống gồm các loại tài nguyên, kí hiệu R1, R2,…, Rm , ví dụ: CPU, không gian bộ nhớ, thiết bị I/O nào đó. Mỗi loại tài nguyên Ri có Wi thực thể (instance). Để sử dụng tài nguyên, tiến trình thực hiện theo các bước sau:
IV.2.3. Điều kiện hình thành tắc nghẽn (Deadlock Characterization) Tắc nghẽn chỉ xảy ra khi đồng thời cả bốn điều kiện sau thỏa mãn: 1. Điều kiện ngăn chặn lẫn nhau (mutual exclusion): các tiến trình thực hiện loại trừ lẫn nhau trên đoạn găng. VD: Cập nhật dữ liệu một bản ghi vào một CSDL trên mạng. 2. Điều kiện giữ và đợi (hold & wait): tiến trình đang giữ ít nhất một tài nguyên và yêu cầu thêm tài nguyên khác mà chúng lại đang bị giữ bởi một tiến trình khác. 3. Điều kiện không có ưu tiên trước Nonpre-emption: tài nguyên chỉ được giải phóng khi tiến trình đang giữ nó kết thúc công việc. 4. Điều kiện đợi vòng (circular-wait): các tiến trình giữ và đợi tài nguyên tạo thành vòng luẩn quẩn. VD: P0 đợi tài nguyên bị giữ bởi P1, P1… P2, P2…Pn, Pn .. P0. Đồ họa phân phối tài nguyên R cho các tiến trình P với deadlock và không có deadlock xem kỹ trang 246 đến trang 249 chương 8 tài liệu 1. IV.2.4. Ngăn ngừa tắc nghẽn (deadlock prevention) Đảm bảo ít nhất một trong bốn điều kiện sinh ra deadlock không được xảy ra.
Cách 1: mỗi process yêu cầu toàn bộ tài nguyên cần thiết một lần. Nếu có đủ tài nguyên thì hệ thống sẽ cấp phát, nếu không đủ tài nguyên thì process phải bị blocked. Cách 2: khi yêu cầu tài nguyên, process không được giữ bất kỳ tài nguyên nào. Nếu đang giữ thì phải trả lại trước khi yêu cầu.
Nếu process A có giữ tài nguyên và đang yêu cầu tài nguyên khác nhưng tài nguyên này chưa cấp phát ngay được thì: Cách 1: Hệ thống đòi lại mọi tài nguyên mà A đang giữ, A chỉ bắt đầu lại được khi có được các tài nguyên ban đầu cùng với tài nguyên đang yêu cầu. Cách 2: Hệ thống sẽ xem tài nguyên mà A yêu cầu: Nếu tài nguyên được giữ bởi một process khác đang đợi thêm tài nguyên, tài nguyên này được hệ thống đòi lại để cấp phát cho A. Nếu tài nguyên được giữ bởi process không đợi tài nguyên nào khác nữa, A phải đợi và tài nguyên mà A đang giữ bị hệ thống đòi lại. Tuy nhiên hệ thống chỉ đòi lại các tài nguyên mà có process khác yêu cầu.
IV.2.5 Tránh deadlock (deadlock avoidance) Tránh deadlock là vẫn đảm bảo hiệu suất sử dụng tài nguyên tối đa đến mức có thể. Mỗi tiến trình process phải khai báo số lượng tài nguyên tối đa mà nó cần để thực hiện công việc. Giải thuật tránh deadlock phải kiểm tra trạng thái cấp phát của tài nguyên (resource-allocation state) để bảo đảm hệ thống không bao giờ rơi vào trạng thái deadlock. Trạng thái cấp phát tài nguyên được định nghĩa dựa trên số tài nguyên còn lại, số tài nguyên đã được cấp phát và số tài nguyên tối đa mà mỗi process yêu cầu.
IV.2.6. Phát hiện deadlock (deadlock detection) Nếu chấp nhận xảy ra deadlock trong hệ thống, thì ta cần kiểm tra trạng thái của hệ thống bằng giải thuật phát hiện deadlock. Nếu có deadlock thì tiến hành phục hồi hệ thống Các giải thuật phát hiện deadlock thường sử dụng mô hình RAG. Hệ thống cấp phát tài nguyên được khảo sát trong các trường hợp sau Mỗi loại tài nguyên chỉ có một thực thể (instance) Mỗi loại tài nguyên có thể có nhiều thực thể (instances) IV.2.7. Khắc phục deadlock (Recovery from Deadlock) Cách1:Báo cho người vận hành (operator) hệ thống. Khi đó người vận hành sẽ tự xác định biện pháp và khắc phục tắc nghẽn một cách thủ công. Cách 2: Hệ thống tự động phục hồi bằng cách phá vỡ điều kiện đợi vòng (circular wait) hoặc cách khác là cướng bức (preempt) tài nguyên của một hay một số tiến trình.
HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH Bộ môn: Khoa học Máy tính Giáo viên: 1) TRỊNH Minh Châu 2)
IV.4 Hệ thống tệp tin
Hiểu được các khía cạnh khác nhau đối với tệp tin và cấu trúc thư mục Nắm đượccác cơ chế quản lý, kiểm soát, bảo vệ tệp tin trong môi trường đa trình đa nhiệm với nhiều người sử dụng; hiểu cách chia sẻ tệp tin
IV.4.1 Tệp tin (File Concept) Thông tin lưu trữ trên các loại thiết bị lưu trữ khác nhau về mặt vật lý có thể khác nhau. Để tiện dụng cho người sử dụng, HĐH cung cấp một cái nhìn logic thống nhất đối với việc lưu trữ thông tin. File hay tệp tin là đơn vị nhỏ nhất của HĐH quản lý dưới góc nhìn người sử dụng. File chính là một tập hợp thông tin có liên quan được ghi trên bộ nhớ ngoài. Có các loại file sau: chương trình, dữ liệu, âm thành, hình ảnh, Multimedia,… File có thể có/ không có cấu trúc. IV.4.1.1 Thuộc tính tệp tin (File Attributes)
IV.4.1.2 Tác nghiệp trên tệo tin (File Operations) Tệp tin là một kiểu dữ liệu trừu tượng. Để định nghĩa chính xác một tệp tin, cần xem xét các tác nghiệp có thể thực hiện đối với một tệp tin. HĐH cung cấp các lời gọi hệ thống để thực hiện các công việc này, bao gồm:
IV.4.1.3 Các kiểu tệp tin (File Type) Thông thường phần tên file mở rộng thể kiện kiểu của tệp tin. Chẳng hạn như file thực hiện được có phần tên mở rộng là .com hay .exe hay .bin, file chương trình mã nguồn: .c, .pas, .cpp hay .asm (xem thêm trang 377 tài liệu 1). Ngoài ra cũng có thể nhóm chúng lại làm mấy dạng tệp tin sau:
IV.4.2 Các phương thức truy nhập tệp tin (Access Methods) (Xem thêm phần các phương pháp cấp phát – Allocation Methods, ở mục sau) Tệp tin chứa thông tin lưu trữ trên bộ nhớ ngoài. Khi cần thiết chúng phải được đọc vào bộ nhớ trong của hệ thống máy tính. Có một số phương thức truy cập. Các mô hình hệ thống khác nhau có thể cho phép đọc bằng một phương thức, có hệ thống có thể cho phép truy cập bằng nhiều nhiều phương thức:
Read next Write next
Read n Write n IV.4.3 Cấu trúc thư mục (Directory Structure) Một thiết bị lưu trữ thường chứa rất nhiều tệp tin, có thể là hàng ngàn tới hàng triệu, vì thế cần phải tổ chức lại chúng. Việc tổ chức này thường được thực hiện bởi hai phần: Thứ nhất là chia chúng thành hơn các phân khu (partitions) hay phân vùng (Volumes), thứ hai là mỗi phân khu chứa thông tin về các tệp tin thuộc phân khu đó. Thông tin này được lưu ở phần đầu mỗi phân khu gọi là thư mục hay bảng mục lục phân vùng. Các thao tác có thể thực hiện trên thư mục:
IV.4.4 Bảo vệ tệp tin (Protection) Thông tin của hệ thống máy tính dù được lưu trữ trên thiết bị lưu trữ ngoài vẫn cần được bảo đảm an toàn ở những mức độ theo yêu cầu quan trọng của thông tin. Khả năng tin cậy của các tệp tin thường được đảm bảo bằng cách nhân bản chúng dưới các hình thức khác nhau với mục đích là thông tin bị hỏng có thể khôi phục lại nhanh chóng và dễ dàng. Sao lưu và Backup tự động là biện pháp hữu hiệu, về vấn đề này có thể đọc thêm về RAID. Ở đây sẽ bàn về vấn đề bảo vệ tệp tin trước những truy nhập từ người dùng. IV.4.4.1 Các kiểu truy cập (Type of Access) Quản lý, giới hạn quyền truy cập tới tệp tin để thực hiện các thao tác sau trên tệp tin:
IV.4.4.2 Kiểm soát truy cập (Access Control) Người dùng, nhóm người sử dụng khác nhau có thể được quản lý bởi việc cấp các quyền truy cập khác nhau. Về mode truy cập lên tệp tin có thể chia thành ba loại bao gồm:
IV.4.4.3 Các tiếp cận bảo vệ khác (Other Protection Approaches) Khá phổ biến và dễ phát triển như cơ chế mật khẩu (Password). Có hệ thống cho phép gắn mật khẩu với từng tệp tin, có hệ thống còn cho phép gắn mật khẩu với cả thư mục con IV.4.5 Các phương pháp cấp phát (Allocation Methods) Đối với đĩa, việc truy cập trực tiếp cho phép khả năng linh hoạt trong việc cài đặt tệp tin. Vấn đề đáng quan tâm là cấp phát không gian lưu trữ thế nào để sử dụng hiệu quả và các tệp tin có thể truy cập nhanh chóng. Có ba phương pháp chính cấp phát không gian đĩa: cấp phát kề, liên kết và chỉ mục:
Bộ môn Khoa học Máy tính Page Chia sẻ với bạn bè của bạn:
|