Bài giảng Hệ điều hành - Chương 4: Định thời CPU - Hà Duy An

Khoa Công Nghệ Thông Tin & Truyền Thông Đại học Cần Thơ Giảng viên: Hà Duy An 9/19/2013 Chương 4: Định thời CPU1 1. Các khái niệm 2. Các giải thuật định thời 3. Định thời trong hệ thống có nhiều bộ xử lý 4. Đánh giá giải thuật 9/19/2013 Chương 4: Định thời CPU2 • Kỹ thuật đa chương giúp việc sử dụng CPU đạt hiệu quả cao nhất. • Chu kỳ CPU-I/O o Sự thực thi của tiến trình bao gồm nhiều chu kỳ CPU-I/O o Một chu kỳ CPU-I/O bao gồm chu kỳ thực thi CPU (CPU burst) và theo sau bởi chu kỳ chờ đợi vào/ra (I/O burst). => Việc phân phối chu kỳ CPU-I/O là một đặt điểm quan trọng để chọn lựa giải thuật định thời phù hợp 9/19/2013 Chương 4: Định thời CPU4 9/19/2013 Chương 4: Định thời CPU5 • Bộ định thời CPU hay bộ định thời ngắn kỳ (Short-term scheduler) chọn một trong các tiến trình trong hàng đợi sẵn sàng và cấp phát CPU cho nó thực thi o Hàng đợi có thể được sắp xếp theo nhiều cách • Quyết định định thời xảy ra khi một tiến trình: 1. Chuyển từ trạng thái đang chạy sang trạng thái chờ đợi 2. Chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng 3. Chuyển từ trạng thái chờ đợi sang sẵn sàng 4. Kết thúc • Định thời không trưng dụng (nonpreemptive): tiến trình sẽ giữ CPU và chỉ giải phóng CPU khi nó cần (trường hợp 1 và 4) • Định thời trưng dụng (preempty): các trường hợp 2 và 3; Vấn đề: o Tiến trình đang cập nhật dữ liệu chia sẽ chung? o Tiến trình đang xử lý trong chế độ nhân (kernel mode)? o Không thể bỏ qua tất cả các ngắt? 9/19/2013 Chương 4: Định thời CPU6 • Bộ điều phối (Dispatcher): Có nhiệm vụ trao quyền điều khiển CPU cho tiến trình được chọn bởi bộ định thời CPU, công việc này bao gồm: o Chuyển ngữ cảnh o Chuyển sang chế độ người dùng o Nhảy tới vị trí thích hợp trong chương trình người dùng để khởi động lại chương trình đó • Bộ điều phối cần nhanh nhất có thể. • Độ trễ điều phối (Dispatch Latency): thời gian Dispatcher cần để ngưng một tiến trình và khởi động một tiến trình khác 9/19/2013 Chương 4: Định thời CPU7 1. Hiệu suất sử dụng CPU: giữ CPU luôn bận nhiều nhất có thể. 2. Thông lượng (Throughput): số lượng tiến trình hoàn thành trên một đơn vị thời gian. 3. Thời gian xoay vòng (Turnaround time): là khoảng thời gian từ khi một tiến trình được khởi tạo đến khi nó hoàn thành. Nó là tổng các khoảng thời gian chờ đợi để đưa vào bộ nhớ, chờ trong hàng đợi sẵn sàng, thời gian thực thi trên CPU và thực hiện các xử lý I/O. 4. Thời gian chờ đợi (Waiting time): tổng thời gian trong trong hàng đợi sẵn sàng (ready queue). 5. Thời gian đáp ứng (Response time): lượng thời gian từ lúc một yêu cầu được đệ trình cho đến khi tín hiệu trả lời đầu tiên xuất hiện (dùng cho môi trường chia thời gian). 9/19/2013 Chương 4: Định thời CPU8 • Việc đánh giá giải thuật định thời được kiểm tra thông qua khả năng tối ưu hóa các tiêu chí đinh thời của nó: o Hiệu suất sử dụng CPU tối đa o Thông lượng tối đa o Thời gian xoay vòng tối thiểu o Thời gian chờ đợi tối thiểu o Thời gian đáp ứng tối thiểu 9/19/2013 Chương 4: Định thời CPU9 1. First-Come, First-Served 2. Shortest-Job-First 3. Priority 4. Round-Robin 5. Hàng đợi đa cấp 6. Hàng đợi phản hồi đa cấp 9/19/2013 Chương 4: Định thời CPU11 Tiến Trình TG sử dụng CPU P1 24 P2 3 P3 3 • Giả sử các tiến trình xuất hiện theo thứ tự P1, P2, P3. Biểu đồ Gantt cho lịch biểu là: • Thời gian chờ đợi: P1 = 0; P2 = 24; P3 = 27 • Thời gian chờ đợi trung bình: (0 + 24 + 27)/3 = 17 P1 P2 P3 24 27 300 9/19/2013 Chương 4: Định thời CPU12 • Giả sử các tiến trình xuất hiện theo thứ tự P2, P3, P1. Biểu đồ Gantt cho lịch biểu là: • Thời gian chờ đợi: P1= 6; P2 = 0; P3 = 3 • Thời gian chờ đợi trung bình: (6 + 0 + 3)/3 = 3 • Tốt hơn nhiều so với trường hợp trước. • Tác động nối đuôi: tiến trình ngắn nằm sau tiến trình dài. • FCFS là giải thuật định thời không trưng dụng, không thích hợp cho hệ thống chia thời gian. P1P3P2 63 300 9/19/2013 Chương 4: Định thời CPU13 • Kết hợp với mỗi tiến trình độ dài thời gian mà nó sẽ sử dụng CPU lần kế tiếp. Khi CPU rãnh, nó sẽ được cấp cho tiến trình có thời gian sử dụng CPU lần kế tiếp ngắn nhất. • Có hai cách thức thực hiện giải thuật: o Không trưng dụng: một khi CPU được giao cho một tiến trình, nó không thể bị trưng dụng để giao cho tiến trình khác có thời gian ngắn hơn cho đến khi tiến trình này sử dụng CPU xong. o Trưng dụng: nếu một tiến trình mới đến có thời gian sử dụng CPU ngắn hơn thời gian thực thi còn lại của tiến trình đang chạy, thì ưu tiên giao CPU cho tiến trình mới đến. Cách thức này được gọi là Shortest-Remaining-Time-First (SRTF). • SJF là tối ưu – nó tạo ra thời gian chờ đợi trung bình ngắn nhất. 9/19/2013 Chương 4: Định thời CPU14 Tiến trình TG đến TG sử dụng CPU P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 • SJF (không trưng dụng) • Thời gian chờ đợi trung bình = (0 + 6 + 3 + 7)/4 = 4 P1 P3 P2 73 160 P4 8 12 9/19/2013 Chương 4: Định thời CPU15 Tiến trình TG đến TG sử dụng CPU P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 • SJF (trưng dụng) • Thời gian chờ đợi trung bình = (9 + 1 + 0 +2)/4 = 3 • Bài Tập P1 P3P2 42 110 P4 5 7 P2 P1 16 9/19/2013 Chương 4: Định thời CPU16 • Chỉ có thể ước lượng độ dài – có thể tương tự như lần sử dụng trước đó. • Độ dài ước lượng được tính toán dựa trên chiều dài thời gian sử dụng CPU lần trước đó, sử dụng công thức trung bình mũ: • Thông thường α = ½ nnn n n t t    )1( 1 1       :nghóa Ñònh4. 10 , 3. 1n thöù laàn CPU duïng söû gian thôøi löôïng öôùc 2. n thöùlaàn teáthöïcCPUduïngsöûgianthôøi 1. 9/19/2013 Chương 4: Định thời CPU17 9/19/2013 Chương 4: Định thời CPU18 • α =0 o τn+1 = τn o Không tính đến thời gian sử dụng CPU gần nhất • α =1 o τn+1 = tn o Chỉ tính đến thời gian sử dụng CPU thực gần nhất • α =1/2, lịch sử quá khứ và gần đây có trọng số tương đương. • Nếu mở rộng công thức, ta có: τn+1 = α tn+(1 - α) α tn-1 + +(1 - α )j+1 α tn-j + +(1 - α )n+1τ0 • Vì α và (1- α) nhỏ hơn hay bằng 1, mỗi số hạng tiếp theo có trọng số nhỏ hơn số hạng trước đó. 9/19/2013 Chương 4: Định thời CPU19 • Một chỉ số ưu tiên được gán cho mỗi tiến trình • CPU sẽ được cấp cho tiến trình có độ ưu tiên cao nhất, nghĩa là chỉ số ưu tiên nhỏ nhất (smallest integer ≡ highest priority). • Có thể trưng dụng hoặc không trưng dụng • SJF là một trường hợp của định thời ưu tiên, trong đó độ ưu tiên là thời gian ước tính sử dụng CPU lần kế tiếp. • Vấn đề đói CPU (starvation): các tiến trình có độ ưu tiên thấp có khả năng không bao giờ được thực thi. • Giải pháp: đặt thời hạn (aging) – khi thời gian trôi đi, độ ưu tiên của tiến trình càng tăng theo. 9/19/2013 Chương 4: Định thời CPU20 ProcessAarri Burst TimeT Priority P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 • Priority scheduling Gantt Chart • Average waiting time = 8.2 msec 9/19/2013 Chương 4: Định thời CPU21 P2 P3P5 1 180 16 P4 196 P1 • Mỗi tiến trình được CPU phục vụ trong một đơn vị thời gian nhỏ, gọi là định mức thời gian (time quantum), thường là 10-100 milliseconds. • Sau khoảng thời gian này, CPU bị trưng dụng và giao cho tiến trình khác, tiến trình bị ngưng và chuyển vào hàng đợi sẵn sàng. • Nếu có n tiến trình đang nằm trong hàng đợi sẵn sàng và định mức thời gian là q, thì mỗi tiến trình sẽ nhận được 1/n tổng thời gian của CPU, thời gian phục vụ của CPU cho nó tối đa là q. Sẽ không có tiến trình nào phải chờ đợi quá lượng thời gian là (n-1)q. • Bộ điếm thời gian (Timer) sẽ phát ra các ngắt (interrupt) sau mỗi định mức thời gian để định thời cho tiến trình tiếp theo • Hiệu năng: o q lớn⇒ FCFS (FIFO) o q nhỏ⇒ q phải đủ lớn do ta phải quan tâm đến việc chuyển đổi ngữ cảnh, nếu không, thời gian lãng phí sẽ rất cao. o q thường 10-100 ms, context switch < 10 μsec 9/19/2013 Chương 4: Định thời CPU22 9/19/2013 Chương 4: Định thời CPU23 9/19/2013 Chương 4: Định thời CPU24 80% of CPU bursts should be shorter than q Process TG sử dụng CPU P1 53 P2 17 P3 68 P4 24 • Biểu đồ Gantt: • Thông thường, RR có thời gian chờ đợi trung bình lớn hơn SJF, nhưng đảm bảo thời gian đáp ứng tốt hơn. P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 57 77 97 117 121 134 154 162 9/19/2013 Chương 4: Định thời CPU25 • Hàng đợi sẵn sàng được chia thành nhiều hàng đợi, tiến trình được gán cố định vào một hàng đợi, vd: o foreground (interactive): cần thời gian đáp ứng nhanh hơn -> ưu tiên hơn; o background (batch): có thể đáp ứng chậm hơn -> ít ưu tiên hơn. • Mỗi hàng đợi có giải thuật lập lịch biểu riêng: o foreground – RR o background – FCFS • Thực hiện định thời giữa các hàng đợi, 2 khả năng: o Định thời với độ ưu tiên cố định (nghĩa là, phục vụ tất cả tiến trình trong foreground trước rồi đến background). Có khả năng dẫn đến việc đói CPU. o Phân chia thời gian (time slice) – mỗi hàng đợi nhận được một khoảng thời gian phục vụ nào đó của CPU để định thời cho các tiến trình nằm trong đó; VD 80% cho foreground với RR và 20% cho background với FCFS 9/19/2013 Chương 4: Định thời CPU26 9/19/2013 Chương 4: Định thời CPU27 • Một tiến trình có thể di chuyển giữa các hàng đợi khác nhau. • Cơ chế định thời hạn có thể được cài đặt theo cách: o Nếu tiến trình dùng quá nhiều thời gian CPU, nó sẽ được di chuyển vào hàng đợi có độ ưu tiên thấp hơn; o Nếu tiến trình đã chờ quá lâu trong 1 hàng đợi với độ ưu tiên thấp, nó sẽ được chuyển sang hàng đợi có độ ưu tiên cao hơn => aging • Bộ định thời đa cấp có phản hồi được định nghĩa bằng những tham số sau: o Số lượng hàng đợi o Giải thuật định thời cho từng hàng đợi o Phương thức dùng để quyết định khi nào thì nâng cấp một tiến trình. o Phương thức dùng để quyết định khi nào thì hạ cấp một tiến trình o Phương thức dùng để quyết định là nên đặt tiến trình vào hàng đợi nào khi tiến trình này cần được phục vụ. 9/19/2013 Chương 4: Định thời CPU28 • Có 3 hàng đợi: o Q0: định mức thời gian là 8 milliseconds o Q1: định mức thời gian là 16 milliseconds o Q2: FCFS • Định thời: 9/19/2013 Chương 4: Định thời CPU29 o Một công việc mới sẽ bước vào Q0 mà ở đó nó sẽ được phục vụ theo kiểu FCFS. Khi đạt được CPU, công việc sẽ nhận được thời gian 8 milliseconds. Nếu nó không hoàn thành trong vòng 8 milliseconds, công việc sẽ được chuyển sang Q1. o Tại Q1 công việc sẽ lại được phục vụ theo kiểu FCFS và nhận được thêm 16 milliseconds. Nếu nó vẫn chưa hoàn thành, nó sẽ bị tước CPU và chuyển qua Q2. • Định thời CPU sẽ phức tạp hơn với nhiều CPU hiện hữu. • Các bộ xử lý giống nhau trong cùng một hệ thống đa xử lý. • Việc định thời có thể thực hiện: o Đa xử lý bất đối xứng (Asymmetric Multiprocessor): chỉ một CPU truy cập đến các cấu trúc dữ liệu dùng chung => giảm việc bảo vệ các dữ liệu dùng chung o Đa xử lý đối xứng (Symmetric Multiprocessor): mỗi CPU tự định thời từ hàng đợi chung, hay có riêng một hàng đợi cho mỗi CPU => đang được sử dụng phổ biến ngày nay • Thực thi một tiến trình trên cùng một bộ xử lý trong suốt tiến trình thực thi của tiến trình – processor affinity o Soft affinity o Hard affinity 9/19/2013 Chương 4: Định thời CPU31 9/19/2013 Chương 4: Định thời CPU32 Note that memory-placement algorithms can also consider affinity • Đối với hệ thống SMP cần giữ tải cân bằng giữa các CPU nhằm nâng cao hiệu quả hoạt động của hệ thống • Cân bằng tải (load balancing) được thực hiện bằng cách cố gắng phân phối các công việc cho các CPU bằng nhau: o Push migration – định kỳ kiểm tra tải trên mỗi CPU, nếu CPU nào bị quá tải thì "đẩy"bớt công việc cho CPU khác o Pull migration – các CPU rãnh "kéo" các công việc đang chờ trên một CPU khác về thực thi 9/19/2013 Chương 4: Định thời CPU33 • Nhiều lõi vi xử lý được đặt trên cùng một bộ xử lý => vi xử lý đa nhân • Nhanh hơn và tiêu tốn ít năng lượng hơn • Hỗ trợ đa luồng trên mỗi nhân o Một luồng có thể được thực thi trong khi luồng khác đang truy xuất bộ nhớ. 9/19/2013 Chương 4: Định thời CPU34 9/19/2013 Chương 4: Định thời CPU35 1. Mô hình xác định 2. Mô hình hàng đợi 3. Mô phỏng 4. Cài đặt • Cách đánh giá và chọn giải thuật thích hợp cho một hệ điều hành? • Xác định các tiêu chí, đánh giá giải thuật dựa trên các tiêu chí đó • Deterministic modeling – mô hình xác định o Đánh giá dựa trên sự phân tích o Dựa vào tải công việc (workload) được xác định trước và tính toán hiệu năng của mỗi giải thuật. • Cho các tiến trình đến vào cùng một thời điểm: 9/19/2013 Chương 4: Định thời CPU37 • Với mỗi giải thuật tính thời gian chờ trung bình • Đơn giản, nhanh chóng, nhưng yêu cầu phải có các số liệu đầu vào chính xác, và chỉ đúng cho những dữ liệu đầu vào như đã cho o FCFS: 28ms o Non-preemptive SJF: 13ms o RR: 23ms 9/19/2013 Chương 4: Định thời CPU38 • Xác định sự phân phối các tiến trình đến và chu kỳ CPU-I/O theo xác xuất, là điều có thể xác định được trong thưc tế. o Thông thường phân phối theo hàm mũ o Từ hai phân phối trên ta có thể tính trung bình thông lượng, hiệu năng tận dụng CPU, thời gian chờ, • Hệ thống máy tính được mô tả như một mạng các server có các hàng đợi riêng (CPU là một server với hàng đợi sẵn sàng). o Biết tốc độ đến và tốc độ phục vụ (dựa vào sự phân bổ chu kỳ CPU-I/O) => có thể tính khả năng sử dụng, chiều dài hàng đợi trung bình, thời gian chờ trung bình. 9/19/2013 Chương 4: Định thời CPU39 • Luật Little – khi hệ thống trong trạng thái ổn định, số lượng các tiến trình rời khỏi hàng đợi sẽ bằng với số lượng các tiến trình vào hàng đợi: n =  xW • Trong đó: o n: chiều dài hàng đợi trung bình o λ: tốc độ đến trung bình cho các tiến trình mới (vd 4 tiến trình/giây) o W: thời gian chờ trung bình trong hàng đợi • VD: trung bình có 7 tiến trình đến mỗi giây, và thông thường có 14 tiến trình trong hệ thống, thì thời gian chờ trung bình của mỗi tiến trình là: 2s 9/19/2013 Chương 4: Định thời CPU40 • Mô hình hàng đợi có độ chính xác giới hạn • Mô phỏng cho kết quả chính xác hơn: o Dùng phần mềm mô phỏng hệ thống máy tính o Clock là một biến o Khi thực thi mô phỏng, các thống kê hiệu năng của các giải thuật sẽ được ghi nhận và là cơ sở cho vịêc so sánh các giải thuật. o Dữ liệu dùng để thực hiện mô phỏng: • Bộ sinh số ngẫu nhiên theo xác xuất o Phân phối theo mô hình toán học hay theo kinh nghiệm • Các sự kiện dược ghi lại trong hệ thống thực 9/19/2013 Chương 4: Định thời CPU41 9/19/2013 Chương 4: Định thời CPU42 • Kể cả mô phỏng cũng cho kết quả giới hạn • Cài đặt và kiểm tra các giải thuật định thời trên hệ thống thật sẽ cho độ chính xác cao nhất o Chi phí cao, rủi ro cao o Môi trường đa dạng • Hầu hết các bộ định thời có thể được sửa đổi để phù hợp với từng hệ thống => kết quả không chính xác trong các tình huống tổng quát khác. 9/19/2013 Chương 4: Định thời CPU43