lịch sử hệ điều hành mã nguồn mở và miễn phí real time scheduling principles of deadlock

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.25 MB, 20 trang )

<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

TIỂU LUẬN GIỮA KÌMƠN NHẬP MƠN HỆ ĐIỀU HÀNH

CHỦ ĐỀ 1: LỊCH SỬ HỆ ĐIỀU HÀNH MÃNGUỒN MỞ VÀ MIỄN PHÍ

CHỦ ĐỀ 2: REAL-TIME SCHEDULINGCHỦ ĐỀ 3: PRINCIPLES OF DEADLOCK

Người hướng dẫn: TRẦN TRUNG TÍNNgười thực hiện: NGUYỄN NGỌC HƯƠNG GIANG - 52100019Lớp : 21050201Khoá : 25

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2022

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

TIỂU LUẬN GIỮA KÌMƠN NHẬP MƠN HỆ ĐIỀU HÀNH

CHỦ ĐỀ 1: LỊCH SỬ HỆ ĐIỀU HÀNH MÃNGUỒN MỞ VÀ MIỄN PHÍ

CHỦ ĐỀ 2: REAL-TIME SCHEDULINGCHỦ ĐỀ 3: PRINCIPLES OF DEADLOCK

Người hướng dẫn: TRẦN TRUNG TÍNNgười thực hiện: NGUYỄN NGỌC HƯƠNG GIANG - 52100019Lớp : 21050201Khố : 25

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2022

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

LỜI CẢM ƠN

Để có được một tiểu luận giữa kì hồn chỉnh ,trước hết, em xin gửi lời cảmơn chân thành nhất đến toàn bộ quý thầy cô Trường Đại học Tôn Đức Thắng nóichung đã tạo điều kiện tốt nhất cho em nghiên cứu vào học tập đặc biệt là thầy TrầnTrung Tín nói riêng đã tận tình chỉ dạy và trang bị cho em những kiến thức cần thiếttrong suốt thời gian qua giúp em dần trở nên hoàn thiện và khắc phục được nhữngkhuyết điểm, sai sót trong q trình học tập.

Tuy bài tiểu luận đã hồn thành nhưng vẫn khơng tránh khỏi những sai sót.Rất mong q thầy cơ đánh giá góp ý để bài tiểu luận của em được tốt hơn. Một lầnnữa em xin cảm ơn và gửi lời chúc sức khỏe đến quý thầy cô.

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

TIỂU LUẬN ĐƯỢC HỒN THÀNHTẠI TRƯỜNG ĐẠI HỌC TƠN ĐỨC THẮNG

Tơi xin cam đoan đây là cơng trình nghiên cứu của riêng tôi và được sựhướng dẫn khoa học của thầy Trần Trung Tín. Các nội dung nghiên cứu, kếtquả trong đề tài này là trung thực và chưa cơng bố dưới bất kỳ hình thức nàotrước đây. Những số liệu trong các bảng biểu phục vụ cho việc phân tích, nhậnxét, đánh giá được chính tác giả thu thập từ các nguồn khác nhau có ghi rõtrong phần tài liệu tham khảo.

Ngồi ra, trong bài tiểu luận cịn sử dụng một số nhận xét, đánh giá cũngnhư số liệu của các tác giả khác, cơ quan tổ chức khác đều có trích dẫn và chúthích nguồn gốc.

Nếu phát hiện có bất kỳ sự gian lận nào tơi xin hoàn toàn chịu tráchnhiệm về nội dung tiểu luận của mình. Trường Đại học Tơn Đức Thắngkhơng liên quan đến những vi phạm tác quyền, bản quyền do tôi gây ra trongq trình thực hiện (nếu có).

TP. Hồ Chí Minh, ngày 27 tháng 5 năm 2022Tác giả

(Ký tên và ghi rõ họ tên)

Nguyễn Ngọc Hương Giang

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

PHẦN XÁC NHẬN VÀ ĐÁNH GIÁ CỦA GIẢNG VIÊN

* Phần xác nhận của GV hướng dẫn

_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Tp. Hồ Chí Minh, ngày tháng năm

(kí và ghi họ tên)

* Phần đánh giá của GV chấm bài

(kí và ghi họ tên)

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

TÓM TẮT

