Tiêu chí đánh giá lập lịch

Loading Preview

Sorry, preview is currently unavailable. You can download the paper by clicking the button above.

11Nguyên lý hệđiềuhànhNguyễnHải ChâuKhoa Công nghệ thông tinTrường Đạihọc Công nghệ2Lậplịch CPU3Tạisaophảilậplịch CPU?z Số lượng NSD, số lượng tiến trình luôn lớnhơnsố lượng CPU củamáytínhrất nhiềuz Tạimộtthời điểm, chỉ có duy nhấtmộttiếntrình đượcthựchiệntrênmộtCPUz Vấn đề: z Nhu cầusử dụng nhiềuhơn tài nguyên (CPU) đang cóz Do đócầnlậplịch để phân phốithờigiansử dụngCPU cho các tiếntrìnhcủa NSD và hệ thống4Hàng chờ lậplịch tiếntrìnhHàng chờ sẵnsàng thựchiệnHàng chờ vào/raYêu cầuvào/raHếtthờigiansử dụng CPUTạomộttiếntrình conChờ ngắtCPUVào/raTiếntrìnhcon thựchiệnNgắtxuấthiện5CPU-burst và IO-burstz Trong suốtthờigiantồntạitronghệ thống, tiếntrìnhđược xem như thựchiệnhailoạicông việcchính:z Khi tiếntrìnhở trạng thái running: Sử dụng CPU(thuậtngữ: CPU-burst)z Khi tiếntrìnhthựchiện các thao tác vào ra: Sửdụng thiếtbị vào/ra (thuậtngữ: I/O burst)6Microsoft Office Outlook CPU-burstAdobe Photoshop CPU-burst27Hai loạitiếntrìnhchínhz Căn cứ theo cách sử dụng CPU của tiến trình, có hai loại tiến trình:z Tiếntrìnhloại CPU-bound: Tiếntrìnhcómộthoặcnhiều phiên sử dụng CPU dàiz Tiếntrìnhloại I/O-bound: Tiến trình có nhiềuphiên sử dụng CPU ngắn(tứclàthờigianvàoranhiều)8Bộ lậplịch ra hoạt động khi…1. Mộttiến trình chuyểntừ trạng thái running sang waiting2. Mộttiến trình chuyểntừ trạng thái running sang ready3. Mộttiến trình chuyểntừ trạng thái waiting sang ready4. Mộttiếntrìnhkếtthúc9Các phương pháp lậplịchterminatednewready runningwaitingadmittedexitI/O hoặcsự kiệnđãhoàntấtBị ngắt(Interrupt)Chờ I/O hoặcsự kiệnLậplịch2134z 1 và 4: Lậplịch non-preemptivez Ngượclại: Lậplịch preemptive10Lậplịch non-preemptivez Mộttiếntrìnhgiữ CPU đếnkhinókết thúchoặcchuyển sang trạng thái waiting.z Ví dụ: Microsoft Windows 3.1, Apple Macintosh sử dụng lậplịch non-preemptivez Có thể sử dụng trên nhiềuloạiphầncứng vìkhông đòi hỏitimer11Lậplịch preemptivez Hiệuquả hơnlậplịch non-preemptivez Thuậttoánphứctạphơn non-preemptive vàsử dụng nhiều tài nguyên CPU hơnz Ví dụ: Microsoft Windows XP, Linux, UNIX sử dụng lậplịch preemptive12Bộđiềuphối (dispatcher)z Nhiệmvụ:z Chuyểntrạng thái (context switch)z Chuyểnvề user-modez Thựchiệntiến trình theo trạng thái đãlưuz Cầnhoạt động hiệuquả (tốc độ nhanh)z Thờigiancần để bộđiềuphốidừng mộttiếntrình và thựchiệntiến trình khác gọilàđộ trễ(latency) củabộđiềuphối313Các tiêu chí đánh giá lậplịchz Khả năng tậndụng CPU (CPU utilization): Thể hiệnqua tảiCPU –làmộtsố từ 0% đến100%. z Trong thựctế các hệ thống thường có tảitừ 40% (tảithấp) đến 90% (tảicao)z Thông lượng (throughput): Là số lượng cáctiến trình hoàn thành trong một đơnvị thờigian14Các tiêu chí đánh giá lậplịchz Thời gian hoàn thành (turnaround time):z tturnaround= to-tivới tilà thời điểmtiếntrìnhvàohệthống, tolà thời điểmtiếntrìnhrakhỏihệ thống(kếtthúcthựchiện)z Như vậy tturnaroundlà tổng: thờigiantảivàobộ nhớ, thờigianthựchiện, thời gian vào ra, thờigiannằm trong hàng chờ…15Các tiêu chí đánh giá lậplịchz Thờigianchờ (waiting time): Là tổng thờigian tiến trình phảinằm trong hàng chờready (twaiting)z Các thuậttoánlậplịch CPU không có ảnh hưởngđếntổng thờigianthựchiệnmộttiến trình mà chỉcó ảnh hưởng đếnthờigianchờ củamộttiếntrình trong hàng chờ ready z Thờigianchờ trung bình (average waiting time): taveragewaiting=twaiting/ n, n là số lượng tiến trình tronghàng chờ16Các tiêu chí đánh giá lậplịchz Thờigianđáp ứng (response time): Làkhoảng thờigiantừ khi tiếntrìnhnhận đượcmộtyêucầuchođếnkhibắt đầu đáp ứngyêu cầu đóz tres= tr– ts, trong đó trlà thời điểmnhậnyêucầu, tslà thời điểmbắt đầu đáp ứng yêu cầu17Đánh giá các thuậttoánlậplịchXấuTốtThờigianđáp ứng (response time)XấuTốtThờigianchờ (waiting time)-> Thờigianchờ trung bìnhXấuTốtThờigianhoànthành(turnaround time)TốtXấuThông lượng (throughput)TốtXấuKhả năng tậndụng CPU (CPU utilization)Giá trị caoGiá trị thấpTiêu chí18Các thuậttoánlậplịch419FCFS (First Come First Served)z Tiến trình nào có yêu cầusử dụng CPU trướcsẽđượcthựchiệntrướcz Ưu điểm: Thuậttoánđơngiảnnhấtz Nhược điểm: Hiệuquả củathuậttoánphụthuộcvàothứ tự củacáctiến trình trong hàngchờ, vì thứ tự này ảnh hưởng rấtlớn đến thờigian chờ trung bình (average waiting time)20Ví dụ FCFS 1az Giả sử có 3 tiếntrìnhP1, P2, P3vớithờigianthựchiệntương ứng là 24ms, 3ms, 6msz Giả sử 3 tiếntrìnhxếphàngtheothứ tự P1, P2, P3. Khi đótacóbiểu đồ Gantt như sau:z Thờigianchờ củacáctiếntrìnhlà: P1 chờ0ms, P2 chờ 24ms, P3chờ 27msz Thờigianchờ trung bình: (0+24+27)/3=17msP1P2P3024273321Ví dụ FCFS 1bz Xét ba tiếntrìnhtrongvídụ 1a vớithứ tự xếphàng P3, P2, P1z Biểu đồ Gantt:z Thờigianchờ củacáctiếntrìnhlà: P3 chờ0ms, P2 chờ 6ms, P3chờ 9msz Thờigianchờ trung bình: (0+6+9)/3=5msz Thờigianchờ trung bình thấphơnthờigianchờ trung bình trong ví dụ 1aP1P2P3069 3322Hiệntượng “đoàn hộ tống”z Thuậtngữ: convoy effectz Xảyrakhicómộttiến trình “lớn” P nằm ởđầuhàng chờ và nhiềutiến trình “nhỏ” Qixếphàngsau P. z “Lớn”: Sử dụng nhiềuthờigianCPU vàvàoraz “Nhỏ”: Sử dụng ít thời gian CPU và vào raz Thuậttoánlậplịch đượcsử dụng là FCFS.:z Hiệntượng xảy ra: CPU, thiếtbị vàoracónhiềuthờigianrỗi, thờigianchờ trungbìnhcủacáctiến trình cao23Ví dụ convoy effectHàng chờ sẵnsàng thựchiệnHàng chờ vào/raYêu cầuvào/raHếtthờigiansử dụng CPUTạomộttiếntrình conChờ ngắtCPUVào/raTiến trình con thựchiệnNgắtxuấthiệnQ3(10) Q2(10) Q1(10) P (40)P (50) Q1(10) Q2(10) Q3(10)24Convoy effect: Thờigiansửdụng CPU và thiếtbị vào raThiếtbịvào raCPU040 50 60 70PQ1Q2Q3400Rỗi90P90RỗiQ1Q2Q3100 110 120 130130PRỗi140Q1Q2Q3150 160 180180Pz Giả sử P là tiến trình “lớn” có chu kỳ sử dụng CPU trong 40ms và vào ra trong 50msz Q1, Q2, Q3là 3 tiến trình “nhỏ”cóchukỳ sử dụng CPU trong10ms và vào ra trong 10msz Thứ tự xếp hàng: P, Q1, Q2, Q3Rỗi525SJF (Shortest Job First)z Với SJF, tham số lậplịch có thêm độ dài củaphiên sử dụng CPU tiếp theo tnextburstz Tiếntrìnhcótnextburstnhỏ nhấtsẽđượclậplịch sử dụng CPU trướcz Nếu hai tiếntrìnhcótnextburstbằng nhau thìFCFS đượcápdụng26SJF (Shortest Job First)z Vớilậplịch dài hạn: Có thể biết tnextburstvì cótham số chỉ ra thờigianchạycủatiếntrìnhkhiđưatiếntrìnhvàohệ thống (job submit)z Khó khăn: Chỉ có thể phỏng đoán được tnextburrtvớilậplịch ngắnhạnz Đọc ở nhà: Dựđoán tnextburstbằng công thứctrung bình mũ (exponential average) trang160-162 trong giáo trìnhz SJF không tối ưu đượcvớilậplịch ngắnhạnz SJF thường đượcápdụng cho lậplịch dài hạn27Lậplịch có độ ưutiênz Thuậtngữ: Priority schedulingz Mỗitiếntrìnhđượcgắnmộtthamsố lậplịch gọilàđộưutiênp, với p là mộtsố thựcz Tiếntrìnhcóđộ ưutiêncaonhất đượcsử dụng CPUz Qui ướctrongmônhọcnày:z TiếntrìnhP1và P2có độ ưutiênp1, p2tương ứngz p1>p2có nghĩalàtiếntrìnhP1có độ ưutiênthấphơn P2z SJF là trường hợp đặcbiệtcủalậplịch có ưutiênvớiưutiêncủacáctiếntrìnhlànghịch đảo độ dài phiênsử dụng28Lậplịch có độ ưutiênz Hai cách xác định độ ưu tiên:z Độ ưutiêntrong: Được tính toán dựatrêncáctham sốđịnh lượng củatiếntrìnhnhư giớihạnvềthờigian, bộ nhớ, số file đang mở, thờigiansửdụng CPUz Độ ưutiênngoài: Dựavàocácyếutố như mứcđộ quan trọng, chi phí thuê máy tính…z Chờ không xác định: Mộttiếntrìnhcóđộ ưutiên thấpcóthể nằm trong hàng chờ trongmộtkhoảng thờigiandàinếu trong hàng chờluôn có các tiếntrìnhcóđộ ưutiêncaohơn29Lậplịch có độ ưutiênz Để tránh hiệntượng chờ không xác định, cóthêm tham số tuổi để xác định thờigiantiếntrình thờigiannằm trong hàng chờz Tham số tuổi đượcsử dụng để làm tăng độưutiêncủatiếntrìnhz Ví dụ thựctế: Khi bảodưỡng máy tính IBM 7094 của MIT năm 1973, ngườitathấymộttiếntrìnhnằm trong hàng chờ từ năm 1967 nhưng vẫnchưa đượcthựchiện30Ví dụ lậplịch có độ ưutiênz Xét 5 tiến trình như trongbảng vớithứ tự trong hàngchờ là P1, P2, P3, P4, P5z Sử dụng thuậttoánlậplịchcó ưu tiên, ta có thứ tựthựchiệncủacáctiếntrìnhnhư sau biểu đồ dướiz Thờigianchờ trung bình là(1+6+16+18)/5=8.2ms31452101215P1P2P3P4P5Độ ưutiênThờigianthựchiện(ms)TiếntrìnhP1(3)P5(2)06 16P2(1)1P3(4) P4(5)1819631Round-robin (RR)z Còn gọilàlậplịch quay vòngz Đượcthiếtkếđểáp dụng cho các hệ phânchia thời gian (time-sharing)z RR hoạt động theo chếđộpreemptivez Tham số lượng tử thời gian (time quantum) tquantum: Mỗitiếntrìnhđượcsử dụng CPU trong nhiềunhấtbằng tquantum, sau đó đếnlượttiến trình khác32Round-robin (RR)z Hiệuquả của RR phụ thuộc độ lớncủatquantumz Nếu tquantumnhỏ thì hiệuquả của RR giảmvìbộđiềuphốiphảithựchiệnnhiềuthaotácchuyểntrạng thái, lãng phí thờigianCPUz Nếu tquantumlớnthìsố thao tác chuyểntrạng tháigiảm điz Nếu tquantumrấtnhỏ (ví dụ 1ms) thì RR đượcgọi là processor sharingz Nếu tquantum= ∞ thì RR trở thành FCFS33Ví dụ RRz Giả sử có 3 tiếntrìnhP1, P2, P3vớithờigianthựchiệntương ứng là 24ms, 3ms, 6ms, thứ tự tronghàng chờ P1, P2, P3,vào hàng chờ cùng thời điểm0z Giả sử tquantum=4msz RR lậplịch các tiến trình như sau:P2P3P1P3P1P1P1P1P104 7 11 15 17 21 25 29 33zThờigianchờz P1: 0+(11-4)+(17-15)=9msz P2: 4msz P3: 7+(15-11)=11msz Thờigianchờ trung bình: (9+4+11)/3=8ms34Lậplịch vớihàngchờđamứcz Thuậtngữ: Multilevel queue schedulingz Đượcsử dụngkhitacóthể chia các tiếntrình thành nhiềulớp khác nhau để lậplịchtheo các tiêu chí khác nhau, ví dụ:z Lớpcáctiến trình có tương tác (interactive hoặcforeground process) cầncóđộ ưutiêncaohơnz Lớpcáctiếntrìnhchạynền (background) thườngkhôngcótương tác vớiNSD: Độ ưutiênthấphơn35Lậplịch vớihàngchờđamứcz Thuậttoánlậplịch với hàng chờđamứcchiahàng chờ ready thành nhiềuhàngchờ con khác nhau, mỗihàngchờ con đượcápdụngmộtloạithuật toán khác nhau, ví dụ:z Hàng chờ các tiến trình background: FCFSz Hàng chờ các tiếntrìnhcótương tác:RRz Các tiếntrìnhđượcphânlớpdựavàođặctính như bộ nhớ, độ ưu tiên, …z Cầncóthuậttoánlậplịchchocáchàngchờcon, ví dụ: preemptive có độ ưutiêncốđịnh36Ví dụ hàng chờđamứcz Ví dụ các hàng chờđamứccóđộ ưutiêngiảmdần:z Hàng chờ các tiếntrìnhhệ thốngz Hàng chờ các tiếntrìnhcótương tácz Hàng chờ các tiến trình là editorz Hàng chờ các tiếntrìnhhoạt động theo lôz Hàng chờ các tiếntrìnhthựctậpcủasinhviên737Lậplịch vớihàngchờđamứccó phảnhồiz Thuậtngữ: Multilevel feedback-queue schedulingz Thuậttoánlậplịch kiểu này nhằmkhắcphụcnhược điểm không mềmdẻo củalậplịch vớihàng chờđamứcz Ý tưởng chính: Cho phép tiến trình chuyểntừhàng chờ này sang hàng chờ khác, trong khilậplịch với hàng chờđamức không cho phépđiềunày38Lậplịch vớihàngchờđamứccó phảnhồiz Cách thựchiện:z Độ dài phiên sử dụng CPU và thờigianđãnằmtronghàngchờ là tiêu chuẩnchuyểntiếntrìnhgiữa các hàng chờz Tiến trình chiếmnhiềuthờigianCPU sẽ bịchuyểnxuống hàng chờ có độ ưutiênthấpz Tiếntrìnhnằm lâu trong hàng chờ sẽđượcchuyển lên hàng chờ có độ ưutiêncaohơn39Các tham số củabộ lậplịchhàng chờđamứccóphảnhồiz Số lượng các hàng chờz Thuậttoánlậplịch cho mỗihàngchờz Phương pháp tăng độ ưutiênchomộttiếntrìnhz Phương pháp giảm độ ưutiênchomộttiếntrìnhz Phương pháp xác định hàng đợinàođể đưamộttiếntrìnhvào40Các thuậttoánlậplịch khácz Sinh viên tìm hiểu trong giáo trình:z Lậplịch đaxử lýz Lậplịch thờigianthực41Các phương pháp đánhgiá thuậttoánlậplịch42Mô hình xác địnhz Thuậtngữ: Deterministic modelingz Dựa vào các trường hợpcụ thể (chẳng hạncác ví dụđã nói trong bài giảng này) để rút racác kếtluận đánh giáz Ưu điểm: Nhanh và đơngiảnz Nhược điểm: Không rút ra đượckếtluậnđánh giá cho trường hợptổng quát843Mô hình hàng chờz Thuậtngữ: Queueing modelz Dựatrênlýthuyếtxácsuất, quá trình ngẫu nhiên. Tàiliệuthamkhảo:z Leonard Kleinrock, Queueing Systems: Volume I – Theory(Wiley Interscience, New York, 1975) z Leonard Kleinrock, Queueing Systems: Volume II –Computer Applications (Wiley Interscience, New York, 1976) z Ưu điểm: So sánh đượccácthuật toán lậplịch trongmộtsố trường hợpz Hạnchế: Phứctạpvề mặttoánhọc, lớpcácthuậttoán phân tích so sánh đượccònhạnchế44Mô phỏngz Thuậtngữ: Simulationz Thựchiện các tình huống giảđịnh trên máytính để đánh giá hiệuquả củacácthuật toánlậplịch, kiểm nghiệmcáckếtquả lý thuyếtz Mô phỏng thường tốnthờigianCPU vàkhông gian lưutrữz Đượcsử dụng nhiều trong công nghiệpz Ví dụ các hệ mô phỏng mạng (có module hàng chờ): OPNET, NS-2, Qualnet45Cài đặtthử trong thựctếz Mô phỏng có thể xem như “qui nạp khônghoàn toàn”z Có thể xây dựng hệ thống thử trong thựctếz Ưu điểm: Đánh giá đượchiệuquả thựcsựkhi sử dụngz Nhược điểm: z Chi phí caoz Hành vi củangườisử dụng có thể thay đổi theomôi trường hệ thống46Tóm tắtz Khái niệmlậplịch, các tiêu chí đánh giá thuậttoán lậplịchz Các phương thứchoạt động preemptive vànon-preemptivez Các thuật toán lậplịch FCFS, SJF, ưu tiên, RRz Lậplịch vớihàngchờđamức, có và khôngcó phảnhồiz Các phương pháp đánh giá thuậttoánlậplịch47Bài tậpz Thựchiệnvídụ RR vớilượng tử thờigian2ms, 6ms và 6ms. z Tính thờigianchờ trungbìnhcủacáctiếntrìnhtrong các trường hợp này. z Khi lượng tử thời gian thay đổi, thờigianchờtrung bình thay đổithế nào?z Tính thời gian hoàn thành (turnaround time) củatấtcả các tiến trình trong các trường hợptrênz Nhậnxétvề sự thay đổithời gian hoàn thành củacác tiếntrìnhkhilượng tử thời gian thay đổi48Bài tậpz Hãy xây dựng mộtvídụ về hiệntượng convoy effect sao cho thờigianrỗicủathiếtbị vào raít hơnthờigianrỗicủaCPU. Giả sử có 4 tiếntrình, trong đó P là tiếntrình“lớn”, Q1, Q2, Q3là các tiến trình “nhỏ” đượcnằm trong hàngchờ theo thứ tự: P, Q1, Q2, Q3z Tìm hai ví dụ trong thựctế về hàng chờđamức và hàng chờđamứccóphảnhồivàgiảithích các ví dụ này.