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

Trang chủ » Sjf Không độc Quyền » Giải Thuật điều Phối Shortest-Job-First Scheduling (SJF)

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 Tuesday, November 26, 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 Shortest-Job-First Scheduling (SJF) Facebook Twitter Pinterest WhatsApp

Tiếp theo các giải thuật định thời  CPU; First-Come, First-Served Scheduling, Round Robin (RR) hôm nay sinhvientot.net gởi đến bạn giải thuật Shortest-Job-First Scheduling.

Một hướng giải quyết khác cho vấn đề điều phối tiến trình CPU là thuật toán shortest-job-first (SJF). Khi CPU được cấp, nó sẽ đưa vào tiến trình có chiều dài burt time nhỏ nhất để xử lý.

image001

Là một dạng độ ưu tiên đặc biệt với độ ưu tiên pi = thời_gian_còn_lại(Processi)

Thuật toán shortest-job-first (SJF) Có thể được cài đặt độc quyền hoặc không độc quyền

Minh họa SJF (không độc quyền)

image002

Nếu trong các tiến trình cần nạp vào có 2 tiến trình giống nhau về burst time, nó sẽ áp dụng thuật toán FCFS ta đã nói ở bài trước để giải quyết vấn đề này.Lấy một ví dụ về SJF, ta có bảng các tiến trình cần nạp vào như hình bên dưới, với quy ước các burst time của lần lượt các tiến trình cần nạp vào có đơn vị đồng nhất là milisecond.

image004 Nếu dùng thuật toán SJF để giải quyết bài toán này, chúng ta sẽ có được lược đồ như hình bên dưới, áp dụng giản đồ Gantt để trình bày. image006

Như vậy, thời gian chờ của P1 sẽ là 3 (ms), 16 (ms) đối với P2, 9 (ms) với tiến trình P3 và 0 (ms) cho P4. Từ đó, ta tính được thời gian chờ trung bình sẽ là: (3+16+9+0)/4=7 (ms). Hãy thử so sánh, ta sẽ thấy, nếu dùng FCFS để giải quyết vấn đề này, thì ta sẽ tốn tổng cộng 10.25 ms thời gian chờ trung bình.

Thuật toán SJF đã được chứng minh là sẽ cho ra thời gian chờ trung bình cho các tiến trình cần xử lý với một số con tối thiểu nhất. Bằng cách chuyển cách tiến trình ngắn hơn lên trước các tiến trình tốn thời gian dài, nó đã giảm một cách đáng kể thời gian chờ cho các tiến trình ngắn, kéo theo giảm rõ rệt thời gian chờ trung bình.

Vấn đề khó khăn thực sự đối với giải thuật SJF này đó là việc xác định độ dài tiếp theo cần đưa vào để CPU xử lý. Đối với các hệ thống batch, chúng ta có thể sử dụng thời gian xử lý giới hạn do người dùng chỉ định khi người dùng nạp vào một công việc bất kỳ.

Như vậy, trong trường hợp này, người dùng có thể tự tính toán thời gian giới hạn xử lý một cách chính xác, bởi vì với giá trị càng nhỏ thì tốc độ phản hồi xử lý càng nhanh nhưng giá trị này quá nhỏ cũng có thể gây nên tình trạng lỗi thời gian chờ quá hạn dẫn đến yêu cầu xác nhận lại. Do đó mà SJF thường được dùng trong các bài toán cần xử lý dài hạn nhiều hơn.

Với SJF, thuật toán này đồng thời có thể ở trạng thái ưu tiên (preemtive) hoặc không ưu tiên (nonpreemtive).  Sự chọn lựa xảy ra khi có một tiến trình mới được đưa vào danh sách sẵn sàng trong khi một tiến trình khác đang xử lý.

Có nhiều bạn gặp rắc rối với 2 khái niệm vừa nêu ở trên. Ở đây ta cần phân biệt: preemtive (ưu tiên) tức là thuật toán này thuộc dạng không độc quyền. Có ưu tiên thì tính độc quyền không còn. Nhưng với nonpreemtive – không ưu tiên – tức là độc quyền nắm giữ.

Tiến trình mới có thể sỡ hữu một yêu cầu thời gian sử dụng CPU cho lần tiếp theo (CPU-burst) ngắn hơn thời gian còn lại mà tiến trình hiện hành cần xử lý.

Giải thuật SJF không độc quyền sẽ dừng hoạt động của tiến trình hiện hành, trong khi giải thuật độc quyền sẽ cho phép tiến trình hiện hành tiếp tục xử lý.

Lấy ví dụ cho vấn đề này, ta có bảng dữ liệu đầu vào như sau:

image008 Giản đồ Gantt thể hiện kết quả của thuật toán SJF với cơ chế ưu tiên (không độc quyền) như sau: image010

Ta thấy trong hình, P1 được bắt đầu ở giây thứ 0, và quan sát dữ liệu đầu vào, ta thấy nó đồng thời cũng là tiến trình duy nhất vào đầu tiên. Tiến trình P­2 tiến vào ở giây thứ 1. Thời gian đợi cho P1 là 7 ms, lớn hơn nhiều so với P2 (P2 chỉ chiếm 4 ms). Suy rộng ra, ta có tổng thời gian chờ cho ví dụ này là [(10-1) + (1-1) + (17-2) + (5-3)]/4=26/4=6.5 ms.

Nhận xét SJF

– Tối ưu thời gian chờ – Làm sao biết được thời gian còn lại cần thực thi của một tiến trình – Không khả thi ? – Ước lượng – sử dụng thời gian sử dụng CPU ngay trước, dùng qui luật trung bình giảm theo hàm mũ. image011 VÕ TÌNH THƯƠNG votinhthuong9@gmail.com

Bài tập có hướng dẫn về chiến lược điều phối Shortest-Job-First Scheduling (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

1 COMMENT

  1. Cho em hỏi tại sao mà Time Watting của hai tiến trình không được giống nhau ạ,Trong SJF độc quyền

    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

Cấu hình cơ bản trên Switch, Router Cisco

Mr Good - April 20, 2016 0

Bài 02: Cấu trúc một chương trình C# (Csharp)

Nguyễn Quýt - July 10, 2016 0

Từ khóa » Sjf Không độc Quyền