Diễn giải thuật toán First Come First Served trong lập lịch cho CPU
|
First Come, First Served (FCFS) là Đến trước phục vụ trước (FCFS). Đây là nghĩa tiếng Việt của thuật ngữ First Come, First Served (FCFS) - một thuật ngữ thuộc nhóm Technology Terms - Công nghệ thông tin. Show Độ phổ biến(Factor rating): 5/10 Lần đầu tiên đến, đầu tiên phục vụ (FCFS) là một hành trình hệ thống thuật toán lập kế hoạch và một mạng định tuyến cơ chế quản lý tự động thực hiện các yêu cầu và quy trình xếp hàng theo lệnh của họ đến. Với đầu tiên ai đến trước được phục vụ, những gì xảy ra trước được xử lý đầu tiên; các yêu cầu tiếp theo trong dòng sẽ được thực hiện một lần một trước khi nó hoàn tất. Xem thêm: Thuật ngữ công nghệ A-Z Giải thích ý nghĩaFCFS cung cấp một, đơn giản và có lỗi quá trình thuật toán lập lịch trình hiệu quả mà tiết kiệm tài nguyên CPU có giá trị. Nó sử dụng lập lịch trình nonpreemptive trong đó một quá trình được tự động xếp hàng đợi và xử lý xảy ra theo một yêu cầu đến hoặc để quá trình. FCFS bắt nguồn ý tưởng của mình từ dịch vụ khách hàng thực tế cuộc sống. What is the First Come, First Served (FCFS)? - DefinitionFirst come, first served (FCFS) is an operating system process scheduling algorithm and a network routing management mechanism that automatically executes queued requests and processes by the order of their arrival. With first come, first served, what comes first is handled first; the next request in line will be executed once the one before it is complete. Understanding the First Come, First Served (FCFS)FCFS provides an efficient, simple and error-free process scheduling algorithm that saves valuable CPU resources. It uses nonpreemptive scheduling in which a process is automatically queued and processing occurs according to an incoming request or process order. FCFS derives its concept from real-life customer service. Thuật ngữ liên quan
Source: First Come, First Served (FCFS) là gì? Technology Dictionary - Filegi - Techtopedia - Techterm
This site uses cookies. By continuing, you agree to their use. Learn more, including how to control cookies. Xin chào mọi người, nối tiếp seri về kinh nghiệm IT: https://huongtlu.wordpress.com//kinh-nghiem-it/ bài viết này mình chia sẻ về 3 thuật toán chính liên quan tại bài viết: https://huongtlu.wordpress.com/2020/06/26/huong-dan-tu-hoc-de-do-chung-chi-fe-fundamental-it-engineer-bai-6/ Đây là 3 thuật toán liên quan tới xử lý tiến trình trong hệ điều hành máy tính. Đề thi FE (Fundamental IT Engineer) các năm gần đây mình thấy đa số đều có ít nhất 1 câu liên quan tới các thuật toán này. Ngoài ra còn có 1 số thuật toán khác như: Round Robin, … Theo dõi list bài học luyên thi FE (Fundamental IT Engineer): TẠI ĐÂY XEM VIDEO HƯỚNG DẪN:
Bài tập kiểm traQuiz 1: Below is the list of processes, P1, P2, P3, and P4, and their burst time for CPU scheduling algorithms. Which of the following combinations is the average waiting time in millisecond for a First-Come, First-Serve (FCFS) scheduling and Shortest-Job-First (SJF) scheduling given that the process arrives in the order P1, P2, P3, and P4, and the latency can be ignored. Note that the burst time is the actual time required to complete a process. Hường TLU Follow me on social media Trong bài viết trước mình đã giới thiệu sơ lược điều phối tiến trình trong hệ điều hành, bài viết này sẽ trình bày về chiến lược một hàng đợi nhiều tiến trình chờ phân phối xử lý. Trong chiến lược một hàng đợi này có 4 thuật toán chính FIFO, SJF ,RR, thuật toán ƯU TIÊN First In First Out (FIFO)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. Ư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 phí 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:
Ví dụ:
Thứ tự cấp phát tiến trình:
Thời gian chờ trung bình: (23+25)/3=16. 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 (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ó 1chu 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. • Ưu điểm:
• Nhược điểm:
Ví dụ:
Quantum = 4 Thì thứ tự cấp processor cho các tiến trình lần lượt là:
Vậy thời gian chờ đợi trung bình sẽ là: (3+5+6)/3 = 4,67 Như vậy RR có thời gian chờ đợi trung bình nhỏ hơn so với FIFO 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:
• Nhược điểm:
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:
• Nhược điểm:
Mr.Nara |
