ĐÁP ÁN HỆ ĐIỀU HÀNHCâu 1: Ý nghĩa của System Call. Hãy giải thích bình thường các phần mềm ứng dụng “khai thác” phần cứng của máy như thế nào?• Ý nghĩa của System Call- HĐH cung cấp 1 giao tiếp sử dụng được gọi là "System Call", mỗi system call là 1 hàm thực hiện 1 chức năng xác định.- Hệ thống gọi cung cấp giao diện giữa một chương trình đang chạy và hệ thống điều hành. + Nói chung có sẵn như là ngôn ngữ bậc cao. + Ngôn ngữ định rõ sự thay thế của ngôn ngữ bậc cao cho các hệ thống lập trình.Nó cho phép hệ thống gọi được thực hiện trực tiếp (ví dụ, C. Bliss, PL/360) - Ba phương pháp truyền tham số khi sử dụng system call + Truyền thông số qua thanh ghi . + Truyền tham số thông qua một vùng nhớ, địa chỉ của vùng nhớ được gửi đến hệ điều hành qua thanh ghi . + Truyền tham số qua stack - Mỗi hệ điều hành có thể thiết lập riêng các hệ thống gọi được gọi là hệ điều hành của API.• Giải thích: Có thể nói hệ điều hành là một hệ thống các chương trình đóng vai trò trung gian giữa người sử dụng và phần cứng máy tính. Mục tiêu chính của nó là cung cấp một môi trường thuận lợi để người sử dụng dễ dàng thực hiện các chương trình ứng dụng của họ trên máy tính và khai thác triệt để các chức năng của phần cứng máy tính. Để đạt được mục tiêu trên hệ điều hành phải thực hiện 2 chức năng chính sau đây:+ Giả lập một máy tính mở rộng: Giúp người sử dụng khai thác các chức năng của phần cứng máy tính dễ dàng và hiệu quả hơn. + Quản lý tài nguyên của hệ thống: Tài nguyên hệ thống có thể là: processor memory, I/O device, printer, file,…. Khi người sử dụng cần thực hiện một chương trình hay khi một chương trình cần nạp thêm một tiến trình mới vào bộ nhớ thì hệ điều hành phải cấp phát không gian nhớ cho chương trình, tiến trình đó để chương trình, tiến trình đó nạp được vào bộ nhớ và hoạt động được. Do đó hệ điều hành phải tổ chức cấp phát bộ nhớ sao cho hợp lý để đảm bảo tất cả các chương trình, tiến trình khi cần đều được nạp vào bộ nhớ để hoạt động. Ngoài ra hệ điều hành còn phải tổ chức bảo vệ các không gian nhớ đã cấp cho các chương trình, tiến trình để tránh sự truy cập bất hợp lệ và sự tranh chấp bộ nhớ giữa các chương trình, tiến trình, đặc biệt là các tiến trình đồng thời hoạt động trên hệ thống.Trong mọi trường hợp tất cả các chương trình, tiến trình nếu cần được cấp phát tài nguyên để hoạt động thì sớm hay muộn nó đều được cấp phát và được đưa vào trạng thái hoạt động.Câu 3: Nêu định nghĩa “Hệ điều hành”. Hệ điều hành thực hiện những chức năng chính gì?• Khái niệm HĐH : HĐH là chương trình trung gian giữa phần cứng máy tính và người sử dụng, có chức năng điều khiển phần cứng và cung cấp các dịch vụ cơ bản cho các ứng dụng• Chức năng: - Phân chia thời gian xử lý trên CPU (định thời) - Phối hợp và đồng bộ hoạt động giữa các quá trình .- Quản lý tài nguyên hệ thống hiệu quả .- Kiểm soát quá trình truy cập, bảo vệ hệ thống .- Duy trì sự nhất quán của hệ thống, kiểm soát lỗi và phục hồi hệ thống khi có lỗi xảy ra.- Cung cấp giao diện làm việc thuận tiện cho người dùngCâu 4: Multi-tasking là gì? Giải thích sự khác nhau giữa các hình thức Multi-tasking (cooperative and pre-emtive multi-tasking). • Multi-tasking : Thực hiện nhiều nhiệm vụ cùng một lúc, CPU sẽ luân phiên xử lý các tiến trình trong một khoảng thời gian rồi chuyển sang cho tiến trình khác.• Multiprograming: có nhiều hơn một chương trình đang nằm trong bộ nhớ để được lựa chọn chuyển giao cho CPU thực thi.• Multiprocessing: sử dụng nhiều hơn 1 CPU để có thể xử lý song song cùng lúc nhiều tiến trình.Câu 5: Sự giống nhau và khác nhau giữa Chương trình, Tiến trình và Luồng (Program, Process and Thread).• Sự giống nhau: - Tiểu trình cũng là đơn vị xử lý cơ bản trong hệ thống, nó cũng xử lý tuần tự đoạn code của nó, nó cũng sở hữu một con trỏ lệnh, một tập các thanh ghi và một vùng nhớ stack riêng và các tiểu trình cũng chia sẻ thời gian xử lý của processor như các tiến trình. • Sự khác nhau giữa tiến trình và chương trình và Luồng - Chương trình là một thực thể thụ động chứa lệnh & dữ liệu để tiến hành một tác vụ( công việc). Khi thực hiện các lệnh, chương trình chuyển thành tiến trình.- Tiến trình là một thực thể hoạt động.- Luồng(Thread): trong hệ thống có thể tồn tại nhiều dòng xử lý cùng chia sẻ một không gian địa chỉ bộ nhớ, các dòng xử lý này hoạt động song song với nhau.Câu 7: Hãy giải thích cơ chế CPU chuyển từ việc thực hiện process này sang process khác. Làm sao có thể đảm bảo được việc thực hiện đúng các lệnh của process tương ứng?- Làm cho thời gian thực hiện các tiến trình khác nhau là ít nhất tức là trong một khoảng thời gian sẽ có nhiều tiến trình được thực hiện.- Khai thác CPU làm việc một cách hiệu quả nhất.Tức là lúc nào CPU cũng trong trạng thái bận.- Tối thiểu hoá thời gian một tiến trình chờ trong hàng đợi.- Tối thiểu hoá thời gian từ khi gửi một yêu cầu tới hệ thống cho tới khi nhận đ-ợc câu trả lời từ hệ thống.- Đảm bảo tất cả các tiến trình đều đ-ợc thực hiện - HĐH hiện nay th-ờng là HĐH đa nhiệm,tức là cùng một lúc sẽ có nhiều tiến trình cùng đ-ợc thực hiện .Về nguyên tắc để thực hiện đ-ợc điều này thì hệ thống phải có nhiều processor ,mỗi processor có nhiệm vụ thựchiện một ch-ơng trình ,nh-ng mong muốn của HĐH cũng nh- ng-ời sử dụng là thực hiện đa ch-ơng trình trên các hệ thống chỉ có 1 processor- Để thực hiện đ-ợc điều này HĐH phải phân phối processor cho các tiến trình sao cho phù hợp .- Trong mô hình tiến trình HĐH chia ch-ơng trình thành nhiều tiến trình khởi tạo và đưa vào hệ thống nhiều tiến trình của một chương trình hoặc cuả nhiều chương trình khác nhau ,cấp phát đầy đủ tài nguyên (trừ prcessor ) cho các tiến trình và các tiến trình đều ở trạng thái sẵn sàng.Tại một thời điểm HĐH chỉ cung cấp processor cho 1tiến trình,sau một thời gian th-c hiện HĐH sẽ thu hồi lại nguyên (trừ prcessor ) cho các tiến trình và các tiến trình đều ở trạng thái sẵn sàng.Tại một thời điểm HĐH chỉ cung cấp processor cho 1tiến trình,sau một thời gian th-c hiện HĐH sẽ thu hồi lại- Processor của tiến trình đó và cấp processor cho một tiến trình khác.Tiến trình đang hoạt động bây giờ sẽ chuyển sang trạng thái(ready or blocked).Nhưng trước khi chuyển trạng thái thì HĐH phải làm các việc sau đây:- L-u ngữ cảnh của processor ,bao gồm thanh ghi bộ đếm ch-ơng trình (PC:program count) và các thanh ghi khác . -- Cập nhật PCB(process control block)của tiến trình sao cho phù hợp với trạng thái mới của tiến trình và các thông tin tính toán.- Di chuyển PCB của tiến trình đến một hàng đợi thích hợp ,để đáp ứng được các yêu cầu của công tác điều phối tiến trình . -- Chọn một tiến trình khác để cho phép nó thực hiện . - Cập nhật PCB của tiến trình vừa đ-ợc chọn thực hiện ở trên ,chủ yếu là thay đổi trạng thái của tiến trình đến trạng thái runing . -- Cập nhật các thông tin liên quan đến quan lí bộ nhớ đang được sử dụng . Khôi phục lại ngữ cảnh của processor và thay đổi giá trị của bọ đếm ch-ơng trình và các thanh ghi khác sao cho phù hợp với tiến trình đ-ợc chọn ở trên,để tiến trình này có thể bắtđầu hoạt động.- CPU thực hiện được đúng các lệnh của process vì:Khi HĐH chuyển một tiến trình từ trạng thái running sang ready (hoặc block) thì HĐH đã đồng thời lưu giữ các thông tin về process trên các PCB .Mặt khác mỗi một PCB là một kho chứa tất cả mọi thông tin của một process.Vì vậy khi CPU phải thực hiện một process nào nó chỉ việc lấy thông tin đã chứa trong các PCB tương ứng ra và thực hiện Câu 8: Mục đích và nguyên tắc của việc lập lịch cho CPU (Process Scheduling)Mục đích: + Làm cho thời gian thực hiện của các tiến trình khác nhau tức là trong một khoảng thời gian sẽ có nhiều tiến trình thực hiện.+ Khai thác CPU một cách hiệu quả tức là lúc nào CPU cũng ở trong trạng thái bận.+ Tối thiểu hóa thời gian một tiến trình chờ trong hàng đợi.+ Tối thiểu hóa thời gian từ khi gửi một yêu cầu tới hệ thống cho tới khi nhận được câu trả lời từ hệ thống .+ Đảm bảo tất cả các tiến trình đều được thực hiện. Nguyên tắc: tổ chức dòng xếp hàng cho các tiến trình,sau đó xác lập một chính sách phục vụ cho các dòng xếp hàng đó.Câu 9: Ý nghĩa căn bản của Lập lịch, Sự khác nhau giữa Lập lịch dài kì và lập lịch ngắn hạn?- Ý nghĩa của lập lịch: có nghĩa là tổ chức một hàng đợi các tiến trình sẵn sàng để phân phối giờ CPU cho chúng dựa trên độ ưu tiên của các tiến trình sao cho hiệu suất sử dụng là tối ưu nhất.- Lập lịch dài kì: áp dụng với những tiến trình đã được lập danh sách và SPOOL,- Lập lịch ngắn hạn: áp dụng với những tiến trình mà mã nguồn của nó đã được đẩy vào bộ nhớ trong(tiến trình đã sẵn sàng nhận giờ phân bổ của CPU). Câu 10: Giới thiệu sơ lược 5 cách lựa chọn tiến trình từ “ready to run” để thực hiện. Đánh giá thuật toán FCFS.- Sơ lược 5 cách lựa chọn tiến trình từ “ready to run” để thực hiện”Ngay sau khi khởi tạo các tiến trình, đưa tiến trình vào hệ thống và cấp phát đầy đủ tài nguyên (trừ processor)cho tiến trình , hệ điều hành đưa tiến trình vào trạng thái Ready.Hay nói cách khác trạng thái ready là trạng thái của một tiến trình trong hệ thống đang chờ được cấp phát processor để bắt đầu thực hiện.- Đánh giá thuật toán FCFS.-Tiến trình nào yêu cầu CPU trước sẽ được phân phối CPU trước→ Giải thuật FCFS là không được ưu tiên-Là giải thuật đơn giản nhất-Process Burst Time (thời gian xử lý-thời gian sử dụng CPU, ms)P1 24P2 3P3 3-Giả định rằng các tiến trình đến theo thứ tự: P1, P2, P3 thì biểu đồ Gantt (Gantt Chart) của lịch biểu như sau:-Thời gian chờ đợi của các tiến trình: P1 = 0; P2 = 24; P3 = 27-Thời gian chờ đợi trung bình: (0 + 24 + 27)/3 = 17Câu 11: Giới thiệu sơ lược 5 cách lựa chọn tiến trình từ “ready to run” để thực hiện. Đánh giá thuật toán SJF- Sơ lược 5 cách lựa chọn tiến trình từ “ready to run” để thực hiện”Ngay sau khi khởi tạo các tiến trình, đưa tiến trình vào hệ thống và cấp phát đầy đủ tài nguyên (trừ processor)cho tiến trình , hệ điều hành đưa tiến trình vào trạng thái Ready.Hay nói cách khác trạng thái ready là trạng thái của một tiến trình trong hệ thống đang chờ được cấp phát processor để bắt đầu thực hiện.Đánh giá thuật toán SJF- Gắn với mỗi tiến trình là thời gian sử dụng CPU tiếp sau của nó.- Thời gian này được sử dụng để lập lịch các tiến trình với thời gian đợi ngắn nhất. + Hai phương pháp: . Không ưu tiên trước (non-preemptive)– một tiến trình nếu sử dụng CPU thì không nhường cho tiến trình khác cho đến khi nó kết thúc. . Có ưu tiên trước – nếu một tiến trình đến có thời gian sử dụng CPU ngắn hơn thời gian còn lại của tiến trình đang thực hiện thì ưu tiên tiến trình mới đến trước. Phương pháp này còn được gọi là Shortest-Remaining-Time-First (SRTF)- SJF là tối ưu – cho thời gian chờ đợi trung bình của các tiến trình là nhỏ nhấtCâu 12: Giới thiệu sơ lược 5 cách lựa chọn tiến trình từ “ready to run” để thực hiện. Đánh giá thuật toán SRF- Sơ lược 5 cách lựa chọn tiến trình từ “ready to run” để thực hiện”Ngay sau khi khởi tạo các tiến trình, đưa tiến trình vào hệ thống và cấp phát đầy đủ tài nguyên (trừ processor)cho tiến trình , hệ điều hành đưa tiến trình vào trạng thái Ready.Hay nói cách khác trạng thái ready là trạng thái của một tiến trình trong hệ thống đang chờ được cấp phát processor để bắt đầu thực hiện. Câu 13: Giới thiệu sơ lược 5 cách lựa chọn tiến trình từ “ready to run” để thực hiện. Đánh giá thuật toán RR- Sơ lược 5 cách lựa chọn tiến trình từ “ready to run” để thực hiện”Ngay sau khi khởi tạo các tiến trình, đưa tiến trình vào hệ thống và cấp phát đầy đủ tài nguyên (trừ processor)cho tiến trình , hệ điều hành đưa tiến trình vào trạng thái Ready.Hay nói cách khác trạng thái ready là trạng thái của một tiến trình trong hệ thống đang chờ được cấp phát processor để bắt đầu thực hiện.Đánh giá thuật toán RRMỗi tiến trình sử dụng một lượng nhỏ thời gian của CPU (time quantum – thời gian định lượng, q), thường là 10-100 ms. - Sau thời gian thực hiện q, tiến trình đưa vào cuối của ready queue.- Ready queue được tổ chức dạng FIFO (FCFS)- Nếu tiến trình có thời gian sử dụng CPU còn lại < q thì tiến trình sẽ giải phóng CPU khi kết thúc và không có mặt trong ready queue. Trình lập lịch sẽ chọn tiến trình kế tiếp trong ready queue.- Nếu tiến trình có thời gian sử dụng CPU còn lại > q thì bộ định thời (timer) sẽ đếm lùi và gây ngắt HĐH khi nó = 0. Việc chuyển ngữ cảnh được thực hiện để chuyển điều khiển CPU cho tiến trình ở đầu hàng đợi, và tiến trình hiện tại được đưa xuống cuối ready queue. Câu 15: Giải thích ngắn gọn trạng thái của các tiến trình, các mô hình tiến trình hệ thống (process models) chung.-Trạng thái của tiến trình tại một thời điểm được xác định bởi hoạt động hiện thời của tiến trình tại thời điểm đó.-Tại một thời điểm, một tiến trình có thể nhận một trong các trạng thái sau đây :+Mới tạo : 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ộtsự kiện xảy ra (hoàn thành nhập xuất hay nhận một tín hiệu) .+ 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.Sơ đồ cung chuyển đổi trạng thái: Câu 16: Giải thích vai trò của PCB (process control block). Mỗi quá trình được hiện diện trong hệ điều hành bởi một khối điều khiển quá trình (Process Control Block-PCB) – cũng được gọi khối điều khiển tác vụ. Một PCB được hiển thị trong hình III-2. Nó chứa nhiều phần thông tin được gắn liền với một quá trình xác định, gồm: - Trạng thái quá trình (process state): trạng thái có thể là mới, sẳn sàng, đang chạy, chờ đợi, kết thúc, … - Bộ đếm chương trình (program counter): bộ đếm hiển thị địa chỉ của chỉ thị kế tiếp được thực thi cho quá trình này. - Các thanh ghi (registers) CPU: các thanh ghi khác nhau về số lượng và loại, phụ thuộc vào kiến trúc máy tính. Chúng gồm các bộ tổng (accumulators), các thanh ghi chỉ mục, các con trỏ ngăn xếp, và các thanh ghi đa năng (general-purpose registers), cùng với thông tin mã điều kiện (condition-code information). Cùng với bộ đếm chương trình, thông tin trạng thái này phải được lưu khi một ngắt xảy ra, cho phép quá trình được tiếp tục một cách phù hợp sau đó (Hình III.3). - Thông tin lập thời biểu CPU (CPU-scheduling information): thông tin gồm độ ưu tiên của quá trình, các con trỏ chỉ tới các hàng đợi lập thời biểu, và bất kỳ tham số lập thời biểu khác. Mới tạo Kết thúcReady RunningBlocked- Thông tin quản lý bộ nhớ (Memory-management information): thông tin này có thể gồm những thông tin như giá trị của các thanh ghi nền và thanh ghi giới hạn, các bảng trang hay các bảng phân đoạn, phụ thuộc hệ thống bộ nhớ được dùng bởi hệ điều hành. - Thông tin tính toán (accounting information): thông tin này gồm lượng CPU và thời gian thực được dùng, công việc hay số quá trình,… - Thông tin trạng thái nhập/xuất (I/O status information): thông tin này gồm danh sách của thiết bị nhập/xuất được cấp phát quá trình này, một danh sách các tập tin đang mở, - 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 17: Giới thiệu và giải thích ngắn gọn các thành phần (components) của Hệ điều hành. Một hệ điều hành là một thành phần quan trọng của mọi hệ thống máy tính. Một hệ thống máy tính có thể được chia thành bốn thành phần: phần cứng, hệ điều hành, các chương trình ứng dụng và người dùng. - Phần cứng (Hardware): bao gồm bộ xử lý trung tâm (CPU), bộ nhớ, thiết bị xuất/nhập, cung cấp tài nguyên cơ bản cho hệ thống. - Các chương trình ứng dụng (application programs): trình biên dịch (compiler), trình soạn thảo văn bản (text editor), hệ cơ sở dữ liệu (database system), trình duyệt Web, định nghĩa cách mà trong đó các tài nguyên được sử dụng để giải quyết yêu cầu của người dùng. - Người dùng (user): có nhiều loại người dùng khác nhau, thực hiện những yêu cầu khác nhau, do đó sẽ có nhiều ứng dụng khác nhau. - Hệ điều hành (operating system): hay còn gọi là chương trình hệ thống, điều khiển và hợp tác việc sử dụng phần cứng giữa những chương trình ứng dụng khác nhau cho những người dùng khác nhau. Hệ điều hành có thể được khám phá từ hai phía: người dùng và hệ thống.Câu 18: Nêu vắn tắt các kĩ thuật cấp phát bộ nhớ (nạp chương trình vào bộ nhớ). • Kỹ thuật phân vùng cố định (Fixed Partitioning)- Quản lý bộ nhớ với những phân đọan cố định .Hệ điều hành chia bộ nhớ thành n vùng nhớ cố định( có thể không bằng nhau)- Việc phân chia này được thực hiện vào lúc khởi động hệ thống và không thay đổi suốt quá trình chạy.Với tổ chức như vậy cần duy trì một hàng đợi duy nhất để lưu trữ những tiến trình chưa được cấp phát bộ nhớ - Tất cả tiến trình được đặt trong một hàng đợi duy nhất. Khi có một phân vùng tự do , tiến trình đầu tiên trong hàng đợi có kích thước phù hợp sẽ được đặt vào phân vùng này và cho xử lý. - Nếu kích thước của tiến trình không vừa đúng bằng kích thước phân vùng chứa nó, phần bộ nhớ không sử dụng đến trong phân vùng sẽ bị lãng phí xảy ra hiện tượng phân mảnh nội vi. - Mức độ đa chương của hệ thống bị giới hạn bởi số lượng phân vùng.Vấn đề bảo vệ giữa các phân vùng: Để bảo vệ cần tổ chức hai thanh ghi : thanh ghi nền và thanh ghi giới hạn. -Khi tiến trình được tạo lập, nạp vào thanh ghi nền địa chỉ bắt đầu của phân vùng được cấp phát cho tiến trìnhvà nạp vào thanh ghi giới hạn kích thước của tiến trình - Sau đó mỗi đị chỉ bộ nhớ được phát sinh sẽ tự động được cộng với địa chỉ chứa trong thanh ghi nền để cho ra địa chỉ tuyệt đối trong bộ nhớ và các địa chỉ được đối chiếu với thanh ghi giới hạn để bảo đảm tiến trình không truy xuất ngoài phạm vi được cấp phát cho nó.Kỹ thuật phân vùng động (Dynamic Partitioning)- Số lượng các phân vùng trên bộ nhớ và kích thước của mỗi phân vùng là có thể thay đổi.- Phần user program trên bộ nhớ không được phân chia trước mà nó chỉ được ấn định sau khi đã có một tiến trình được nạp vào bộ nhớ chính. -Khi có một tiến trình được nạp vào bộ nhớ nó được hệ điều hành cấp cho nó không gian vừa đủ để chứa tiến trình, phần còn lại để sẵn sàng cấp cho tiến trình khác sau này. - Khi một tiến trình kết thúc nó được đưa ra ngoài và phần không gian bộ nhớ mà tiến trình này trả lại cho hệ điều hành sẽ được hệ điều hành cấp cho tiến trình khác, cả khi tiến trình này có kích thước nhỏ hơn kích thước của không gian nhớ trống đó. - Khi có một tiến trình cần được nạp vào bộ nhớ mà trong bộ nhớ có nhiều hơn một khối nhớ trống (Free Block) có kích thước lớn hơn kích thước của tiến trình đó, thì hệ điều hành phải quyết định chọn một khối nhớ trống phù hợp nào để nạp tiến trình sao cho việc lựa chọn này dẫn đến việc sử dụng bộ nhớ chính là hiệu quả nhất.Câu 19. Trong kỹ thuật cấp phát bộ nhớ phân vùng động, khi nạp tiến trình mới vào bộ nhớ cần lựa chọn một vùng còn “ rỗng” nào đó. Nêu các phương pháp/thuật toán lựa chọn.- Có 3 thuật toán mà hệ điều hành sử dụng trong trường hợp này, đó là: Best-fit, First-fit, và Word-fit. Cả 3 thuật toán này đều phải chọn một khối nhớ trống có kích thước bằng hoặc lớn hơn kích thước của tiến trình cần nạp vào, nhưng nó có các điểm khác nhau cơ bản sau đây -Best-fit: chọn khối nhớ có kích thước vừa đúng bằng kích thước của tiến trình cần được nạp vào bộ nhớ. - First-fit: trong trường hợp này hệ điều hành sẽ bắt đầu quét qua các khối nhớ trống bắt đầu từ khối nhớ trống đầu tiên trong bộ nhớ, và sẽ chọn khối nhớ trống đầu tiên có kích thước đủ lớn để nạp tiến trình. -Word -fit: tương tự như First-fit nhưng ở đây hệ điều hành bắt đầu quét từ khối nhớ trống kế sau khối nhớ vừa được cấp phát và chọn khối nhớ trống kế tiếp đủ lớn để nạp tiến trình. Câu 20: Phân tích hai khái niệm Page và Paging (trang và phân trang). -Page: Một trong các cơ cấu đơn giản để thực thi không gian địa chỉ ảo thì bao gồm việc phân đoạn bộ nhớ thành những đơn vị có độ lớn bằng nhau: những đơn vị tách chia này gọi là những trang (pages). Các độ lớn trang tiện dụng thì khoảng 1kB, 4kB hay 8kB. Địa chỉ và trạng thái của mỗi trang được dẫn tới trong một bảng trang (pape table), bảng này tồn tại cho mỗi chương trình ở trong bộ nhớ chính. -Paging: Không gian địa chỉ logic của một tiến trình có thể không kề nhau tiến trình được phân phối bộ nhớ vật lý bất kỳ lúc nào khi bộ nhớ sẵn có.Câu 21: Giả thích cơ chế phân đoạn (segmentation) trong quản lý bộ nhớ của hệ điều hành.Ý tưởng: quan niệm không gian địa chỉ là một tập các phân đoạn (segments) – các phân đoạn là những phần bộ nhớ kích thước khác nhau và có liên hệ logic với nhau. Mỗi phân đoạn có một tên gọi (số hiệu phân đoạn) và một độ dài. Người dùng sẽ thiết lập mỗi địa chỉ với hai giá trị : <số hiệu phân đoạn, offset>.Hình 3.18 Mô hình phân đoạn bộ nhớCơ chế MMU trong kỹ thuật phân đoạn: Hình 3.19 Cơ chế phần cứng hổ trợ kĩ thuật phân đoạnCần phải xây dựng một ánh xạ để chuyển đổi các địa chỉ 2 chiều được người dùng định nghĩa thành địa chỉ vật lý một chiều. Sự chuyển đổi này được thực hiện qua một bảng phân đoạn. Mỗi thành phần trong bảng phân đoạn bao gồm một thanh ghi nền và một thanh ghi giới hạn. Thanh ghi nền lưu trữ địa chỉ vật lý nơi bắt đầu phân đoạn trong bộ nhớ, trong khi thanh ghi giới hạn đặc tả chiều dài của phân đoạn. Câu 22: Mô tả ngắn gọn “Bộ nhớ ảo” – Virtual memory. Bộ nhớ ảo có lợi và thiệt hại gì đối với việc tối ưu hoá sử dụng CPU.- Khái niệm bộ nhớ ảo: Bộ nhớ ảo là một kỹ thuật cho phép xử lý một tiến trình không được nạp toàn bộ vào bộ nhớ vật lý. Bộ nhớ ảo mô hình hoá bộ nhớ như một bảng lưu trữ rất lớn và đồng nhất, tách biệt hẳn khái niệm không gian địa chỉ và không gian vật lý. Người sử dụng chỉ nhìn thấy và làm việc trong không gian địa chỉ ảo, việc chuyển đổi sang không gian vật lý do hệ điều hành thực hiện với sự trợ giúp của các cơ chế phần cứng cụ thể.- Cần kết hợp kỹ thuật swapping đển chuyển các phần của chương trình vào-ra giữa bộ nhớ chính và bộ nhớ phụ khi cần thiết.- Nhờ việc tách biệt bộ nhớ ảo và bộ nhớ vật lý, có thể tổ chức một bộ nhớ ảo có kích thước lớn hơn bộ nhớ vật lý.- Bộ nhớ ảo cho phép giảm nhẹ công việc của lập trình viên vì họ không cần bận tâm đến giới hạn của vùng nhớ vật lý, cũng như không cần tổ chức chương trình theo cấu trúc overlays.Hình 3.25 Bộ nhớ ảo- Cài đặt bộ nhớ ảoBộ nhớ ảo thường được thực hiện với kỹ thuật phân trang theo yêu cầu (demand paging). Cũng có thể sử dụng kỹ thuật phân đoạn theo yêu cầu ( demand segmentation) để cài đặt bộ nhớ ảo, tuy nhiên việc cấp phát và thay thế các phân đoạn phức tạp hơn thao tác trên trang, vì kích thước không bằng nhau của các đoạn.Câu 23: Trong kỹ thuật bộ nhớ ảo thường sử dụng Phân trang theo yêu cầu (demand paging). Hãy giới thiệu cơ chế này.Một hệ thống phân trang theo yêu cầu là hệ thống sử dụng kỹ thuật phân trang kết hợp với kỹ thuật swapping. Một tiến trình được xem như một tập các trang, thường trú trên bộ nhớ phụ ( thường là đĩa). Khi cần xử lý, tiến trình sẽ được nạp vào bộ nhớ chính. Nhưng thay vì nạp toàn bộ chương trình, chỉ những trang cần thiết trong thời điểm hiện tại mới được nạp vào bộ nhớ. Như vậy một trang chỉ được nạp vào bộ nhớ chính khi có yêu cầu.Với mô hình này, cần cung cấp một cơ chế phần cứng giúp phân biệt các trang đang ở trong bộ nhớ chính và các trang trên đĩa. Có thể sử dụng lại bit valid-invalid nhưng với ngữ nghĩa mới:valid : trang tương ứng là hợp lệ và đang ở trong bộ nhớ chính . invalid : hoặc trang bất hợp lệ (không thuộc về không gian địa chỉ của tiến trình) hoặc trang hợp lệ nhưng đang được lưu trên bộ nhớ phụ.Một phần tử trong bảng trang mộ tả cho một trang không nằm trong bộ nhớ chính, sẽ được đánh dấu invalid và chứa địa chỉ của trang trên bộ nhớ phụ Câu 24: Trong kỹ thuật sử dụng Bộ nhớ ảo Hệ điều hành cần có bộ phận quản lý việc hoán chuyển các trang/đoạn giữa bộ nhớ thực và bộ nhớ ảo và có thể xảy ra “Lỗi trang” (page fault). Hệ điều hành gải quyết vấn đề đó như thế nào và mục tiêu cần đạt được?Khi hệ thống truy xuất tới một trang nhưng trang này chưa được nạp vào bộ nhớ trong sẽ sinh ra lỗi trang.Hệ điều hành sẽ xử lý lỗi theo các bước sau:- Step 1: Kiểm tra việc truy xuất tới bộ nhớ có hợp lệ hay không. Nếu có ,goto Step2.Ngược lại kết thúc chương trình.- Step 2: Tìm vị trí chứa trang cần truy xuất trên đĩa từ.- Step 3: Tìm một trang vật lý trống trong bộ nhớ chính.Nếu tìm thấy go to step 4Nếu không ,chọn một trang đang sử dụng và chuyển nội dung trang này ra bộ nhớ ngoài (lưu nội dung trang này vào đĩa từ ),cập nhật bảng quản lý trang tương ứng.- Step 4: Chuyển trang muốn truy xuất từ bộ nhớ ngoài vào bộ nhớ trong :nạp trang cần truy xuất vào trang vật lý trống ,cập nhật nội dung bảng quản lý trang.- Step 5 : Tải kích hoạt chương trình Câu 25: Đánh giá các thuật toán thay trang (Page Replacement) trong kỹ thuật sử dụng Bộ nhớ ảo.Các thuật toán thay thế trang được áp dụng như trong sơ đồ quản lý bộ nhớ theo kiểu phân trang gồm:- Thay thế trang có thời gian tồn tại trong bộ nhớ lâu nhất(FIFO).- Thay thế trang có lần sử dụng cuối cùng , cách thời điểm hiện tại lâu nhất (LRU).- Thay thế trang có tần xuất sử dụng thấp nhất (LFU).- Thay thế trang có tần xuất sử dụng nhiều nhất (MFU- Most Frequently Used).Câu 26: Nêu ngắn gọn các thuật toán Thay thế trang trong kỹ thuật bộ nhớ ảo, Trình bày và giải thích bằng ví dụ thuật toán FIFO.Ghi nhận thời điểm một trang được mang vào bộ nhớ chính. Khi cần thay thế trang, trang ở trong bộ nhớ lâu nhất sẽ được chọnĐể áp dụng thuật toán FIFO, thực tế không nhất thiết phải ghi nhận thời điểm mỗi trang được nạp vào bộ nhớ, mà chỉ cần tổ chức quản lý các trang trong bộ nhớ trong một danh sách FIFO, khi đó trang đầu danh sách sẽ được chọn để thay thế.Thuật toán they thế trang FIFO dễ hiểu, dễ cài đặt. Tuy nhiên khi thực hiện không phải lúc nào cũng có kết qủa tốt : trang được chọn để thay thế có thể là trang chức nhiều dữ liệu cần thiết, thường xuyên được sử dụng nên được nạp sớm, do vậy khi bị chuyển ra bộ nhớ phụ sẽ nhanh chóng gây ra lỗi trang.Số lượng lỗi trang xảy ra sẽ tăng lên khi số lượng khung trang sử dụng tăng. Hiện tượng này gọi là nghịch lý Belady.Câu 27: Nêu ngắn gọn các thuật toán Thay thế trang trong kỹ thuật bộ nhớ ảo, Trình bày và giải thích bằng ví dụ thuật toán Tối ưu OPT.Thay thế trang sẽ lâu được sử dụng nhất trong tương lai.Thuật toán này bảo đảm số lượng lỗi trang phát sinh là thấp nhất , nó cũng không gánh chịu nghịch lý Belady, tuy nhiên, đây là một thuật toán không khả thi trong thực tế, vì không thể biết trước chuỗi truy xuất của tiến trình!Câu 28: Nêu ngắn gọn các thuật toán Thay thế trang trong kỹ thuật bộ nhớ ảo, Trình bày và giải thích bằng ví dụ thuật toán LRU.Với mỗi trang, ghi nhận thời điểm cuối cùng trang được truy cập, trang được chọn để thay thế sẽ là trang lâu nhất chưa được truy xuất.Thuật toán FIFO sử dụng thời điểm nạp để chọn trang thay thế, thuật toán tối ưu lại dùng thời điểm trang sẽ được sử dụng, vì thời điểm này không thể xác định trước nên thuật toán LRU phải dùng thời điểm cuối cùng trang được truy xuất – dùng quá khứ gần để dự đoán tương lai.Thuật toán này đòi hỏi phải được cơ chế phần cứng hỗ trợ để xác định một thứ tự cho các trang theo thời điểm truy xuất cuối cùng. Có thể cài đặt theo một trong hai cách Câu 29: Phân biệt hai hiện tượng phân mảnh nội (internal fragmentation) và phân mảnh ngoài (external fragmentation), chúng xuất hiện khi nào và tại sao? Kĩ thuật phân vùng cố định: Có phân mành trong vì một tiến trình được phân phối kích thước nhỏ hơn so với dung lượng của nó. Phân vùng động: Không phân mành trong do tiến trình chỉ được phân phối kích thước bằng dung lượng của nó. Có phân mành ngoài. Phân trang: Phân mành trong khi kích thước tiến trình nhỏ hơn kích thước 1 trang.Không có phân mành ngoài.Phân đoạn: Phân mành trong khi kích thước trong thay đổi. Có phân mành ngoài thì vùng rỗi nhỏ hơn đoạn cần thiếtCâu 30: Giải thích khái niệm “hoán chuyển” (swapping); Ý nghĩa, ứng dựng của việc áp dụng kĩ thuật này. Swapping: Sử dụng một thiết bị nhớ thứ cấp đủ lớn (Backing Store) để cung cấp bản sao của tất cả hình ảnh bộ nhớ cho tất cả người sử dụng. Trong các hệ điều hành sử dụng swapping, tồn tại module hệ thống swapper có chức năng: chọn tiến trình swap out (chọn tiến trình để đưa ra backing store), chọn tiến trình swap in(chọn tiến trình từ backing store để đưa vào bộ nhớ trong), định vị & quản lý không gian chuyểnCâu 31: Hãy giải thích vì sao DMA thường được “ưu ái” sử dụng như là phương thức thực thi trao đổi với ngoại vi? DMA có lợi điểm gì không đối với input thông qua bàn phím? Giải thích tại sao hoặc tại sao không?Câu 33: Khi học môn “Tin học đại cương” chúng ta đã được biết đến một cách chia các thiết bị ngoại vi thành 2 hoặc 3 loại (nhóm) là “VÀO’, “RA” và/hoặc vừa “VÀO vừa RA”; Dưới góc nhìn người thiết kế Hệ điều hành chúng ta có thể chia thiết bị ngoại vi thành 2 loại. Đó là gì và cách chia này dựa trên căn cứ nào? Hãy nêu ví dụ một số ngọai vi thuộc từng loại trên. Câu 34: Giải thích sự khác biệt giữa “polled I/O” và “interrupt-driven I/O”. Nêu những ưu điểm của “interrup-driven I/O” so với “polled I/O”.Câu 36: Hãy giải thích thuật toán Lập lịch cho đầu từ FCFS là gì, cho ví dụ để mô tả để tính được seek time.Phương pháp lập lịch đơn giản nhất là FCFS(first-come,first-served). Thuật toán này rất dể lập trình nhưng không cung cấp được một dịch vụ tốt. Ví dụ : cần phải đọc các khối theo thứ tự như sau :98, 183, 37, 122, 14, 124, 65, và 67Giả sử hiện tại đầu đọc đang ở vị trí 53. Như vậy đầu đọc lần lượt đi qua các khối 53, 98, 183, 37, 122, 14, 124, 65, và 67 như hình sau :Câu 37: Hãy giải thích thuật toán Lập lịch cho đầu từ SSTF là gì, cho ví dụ để mô tả để tính được seek time.Thuật toán này sẽ di chuyển đầu đọc đến các khối cần thiết theo vị trí lần lượt gần với vị trí hiện hành của đầu đọc nhất. Ví dụ : cần đọc các khối như sau : 98, 183, 37, 122, 14, 124, 65, và 67Giả sử hiện tại đầu đọc đang ở vị trí 53. Như vậy đầu đọc lần lượt đi qua các khối 53, 65, 67, 37, 14, 98, 122, 124 và 183 như hình sau :Hình 4.12 Phương pháp SSTFVới ví dụ này, thuật toán SSTF làm giảm số khối mà đầu đọc phải di chuyển là 208 khối.Câu 38: Hãy giải thích thuật toán Lập lịch cho đầu từ SCAN là gì, cho ví dụ để mô tả để tính được seek time.Theo thuật toán này, đầu đọc sẽ di chuyển về một phía của đĩa và từ đó di chuyển qua phía kia. Ví dụ : cần đọc các khối như sau : 98, 183, 37, 122, 14, 124, 65, và 67Giả sử hiện tại đầu đọc đang ở vị trí 53. Như vậy đầu đọc lần lượt đi qua các khối 53, 37, 14, 0 , 65, 67, 98, 122, 124 và 183 như hình sau :Thuật toán này còn được gọi là thuật toán thang máy. Hình ảnh thuật toán giống như hình ảnh của một người quét tuyết, hay quét lá.Câu 39: Hãy giải thích thuật toán Lập lịch cho đầu từ C-SCAN là gì, cho ví dụ để mô tả để tính được seek time.Thuật toán này tương tự như thuật toán SCAN, chỉ khác là khi nó di chuyển đến một đầu nào đó của đĩa, nó sẽ lập tức trở về đầu bắt đầu của đĩa. Lấy lại ví dụ trên, khi đó thứ tự truy xuất các khối sẽ là : 53, 65, 67, 98, 122, 124, 183, 199, 0, 14, 37 như hình sau :Hình 4.13 Phương pháp C-SCANCâu 40: Hãy giải thích thuật toán Lập lịch cho đầu từ C-LOOK là gì, cho ví dụ để mô tả để tính được seek time.Tương tự như Look nhưng đầu từ đọc/ghi không phục vụ đường về. Theo ví dụ trên, sơ đồ dịch chuyển đầu từ đọc/ghi theo thuật toán SSTF được thể hiện như sau:Hình 5.10 - Thuật toán lập lịch C - LOOKChú ý: Thuật toán FCFS, SSTF được áp dụng phổ biến, các thuật toán kiểu Scan, Look chỉ được áp dụng cho những đĩa chịu tải lớn.Câu 48: Tại sao ta có thể nói “Hệ điều hành thực hiện Vào/Ra”. Hãy giải thích cơ chế Chương trình ứng dụng thực hiện I/O như thế nào?Câu 49: Phân biệt Device, Driver và Device Controller.14 37 53 65 67 98122124183 |
