Giải Thuật điều Phối Round Robin (RR)

Trang chủ » Chiến Lược điều Phối Fifo Là Gì » Giải Thuật điều Phối Round Robin (RR)

Có thể bạn quan tâm

Sign in Sign in Welcome!Log into your account your username your password Forgot your password? Password recovery Recover your password your email Search Monday, December 16, 2024
  • Sign in / Join
Sign in Welcome! Log into your account your username your password Forgot your password? Get help Password recovery Recover your password your email A password will be e-mailed to you. sinhvientot.net sinhvientot.net sinhvientot.net sinhvientot.net Home Thủ thuật Thủ thuật Windows Giải thuật điều phối Round Robin (RR) Facebook Twitter Pinterest WhatsApp

Hôm nay ra tiếp tục với một thuật giải định thời CPU khác, đó là Round Robin (RR).

Đối với thuật giải RR, mỗi tiến trình trước khi bắt đầu được đưa vào CPU xử lý, sẽ được cấp phát cho một đơn vị thời gian chiếm dụng CPU nhất định.

Ta gọi chung giá trị hằng số này với cái tên là quantum. Điểm khác biệt của RR với FCFS đó  là RR tuân thủ theo cơ chế không độc quyền (preemtive).

image001 Như vậy, khi một tiến trình sử dụng hết thời gian quantum mà nó được cấp phát, thì dù vẫn còn phải xử lý tiếp, phần dư của nó cũng sẽ được chuyển về phía sau trong danh sách hàng đợi. Sau đó, căn cứ vào danh sách Ready list đã nạp trước đó, CPU sẽ lấy tiếp tiến trình kế cận để đưa vào xử lý, với mức quantum là như nhau cho tất cả các tiến trình.

Nếu gọi n là số tiến trình có trong Ready list, thời gian quantum là q, như vậy mỗi tiến trình sẽ có một khoảng thời gian là image002 để sử dụng CPU.

Về mặt thời gian thì với RR, thời gian hoàn tất trung bình sẽ cao hơn SJF, bù lại, tính đáp ứng sẽ tốt hơn.

Để hình dung rõ ràng, ta sẽ xét 2 ví dụ sau đây.

Process Arrival Time Burst Time
P1 0 24
P2 1 3
P3 2 3

Với bảng dữ liệu trên, ta biết thêm được quantum time=4. Như vậy, để tính toán thuận tiện, ta cũng tiếp tục sử dụng giản đồ Gantt:

image005

Với giản đồ Gantt này, ta có thể tính được: – Thời gian xử lý: P1=24, P2=3 và P3= 3. – Thời gian đợi lần lượt: + P1 đợi 0 + (10-4) (ms). + P2 đợi 4-1=3 (ms). + P3 đợi 7-2=5 (ms). – Thời gian hoàn tất tiến trình: + P1: 30 (ms). + P2: 6 (ms). + P3: 8 (ms). – Thời gian trung bình: AvgWT = (6+3+5)/3 = 4.66

Các bạn có thể xem chi tiết ở đây

image006

Nhận xét RR

– Loại bỏ hiện tượng độc chiếm CPU – Phù hợp với hệ thống tương tác người dùng – Hiệu quả ? Phụ thuộc vào việc lựa chọn quantum q + q quá lớn => FCFS (giảm tính tương tác) + q quá nhỏ => chủ yếu thực hiện chuyển đổi ngữ cảnh (context switching) + Thường q = 10-100 milliseconds

Điều phối với độ ưu tiên

– Một độ ưu tiên (integer) được gán vào mỗi tiến trình – Phân biệt tiến trình quan trọng với tiến trình bình thường – Tiêu chí lựa chọn tiến trình Tiến trình có độ ưu tiên cao nhất – Thời điểm lựa chọn tiến trình + Độc quyền + Không độc quyền (có độ ưu tiên)

Minh họa điều phối với độ ưu  tiên (không độc quyền)

image007

Nhận xét điều phối với độ ưu tiên

Cách tính độ ưu tiên ? – Hệ thống gán – Người dùng gán Tính chất độ ưu tiên – Tĩnh + Vấn đề Starvation: các tiến trình độ ưu tiên thấp có thể không bao giờ thực thi được + Giải pháp Aging – tăng độ ưu tiên cho tiến trình chờ lâu trong hệ thống (sống lâu lên lão làng…) – Động Võ T. Thương thuongvt@hotmail.com

Bài tập có hướng dẫn về chiến lược điều phối Round Robin (Xem tiếp trang sau)

RELATED ARTICLESMORE FROM AUTHOR

Thủ thuật Windows