Nội dung bài tiểu luận bao gồm 3 phần được giao thuộc môn Nhập mơn Hệđiều hành. Ở phần 1, em sẽ trình bài về lịch sử hệ điều hành mã nguòn mở và miễnphí. Ở phần 2, em sẽ làm về real-time scheduling và phần cuối cùng sẽ về principlesof deadlock.

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

CHỦ ĐỀ 1 - LỊCH SỬ HỆ ĐIỀU HÀNH MÃ NGUỒN MỞ VÀMIỄN PHÍ

1.1 Lịch sử

- Những năm 1950, phần mềm thường đi kèm với mã nguồn. Tuy nhiên các nhómngười dùng “Homebrew” lúc bấy giờ đã trao đổi chấp nhận đóng góp của cácchương trình mã nguồn, thu thập và phân phối chúng cho các thành viên khác trongnhóm. Năm 1970, hệ điều hành của Digital được phân phối dưới dạng mã nguồn màkhơng có hạn chế hoặc thơng báo bản quyền.

- Với mục đích để hạn chế việc sử dụng phần mềm của các công ty máy tính vàphần mềm đối với các máy tính được ủy quyền và khách hàng trả tiền, họ đã chophát hành mã nguồn mở có sẵn ở định dạng mã nguồn chứ không phải là mã nhịphân được biên dịch.

=> Hệ điều hành mã nguồn mở ra đời

- Phần mềm miễn phí và phần mềm nguồn mở là hai ý tưởng khác nhau được cácnhóm người khác nhau ủng hộ. Phần mềm miễn phí khơng chỉ cung cấp mã nguồnmà cịn được cấp phép để cho phép sử dụng, phân phối lại và sửa đổi miễn phí.Trong khi đó phần mềm nguồn mở không nhất thiết phải cung cấp giấy phép nhưvậy. Do đó, mặc dù tất cả phần mềm miễn phí đều là mã nguồn mở, nhưng một sốphần mềm mã nguồn mở khơng phải là “miễn phí”.

- Đến năm 1980, phần mềm độc quyền là trở nên thông thường.

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

Hình ảnh các hệ điều hành mã nguồn mở được phát triển và giới thiệu hiện nay1.2 Free Operating Systems

- Richard Stallman là người khởi xướng và bắt đầu phát triển một hệ điều hànhmiễn phí tương thích với UNIX được gọi là GNU vào năm 1984.

- Với phong trào này người dùng được hưởng 4 quyền tự do:Tự do chạy chương trình

Tự do nghiên cứu thay đổi mã nguồnTự do phân phối lại các bản saoTự do cải thiện chương trình

- Năm 1985, Stallman xuất bản Tuyên ngôn GNU, lập luận rằng tất cả phần mềmphải miễn phí. Ơng cũng thành lập Quỹ Phần mềm Tự do (FSF vt. Free SoftwareFoundation) với mục tiêu khuyến khích việc sử dụng và phát triển phần mềm miễnphí.

- Giấy phép Công cộng GNU (GPL vt. General Public License) là một giấy phépphổ biến theo đó phần mềm tự do được phát hànhđảm bảo cho người dùng cuối tựdo chạy, nghiên cứu, sửa đổi và chia sẻ phần mềm.

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

CHỦ ĐỀ 2 - REAL-TIME SCHEDULING

- Ba lớp lập lịch là:

SCHED_FIFO: luồng first in first out real timeSCHED_RR: luồng round robin real timeSCHED_OTHER: những luồng non real time

- Những lớp ưu tiên theo thời gian thực nằm trong phạm vi từ 0 đến 99.LớpSCHED_OTHER trong khoảng từ 100 đến 139. Số thấp hơn tương đương mức ưutiên cao hơn.

2.1 SCHED_FIFO

- FIFO là từ viết tắt của first in, first out (nhập trước, xuất trước) là một phươngpháp để tổ chức thao tác cấu trúc dữ liệu nơi cũ nhất (đầu tiên) mục nhập, hoặc"đầu" của hàng đợi được xử lý đầu tiên. Cụ thể khi 1 tiến trình được đưa vào hàngđợi ready thì bộ điều khiển tiến trình (PCB) sẽ đưa nó vào cuối hàng đợi, nó sẽ phảiđợi các tiến trình phía trên thực thi xong thì mới đến lượt nó.

