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

Đề tài: Xây dựng chương trình mô phỏng các giải thuật định thời cho CPU

Chia sẻ: Huỳnh Thanh Phong | Ngày: | Loại File: DOC | Số trang:32

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

Hệ điều hành là phần gắn bó trực tiếp với phần cứng và là môi trường để cho các chương trình ứng dụng khác chạy trên nó. Với chức năng quản lý và phân phối tài nguyên một cách hợp lý, đồng thời giả lập một máy tính mở rộng và tạo giao diện tiện lợi với người sử dụng, hệ điều hành là một thành phần then chốt không thể thiếu được trong mỗi một hệ thống máy tính điện tử. Một trong những chức năng quan trọng của hệ điều hành là quản lý CPU. Trong môi trường xử...

Chủ đề:

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

Lưu

Nội dung Text: Đề tài: Xây dựng chương trình mô phỏng các giải thuật định thời cho CPU

  1. TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN MẠNG VÀ TRUYỀN THÔNG    ĐỒ ÁN HỆ ĐIỀU HÀNH Đề tài: Xây dựng chương trình mô phỏng các giải thuật định thời cho CPU : Lê Phương Tiến Sinh viên 07T2 Hà Phước Việt 07T1 Cán bộ hướng dẫn : Ths Nguyễn Văn Nguyên Đà Nẵng 2010
  2. Bộ môn Mạng và Truyền Thông 4 MỤC LỤC TỔNG QUAN VỀ ĐỀ TÀI CHƯƠNG 1. TỔNG QUAN VỀ ĐỀ TÀI..............................................................5 1.1. BỐI CẢNH VÀ LÝ DO THỰC HIỆN ĐỀ TÀI......................................................................5 1.2. MỤC TIÊU CỦA ĐỀ TÀI..............................................................................................5 CHƯƠNG 2. CƠ SỞ LÝ THUYẾT......................................................................6 2.1. GIỚI THIỆU..............................................................................................................6 2.1.1. Mục tiêu lập lịch................................................................................6 2.1.2. Các đặc điểm của tiến trình..............................................................6 2.1.3. Điều phối không độc quyền và điều phối độc quyền.....................7 2.2. CÁC KHÁI NIỆM CƠ BẢN............................................................................................9 2.2.1. Khái niệm giờ CPU............................................................................9 2.2.2. Các trạng thái của tiến trình liên quan đến giờ CPU.......................9 2.2.3. Khái niệm lập lịch cho CPU............................................................11 2.3. CÁC THUẬT TOÁN LẬP LỊCH..................................................................................12 2.3.1. First Come First Served(FCFS)........................................................12 2.3.2. Round robin(RR)...............................................................................12 2.3.3. Shortest Job First(SJF)......................................................................14 2.3.4. Shortest Remain Time(SRT).............................................................15 CHƯƠNG 3. CÀI ĐẶT THUẬT TOÁN..............................................................16 3.1. MÔ HÌNH CÀI ĐẶT THUẬT TOÁN................................................................................16 3.1.1. Cấu trúc dữ liệu...............................................................................16 3.1.2. Thuật toán xử lý chung....................................................................18 3.2. THUẬT TOÁN..........................................................................................................20 3.2.1. First In First Out(FIFO)....................................................................20 3.2.2. Round Robin(RR).............................................................................22 3.2.3. Shortest Job First(SRT)....................................................................24 3.2.4. Shortest Remain Time(SRT).............................................................26 CHƯƠNG 4. XÂY DỰNG CHƯƠNG TRÌNH DEMO..................................... 28 4.1. CÁC MODUN CHÍNH.................................................................................................28 4.2. MÔI TRƯỜNG PHÁT TRIỂN.......................................................................................28 4.3. GIAO DIỆN CỦA CHƯƠNG TRÌNH...............................................................................28 4.3.1. About.................................................................................................28 4.3.2. Input..................................................................................................29 4.3.3. Output................................................................................................31 4.3.4. Control..............................................................................................31 4.4. ĐÁNH GIÁ VÀ NHẬN XÉT.........................................................................................33 Lê Phương Tiến – Hà Phước Việt
  3. Xây dựng chương trình mô phỏng giải thuật định thời CPU 5 T Ổ NG QUAN V Ề Đ Ề TÀI Chương 1. 1.1. Bối cảnh và lý do thực hiện đề tài Hệ điều hành là phần gắn bó trực tiếp với ph ần c ứng và là môi tr ường đ ể cho các chương trình ứng dụng khác chạy trên nó. V ới ch ức năng qu ản lý và phân ph ối tài nguyên một cách hợp lý, đồng thời giả lập m ột máy tính m ở r ộng và t ạo giao diện tiện lợi với người sử dụng, hệ điều hành là m ột thành ph ần then ch ốt không thể thiếu được trong mỗi một hệ thống máy tính điện tử. Một trong những chức năng quan trọng c ủa h ệ đi ều hành là qu ản lý CPU. Trong môi trường xử lý đa chương, có thể xảy ra tình huống nhi ều ti ến trình đ ồng th ời sẵn sàng để xử lý. Mục tiêu của các hệ phân chia th ời gian(time-sharing) là chuy ển đổi CPU qua lại giữa các tiến trình một cách th ường xuyên đ ể nhi ều ng ười s ử d ụng có thể tương tác cùng lúc với từng chương trình trong quá trình x ử lý. Để thực hiện được mục tiêu này, hệ điều hành phải lựa chọn tiến trình đ ược xử lý tiếp theo. Bộ điều phối sẽ sử dụng một giải thuật điều ph ối thích h ợp đ ể th ực hiện nhiệm vụ này. Một thành phần khác của hệ điều hành cũng ti ểm ẩn trong công tác điều phối là bộ điều phối(dispatcher). Bộ phân ph ối sẽ ch ịu trách nhi ệm chuy ển đổi ngữ cảnh và trao CPU cho tiến trình được chọn b ởi b ộ điều ph ối để x ử lý. Vì những lợi ích lơn lao mà giải thuật đi ều ph ối CPU đem l ại và đ ể tìm hi ểu kĩ hơn về nguyên tắc hoạt động của chúng, chúng em quyết đ ịnh ch ọn đ ề tài: Xây dựng chương trình mô phỏng các giải thuật định thời cho CPU. 1.2. Mục tiêu của đề tài − Tìm hiểu các giải thuật: First In First Out(FIFO), Round Robin(RR), Shortest Job First(SJF), Shortest Remain Time(SRT). − Chỉ ra được ưu và nhược điểm cả các giải thuật lập lịch CPU. − Xây dựng chương trình mô phỏng các giải thuật đã tìm hi ểu và k ết qu ả demo. Lê Phương Tiến – Hà Phước Việt
  4. Bộ môn Mạng và Truyền Thông 6 C Ơ S Ở LÝ THUY Ế T Chương 2. 2.1. Giới thiệu 2.1.1. Mục tiêu lập lịch Bộ điều phối không cung cấp c ơ chế, mà đưa ra các quy ết đ ịnh. Các h ệ đi ều hành xây dựng nhiều chiến lượt khác nhau đ ể th ực hi ện việc đi ều ph ối, nh ưng t ựu chung cần đạt được các mục tiêu sau: − Sự công bằng: các tiến trình chia sẻ CPU m ột cách công b ằng không có tiến trình nào phải đợi vô hạn để được cấp phát CPU − Tính hiệu quả: Hệ thống phải tận dụng được CPU 100% thời gian − Thời gian đáp ứng hợp lý: cực tiểu hóa thời gian h ồi đáp cho các t ương tác của người sử dụng − Thời gian lưu lại trong hệ thống: c ực tiểu hóa th ời gian hoàn t ất các tác vụ xử lý theo lô − Thông lượng tối đa: cực đại hóa số công việc đ ược x ử lý trong m ột đ ơn vị thời gian Tuy nhiên thường không thể thỏa mãn tất c ả các m ục tiêu k ể trên vì b ản thân chũng có sự mâu thuẩn với nhau mà chỉ có th ể th ể dung hòa chúng ở m ức đ ộ nào đó. 2.1.2. Các đặc điểm của tiến trình Điều phối hoạt động của các tiến trình là m ột vấn đề rất ph ức t ạp, đòi h ỏi h ệ điều hành khi giải quyết phải xem xét nhiều yếu t ố khác nhau đ ể có th ể đ ạt đ ược những mục tiêu đề ra. Một số đặc tính của tiến trình c ần đ ược quan tâm nh ư tiêu chuẩn điều phối: − Tính hướng xuất/ nhập của tiến trình: Khi một tiến trình được nhận CPU, chủ yếu nó chỉ sử dụng CPU đến khi phát sinh m ột yêu c ầu nhập xu ất? Lê Phương Tiến – Hà Phước Việt
  5. Xây dựng chương trình mô phỏng giải thuật định thời CPU 7 Hoạt động của các tiến trình như thế thường bao gồm nhi ều l ượt s ử dụng CPU, mỗi lượt trong một thời gian khá ngắn. − Tính hướng xử lý của tiến trình: Khi một tiến trình đ ược nh ận CPU, nó có khuynh hướng sử dụng CPU đến khi hết th ời gian dành cho nó? Ho ạt động của các tiến trình như thế thường bao gồm m ột s ố ít l ượt s ử d ụng CPU, nhưng mỗi lượt trong một thời gian đủ dài. − Tiến trình tương tác hay xử lý theo lô: Người sử dụng theo ki ểu t ương tác thường yêu cầu được hồi đáp tức thời đối với các yêu c ầu c ủa h ọ, trong khi các tiến trình của các tác vụ đ ược x ử lý theo lô nói chung có th ể trì hoãn trong một thời gian chấp nhận được. − Độ ưu tiên của tiến trình: Các tiến trình có th ế đ ược phân c ấp theo m ột số tiêu chuẩn đánh giá nào đó, một cách h ợp lý, các ti ến trình quan tr ọng hơn(có độ ưu tiên cao hơn) cần được ưu tiên cao hơn. − Thời gian đã sử dụng CPU của tiến trình: m ột s ố quan điểm ưu tiên ch ọn những tiến trình đã sử dụng CPU nhiều th ời gian nhất vì hy v ọng chúng sẽ cần ít thowig gian nhất để hoàn tất và rời kh ỏi h ệ th ống. Tuy nhiên cũng có quan ddierm cho răng các ti ến trình nh ận đ ược CPU trong ít th ời gian là những tiến trình đã phải chờ lâu nhất, do vậy ưu tiên ch ọn chúng. − Thời gian còn lại tiến trình cần để hoàn tất: Có th ể gi ảm thi ểu th ời gian chờ trung bình của các tiến trình bằng cách cho các ti ến trình c ần ít th ời gian nhất để hoàn tát được thực hiện trước. Tuy nhiên đáng ti ếc là r ất hiếm khi biết được tiến trình cần bao nhiêu th ời gian nữa đ ể k ết thúc x ử lý. 2.1.3. Điều phối không độc quyền và điều phối độc quyền Thuật toán điều phối cần xem xét và quyết định th ời đi ểm chuyển đ ổi CPU gi ữa các tiến trình. Hệ điều hành các thể th ực hiện c ơ ch ế đi ều ph ối theo nguyên lý đ ọc quyền hoặc không đọc quyền: Lê Phương Tiến – Hà Phước Việt
  6. Bộ môn Mạng và Truyền Thông 8 − Điều phối độc quyền: Nguyến lý điều phối độc quyền cho phép m ột ti ến trình khi nhậ được CPU sẽ có quyền độc chiếm CPU đ ến khi hoàn t ất x ử lý hoặc tự nguyện giải phóng CPU. Khi đó quyết định đi ều ph ối CPU s ẽ xảy ra trong các tình huống sau: o Khi tiến trình chuyển từ trạng thái đang xử lý (running) sang tr ạng thái bị blocked (ví dụ chờ một thao tác nhập xuất hay ch ờ m ột ti ến trình con kết thúc…). o Khi tiến trình kết thúc. Các giải thuật độc quyền thường đơn giản và dễ cài đặt. Tuy nhiên chúng thường không thích hợp với các hệ th ống t ổng quát nhi ều ng ười dùng, vì nếu cho phép một tiến trình có quyền xử lý bao lâu tùy ý, có nghĩa là ti ến trình này đã giữ CPU một thời gian không xác đ ịnh, có th ể ngăn c ản những tiến trình còn lại trong hệ thống có một c ơ hội để xử lý. − Điều phối không độc quyền: Ngược với nguyên lý độc quyền, điều ph ối theo nguyên lý không đọc quyền cho phép t ạm d ừng hoạt đ ộng c ủa m ột tiến trình sẵn sàng xử lý. Khi một tiến trình nh ận được CPU, nó v ẫn được sử dụng CPU đến khi hoàn tất hoặc tự nguyện giải phóng CPU, nhưng khí có một tiến trình khác có đ ộ ưu tiên có th ể dành quy ền s ử dụng CPU của tiến trình ban đầu. Như vậy là ti ến trình có th ế b ị t ạm dừng hoạt động bất cứ lúc nào mà không được báo trước, đ ể ti ến trình khác xử lý. Các quyết định điều phối xảy ra khi: o Khi tiến trình chuyển từ trạng thái đang x ử lý(running) sang tr ạng thái bị khóa blocked. o Khi tiến trình chuyển từ trạng thái đang x ử lý(running) sang tr ạng thái ready(vì xảy ra một ngắt). o Khi tiến trình chuyển từ trạng thái chờ (blocked) sang tr ạng thái ready (ví dụ một thao tác nhập xuất hoàn tất). o Khi tiến trình kết thúc. Lê Phương Tiến – Hà Phước Việt
  7. Xây dựng chương trình mô phỏng giải thuật định thời CPU 9 Trong các hệ thống sử dụng nguyên lý điều phối độc quyền có th ể xảy ra tình trạng các tác vụ cần thời gian xử lý ngắn phải ch ờ tác v ụ x ử lý v ới thời gian rất dài hoàn tất! Nguyên lý điều phối đ ộc quyền th ường ch ỉ thích hợp với các hệ xử lý theo lô. Đối với các hệ thống tương tác (time sharing), các h ệ th ời gian th ực (real time), cần phải sử dụng nguyên lý điều phối không độc quyền để các tiến trình quan trọng có c ơ hội hồi đáp kịp th ời. Tuy nhiên th ực hi ện hi ện đi ều phối theo nguyên lý không độc quyền đòi hỏi nhưng c ơ ch ế ph ức t ạp trong việc phân định độ ưu tiên, và phát sinh thêm chi phí khi chuy ển đ ổi CPU qua lại giữa các tiến trình. 2.2. Các khái niệm cơ bản 2.2.1. Khái niệm giờ CPU CPU là một loại tài nguyên quan trọng của máy tính. M ọi ti ến trình mu ốn ho ạt động được đều phải có sự phục vụ của CPU(để xử lý, tính toán…). Th ời gian mà CPU phục vụ cho tiến trình hoạt động được gọi là giờ CPU. Tại mỗi thời điểm nhất, chỉ có một tiến trình đ ược phân ph ối gi ờ CPU đ ể ho ạt động(thực hiện các lệnh của mình). 2.2.2. Các trạng thái của tiến trình liên quan đến giờ CPU Trong chế độ đa chương trình, có ba trạng thái c ủa ti ến trình liên quan m ật thi ết đến giờ CPU bao gồm: Ready Running Lê Phương Tiến – Hà Phước Việt
  8. Bộ môn Mạng và Truyền Thông 10 Waiting − Sẵn sàng(ready): là trạng thái mà tiến trình đ ược phân ph ối đ ầy đ ủ m ọi tài nguyên cần thiết và đang chờ giờ CPU. − Thực hiện(running): là trạng thái mà tiến trình đ ược phân ph ối đ ầy đ ủ mọi tài nguyên cần thiết và giờ CPU. − Đợi(waiting): là trạng thái tiến trình không th ực hiện đ ược vì thi ếu m ột vài điều kiện nào đó(đợi dữ liệu vào/ra, đợi tài nguyên b ổ sung…). Khi s ự kiện mà nó chờ đợi xuất hiện, tiến trình sẽ quay lại trạng thái sẵn sàng. Như vậy, trong suốt thời gian tồn tại của mình, các ti ến trình s ẽ tuân th ủ theo s ơ đồ thực hiện sau: Sử dụng CPU Sử dụng CPU Sử dụng CPU Bắt đầu Kết thúc ……… ……… Đợi I/O đợi I/O Một tiến trình đang trong trạng thái th ực hi ện, nó có th ể r ời kh ỏi tr ạng thái b ởi một trong ba lý do: − Tiến trình đã hoàn thành công việc, khi đó nó tr ải l ại gi ờ CPU và chuy ển sang chờ xử lý kết thúc. − Tiến trình tự ngắt: Khi tiến trình ch ờ đợi m ột s ự ki ện nào đó, ti ến trình sẽ được chuyển sang trạng thá thực hiện khi có xuất hi ện s ự ki ện nó đang chờ. − Tiến trình sử dụng hết giờ CPU dành cho nó, khi đó nó s ẽ đ ược chuy ển sang trạng thái sẵn sàng. Việc chuyển tiến trình sang trạng thái sẵn sàng về bản ch ất là th ực hi ện v ệc phân phối lại giờ CPU. Lê Phương Tiến – Hà Phước Việt
  9. Xây dựng chương trình mô phỏng giải thuật định thời CPU 11 2.2.3. Khái niệm lập lịch cho CPU Để điều khiển tiến trình ở nhiều trạng thái khác nhau, h ệ th ống th ường t ổ ch ức các từ trạng thái(thực chất là các kh ối điều khi ển ti ến trình) đ ể ghi nh ận tình tr ạng sử dụng tài nguyên và trạng thái tiến trình. Các t ừ trạng thái đ ược t ổ ch ức theo ki ểu hàng đợi như sau: Read Queue CPU I/O Queue I/O I/O Queue I/O …… …… I/O Queue I/O Như vậy lập lịch cho CPU 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 CPU là tối ưu nhất. Mỗi tiến trình ở trạng thái sẵn sàng sẽ được gắn với m ột th ứ t ự ưu tiên. Th ứ t ự ưu tiên này được xác định dựa vào các yếu t ố như: th ời đi ểm hình thành ti ến trình, thời gian thực hiện tiến trình, thời gian kết thúc tiến trình… Lê Phương Tiến – Hà Phước Việt
  10. Bộ môn Mạng và Truyền Thông 12 2.3. Các Thuật Toán Lập Lịch 2.3.1. First Come First Served(FCFS) Trong thuật toán này, độ ưu tiên phục vụ tiến trình căn c ứ vào th ời đi ểm hình thành tiến trình. Hàng đợi các tiến trình được t ổ ch ức theo ki ểu FIFO. M ọi ti ến trình đều được phục vụ theo trình tự xuất hiện cho đến khi k ết thúc hoặc bị ng ắt. Ready list CPU A B C Hình 2.3.1-1. Điều phối FIFO Ưu điểm của thuật toán này là giờ CPU không bị phân ph ối lại(không b ị ng ắt) và chi phsi thực hiện thấp nhất(vì không phải thay đ ổi th ứ t ự ưu tiên ph ục v ụ, th ứ t ự ưu tiên là thứ tự của tiến trình trong hàng đợi). Nhược điểm của thuật toán là thời gian trung bình ch ờ ph ục v ụ c ủa các ti ến trình là như nhau(không kể tiến trình ngắn hay dài), do đó d ẫn t ới ba đi ểm sau: − Thời gian chờ trung bình sẽ tăng vô hạn khi h ệ th ống ti ếp c ận t ới h ạn khả năng phục vụ của mình. − Nếu độ phát tán thời gian thực hiện tiến trình tăng thì th ời gian ch ờ đ ợi trung bình cũng tăng theo. − Khi có tiến trình dài, ít bị ngắt thì các ti ến trình khác ph ải ch ờ đ ợi lâu hơn. 2.3.2. Round robin(RR) Giải thuật định thời luân phiên (round-robin scheduling algorithm-RR) được thiết kế đặc biệt cho hệ thống chia sẻ thời gian. Tương tự như định thời FIFO nhưng sự trưng dụng CPU được thêm vào để chuyển CPU giữa các quá trình. Đơn vị thời gian nhỏ được gọi là định mức thời gian (time quantum) hay phần thời gian Lê Phương Tiến – Hà Phước Việt
  11. Xây dựng chương trình mô phỏng giải thuật định thời CPU 13 (time slice) được định nghĩa. Định mức thời gian thường từ 10 đến 100 mili giây. Hàng đợi sẳn sàng được xem như một hàng đợi vòng. Bộ định thời CPU di chuyển vòng quanh hàng đợi sẳn sàng, cấp phát CPU tới mỗi quá trình có khoảng thời gian tối đa bằng một định mức thời gian. Để cài đặt định thời RR, chúng ta quản lý hàng đợi sẳn sàng như một hàng đợi FIFO của các quá trình. Các quá trình mới được thêm vào đuôi hàng đợi. Bộ định thời CPU chọn quá trình đầu tiên từ hàng đợi sẳn sàng, đặt bộ đếm thời gian để ngắt sau 1 định mức thời gian và gởi tới quá trình. Sau đó, một trong hai trường hợp sẽ xảy ra. Quá trình có 1 chu kỳ CPU ít hơn 1 định mức thời gian. Trong trường hợp này, quá trình sẽ tự giải phóng . Sau đó, bộ định thời biểu sẽ xử lý quá trình tiếp theo trong hàng đợi sẳn sàng. Ngược lại, nếu chu kỳ CPU của quá trình đang chạy dài hơn 1 định mức thời gian thì độ đếm thời gian sẽ báo và gây ra một ngắt tới hệ điều hành. Chuyển đổi ngữ cảnh sẽ được thực thi và quá trình được đặt trở lại tại đuôi của hàng đợi sẳn sàng. Sau đó, bộ định thời biểu CPU sẽ chọn quá trình tiếp theo trong hàng đợi sẳn sàng. Ready List CPU A B C A Hình 2.3.2-1. Round Robin • Ưu điểm : - Các quá trình sẽ được luân phiên cho CPU xữ lý nên thời gian chờ đợi sẽ ít. Lê Phương Tiến – Hà Phước Việt
  12. Bộ môn Mạng và Truyền Thông 14 - Đối với các quá trình liên quan đến nhập xuất,IO,người dùng thì rất hiệu quả. - Việc cài đặt không quá phức tạp • Nhược điểm : - Thời gian chờ đợi trung bình dưới chính sách RR thường là quá dài. - Nếu thời gian định mức cho việc xữ lý quá lớn thì RR thành FIFO - Nếu thời gian quá ngắn so với thời gian xữ lý của một tiến trình trong danh sách hàng đợi thì việc chờ đợi và xữ lý luân phiên sẽ nhiều. - Qui tắc là định mức thời gian nên dài hơn 80% chu kỳ CPU. 2.3.3. Shortest Job First(SJF) Một tiếp cận khác đối với việc định thời CPU là giải thuật định thời công việc ngắn nhất trước (shortest-job-first-SJF). Giải thuật này gán tới mỗi quá trình chiều dài của chu kỳ CPU tiếp theo cho quá trình sau đó. Khi CPU sẵn dùng, nó được gán tới quá trình có chu kỳ CPU kế tiếp ngắn nhất. Nếu hai quá trình có cùng chiều dài chu kỳ CPU kế tiếp, định thời FIFO được dùng. Chú ý rằng thuật ngữ phù hợp hơn là chu kỳ CPU kế tiếp ngắn nhất (shortest next CPU burst) vì định thời được thực hiện bằng cách xem xét chiều dài của chu kỳ CPU kế tiếp của quá trình hơn là toàn bộ chiều dài của nó. Chúng ta dùng thuật ngữ SJF vì hầu hết mọi người và mọi sách tham khảo tới nguyên lý của loại định thời biểu này như SJF. • Ưu điểm : - Giải thuật được xem là tối ưu, thời gian chờ đợi trung bình giảm - Tận dụng hết năng lực của CPU • Nhược điểm : - Cài đặt thuật toán phức tạp,tốn nhiều xữ lý cho quá trình quản lý. Lê Phương Tiến – Hà Phước Việt
  13. Xây dựng chương trình mô phỏng giải thuật định thời CPU 15 - Mặc dù SJF là tối ưu nhưng nó không thể được cài đặt tại cấp định thời CPU ngắn vì không có cách nào để biết chiều dài chu kỳ CPU tiếp theo. - Giải thuật SJF có thể trưng dụng hoặc không trưng dụng CPU, dẫn tới giải thuật này có nhiều dị bản khác nhau và sẽ tối ưu hay không tối ưu phụ thuộc vào trưng dụng CPU. 2.3.4. Shortest Remain Time(SRT) Tương tự như SJF nhưng trong thuật toán này, đ ộ ưu tiên th ực hi ện các ti ến trình dựa vào thời gian cần thiết để thực hiện n ốt ti ến trình(b ằng t ổng th ời gian tr ừ đi thời gian đã thực hiện). Như vậy, trong thuật toán này c ần ph ải th ường xuyên cập nhật thông tin về giời gian đã thực hiện c ủa ti ến trình. Đ ồng th ời, ch ế đ ộ phân bổ lại giờ CPU cũng phải được áp dụng nếu không sẽ làm m ất tình ưu vi ệc c ủa thuật toán. • Ưu điểm : - Thời gian chờ đợi,tồn tại trong hệ thống của mỗi tiến trình đều ngắn - Thuật toán tối ưu nhất • Nhược điểm : - Việc cài đặt thuật toán khá phức tạp - Cần quản lý chặt chẽ việc điều phối các tiến trình - Quản lý thời gian đến của mỗi tiến trình Lê Phương Tiến – Hà Phước Việt
  14. Bộ môn Mạng và Truyền Thông 16 CÀI Đ Ặ T THU Ậ T TOÁN Chương 3. 3.1. Mô hình cài đặt thuật toán 3.1.1. Cấu trúc dữ liệu − Tiến trình Cấu trúc dữ liệu đề xuất cho việc quả lý tiến trình được xây dựng thành m ột lớp nhằm tạo điều kiện cho việc quản lý các tiến trình được dễ dàng. Code class TIENTRINH { private: int stt; int t_den ; int t_xuly; int t_cho ; int finish ; public : TIENTRINH(); TIENTRINH(int stt,int t_den ,int t_xuly); void insert( int stt,int t_den ,int t_xuly); int getT_DEN(); void setT_DEN( int a); Lê Phương Tiến – Hà Phước Việt
  15. Xây dựng chương trình mô phỏng giải thuật định thời CPU 17 int getT_XULY (); void setT_XULY (int a); int getT_CHO(); void setT_CHO( int a); int getFINISH(); void setFINISH(int a); int getSTT (); }; • Stt : số thứ tự của tiến trình • t_den : thời gian đến của tiến trình • t_xuly : thời gian xữ lý của tiến trình • t_cho : thời gian chờ của tiến trình • finish : thời gian hoàn thành của tiến trình • và các hàng thiết lập và lấy thông tin − Ready List Ready list tổ chức theo danh sách liên kết chỉ chứa số thứ tự c ủa các tiến trình.Và việc tổ chức các tiến trình vào ra trong ready list tuân theo các gi ải thuật được dùng trên danh sách liên kết. Code struct DS { int id; DS *next; }; typedef DS* list; • Id: chứa số thứ tự tiến trình trong Ready List − Input Lê Phương Tiến – Hà Phước Việt
  16. Bộ môn Mạng và Truyền Thông 18 Input được tổ chức theo danh sách liên kết đơn nhằm lưu giữ các giá trị khi nhập các tiến trình và là dữ liệu để phục hồi lại các tiến trình nhằm để tránh các trường hợp sai lệnh và mất dữ liệu khi xử lý. Code struct Input { int den ,xuly; Input *next; }; typedef Input * IN; • den: thời gian đến của tiến trình khi nhập liệu • xử lý: thời gian xử lý của tiến trình khi nhập liệu 3.1.2. Thuật toán xử lý chung Việc cài đặt thuật toán được mô phòng theo cách làm việc c ủa CPU và t ất các thuật toán con đều theo mô hình thuật toán này. − Tiến trình ở đầu danh sách sẽ được ưu tiên xữ lý trước và nó chiếm dụng CPU tại thời điểm đó. − Việc đi kèm thèo là xem xét thời gian xữ lý các tiến trình đã h ết ch ưa. Nếu đã hết thì nghĩa là hoàn thành việc xữ lý, ngược lại thì ti ếp t ục x ữ lý theo thuật toán. − Xong mỗi chu kỳ của CPU ( 1 quantum ) thì cập nhật lại danh sách để loại bỏ các tiến trình đã hoàn thành hay sắp xếp hay thêm các ti ến trình mới vào Lê Phương Tiến – Hà Phước Việt
  17. Xây dựng chương trình mô phỏng giải thuật định thời CPU 19 Begin X ữ lý tiến trình đầu danh sách Đúng Kiểm tra danh sách rỗng Sai X ữ lý theo thuật toán Cập nhật l ại danh sách End Hình 3.1.2-1. Sơ đồ thuật toán đề xuất chung cho các giải thuật Lê Phương Tiến – Hà Phước Việt
  18. Bộ môn Mạng và Truyền Thông 20 3.2. Thuật toán 3.2.1. First In First Out(FIFO) Begin Sai ok Đúng Sai Đúng xác l ập thoát xác l ập finish ok quantum Sai quantum Đúng Đúng Tăng thời gian Tg đến Nạp tiến trình chờ Đúng X ữ lý ti ến readyList Tăng quantum trình Sai xác l ập thoát quantum End Hình 3.2.1-1.Thuật toán FIFO Code Lê Phương Tiến – Hà Phước Việt
  19. Xây dựng chương trình mô phỏng giải thuật định thời CPU 21 void FIFO() { int time=0,ok =1,i,j=0 ,ID; while(ok ) { ID=-1; PrintRL(ready,time); listBox2->Items->Add ( "------------------"); for(i=0;iAdd ( "Time = "+time.ToString ()+" : Nap tien trinh : "+( tt[j- 1]. getSTT ()).ToString ()); } // nen ton tai tt trong readylist thi lam,ko thi thoat quantum if(ready) { ID=(* ready).id; listBox2->Items->Add ( "Time = "+time.ToString ()+" : xu ly tien trinh : "+(tt[ ID]. getSTT ()).ToString ()); if(tt[ID]. getT_XULY ()>0) { // tang thoi gian cho cua cac tt trong ready tangT_CHO(ready,ID); tt[ID]. setT_XULY ( tt[ID]. getT_XULY () - 1); if(tt[ ID]. getT_XULY ()==0) xoa(); } time++; if(tt[ID]. getT_XULY ()==0) { tt[ID]. setFINISH( time); listBox2->Items->Add ( "Time = "+time.ToString () +" : hoan thanh tien trinh : "+( tt[ID]. getSTT ()).ToString ()); break; } } else { tangT_CHO(ready,-1); time++; break; } } listBox2->Items->Add ( "-------Hoan thanh chu ky-------"); listBox2->Items->Add ( "------------------"); if(checkFinish ()) ok =0; } TIME =time } Lê Phương Tiến – Hà Phước Việt
  20. Bộ môn Mạng và Truyền Thông 22 3.2.2. Round Robin(RR) Begin Sai ok Hoán vị ReadyList Đúng Sai Đúng xác l ập thoát xác l ập finish ok quantum Sai quantum Đúng Đúng Tăng thời gian Tg đến Nạp ti ến trình chờ Đúng Xữ lý tiến readyList Tăng quantum trình Sai xác l ập thoát quantum End Hình 3.2.2-1.Round Robin Lê Phương Tiến – Hà Phước Việt
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Tài Chính Ngân Hàng
172 tài liệu
837 lượt tải
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
3=>0