Giới thiệu về hệ điều hành
Này Habr! Theo quan điểm của tôi, tôi muốn giới thiệu với các bạn một loạt bài viết-bản dịch của một nền văn học thú vị - OSTEP. Tài liệu này thảo luận khá sâu về công việc của các hệ điều hành giống unix, cụ thể là làm việc với các tiến trình, các bộ lập lịch khác nhau, bộ nhớ và các thành phần tương tự khác tạo nên một hệ điều hành hiện đại. Bạn có thể xem bản gốc của tất cả các tài liệu ở đây . Xin lưu ý rằng bản dịch được thực hiện không chuyên nghiệp (khá tự do), nhưng tôi hy vọng tôi vẫn giữ được ý nghĩa chung.
Phòng thí nghiệm về chủ đề này có thể được tìm thấy ở đây:
Những khu vực khác:
Bạn cũng có thể xem kênh của tôi tại =)
Giới thiệu về Trình lập lịch biểu
Bản chất của vấn đề: Làm thế nào để phát triển chính sách lập lịch
Các khung chính sách lập lịch cơ bản nên được thiết kế như thế nào? Những giả định chính nên là gì? Những số liệu nào là quan trọng? Những kỹ thuật cơ bản nào đã được sử dụng trong các hệ thống máy tính đầu tiên?
Giả định về khối lượng công việc
Trước khi thảo luận về các chính sách khả thi, trước tiên chúng ta hãy thực hiện một số lạc đề đơn giản hóa về các quy trình đang chạy trong hệ thống, được gọi chung là khối lượng công việc. Xác định khối lượng công việc là một phần quan trọng trong việc xây dựng chính sách và bạn càng biết nhiều về khối lượng công việc thì bạn càng có thể viết chính sách tốt hơn.
Chúng ta hãy đưa ra các giả định sau về các tiến trình đang chạy trong hệ thống, đôi khi còn được gọi là việc làm (nhiệm vụ). Hầu như tất cả những giả định này đều không thực tế nhưng cần thiết cho sự phát triển của tư duy.
- Mỗi tác vụ chạy trong cùng một khoảng thời gian,
- Tất cả các nhiệm vụ được thiết lập đồng thời,
- Nhiệm vụ được giao thực hiện cho đến khi hoàn thành,
- Tất cả các tác vụ chỉ sử dụng CPU,
- Thời gian chạy của từng nhiệm vụ được biết trước.
Số liệu của người lập lịch
Ngoài một số giả định về tải, cần có một công cụ khác để so sánh các chính sách lập lịch khác nhau: số liệu của bộ lập lịch. Một số liệu chỉ là một số thước đo của một cái gì đó. Có một số số liệu có thể được sử dụng để so sánh các bộ lập lịch.
Ví dụ: chúng tôi sẽ sử dụng số liệu được gọi là thời gian quay vòng (thời gian quay vòng). Thời gian hoàn thành nhiệm vụ được định nghĩa là sự chênh lệch giữa thời gian hoàn thành nhiệm vụ và thời gian đến nhiệm vụ trong hệ thống.
Xoay quanh=Thoàn thành−Đến nơi
Vì chúng ta giả định rằng tất cả các nhiệm vụ đều đến cùng một lúc nên Ta=0 và do đó Tt=Tc. Giá trị này đương nhiên sẽ thay đổi khi chúng ta thay đổi các giả định trên.
Một thước đo khác - công bằng (công bằng, trung thực). Năng suất và sự công bằng thường là những đặc điểm đối lập nhau trong quy hoạch. Ví dụ: bộ lập lịch có thể tối ưu hóa hiệu suất nhưng phải trả giá bằng việc chờ các tác vụ khác chạy, do đó làm giảm tính công bằng.
ĐẦU TIÊN VÀO ĐẦU RA (FIFO)
Thuật toán cơ bản nhất mà chúng ta có thể triển khai được gọi là FIFO hoặc đến trước (vào), phục vụ trước (ra). Thuật toán này có một số ưu điểm: nó rất dễ thực hiện, phù hợp với tất cả các giả định của chúng tôi và thực hiện công việc khá tốt.
Hãy xem xét một ví dụ đơn giản. Giả sử có 3 nhiệm vụ được đặt đồng thời. Nhưng hãy giả sử rằng tác vụ A đến sớm hơn tất cả những tác vụ khác một chút, vì vậy nó sẽ xuất hiện trong danh sách thực thi sớm hơn những tác vụ khác, giống như B so với C. Giả sử rằng mỗi tác vụ trong số chúng sẽ được thực thi trong 10 giây. Thời gian trung bình để hoàn thành những nhiệm vụ này trong trường hợp này là bao nhiêu?
Bằng cách đếm các giá trị - 10+20+30 và chia cho 3, chúng ta có được thời gian thực hiện chương trình trung bình bằng 20 giây.
Bây giờ hãy thử thay đổi giả định của chúng ta. Cụ thể là giả định 1 và do đó chúng ta sẽ không còn giả định rằng mỗi tác vụ cần một khoảng thời gian như nhau để thực hiện. Lần này FIFO sẽ hoạt động như thế nào?
Hóa ra, thời gian thực hiện nhiệm vụ khác nhau có tác động cực kỳ tiêu cực đến năng suất của thuật toán FIFO. Giả sử rằng nhiệm vụ A sẽ mất 100 giây để hoàn thành, trong khi nhiệm vụ B và C vẫn mất 10 giây mỗi nhiệm vụ.
Như có thể thấy từ hình, thời gian trung bình của hệ thống sẽ là (100+110+120)/3=110. Hiệu ứng này được gọi là hiệu ứng đoàn xe, khi một số người tiêu dùng tài nguyên ngắn hạn sẽ xếp hàng sau một người tiêu dùng nhiều. Nó giống như việc xếp hàng ở cửa hàng tạp hóa khi có một khách hàng đứng trước bạn với một xe đẩy đầy hàng. Giải pháp tốt nhất cho vấn đề này là cố gắng thay đổi máy tính tiền hoặc thư giãn và hít thở sâu.
Công việc ngắn nhất đầu tiên
Có thể bằng cách nào đó giải quyết được tình huống tương tự bằng các quy trình nặng nề không? Chắc chắn. Một loại kế hoạch khác được gọi làCông việc ngắn nhất đầu tiên (SJF). Thuật toán của nó cũng khá nguyên thủy - đúng như tên gọi, các tác vụ ngắn nhất sẽ được khởi chạy trước tiên, lần lượt từng tác vụ khác.
Trong ví dụ này, kết quả của việc chạy các quy trình tương tự sẽ là sự cải thiện về thời gian quay vòng chương trình trung bình và nó sẽ bằng 50 thay vì 110, tốt hơn gần gấp 2 lần.
Vì vậy, với giả định rằng tất cả các nhiệm vụ đều đến cùng một lúc, thuật toán SJF dường như là thuật toán tối ưu nhất. Tuy nhiên, giả định của chúng tôi vẫn có vẻ không thực tế. Lần này chúng ta thay đổi giả định 2 và lần này hãy tưởng tượng rằng các nhiệm vụ có thể xuất hiện bất cứ lúc nào chứ không phải tất cả cùng một lúc. Điều này có thể dẫn tới những vấn đề gì?
Hãy tưởng tượng rằng nhiệm vụ A (100c) đến trước và bắt đầu được thực thi. Tại thời điểm t=10, nhiệm vụ B và C đến, mỗi nhiệm vụ sẽ mất 10 giây. Vì vậy, thời gian thực hiện trung bình là (100+(110-10)+(120-10))3 = 103. Bộ lập lịch có thể làm gì để cải thiện điều này?
Thời gian hoàn thành đầu tiên ngắn nhất (STCF)
Để cải thiện tình hình, chúng tôi bỏ qua giả định 3 rằng chương trình được khởi chạy và chạy cho đến khi hoàn thành. Ngoài ra, chúng tôi sẽ cần hỗ trợ phần cứng và như bạn có thể đoán, chúng tôi sẽ sử dụng hẹn giờ để làm gián đoạn một tác vụ đang chạy và chuyển đổi ngữ cảnh. Do đó, bộ lập lịch có thể thực hiện điều gì đó khi nhiệm vụ B, C đến - dừng thực hiện nhiệm vụ A và đưa nhiệm vụ B và C vào xử lý, sau khi hoàn thành chúng sẽ tiếp tục thực hiện quy trình A. Bộ lập lịch như vậy được gọi là STCFhoặc Ưu tiên công việc đầu tiên.
Kết quả của bảng kế hoạch này sẽ là kết quả sau: ((120-0)+(20-10)+(30-10))/3=50. Vì vậy, một bộ lập lịch như vậy càng trở nên tối ưu hơn cho các nhiệm vụ của chúng ta.
Thời gian phản hồi số liệu
Như vậy, nếu chúng ta biết thời gian chạy của các tác vụ và các tác vụ này chỉ sử dụng CPU thì STCF sẽ là giải pháp tốt nhất. Và vào thời kỳ đầu, những thuật toán này hoạt động khá tốt. Tuy nhiên, người dùng hiện dành phần lớn thời gian của mình tại thiết bị đầu cuối và mong đợi trải nghiệm tương tác hiệu quả. Do đó, một số liệu mới đã ra đời - thời gian đáp ứng (phản ứng).
Thời gian đáp ứng được tính như sau:
Tresponse=Tfirstrun−Tarrival
Do đó, đối với ví dụ trước, thời gian phản hồi sẽ là: A=0, B=0, C=10 (abg=3,33).
Và hóa ra thuật toán STCF không tốt lắm trong tình huống 3 nhiệm vụ đến cùng lúc - nó sẽ phải đợi cho đến khi các nhiệm vụ nhỏ được hoàn thành hoàn toàn. Vì vậy, thuật toán này tốt cho chỉ số thời gian quay vòng nhưng lại không tốt cho chỉ số tương tác. Hãy tưởng tượng nếu bạn đang ngồi ở một thiết bị đầu cuối cố gắng nhập các ký tự vào trình soạn thảo và phải đợi hơn 10 giây vì một số tác vụ khác đang chiếm CPU. Nó không dễ chịu lắm.
Vì vậy, chúng tôi phải đối mặt với một vấn đề khác - làm cách nào chúng tôi có thể xây dựng một bộ lập lịch nhạy cảm với thời gian phản hồi?
Round Robin
Một thuật toán đã được phát triển để giải quyết vấn đề này Round Robin (RR). Ý tưởng cơ bản khá đơn giản: thay vì chạy các tác vụ cho đến khi chúng hoàn thành, chúng ta sẽ chạy tác vụ đó trong một khoảng thời gian nhất định (gọi là lát thời gian) rồi chuyển sang một tác vụ khác từ hàng đợi. Thuật toán lặp lại công việc của nó cho đến khi hoàn thành tất cả các nhiệm vụ. Trong trường hợp này, thời gian chạy của chương trình phải là bội số của thời gian, sau đó bộ hẹn giờ sẽ làm gián đoạn quá trình. Ví dụ: nếu bộ hẹn giờ làm gián đoạn một quy trình cứ sau mỗi x = 10 mili giây thì kích thước của cửa sổ thực thi quy trình phải là bội số của 10 và là 10,20 hoặc x*10.
Hãy xem một ví dụ: Các tác vụ ABC đến hệ thống đồng thời và mỗi tác vụ muốn chạy trong 5 giây. Thuật toán SJF sẽ hoàn thành từng nhiệm vụ trước khi bắt đầu nhiệm vụ khác. Ngược lại, thuật toán RR có cửa sổ khởi chạy = 1s sẽ trải qua các tác vụ như sau (Hình 4.3):
(Lại SJF (Không tốt về thời gian phản hồi)
(Round Robin (Tốt cho thời gian phản hồi)
Thời gian phản hồi trung bình cho thuật toán RR là (0+1+2)/3=1, trong khi đối với SJF (0+5+10)/3=5.
Thật hợp lý khi cho rằng cửa sổ thời gian là một tham số rất quan trọng đối với RR; nó càng nhỏ thì thời gian phản hồi càng cao. Tuy nhiên, bạn không nên đặt nó quá nhỏ vì thời gian chuyển ngữ cảnh cũng sẽ đóng một vai trò trong hiệu suất tổng thể. Do đó, việc lựa chọn thời gian thực thi của cửa sổ do kiến trúc sư hệ điều hành đặt ra và phụ thuộc vào các tác vụ được lên kế hoạch thực hiện trong đó. Chuyển ngữ cảnh không phải là hoạt động dịch vụ duy nhất gây lãng phí thời gian - chương trình đang chạy hoạt động trên rất nhiều thứ khác, chẳng hạn như các bộ nhớ đệm khác nhau và với mỗi lần chuyển đổi, cần phải lưu và khôi phục môi trường này, điều này cũng có thể mất rất nhiều thời gian. thời gian.
RR là một công cụ lập lịch tuyệt vời nếu chúng ta chỉ nói về chỉ số thời gian phản hồi. Nhưng thước đo thời gian hoàn thành nhiệm vụ sẽ hoạt động như thế nào với thuật toán này? Xét ví dụ trên, khi thời gian hoạt động của A, B, C = 5s và đến cùng một lúc. Nhiệm vụ A sẽ kết thúc lúc 13, B lúc 14, C lúc 15s và thời gian hoàn thành trung bình sẽ là 14s. Do đó, RR là thuật toán kém nhất cho số liệu doanh thu.
Nói một cách tổng quát hơn, bất kỳ thuật toán loại RR nào cũng công bằng; nó chia đều thời gian CPU cho tất cả các quy trình. Và do đó, các số liệu này liên tục xung đột với nhau.
Do đó, chúng ta có một số thuật toán tương phản và đồng thời vẫn còn một số giả định - rằng thời gian của tác vụ đã được biết và tác vụ đó chỉ sử dụng CPU.
Trộn với I/O
Trước hết, hãy loại bỏ giả định 4 rằng quy trình chỉ sử dụng CPU; một cách tự nhiên, trường hợp này không xảy ra và các quy trình có thể truy cập vào các thiết bị khác.
Thời điểm bất kỳ tiến trình nào yêu cầu thao tác I/O, tiến trình đó sẽ chuyển sang trạng thái bị chặn, chờ I/O hoàn tất. Nếu I/O được gửi tới ổ cứng thì thao tác như vậy có thể mất tới vài mili giây hoặc lâu hơn và bộ xử lý sẽ không hoạt động vào lúc này. Trong thời gian này, bộ lập lịch có thể chiếm giữ bộ xử lý bằng bất kỳ quy trình nào khác. Quyết định tiếp theo mà bộ lập lịch sẽ phải đưa ra là khi nào tiến trình sẽ hoàn thành I/O của nó. Khi điều này xảy ra, một ngắt sẽ xảy ra và HĐH sẽ đưa tiến trình gọi I/O vào trạng thái sẵn sàng.
Hãy xem xét một ví dụ về một số vấn đề. Mỗi trong số chúng yêu cầu 50ms thời gian CPU. Tuy nhiên, cái đầu tiên sẽ truy cập I/O cứ sau 10 mili giây (cũng sẽ được thực thi sau mỗi 10 mili giây). Và quy trình B chỉ cần sử dụng bộ xử lý 50ms không có I/O.
Trong ví dụ này chúng ta sẽ sử dụng bộ lập lịch STCF. Bộ lập lịch sẽ hoạt động như thế nào nếu một quy trình như A được khởi chạy trên nó? Anh ấy sẽ làm như sau: đầu tiên anh ấy sẽ hoàn thiện quy trình A, sau đó xử lý B.
Cách tiếp cận truyền thống để giải quyết vấn đề này là xử lý mỗi nhiệm vụ con 10 ms của quy trình A như một nhiệm vụ riêng biệt. Do đó, khi bắt đầu với thuật toán STJF, việc lựa chọn giữa tác vụ 50 ms và tác vụ 10 ms là hiển nhiên. Sau đó, khi nhiệm vụ phụ A được hoàn thành, quy trình B và I/O sẽ được khởi chạy. Sau khi I/O hoàn tất, thông thường sẽ bắt đầu lại quy trình A 10ms thay vì quy trình B. Bằng cách này, có thể thực hiện chồng chéo, trong đó CPU được sử dụng bởi một quy trình khác trong khi quy trình đầu tiên đang chờ Tôi/O. Và kết quả là hệ thống được sử dụng tốt hơn - tại thời điểm các quy trình tương tác đang chờ I/O, các quy trình khác có thể được thực thi trên bộ xử lý.
Nhà tiên tri không còn nữa
Bây giờ chúng ta hãy thử loại bỏ giả định rằng thời gian chạy của tác vụ đã được biết trước. Đây thường là giả định tồi tệ nhất và phi thực tế nhất trong toàn bộ danh sách. Trên thực tế, trong một hệ điều hành thông thường, bản thân hệ điều hành đó thường biết rất ít về thời gian thực hiện các tác vụ, vậy làm sao bạn có thể xây dựng một bộ lập lịch mà không biết tác vụ sẽ thực hiện trong bao lâu? Có lẽ chúng ta có thể sử dụng một số nguyên tắc RR để giải quyết vấn đề này?
Tổng
Chúng tôi đã xem xét các ý tưởng cơ bản về lập kế hoạch nhiệm vụ và xem xét 2 nhóm người lập lịch trình. Nhiệm vụ đầu tiên bắt đầu nhiệm vụ ngắn nhất trước và do đó làm tăng thời gian quay vòng, trong khi nhiệm vụ thứ hai được chia đều giữa tất cả các nhiệm vụ, tăng thời gian phản hồi. Cả hai thuật toán đều tệ trong khi thuật toán của họ kia tốt. Chúng tôi cũng đã xem xét việc sử dụng song song CPU và I/O có thể cải thiện hiệu suất như thế nào nhưng không giải quyết được vấn đề với khả năng thấu thị của hệ điều hành. Và trong bài học tiếp theo, chúng ta sẽ xem xét một công cụ lập kế hoạch nhìn về quá khứ trước mắt và cố gắng dự đoán tương lai. Và nó được gọi là hàng đợi phản hồi đa cấp.
Nguồn: www.habr.com