- Hệ thống sẽ khơng gián đoạn 1 luồng thực thi FIFO trừ khi thuộc những trườnghợp sau:

Luồng FIFO khác có độ ưu tiên cao hơn trở thành readyLuồng thực thi FIFO bị chặn chờ đợi cho 1 event như nhập xuấtLuồng thực thi FIFO tự nguyện bỏ tiến trình theo 1 lời gọi đến primitive(chiếm quyền ưu tiên) sched_yield.

- Khi luồng FIFO đang thực thi bị gián đoạn, nó sẽ được đặt vào hàng đợi vớimức độ ưu tiên của nó.

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

- Khi 1 luồng FIFO thực thi trở thành ready và nếu luồng đó có độ ưu tiên caohơn luồng hiện tại thì luồng đang thực thi hiện tại sẽ bị chiếm quyền ưu tiên vàluồng FIFO có độ ưu tiên cao nhất sẽ được thực thi. Nếu nhiều hơn 1 luồng có độưu tiên cao hơn, luồng mà đợi lâu nhất sẽ được chọn.

- SCHED_FIFO chỉ có thể được sử dụng với các mức độ ưu tiên tĩnh cao hơn 0,có nghĩa là khi một chuỗi SCHED_FIFO trở nên có thể chạy được, nó sẽ ln chặntrước mọi chuỗi SCHED_OTHER, SCHED_BATCH hoặc SCHED_IDLE hiệnđang chạy. SCHED_FIFO là một thuật toán lập lịch đơn giản mà không cần cắt thờigian.

VD: Cho 3 tiến trình P1 P2 P3 có thời điểm vào Ready List và thời gian xử lí nhưsau:

Nếu thứ tự thực hiện của các tiến trình lần lược là P1 P2 P3 thì ta biểu diễn đượcnhư sau:

Thời gian chờ cho P1 là 0s vì nó vừa vào thì được phục vụ ngay lập tức. P2 phải đợiP1 thực thi xong tức thời gian chờ là 24s. Tương tự thời gian chờ của P3 là 27s. vậythời gian chờ trung bình cho ví dụ trên là (0+24+27)/3 = 17s. Tuy nhiên khi ta thửthay đổi thứ tự vào hàng đợi của 3 tiến trình P1 P2 P3 như hình sau:

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

Lúc này thời gian chờ của P2 là 0s, P3 là 3s và P1 là 6s thì thời gian chờ trung bìnhlà (0+3+6)/3=3. Kết quả thời gian chờ giảm đi đáng kể.

=> Yếu điểm lớn nhất của FIFO là khi các tiêns trình đầu tiên đi vào hàng đợi vàđược phục vụ có thời gian làm việc cao thì thời gian chờ trung bình tăng.

2.2 SCHED_RR

- SCHED_RR là một cải tiến đơn giản của SCHED_FIFO. Mọi thứ được mô tảởtrên cho SCHED_FIFO cũng áp dụng cho SCHED_RR, ngoại trừ việc mỗi luồngchỉ được phép chạy trong một lượng tử thời gian tối đa. Nếu một luồng

SCHED_RR đã chạy trong một khoảng thời gian bằng hoặc lâu hơn lượng tử thờigian, nó sẽ được đặt ở cuối danh sách để ưu tiên của nó.

- Giả sử một quy trình có bốn luồng với ba mức độ ưu tiên tương đối được chỉđịnh như hình 10.10a.

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

- Hình 10.10b cho thấy một luồng trong đó tất cả các luồng thuộc lớp

SCHED_FIFO. Luồng D thực thi cho đến khi nó đợi hoặc kết thúc. Tiếp theo,mặcdù luồng B và C có cùng mức độ ưu tiên, nhưng luồng B bắt đầu bởi vì nó đã đượcchờ lâu hơn luồng C. Luồng B thực thi cho đến khi nó đợi hoặc kết thúc, sau đóluồng C thực thi cho đến khi nó đợi hoặc kết thúc. Cuối cùng, luồng A thực thi.

- Hình 10.10c cho thấy một luồng mẫu nếu tất cả các luồng nằm trong lớpSCHED_RR . Luồng D thực thi cho đến khi nó đợi hoặc kết thúc. Tiếp theo, B và Clà thời gian cắt lát, bởi vì cả hai đều có cùng một mức độ ưu tiên. Cuối cùng, luồngA thực thi.