Cài driver card mạng wifi cho Windows server 2019

Thủ thuật

Authy là gì? Hướng dẫn sử dụng Authy để bảo mật 2FA tài khoản

Phần mềm Khác

Sao lưu và phục hồi máy tính với OneKey Ghost

Thủ thuật Windows

Blockchain là gì ? Blockchain và công nghệ 4.0

Thủ thuật Windows

Hướng dẫn tạo ví Ethereum trên MyEtherWallet

Phần mềm Khác

Hướng dẫn cài đặt VMware Workstation

7 COMMENTS

  1. Bài biết rất hay và dễ hiểu, cảm ơn người đã đăng bài!

    Log in to leave a comment

  2. l

    Log in to leave a comment

    • ???

      Log in to leave a comment

  3. cho em hỏi là khi đề yêu cầu vẽ giảng đồ grantt mà có áp dụng độ ưu tiên không độc quyền thì mình sẽ giải quyết nó ra sao ạ, em xin cảm ơn add!

    Log in to leave a comment

  4. nếu 2 process vào hàng đợi cùng 1 lúc trong chiến lược điều phối Round Robin thì tiêu chí gì để quyết định process nào đc chọn trc nếu 1 process trong chiến lược điều phối Round Robin vừa chạy xong 1 chu kỳ tại thời điểm x và tại thời điểm x này xuất hiện 1 process mới vào hàng đợi, vậy process nào sẽ đứng trước process nào

    Log in to leave a comment

    • 1. “nếu 2 process vào hàng đợi cùng 1 lúc trong chiến lược điều phối Round Robin thì tiêu chí gì để quyết định process nào đc chọn trc” –> HDH sẽ dùng chiến lược SJF (công việc ngắn nhất), tiến trình thời gian use CPU ngắn hơn sẽ được ưu tiên chạy trước. 2. “nếu 1 process trong chiến lược điều phối Round Robin vừa chạy xong 1 chu kỳ tại thời điểm x và tại thời điểm x này xuất hiện 1 process mới vào hàng đợi, vậy process nào sẽ đứng trước process nào” –> tiến trình cũ được ưu tiên trước, mới xếp hàng sau

      Log in to leave a comment

  5. giải thuật RR có quantum=2, tại thời điểm x chỉ còn P3 với thời gian xử lý còn lại = 4. Vậy P3 chạy đến thời điểm x+2 thì quay về hàng đợi rồi chạy tiếp có phải không ạ, nếu phải thì trong biểu đồ gantt P3 chạy từ x đến x+4 hay phải chia thành 2 đoạn x->x+2 và x+2->x+4 ạ

    Log in to leave a comment

LEAVE A REPLY Cancel reply

Log in to leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Kết nối mạng xã hội

666FansLike63SubscribersSubscribe

Bài xem nhiều

Mạng máy tính là gì ?

Mr Good - April 20, 2016 35

Giải thuật điều phối Shortest-Job-First Scheduling (SJF)

April 20, 2016

Hướng dẫn sử dụng Google Classroom cho sinh viên

September 20, 2019

Xóa tất cả các khoảng trắng thừa của xâu ký tự s

May 16, 2017

Cấu trúc dữ liệu danh sách nhân viên

May 27, 2017 Load more

Bài mới

Download

Download Cisco Packet Tracer

Windows 10

Hướng dẫn cài đặt webserver trên localhost để chạy wordpress

HPE

Hướng dẫn cấu hình IP ILO máy chủ HP DL380 Gen10

CentOS

CentOS 8 – Giới thiệu về hệ điều hành Linux (P1)

Phản hồi mới nhất

  • Mr Good on Hướng dẫn tạo Users, OU và phân quyền quản lý OU trên Windows Server 2016/2012/2008/2003
  • Đinh Toàn on Xây dựng và triển khai hệ thống VoIP cho doanh nghiệp vừa và nhỏ
  • Mr Good on Xây dựng Additional Domain Controller trên Windows Server 2016/2012/2008/2003
  • đức on Cấu trúc dữ liệu danh sách nhân viên
  • Quang on Xây dựng Additional Domain Controller trên Windows Server 2016/2012/2008/2003
© Copyright 2016, All Rights Reserved. Donations are always appreciated! MEW: 0x296f1a39d5Ca3cb83C76724eA38af3B90B90109D MORE STORIES

Hướng dẫn đầu tư ICO UQUID từ A – Z

Mr Good - October 29, 2017 0

Hướng dẫn cài mới hoặc nâng cấp lên Windows 10

Mr Good - July 5, 2016 0

Từ khóa » Chiến Lược điều Phối Fifo Là Gì