Chiến Lược điều Phối CPU First-come, First-server (FCFS)

Trang chủ » Tính Fcfs » Chiến Lược điều Phối CPU First-come, First-server (FCFS)

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 Friday, December 26, 2025
  • 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 Chiến lược điều phối CPU first-come, first-server (FCFS)​ Facebook Twitter Pinterest WhatsApp

First-Come, First-Served Scheduling

Cho đến nay, thuật toán định thời CPU đơn giản nhất là first-come, first-server (FCFS). Hiểu đơn giản nghĩa của thuật toán này là: đến trước, phục vụ trước. Với giải thuật này, nó ứng dụng chế độ nonpreemptive – tức là một tiến trình sẽ chiếm giữ CPU cho đến khi nào nó trả CPU, thông qua phương thức ngắt hay yêu cầu nhập/xuất xuất hiện.

Vậy phương thức thực hiện của FCFS trong máy tính là gì? Chính là cơ chế hàng đợi FIFO Queue (First In First Out). Để hiểu rõ hơn về Queue, bạn bắt buộc phải học qua Cấu trúc dữ liệu & Giải thuật hoặc có thể tìm đọc về cơ chế này trên các tài liệu có sẵn trên mạng.

image001

Nếu để ý, ta sẽ thấy ngay từ tên gọi thì cả 2 giải thuật này đều có chung ý tưởng với nhau: Anh vào trước, anh được phục vụ trước.

Lấy một ví dụ để dễ hình dung vấn đề: ta có ba tiến trình được tuần tự đưa vào với các tên gọi là P1 P2 P3 và Burst time của chúng lần lượt là 24 3 3. Ta có các dữ liệu đầu vào cụ thể như bảng sau:

Process Burst time
P1 24
P2 3
P3 3
Ta sẽ ứng dụng giản đồ Gantt – bạn có thể đọc thêm về nó tại Wikipedia để có được sơ đồ cụ thể nhằm giải quyết bài toán hiệu quả hơn. image002

Như vậy, xuất phát từ bên trái, ta sẽ nạp P1 vào để xử lý. Khởi điểm, mốc thời gian luôn luôn mặc định bằng 0. Vì trong dữ liệu đề bài đưa ra thì P1 chiếm 24ms, tức là một đoạn khá lớn. Sau đó, tiến trình tiếp theo sẽ được đưa vào, với burst time của P2 bằng 3, tức là trên giản đồ Gantt, ta lấy 24 + 3 = 27 ms. Sau khi P2 hoàn thành, nó sẽ đưa tiếp P3 vào, và P3 chiếm 3ms nên trên đây, ta lấy tiếp 27 + 3 = 30. Như vậy, giản đồ đã cung cấp cho ta một cái nhìn trực quan nhằm minh họa cụ thể burst time của lần lượt các tiến trình P1 P2 P3.

Bài toán đến đây coi như hoàn thành bước khó khăn. Việc còn lại chỉ là xác định thời gian đợi của từng tiến trình. Cách xác định cũng không có gì phức tạp. Bạn chỉ việc căn cứ vào con số bên trái của từng tiến trình trong giản đồ bên trên. Như vậy: thời gian đợi lần lượt của P1 P2 P3 là 0 24 27.

Bước cuối cùng của thuật toán, đó là xác định thời gian đợi trung bình của cả quá trình. Xác định con số cuối cùng này, bạn hãy cộng tất cả thời gian đợi của toàn bộ các tiến trình có được, sau đó chia cho tổng số tiến trình.

Nói thì có vẻ rắc rối, ở ngay trong ví dụ này, ta có thời gian đợi trung bình là: (0 + 24 + 27) / 3 = 17.

Nhưng nếu để ý kỹ, thuật toán FCFS này có một đặc điểm đó là chiếm khá lớn thời gian chờ đợi, nếu các tiến trình vào theo tuần tự thời gian khác nhau mà có độ chênh lệch quá lớn. Cụ thể, nếu có sự sắp xếp hoặc thay đổi lại thứ tự vào lần lượt của chúng, biết đâu ta có thể rút ngắn thời gian chờ đợi hơn chăng?

Hãy thử với thứ tự vào của các tiến trình là P2 P3 P1 xem có sự khác biệt nào ở con số cuối cùng ta cần đến không.

image005

Cũng vẫn bắt đầu giản đồ Gantt bằng con số 0, ta nạp P2 vào trước tiên. P2 chiếm 3ms, sau đó tới P3 chiếm 3ms, cho nên trên giản đồ, ta sẽ kết thúc P3 ở vị trí 6ms. Sau đó, ta nạp tiến trình cuối cùng là P1 vào ở mốc 6ms, do P1 chiếm 24ms nên 6 + 24  sẽ bằng 30. Có thể bạn thấy ngay là tổng burst time không có gì thay đổi, nhưng đừng nóng vội.

Ta xác định được thời gian đợi ở lần này của từng tiến trình P2 P3 P1 sẽ là 0 3 6 (căn cứ vào con số bên trái của từng tiến trình). Cuối cùng, ta xác định thời gian đợi trung bình: (0 + 3 + 6) / 3 = 3. Con số đã giảm đi rất nhiều so với ban đầu. Như vậy, với thuật toán FCFS thì thời gian đợi trung bình sẽ không phải lúc nào cũng tối ưu nhất cho ta mà còn tùy thuộc vào thứ tự vào của các tiến trình.

Và do thuật toán FCFS này ứng dụng nonpreemptive, nên nó sẽ đặc biệt phiền hà khi sử dụng trong những hệ thống chia sẻ thời gian. Vì mỗi lần thực hiện, nó yêu cầu toàn quyền sử dụng CPU, và điều này sẽ dễ gây nên sự đổ vỡ cho hệ thống nếu có một người dùng nạp quá nhiều tiến trình mà các tiến trình đó có burst time không hề nhỏ trong phiên sử dụng của mình.

Võ T. Thương [email protected]

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

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

Giới thiệu dự án trade.io và token TIO dành cho thị trường forex

Mr Good - November 5, 2017 0

Những ngộ nhận của sinh viên học Đại học Công Nghệ Thông Tin

Mr Good - December 30, 2019 0

Từ khóa » Tính Fcfs