*Lưu ý:Sự khác biệt giữa SCHED_FIFO và SCHED_RR là giữa các tác vụ cócùng mức độ ưu tiên, SCHED_RR thực hiện lặp lại với một mốc thời gian nhất định.Thay vào đó, SCHED_FIFO cần tác vụ để nhường bộ xử lý một cách rõ ràng.

</div><span class="text_page_counter">Trang 14</span><div class="page_container" data-page="14">

CHỦ ĐỀ 3 -PRINCIPLES OF DEADLOCK

- Trong mơi truờng đa chương, nhiều q trình có thể cạnh tranh một số giới hạntài nguyên. Một quá trình u cầu tài ngun, nếu tài ngun khơng sẳn dùng tạithời điểm đó, q trình đi vào trạng thái chờ. Q trình chờ có thể khơng bao giờchuyển trạng thái trở lại vì tài nguyên chúng yêu cầu bị giữ bởi những quá trìnhđang chờ khác. Trường hợp này được gọi là deadlock (khố chết)

Ví dụ:

Trong hình trên cả hai tiến trình đều cần tài nguyên để tiếp tục thực thi. P1 yêu cầutài nguyên bổ sung R1 và sở hữu tài nguyên R2 , P2 yêu cầu tài nguyên bổsung R2 và sở hữu R1 ; không quá trình nào có thể tiếp tục.

- Deadlock là vĩnh viễn vì khơng có sự kiện nào được kích hoạt.

- Tình huống bế tắc trên một tài nguyên có thể phát sinh khi và chỉ khi tất cả cácđiều kiện sau đây đồng thời tồn tại trong một hệ thống:

Loại trừ lẫn nhau : Ít nhất một tài nguyên phải được giữ ở chế độ khôngthể chia sẻ. Nếu không, các quy trình sẽ khơng bị ngăn sử dụng tàingun khi cần thiết. Chỉ một quy trình có thể sử dụng tài nguyên tại bấtkỳ thời điểm nào.

</div><span class="text_page_counter">Trang 15</span><div class="page_container" data-page="15">

Giữ và chờ hoặc giữ tài nguyên : một quy trình hiện đang giữ ít nhất mộttài ngun và u cầu tài nguyên bổ sung đang được các quy trình khácnắm giữ.

Khơng có quyền ưu tiên : một tài ngun chỉ có thể được phát hành mộtcách tự nguyện bởi q trình nắm giữ tài ngun đó.

Chờ theo vịng: mỗi tiến trình phải đợi một tài nguyên đang được giữ bởimột quy trình khác, đến lượt quy trình này lại chờ quy trình đầu tiên giảiphóng tài ngun.

* Một ví dụ phổ biến là tắc nghẽn lưu lượng truy cập:

- Hình 6.1a cho thấy một tình huống trong đó bốn xe ô tô đến giao lộ dừng ởbốn chiều gần như cùng một lúc. Bốn góc phần tư của giao lộ là tài nguyên cầnkiểm soát. Cụ thể, nếu cả 4 ô tô muốn đi thẳng qua giao lộ, các yêu cầu về nguồnlực như sau:

Xe 1 cần có góc phần tư a và b.

Xe 2 cần các góc phần tư b và c.

Xe 3 cần các góc phần tư c và d.

</div><span class="text_page_counter">Trang 16</span><div class="page_container" data-page="16">

Xe 4 cần các góc phần tư d và a.

- Ví dụ: nếu chỉ có xe 2 ơ tơ 1 và 2 đến giao lộ, ô tô 1 sẽ đợi và ô tô bên phảicủa nó (ơ tơ 2) sẽ tiếp tục. Tuy nhiên, nếu cả bốn chiếc xe đến cùng một lúc và cảbốn chiếc đều tuân theo quy tắc, mỗi chiếc sẽ không đi vào giao lộ.

==> deadlock possible (các nguồn lực cần thiết ln có sẵn cho bất kỳ chiếc xenào có thể tiến hành).

- Tuy nhiên, nếu cả bốn ơ tô bỏ qua các quy tắc và tiến vào giao lộ cùng mộtlúc (hình 6.1b), thì mỗi ơ tơ chiếm một tài ngun (một góc phần tư) nhưng khơngthể tiếp tục vì tài nguyên thứ hai cần thiết đã bị ô tô khác chiếm đoạt.

