intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Giáo trình Nguyên lý hệ điều hành - Nguyễn Hải Châu

Chia sẻ: Fgjỉ Guygh | Ngày: | Loại File: PDF | Số trang:87

Thêm vào BST
Báo xấu
378
lượt xem 59
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cung cấp những khái niệm cơ bản về hệ điều hành máy tính: phân loại, nguyên lý, cách làm việc, phân tích thiết kế và chi tiết về một số hệ điều hành cụ thể Yêu cầu sinh viên: Nắm vững các nguyên lý cơ bản, làm tốt các bài tập để lấy đó làm cơ sở - nguyên lý cho các vấn đề khác trong thiết kế và cài đặt các hệ thống thông tin Chú ý liên hệ nội dung môn học với các tình huống thực tế về khía cạnh quản lý, tổ chức ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Nguyên lý hệ điều hành - Nguyễn Hải Châu

  1. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Mục tiêu của môn học Cung cấp những khái niệm cơ bản về hệ điều Nguyên lý hệ điều hành hành máy tính: phân loại, nguyên lý, cách làm việc, phân tích thiết kế và chi tiết về một số hệ điều hành cụ thể Nguyễn Hải Châu Yêu cầu sinh viên: Nắm vững các nguyên lý Khoa Công nghệ thông tin cơ bản, làm tốt các bài tập để lấy đó làm cơ Trường Đại học Công nghệ sở - nguyên lý cho các vấn đề khác trong thiết kế và cài đặt các hệ thống thông tin Chú ý liên hệ nội dung môn học với các tình huống thực tế về khía cạnh quản lý, tổ chức 1 2 Nội dung Tài liệu tham khảo Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, Operating Gồm có 6 phần chính: System Concepts, 7th edition, John Wiley & Sons, Inc., 2005. Tổng quan (3 tiết) William Stallings, Operating Systems: Internals and Design Principles 5th edition, Prentice-Hall, 2005. Quản lý tiến trình (12 tiết) Andrew S. Tanenbaum, Modern Operating Systems, 2nd edition, Prentice-Hall, 2001. Quản lý lưu trữ (12 tiết) Andrew S. Tanenbaum, Albert S Woodhull, Operating Systems: Design Hệ vào/ra (9 tiết) and Implementation, 3rd edition, Prentice-Hall. 2006. (Có mã nguồn kèm theo). Bảo vệ và an ninh (6 tiết) Hà Quang Thụy, Nguyên lý hệ điều hành, NXB KHKT, 2002. Hệ điều hành Linux (optional) + Ôn tập (3 tiết) Robert Love, Linux Kernel Development, Sams Publishing, 2003. Daniel P. Bovet, Marco Cesati, Understanding Linux Kernel, 2nd edition, O'Reilly & Associates, 2002. W. Richard Stevens, Advanced Programming in the UNIX Environment, Addison-Wesley, 1992. 3 4 Giáo trình Bản điện tử của giáo trình Website của Bộ môn Các hệ thống thông tin: http://coltech.vnu.edu.vn/httt Chọn “Góc học tập” ở menu bên trái Chọn “Nguyên lý hệ điều hành” ở phần nội dung chính của trang web Download sách theo chỉ dẫn 5 6 1
  2. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Thi và kiểm tra Kiểm tra giữa kỳ: viết, 45-60 phút Giới thiệu Là điều kiện bắt buộc để được thi cuối kỳ Sau phần quản lý bộ nhớ/lưu trữ Được sử dụng tài liệu Thi cuối kỳ: Thi viết 60-90 phút Được sử dụng tài liệu 7 8 Máy tính - tài nguyên máy tính Hệ điều hành là gì? Tài nguyên: Hệ CPU điều Bộ nhớ trong Đĩa cứng hành Thiết bị ngoại vi (máy in, màn hình, bàn phím, card giao tiếp mạng, USB...) Hệ điều hành là một chương trình “trung gian” (nhân – kernel) giữa NSD và máy tính : Quản lý phần cứng máy tính (các tài nguyên) Cung cấp cho NSD môi trường làm việc tiện lợi và hiệu quả 9 10 Hệ thống máy tính Hai cách nhìn hệ điều hành Người Hệ Phần cứng Các sử điều dụng chương Hệ hành trình điều hệ thống hành Phần cứng: Quản lý & cấp phát tài nguyên để và sử dụng tối đa năng lực phần cứng Phần cứng ứng dụng Người sử dụng: Dễ sử dụng, hiệu quả, ứng dụng phong phú Người sử dụ11 ng 12 2
  3. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Một số loại hệ điều hành Các hệ xử lý theo lô đơn giản Xử lý theo lô (batch processing) Thuật ngữ: Batch processing Đa chương trình (multiprogramming) Các chương trình được đưa vào hàng chờ Phân chia thời gian (time-sharing/multitasking) Máy tính thực hiện tuần tự các chương trình Hệ điều hành cho máy cá nhân của người sử dụng Xử lý song song (parallel) Chương trình không có giao tiếp với người Thời gian thực (real-time) sử dụng Nhúng (embedded) Cầm tay (portable) Đa phương tiện (multimedia) Chuyên dụng (special-purpose) 13 14 Đa chương trình Phân chia thời gian/đa nhiệm Thuật ngữ: time-sharing hoặc multitasking Thuật ngữ: Multiprogramming Thời gian Các chương trình được xếp hàng Người sử dụng Một chương trình được thực hiện và chiếm giữ CPU cho đến khi (1) có yêu cầu vào/ra, hoặc (2) kết thúc Trạm làm việc Khi (1) hoặc (2) xảy ra, chương trình khác sẽ được thực hiện Máy tính Trạm làm việc Tận dụng CPU tốt hơn xử lý theo lô đơn giản 15 16 Một số hệ điều hành Một số hệ điều hành UNIX (UNiplexed Information and Computing Windows (Microsoft): Windows 3.x, Windows Service): (1) AT&T System V (2) Berkeley 95, Windows 98, Windows 2000, Windows (BSD) NT, Windows XP, Windows Vista AIX dựa trên System V (IBM) Mac OS, Mac OS X (Apple Inc.) HP-UX dựa trên BSD (Hewlett-Packard) BeOS IRIX dựa trên System V (Silicon Graphics Inc.) OS 9 Linux OS/2 Solaris, SunOS (Sun Microsystems) DOS Minix PalmOS, Symbian 17 18 3
  4. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Các thành phần của hệ thống Quản lý tiến trình Cấu trúc hệ điều hành Quản lý bộ nhớ trong Quản lý tệp Quản lý vào/ra Quản lý lưu trữ trên bộ nhớ ngoài Liên kết mạng Bảo vệ và an ninh Thông dịch lệnh 19 20 Các dịch vụ của hệ điều hành Các hàm hệ thống Giao diện với người sử dụng Các hàm hệ thống (system calls) cung cấp giao diện lập trình tới các dịch vụ do hệ điều Thực hiện các chương trình hành cung cấp Thực hiện các thao tác vào/ra Ví dụ trong hệ điều hành Unix: Quản lý hệ thống tệp Truyền thông Tạo một tiến trình mới: fork(); Thoát khỏi tiến trình đang thực hiện: exit(1); Phát hiện lỗi fork và exit là các hàm hệ thống (Hàm HT) Cấp phát tài nguyên “Kế toán” Đưa ra các cơ chế bảo vệ và an ninh 21 22 Hàm HT điều khiển tiến trình Hàm HT quản trị tệp Kết thúc tiến trình bình thường/bất thường Tạo, xóa tệp Nạp, thực hiện tiến trình Đóng, mở tệp Tạo, kết thúc tiến trình Đọc, ghi, định vị con trỏ tệp Đọc hoặc thiết lập các thuộc tính cho tiến Đọc, thiết lập thuộc tính của tệp trình Yêu cầu tiến trình vào trạng thái chờ Cấp phát và giải phóng bộ nhớ Xử lý các sự kiện không đồng bộ 23 24 4
  5. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Hàm HT quản trị thiết bị Hàm HT bảo trì thông tin Yêu cầu sử dụng hoặc thôi sử dụng thiết bị Đọc, thiết lập thời gian hệ thống Đọc, ghi, định vị con trỏ Đọc, ghi dữ liệu về hệ thống Đọc, thiết lập thuộc tính cho thiết bị Đọc thuộc tính tệp, thiết bị, tiến trình Attach/detach thiết bị về mặt logic Thiết lập thuộc tính tệp, thiết bị, tiến trình 25 26 Hàm HT về truyền thông Các chương trình hệ thống Các chương trình hệ thống cung cấp môi trường Tạo, hủy các kết nối mạng thuận tiện cho việc thực hiện và phát triển Truyền nhận các thông điệp chương trình. Chúng được phân loại như sau: Thao tác với tệp Lấy thông tin trạng thái truyền thông Thông tin về trạng thái của hệ thống Attach/detach các thiết bị ở xa Sửa đổi tệp Hỗ trợ ngôn ngữ lập trình Nạp và thực hiện chương trình Truyền thông Cách nhìn HĐH của NSD được xác định qua các chương trình hệ thống, không thực sự qua các hàm hệ thống (system calls). 27 28 Cấu trúc HĐH: Đơn giản Cấu trúc HĐH: Phân tầng Thuật ngữ: Simple approach Thuật ngữ: Layered apparoach Ví dụ MS-DOS. (tương tự: UNIX thời gian đầu) Chương trình ứng dụng Chương trình resident Điều khiển thiết bị Điều khiển thiết bị của ROM-BIOS 29 30 5
  6. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Cấu trúc HĐH: Phân tầng Cấu trúc HĐH: Vi nhân Ví dụ UNIX Thuật ngữ: Microkernel Giữ cho nhân có các đủ các chức năng thiết yếu nhất để giảm cỡ Các chức năng khác được đưa ra ngoài nhân Ví dụ: Mach, Tru64 UNIX, QNX 31 32 Cấu trúc HĐH: Module Máy ảo Thuật ngữ: Module approach Thuật ngữ (Virtual Machine) Hiện tại đây là cách tiếp cận tốt nhất (sử Ví dụ: VMware (sản phẩm thương mại) dụng được các kỹ thuật lập trình hướng đối tượng). Ví dụ: Solaris của Sun Microsystem: 33 34 Tóm tắt Tìm hiểu thêm Khái niệm HĐH, nhân Không bắt buộc Hai cách nhìn HĐH từ NSD và hệ thống Bổ sung một hàm hệ thống mới vào nhân Linux và sử dụng hàm đó: Các khái niệm xử lý theo lô, đa chương trình Đọc hướng dẫn trong giáo trình từ trang 74-78 và phân chia thời gian Thử nghiệm trên RedHat Fedora hoặc Các thành phần và dịch vụ của HĐH Ubuntu/Debian Các hàm hệ thống Một số cấu trúc phổ biến của HĐH Máy ảo 35 36 6
  7. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Nguyên lý hệ điều hành Khái niệm tiến trình Nguyễn Hải Châu Khoa Công nghệ thông tin Trường Đại học Công nghệ 1 2 Tiến trình là gì? Tiến trình gồm có… Thuật ngữ: Process Đoạn mã lệnh (code, có sách gọi là text) (tiến trình/quá trình) Đoạn dữ liệu Là một chương trình Đoạn ngăn xếp và heap (stack/heap) đang được thực hiện Các hoạt động hiện tại được thể hiện qua Được xem là đơn vị con đếm lệnh (IP) và nội dung các thanh ghi làm việc trong các HĐH (registers) của bộ xử lý Có hai loại tiến trình: Tiến trình của HĐH Chú ý: Tiến trình của NSD Tiến trình là thực thể chủ động Chương trình là thực thể bị động 3 4 Trạng thái tiến trình Khối điều khiển tiến trình Thuật ngữ: Process Control Block (PCB) Con trỏ Trạng thái tiến trình new terminated Bị ngắt Các thông tin: Số hiệu tiến trình (Process (Interrupt) admitted number) Trạng thái tiến trình exit Con đếm Con đếm (program counter) ready running Các thanh ghi Các thanh ghi (registers) Thông tin về lập lịch Lập lịch Thông tin về bộ nhớ I/O hoặc sự kiện Chờ I/O hoặc đã hoàn tất Giới hạn bộ nhớ Thông tin accounting sự kiện waiting Thông tin vào/ra Danh sách các tệp đang mở 5 6 ….. 1
  8. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Tại sao phải lập lịch? Số lượng NSD, số lượng tiến trình luôn lớn Lập lịch tiến trình hơn số lượng CPU của máy tính rất nhiều Tại một thời điểm, chỉ có duy nhất một tiến trình được thực hiện trên một CPU Vấn đề: Số lượng yêu cầu sử dụng nhiều hơn số lượng tài nguyên đang có (CPU) Do đó cần lập lịch để phân phối thời gian sử dụng CPU cho các tiến trình của NSD và hệ thống 7 8 Hàng chờ lập lịch Hàng chờ lập lịch tiến trình Thuật ngữ: Queue Hàng chờ sẵn CPU sàng thực hiện Các tiến trình chưa được phân phối sử dụng CPU sẽ được đưa vào hàng chờ (queue) Yêu cầu vào/ra Hàng chờ vào/ra Vào/ra Có thể có nhiều hàng chờ trong hệ thống: Hàng chờ sử dụng CPU, hàng chờ sử dụng Hết thời gian sử dụng CPU máy in, hàng chờ sử dụng ổ đĩa CD… Trong suốt thời gian tồn tại, tiến trình phải di Tạo một tiến Tiến trình con trình con thực hiện chuyển giữa các hàng chờ Ngắt xuất hiện Chờ ngắt 9 10 Phân loại các bộ lập lịch Minh họa bộ lập lịch trung hạn Bộ lập lịch dài hạn (long-term scheduler) Các tiến trình swap in swap out Thường dùng trong các hệ xử lý theo lô đang thực hiện Đưa tiến trình từ spool vào bộ nhớ trong dở bị swap out Bộ lập lịch ngắn hạn (short-term scheduler) Còn gọi là bộ lập lịch CPU Hàng chờ sẵn CPU sàng thực hiện Lựa chọn tiến trình tiếp theo được sử dụng CPU Bộ lập lịch trung hạn (medium-term scheduler) Hay còn gọi là swapping (tráo đổi) Vào/ra Hàng chờ vào/ra Di chuyển tiến trình đang trong trạng thái chờ giữa bộ nhớ trong và bộ nhớ ngoài 11 12 2
  9. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Hàng chờ lập lịch tiến trình Chuyển trạng thái swap in swap out Các tiến trình đang thực Thuật ngữ: Context switch hiện dở bị swap out Hàng chờ sẵn Xảy ra khi một tiến trình A bị ngắt ra khỏi CPU sàng thực hiện CPU, tiến trình B bắt đầu được sử dụng CPU Hàng chờ vào/ra Yêu cầu vào/ra Vào/ra Cách thực hiện: Nhân HĐH ghi lại toàn bộ trạng thái của A, lấy từ Hết thời gian PCB (khối điều khiển tiến trình) của A sử dụng CPU Đưa A vào hàng chờ Tạo một tiến Tiến trình con Nhân HĐH nạp trạng thái của B lấy từ PCB của B trình con thực hiện Thực hiện B Chờ ngắt 13 14 Ngắt xuất hiện Chuyển trạng thái Các thao tác với Việc chuyển trạng thái, nói chung, là lãng phí tiến trình thời gian của CPU Do đó việc chuyển trạng thái cần được thực hiện càng nhanh càng tốt Thông thường thời gian chuyển trạng thái mất khoảng 1-1000 micro giây 15 16 Tạo tiến trình Cây tiến trình Tiến trình cha có thể có HĐH cung cấp hàm create-process để tạo nhiều tiến trình con một tiến trình mới Mỗi tiến trình con chỉ có Tiến trình gọi đến hàm create-process là tiến P1 một tiến trình cha trình cha (parent process) Các tiến trình con có Tiến trình được tạo ra sau khi thực hiện hàm P11 P12 thể tạo ra các tiến trình create-process là tiến trình con (child process) con khác… Sau khi tiến trình con được tạo, tiến trình cha P122 P121 P111 có thể: Chờ tiến trình con kết thúc rồi tiếp tục thực hiện Thực hiện “song song” với tiến trình con P1111 P1112 17 18 3
  10. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Minh họa tiến trình cha và con Kết thúc tiến trình Tiến trình Một tiến trình kết thúc khi: cha gọi Thực hiện xong và gọi hàm hệ thống exit (kết Tiến trình con create-process thúc bình thường) Gọi đến hàm abort hoặc kill (kết thúc bất thường khi có lỗi hoặc có sự kiện) Bị hệ thống hoặc tiến trình cha áp dụng hàm abort hoặc kill do: Có thể gọi hoặc Sử dụng quá quota tài nguyên Gọi exit để kết thúc không gọi wait để Tiến trình con không còn cần thiết chờ/không chờ Khi tiến trình cha đã kết thúc (trong một số HĐH) tiến trình con kết thúc 19 20 Minh họa tiến trình trong UNIX Hợp tác giữa các tiến trình #include Các tiến trình có thể hoạt động độc lập hoặc main() hợp tác với nhau { int pid=fork(); /* Tạo tiến trình mới bằng hàm fork() */ Các tiến trình cần hợp tác khi: if (pid
  11. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Truyền thông trực tiếp Minh họa truyền thông trực tiếp Mỗi kết nối được thiết Hai toán tử lập cho một cặp tiến send(P, msg): Gửi msg đến tiến trình P P2 trình duy nhất P1 receive(Q, msg): Nhận msg từ tiến trình Q P3 Mỗi tiến trình chỉ cần Cải tiến: biết tên/số hiệu của tiến send(P, msg): Gửi msg đến tiến trình P trình kia là truyền thông được receive(id, msg): Nhận msg từ bất kỳ tiến trình P6 nào Tồn tại duy nhất một kết nối giữa một cặp P4 P5 tiến trình 25 26 Truyền thông gián tiếp Minh họa truyền thông gián tiếp Hai tiến trình có kết nối Các thông điệp được gửi và nhận qua các nếu sử dụng chung một hộp thư (mailbox) hoặc qua các cổng (port) P2 hộp thư P1 Hai toán tử: P3 Một kết nối có thể sử send(A, msg): Gửi msg đến hộp thư A Hộp dụng cho nhiều tiến thư receive(B, msg): Nhận msg từ hộp thư B trình (>=2) Hộp A thư Minh họa: Topo mạng hình sao Nhiều kết nối có thể tồn B P6 tại giữa một cặp tiến trình (nếu sử dụng các P4 P5 hộp thư khác nhau) 27 28 Vấn đề đồng bộ hóa Các phương thức send/receive send(P, msg) receive(Q, msg) Thuật ngữ: Synchronization Liên quan tới phương thức cài đặt các toán Blocking Tiến trình truyền thông Tiến trình nhận tử send và receive: điệp chờ đến khi msg tạm dừng thực Phương thức có chờ (blocking) được nhận hoặc msg hiện cho đến khi được phân phát đến msg được chuyển Phương thức không chờ (non-blocking) hộp thư tới Non-blocking Tiến trình truyền không Tiến trình nhận trả phải chờ msg đến đích lại kết quả là msg để tiếp tục thực hiện (nếu nhận được) hoặc báo lỗi (nếu chưa nhận được) 29 30 5
  12. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Vấn đề sử dụng vùng đệm Luồng (thread) Các thông điệp nằm trong hàng chờ tạm thời Sinh viên tự tìm hiểu trong giáo trình trang Cỡ của hàng chờ: Chứa được 0 thông điệp: send blocking Chứa được n thông điệp: send non-blocking cho đến khi hàng chờ có n thông điệp, sau đó send blocking Vô hạn: send non-blocking 31 32 Tóm tắt Bài tập Khái niệm tiến trình Viết chương trình C trong Linux/Unix tạo ra 16 tiến trình con. Tiến trình cha chờ cho 16 Các trạng thái, chuyển trạng thái tiến trình tiến trình con này kết thúc rồi mới kết thúc Khối điều khiển tiến trình bằng hàm exit. Sử dụng các hàm fork và Lập lịch tiến trình, các loại bộ lập lịch wait để thực hiện yêu cầu. Truyền thông giữa các tiến trình Hãy tìm một số ví dụ thực tế minh họa cho Gián tiếp, trực tiếp các khái niệm lập lịch/hàng chờ trong tình Blocking và non-blocking (đồng bộ hóa) huống có nhiều người sử dụng và ít tài Vấn đề sử dụng vùng đệm (buffer) nguyên. 33 34 Bài tập Hãy viết chương trình minh họa cho các cơ chế truyền thông non-blocking, blocking Hãy viết chương trình minh họa các cơ chế truyền thông điệp sử dụng buffer có độ dài n trong hai trường hợp: n>0 và n=0 Chú ý: Để làm hai bài tập trên cần sử dụng hai tiến trình; có thể thực hiện bài tập với UNIX/Linux hoặc Windows 35 6
  13. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Nguyên lý hệ điều hành Lập lịch CPU Nguyễn Hải Châu Khoa Công nghệ thông tin Trường Đại học Công nghệ 1 2 Tại sao phải lập lịch CPU? Hàng chờ lập lịch tiến trình Số lượng NSD, số lượng tiến trình luôn lớn Hàng chờ sẵn CPU sàng thực hiện hơn số lượng CPU của máy tính rất nhiều Tại một thời điểm, chỉ có duy nhất một tiến Yêu cầu vào/ra Hàng chờ vào/ra Vào/ra trình được thực hiện trên một CPU Hết thời gian Vấn đề: sử dụng CPU Nhu cầu sử dụng nhiều hơn tài nguyên (CPU) đang có Tạo một tiến Tiến trình con trình con thực hiện Do đó cần lập lịch để phân phối thời gian sử dụng CPU cho các tiến trình của NSD và hệ thống Ngắt xuất hiện Chờ ngắt 3 4 CPU-burst và IO-burst Trong suốt thời gian tồn tại trong hệ thống, tiến trình được xem như thực hiện hai loại Microsoft Office công việc chính: Outlook CPU-burst Adobe Khi tiến trình ở trạng thái running: Sử dụng CPU Photoshop (thuật ngữ: CPU-burst) CPU-burst Khi tiến trình thực hiện các thao tác vào ra: Sử dụng thiết bị vào/ra (thuật ngữ: I/O burst) 5 6 1
  14. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Hai loại tiến trình chính Bộ lập lịch ra hoạt động khi… Căn cứ theo cách sử dụng CPU của tiến Một tiến trình chuyển từ trạng thái running 1. trình, có hai loại tiến trình: sang waiting Tiến trình loại CPU-bound: Tiến trình có một hoặc Một tiến trình chuyển từ trạng thái running 2. nhiều phiên sử dụng CPU dài sang ready Tiến trình loại I/O-bound: Tiến trình có nhiều Một tiến trình chuyển từ trạng thái waiting 3. phiên sử dụng CPU ngắn (tức là thời gian vào ra sang ready nhiều) Một tiến trình kết thúc 4. 7 8 Các phương pháp lập lịch Lập lịch non-preemptive Một tiến trình giữ CPU đến khi nó kết thúc new terminated Bị ngắt hoặc chuyển sang trạng thái waiting. (Interrupt) 4 admitted exit Ví dụ: Microsoft Windows 3.1, Apple 2 Macintosh sử dụng lập lịch non-preemptive ready running Có thể sử dụng trên nhiều loại phần cứng vì 3 Lập lịch không đòi hỏi timer I/O hoặc sự kiện Chờ I/O hoặc đã hoàn tất sự kiện waiting 1 1 và 4: Lập lịch non-preemptive Ngược lại: Lập lịch preemptive 9 10 Lập lịch preemptive Bộ điều phối (dispatcher) Hiệu quả hơn lập lịch non-preemptive Nhiệm vụ: Chuyển trạng thái (context switch) Thuật toán phức tạp hơn non-preemptive và sử dụng nhiều tài nguyên CPU hơn Chuyển về user-mode Thực hiện tiến trình theo trạng thái đã lưu Ví dụ: Microsoft Windows XP, Linux, UNIX Cần hoạt động hiệu quả (tốc độ nhanh) sử dụng lập lịch preemptive Thời gian cần để bộ điều phối dừng một tiến trình và thực hiện tiến trình khác gọi là độ trễ (latency) của bộ điều phối 11 12 2
  15. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Các tiêu chí đánh giá lập lịch Các tiêu chí đánh giá lập lịch Khả năng tận dụng CPU (CPU utilization): Thời gian hoàn thành (turnaround time): Thể hiện qua tải CPU – là một số từ 0% đến tturnaround = to-ti với ti là thời điểm tiến trình vào hệ 100%. thống, to là thời điểm tiến trình ra khỏi hệ thống (kết thúc thực hiện) Trong thực tế các hệ thống thường có tải từ 40% Như vậy tturnaround là tổng: thời gian tải vào bộ nhớ, (tải thấp) đến 90% (tải cao) thời gian thực hiện, thời gian vào ra, thời gian Thông lượng (throughput): Là số lượng các nằm trong hàng chờ… tiến trình hoàn thành trong một đơn vị thời gian 13 14 Các tiêu chí đánh giá lập lịch Các tiêu chí đánh giá lập lịch Thời gian chờ (waiting time): Là tổng thời Thời gian đáp ứng (response time): Là gian tiến trình phải nằm trong hàng chờ khoảng thời gian từ khi tiến trình nhận được ready (twaiting) một yêu cầu cho đến khi bắt đầu đáp ứng yêu cầu đó Các thuật toán lập lịch CPU không có ảnh hưởng đến tổng thời gian thực hiện một tiến trình mà chỉ tres = tr – ts, trong đó tr là thời điểm nhận yêu có ảnh hưởng đến thời gian chờ của một tiến cầu, ts là thời điểm bắt đầu đáp ứng yêu cầu trình trong hàng chờ ready Thời gian chờ trung bình (average waiting time): taveragewaiting=twaiting / n, n là số lượng tiến trình trong hàng chờ 15 16 Đánh giá các thuật toán lập lịch Tiêu chí Giá trị thấp Giá trị cao Các thuật toán lập lịch Khả năng tận dụng CPU Xấu Tố t (CPU utilization) Thông lượng (throughput) Xấu Tố t Thời gian hoàn thành Tố t Xấu (turnaround time) Thời gian chờ (waiting time) Tố t Xấu -> Thời gian chờ trung bình Thời gian đáp ứng (response Tố t Xấu 17 18 time) 3
  16. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com FCFS (First Come First Served) Ví dụ FCFS 1a Tiến trình nào có yêu cầu sử dụng CPU Giả sử có 3 tiến trình P1, P2, P3 với thời gian trước sẽ được thực hiện trước thực hiện tương ứng là 24ms, 3ms, 6ms Ưu điểm: Thuật toán đơn giản nhất Giả sử 3 tiến trình xếp hàng theo thứ tự P1, P2, P3. Khi đó ta có biểu đồ Gantt như sau: Nhược điểm: Hiệu quả của thuật toán phụ thuộc vào thứ tự của các tiến trình trong hàng P1 P2 P3 chờ, vì thứ tự này ảnh hưởng rất lớn đến thời 0 24 27 33 gian chờ trung bình (average waiting time) Thời gian chờ của các tiến trình là: P1 chờ 0ms, P2 chờ 24ms, P3 chờ 27ms Thời gian chờ trung bình: (0+24+27)/3=17ms 19 20 Ví dụ FCFS 1b Hiện tượng “đoàn hộ tống” Xét ba tiến trình trong ví dụ 1a với thứ tự xếp Thuật ngữ: convoy effect hàng P3, P2, P1 Xảy ra khi có một tiến trình “lớn” P nằm ở đầu Biểu đồ Gantt: hàng chờ và nhiều tiến trình “nhỏ” Qi xếp hàng sau P. P3 P2 P1 “Lớn”: Sử dụng nhiều thời gian CPU và vào ra 0 6 9 33 “Nhỏ”: Sử dụng ít thời gian CPU và vào ra Thời gian chờ của các tiến trình là: P3 chờ 0ms, P2 chờ 6ms, P3 chờ 9ms Thuật toán lập lịch được sử dụng là FCFS.: Thời gian chờ trung bình: (0+6+9)/3=5ms Hiện tượng xảy ra: CPU, thiết bị vào ra có nhiều thời gian rỗi, thời gian chờ trung bình của các Thời gian chờ trung bình thấp hơn thời gian tiến trình cao chờ trung bình trong ví dụ 1a 21 22 Convoy effect: Thời gian sử Ví dụ convoy effect dụng CPU và thiết bị vào ra Q3(10) Q2(10) Q1(10) P (40) Hàng chờ sẵn 0 130 140 150 160 180 40 50 60 70 90 CPU sàng thực hiện CPU Q1 Q2 Q3 Rỗi Q1 Q2 Q3 Rỗi P P Yêu cầu vào/ra Hàng chờ vào/ra Vào/ra P (50) Q1(10) Q2(10) Q3(10) 0 40 90 100 110 120 130 180 Thiết bị Hết thời gian vào ra Q2 Q3 Rỗi sử dụng CPU P Rỗi Q1 P Giả sử P là tiến trình “lớn” có chu kỳ sử dụng CPU trong 40ms Tạo một tiến Tiến trình con và vào ra trong 50ms trình con thực hiện Q1, Q2, Q3 là 3 tiến trình “nhỏ” có chu kỳ sử dụng CPU trong 10ms và vào ra trong 10ms Ngắt xuất hiện Chờ ngắt Thứ tự xếp hàng: P, Q1, Q2, Q3 23 24 4
  17. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com SJF (Shortest Job First) SJF (Shortest Job First) Với lập lịch dài hạn: Có thể biết tnextburst vì có Với SJF, tham số lập lịch có thêm độ dài của tham số chỉ ra thời gian chạy của tiến trình khi phiên sử dụng CPU tiếp theo tnextburst đưa tiến trình vào hệ thống (job submit) Tiến trình có tnextburst nhỏ nhất sẽ được lập Khó khăn: Chỉ có thể phỏng đoán được tnextburrt lịch sử dụng CPU trước với lập lịch ngắn hạn Nếu hai tiến trình có tnextburst bằng nhau thì Đọc ở nhà: Dự đoán tnextburst bằng công thức FCFS được áp dụng trung bình mũ (exponential average) trang 160-162 trong giáo trình SJF không tối ưu được với lập lịch ngắn hạn SJF thường được áp dụng cho lập lịch dài hạn 25 26 Lập lịch có độ ưu tiên Lập lịch có độ ưu tiên Hai cách xác định độ ưu tiên: Thuật ngữ: Priority scheduling Độ ưu tiên trong: Được tính toán dựa trên các Mỗi tiến trình được gắn một tham số lập lịch gọi là độ tham số định lượng của tiến trình như giới hạn về ưu tiên p, với p là một số thực thời gian, bộ nhớ, số file đang mở, thời gian sử Tiến trình có độ ưu tiên cao nhất được sử dụng CPU dụng CPU Qui ước trong môn học này: Độ ưu tiên ngoài: Dựa vào các yếu tố như mức Tiến trình P1 và P2 có độ ưu tiên p1, p2 tương ứng độ quan trọng, chi phí thuê máy tính… p1>p2 có nghĩa là tiến trình P1 có độ ưu tiên thấp hơn P2 Chờ không xác định: Một tiến trình có độ ưu SJF là trường hợp đặc biệt của lập lịch có ưu tiên với tiên thấp có thể nằm trong hàng chờ trong ưu tiên của các tiến trình là nghịch đảo độ dài phiên một khoảng thời gian dài nếu trong hàng chờ sử dụng luôn có các tiến trình có độ ưu tiên cao hơn 27 28 Lập lịch có độ ưu tiên Ví dụ lập lịch có độ ưu tiên Tiến Thời gian Độ ưu Xét 5 tiến trình như trong Để tránh hiện tượng chờ không xác định, có bảng với thứ tự trong hàng trình thực hiện tiên thêm tham số tuổi để xác định thời gian tiến chờ là P1, P2, P3, P4, P5 (ms) trình thời gian nằm trong hàng chờ Sử dụng thuật toán lập lịch P1 10 3 Tham số tuổi được sử dụng để làm tăng độ có ưu tiên, ta có thứ tự P2 1 1 thực hiện của các tiến trình ưu tiên của tiến trình như sau biểu đồ dưới P3 2 4 Ví dụ thực tế: Khi bảo dưỡng máy tính IBM Thời gian chờ trung bình là P4 1 5 7094 của MIT năm 1973, người ta thấy một (1+6+16+18)/5=8.2ms P5 5 2 tiến trình nằm trong hàng chờ từ năm 1967 nhưng vẫn chưa được thực hiện P2(1) P5(2) P1(3) P3(4) P4(5) 29 30 1 0 6 16 19 18 5
  18. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Round-robin (RR) Round-robin (RR) Hiệu quả của RR phụ thuộc độ lớn của Còn gọi là lập lịch quay vòng tquantum Được thiết kế để áp dụng cho các hệ phân Nếu tquantum nhỏ thì hiệu quả của RR giảm vì bộ chia thời gian (time-sharing) điều phối phải thực hiện nhiều thao tác chuyển RR hoạt động theo chế độ preemptive trạng thái, lãng phí thời gian CPU Nếu tquantum lớn thì số thao tác chuyển trạng thái Tham số lượng tử thời gian (time quantum) giảm đi tquantum: Mỗi tiến trình được sử dụng CPU Nếu tquantum rất nhỏ (ví dụ 1ms) thì RR được trong nhiều nhất bằng tquantum, sau đó đến gọi là processor sharing lượt tiến trình khác Nếu tquantum = ∞ thì RR trở thành FCFS 31 32 Ví dụ RR Lập lịch với hàng chờ đa mức Giả sử có 3 tiến trình P1, P2, P3 với thời gian thực Thuật ngữ: Multilevel queue scheduling hiện tương ứng là 24ms, 3ms, 6ms, thứ tự trong Được sử dụng khi ta có thể chia các tiến hàng chờ P1, P2, P3 ,vào hàng chờ cùng thời điểm 0 trình thành nhiều lớp khác nhau để lập lịch Giả sử tquantum=4ms theo các tiêu chí khác nhau, ví dụ: RR lập lịch các tiến trình như sau: Lớp các tiến trình có tương tác (interactive hoặc foreground process) cần có độ ưu tiên cao hơn P1 P2 P3 P1 P3 P1 P1 P1 P1 4 7 11 15 17 21 25 29 33 Lớp các tiến trình chạy nền (background) thường 0 không có tương tác với NSD: Độ ưu tiên thấp hơn Thời gian chờ Thời gian chờ trung bình: (9+4+11)/3=8ms P1: 0+(11-4)+(17-15)=9ms P2: 4ms 33 34 P3: 7+(15-11)=11ms Lập lịch với hàng chờ đa mức Ví dụ hàng chờ đa mức Thuật toán lập lịch với hàng chờ đa mức chia Ví dụ các hàng chờ đa mức có độ ưu tiên hàng chờ ready thành nhiều hàng chờ con giảm dần: khác nhau, mỗi hàng chờ con được áp dụng Hàng chờ các tiến trình hệ thống một loại thuật toán khác nhau, ví dụ: Hàng chờ các tiến trình có tương tác Hàng chờ các tiến trình background: FCFS Hàng chờ các tiến trình là editor Hàng chờ các tiến trình có tương tác:RR Hàng chờ các tiến trình hoạt động theo lô Các tiến trình được phân lớp dựa vào đặc Hàng chờ các tiến trình thực tập của sinh viên tính như bộ nhớ, độ ưu tiên, … Cần có thuật toán lập lịch cho các hàng chờ con, ví dụ: preemptive có độ ưu tiên cố định 35 36 6
  19. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Lập lịch với hàng chờ đa mức Lập lịch với hàng chờ đa mức có phản hồi có phản hồi Thuật ngữ: Multilevel feedback-queue Cách thực hiện: scheduling Độ dài phiên sử dụng CPU và thời gian đã nằm trong hàng chờ là tiêu chuẩn chuyển tiến trình Thuật toán lập lịch kiểu này nhằm khắc phục giữa các hàng chờ nhược điểm không mềm dẻo của lập lịch với Tiến trình chiếm nhiều thời gian CPU sẽ bị hàng chờ đa mức chuyển xuống hàng chờ có độ ưu tiên thấp Ý tưởng chính: Cho phép tiến trình chuyển từ Tiến trình nằm lâu trong hàng chờ sẽ được hàng chờ này sang hàng chờ khác, trong khi chuyển lên hàng chờ có độ ưu tiên cao hơn lập lịch với hàng chờ đa mức không cho phép điều này 37 38 Các tham số của bộ lập lịch hàng chờ đa mức có phản hồi Các thuật toán lập lịch khác Sinh viên tìm hiểu trong giáo trình: Số lượng các hàng chờ Lập lịch đa xử lý Thuật toán lập lịch cho mỗi hàng chờ Lập lịch thời gian thực Phương pháp tăng độ ưu tiên cho một tiến trình Phương pháp giảm độ ưu tiên cho một tiến trình Phương pháp xác định hàng đợi nào để đưa một tiến trình vào 39 40 Mô hình xác định Các phương pháp đánh Thuật ngữ: Deterministic modeling giá thuật toán lập lịch Dựa vào các trường hợp cụ thể (chẳng hạn các ví dụ đã nói trong bài giảng này) để rút ra các kết luận đánh giá Ưu điểm: Nhanh và đơn giản Nhược điểm: Không rút ra được kết luận đánh giá cho trường hợp tổng quát 41 42 7
  20. Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Mô hình hàng chờ Mô phỏng Thuật ngữ: Queueing model Thuật ngữ: Simulation Dựa trên lý thuyết xác suất, quá trình ngẫu nhiên. Tài Thực hiện các tình huống giả định trên máy liệu tham khảo: tính để đánh giá hiệu quả của các thuật toán Leonard Kleinrock, Queueing Systems: Volume I – Theory lập lịch, kiểm nghiệm các kết quả lý thuyết (Wiley Interscience, New York, 1975) Mô phỏng thường tốn thời gian CPU và Leonard Kleinrock, Queueing Systems: Volume II – Computer Applications (Wiley Interscience, New York, 1976) không gian lưu trữ Ưu điểm: So sánh được các thuật toán lập lịch trong Được sử dụng nhiều trong công nghiệp một số trường hợp Ví dụ các hệ mô phỏng mạng (có module Hạn chế: Phức tạp về mặt toán học, lớp các thuật hàng chờ): OPNET, NS-2, Qualnet toán phân tích so sánh được còn hạn chế 43 44 Cài đặt thử trong thực tế Tóm tắt Mô phỏng có thể xem như “qui nạp không Khái niệm lập lịch, các tiêu chí đánh giá thuật hoàn toàn” toán lập lịch Có thể xây dựng hệ thống thử trong thực tế Các phương thức hoạt động preemptive và non-preemptive Ưu điểm: Đánh giá được hiệu quả thực sự khi sử dụng Các thuật toán lập lịch FCFS, SJF, ưu tiên, RR Nhược điểm: Lập lịch với hàng chờ đa mức, có và không Chi phí cao có phản hồi Hành vi của người sử dụng có thể thay đổi theo môi trường hệ thống Các phương pháp đánh giá thuật toán lập lịch 45 46 Bài tập Bài tập Thực hiện ví dụ RR với lượng tử thời gian Hãy xây dựng một ví dụ về hiện tượng convoy 2ms, 6ms và 6ms. effect sao cho thời gian rỗi của thiết bị vào ra ít hơn thời gian rỗi của CPU. Giả sử có 4 tiến Tính thời gian chờ trung bình của các tiến trình trình, trong đó P là tiến trình “lớn”, Q1, Q2, Q3 trong các trường hợp này. là các tiến trình “nhỏ” được nằm trong hàng Khi lượng tử thời gian thay đổi, thời gian chờ trung bình thay đổi thế nào? chờ theo thứ tự: P, Q1, Q2, Q3 Tính thời gian hoàn thành (turnaround time) của Tìm hai ví dụ trong thực tế về hàng chờ đa tất cả các tiến trình trong các trường hợp trên mức và hàng chờ đa mức có phản hồi và giải Nhận xét về sự thay đổi thời gian hoàn thành của thích các ví dụ này. các tiến trình khi lượng tử thời gian thay đổi 47 48 8
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2