==> deadlock.

* Một ví dụ khác về deadlock:

</div><span class="text_page_counter">Trang 17</span><div class="page_container" data-page="17">

Hình 6.2 (dựa trên một trong [BACO03]) biểu đồ tiến trình chung, minh họa tiếntrình của hai quy trình cạnh tranh.

- Trong Hình 6.2, trục x biểu thị tiến trình thực hiện P và trục y biểu thị tiến trìnhthực hiện Q.

- Đối với hệ thống đơn xử lý, chỉ một quá trình tại một thời điểm có thể thực thivà đường dẫn bao gồm các phân đoạn ngang và dọc xen kẽ. Phân đoạn ngang đạidiện cho một khoảng thời gian khi P thực thi và Q chờ đợi và hân đoạn dọc biểu thịmột khoảng thời gian khi Q thực hiện và P chờ đợi.

- Hình này chỉ ra các khu vực mà cả P và Q đều yêu cầu tài nguyên A (các đườngxiên lên); cả P và Q đều yêu cầu tài nguyên B (các đường xiên xuống), và cả P và Qđều yêu cầu cả hai tài nguyên.

- Mỗi quy trình cần sử dụng riêng cả hai tài nguyên trong một khoảng thời giannhất định. Hai quá trình P và Q có dạng tổng qt sau:

- Hình vẽ cho thấy sáu đường dẫn thực thi khác nhau. Những điều này có thểđược tóm tắt như sau:

1. Q có được B và sau đó là A và sau đó giải phóng B và A. Khi P tiếp tụcthực hiện, nó sẽ có thể có được cả hai tài nguyên.

</div><span class="text_page_counter">Trang 18</span><div class="page_container" data-page="18">

2. Q có được B và sau đó A. P thực hiện và chặn theo yêu cầu cho A. Q giảiphóng B và A. Khi P tiếp tục thực hiện, nó sẽ có thể lấy được cả hai tài nguyên.

3. Q có được B và sau đó P có được A. Deadlock là khơng thể tránh khỏi, bởivì khi quá trình thực hiện diễn ra, Q sẽ chặn trên A và P sẽ chặn trên B.

4. P có được A và sau đó Q có được B. Deadlock là khơng thể tránh khỏi, vìkhi q trình thực hiện diễn ra, Q sẽ chặn trên A và P sẽ chặn trên B.

5. P có được A và sau đó B. Q thực hiện và chặn theo một yêu cầu cho B. Pgiải phóng A và B. Khi Q tiếp tục thực hiện, nó sẽ có thể lấy được cả hai tài nguyên.

6. P có được A và sau đó là B và sau đó giải phóng A và B. Khi Q tiếp tụcthực hiện, nó sẽ có thể thu được cả hai tài nguyên.

- Vùng tô xám được gọi là vùng chết.Nếu một đường dẫn thực thi đi vào vùngchết này, thì deadlock là khơng thể tránh khỏi.

- Lưu ý rằng sự tồn tại của một vùng chết phụ thuộc vào logic của hai quá trình.

- Tuy nhiên, deadlock chỉ là khơng thể tránh khỏi nếu khớp tiến trình của hai quátrình tạo ra một con đường đi vào vùng chết.Việc deadlock có xảy ra hay khơng phụthuộc vào cả động lực của việc thực thi và vào các chi tiết của ứng dụng.

- Ví dụ, giả sử rằng P không cần cả hai tài nguyên cùng một lúc để hai q trìnhcó dạng sau:

</div><span class="text_page_counter">Trang 19</span><div class="page_container" data-page="19">

- Tình huống này được phản ánh trong Hình 6.3. Một số suy nghĩ sẽ thuyết phụcrằng với thời gian tương đối của hai q trình, deadlock khơng thể xảy ra.

- Như đã trình bày, sơ đồ tiến trình chung có thể được sử dụng để ghi lại lịch sửthực thi của hai quá trình chia sẻ tài nguyên. Trong trường hợp có nhiều hơn hai quytrình có thể cạnh tranh cho cùng một tài nguyên, một sơ đồ có chiều cao hơn sẽđược yêu cầu. Các nguyên tắc liên quan đến các vùng chết và bế tắc sẽ vẫn như cũ.

</div><span class="text_page_counter">Trang 20</span><div class="page_container" data-page="20">