BAO CAO 2 PHAM QUOC Trung 2017 2875 heheiehe PDF

Preview

Summary

ĐẠI HỌC BÁCH KHOA HÀ NỘIVIỆN ĐIỆN TỬ - VIỄN THÔNGBÁO CÁO BÀI TẬP LỚN MÔN HỆ ĐIỀU HÀNHĐỀ TÀI:VẤN ĐỀ “PRIORITY SCHEDULING” VÀ “PRIORITYDONATION” TRONG DỰ ÁN SỐ 1 CỦA HỆ ĐIỀU HÀNHPINTOSHọ và tên sinh viên MSSV Mã lớpPhạm Quốc Trung 20172875 119074Giảng viên hướng dẫn: TS. Phạm Văn TiếnHÀ NỘI 12/MỤC LỤC...

Description

ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN ĐIỆN TỬ - VIỄN THÔNG

BÁO CÁO BÀI TẬP LỚN MÔN HỆ ĐIỀU HÀNH ĐỀ TÀI: VẤN ĐỀ “PRIORITY SCHEDULING” VÀ “PRIORITY DONATION” TRONG DỰ ÁN SỐ 1 CỦA HỆ ĐIỀU HÀNH PINTOS Họ và tên sinh viên

MSSV

Mã lớp

Phạm Quốc Trung

20172875

119074

Giảng viên hướng dẫn: TS. Phạm Văn Tiến HÀ NỘI 12/2020

MỤC LỤC DANH MỤC HÌNH ẢNH ................................................................................................. 1 DANH MỤC BẢNG BIỂU ............................................................................................... 1 CHƯƠNG 1: HỆ ĐIỀU HÀNH PINTOS ........................................................................ 2 1.1 Tổng quan về Pintos ................................................................................................. 2 2.1 Hệ thống thư mụ c của hệ điều hành Pintos ........................................................... 2 CHƯƠNG 2: DỰ ÁN LUỒNG – VẤN ĐỀ “PRIORITY SCHEDULING” ................. 5 2.1 Cấu trúc dữ liệu và các hàm quan trọng ............................................................... 5 2.1.1 Cấu trúc semaphore .......................................................................................... 5 2.1.2 Cấu trúc lock ...................................................................................................... 5 2.1.3 Cấu trúc condition variable .............................................................................. 6 2.2 Vấn đề đặt ra ............................................................................................................ 7 2.3 Mục tiêu của đề tài ................................................................................................... 8 2.4 Phương án giải quyết ............................................................................................... 8 2.4 Triển khai cụ thể .................................................................................................... 10 CHƯƠNG 3: DỰ ÁN LUỒNG – VẤN ĐỀ “PRIORITY DONATION” .................... 11 3.1 Các cấu trúc dữ liệu quan trọng ........................................................................... 11 3.2 Vấn đề đặt ra .......................................................................................................... 11 3.3 Mục tiêu của đề tài ................................................................................................. 12 3.4 Phương án giải quyết ............................................................................................. 12 3.4 Triển khai cụ thể .................................................................................................... 14 CHƯƠNG 4: KẾT QUẢ ................................................................................................. 17 4.1 Kết quả sau khi chạy “make check” ..................................................................... 17 4.2 Kết luận ................................................................................................................... 17

PHẠM QUỐC TRUNG

20172875

DANH MỤC HÌNH ẢNH Hình 2. 1 Cơ chế Round - Robin ........................................................................................ 7 Hình 2. 2 Cơ chế Priority Scheduling ................................................................................. 9 Hình 3. 1 Vấn đề “Priority Inversion” .............................................................................. 11 Hình 3. 2 Ý tưởng thực hiện “Priority Donation”............................................................. 12 Hình 3. 3 Vấn đề Multiple Donation giữa các luồng ........................................................ 13 Hình 3. 4 Vấn đề Nested Donation giữa các luồng .......................................................... 14 Hình 3. 5 Ý tưởng cho vấn đề Multiple Donation ........................................................... 15 Hình 3. 6 Ý tưởng cho vấn đề Nested Donation ............................................................... 15 Hình 4. 1 Kết quả khi chạy make check ........................................................................... 17

DANH MỤC BẢNG BIỂU Bảng 2. 1 Bảng tổng kết các hàm được thêm mới và các hàm được sửa đổi trong vấn đề “Priority Scheduling” ........................................................................................................ 10 Bảng 3. 1 Bảng tổng kết các hàm được thêm mới và các hàm được sửa đổi trong vấn đề “Priority Inversion” ........................................................................................................... 16

1

PHẠM QUỐC TRUNG

20172875

CHƯƠNG 1: HỆ ĐIỀU HÀNH PINTOS 1.1 Tổng quan về Pintos Hệ điều hành Pintos là một hệ điều hành đơn giản chạy trên nền kiến trúc 80x86. Hệ điều hành này được nghiên cứu và phát triển bởi đại học Stanford với mục đích chính để phục vụ cho quá trình học tập và nghiên cứu của sinh viên. Nó có hỗ trợ các cơ chế cơ bản của một hệ điều hành như luồng kernel, tải nạp và chạy các chương trình người dùng, hệ thống filesystem,… Tuy vậy các cơ chế này được triển khai khá đơn giản và còn nhiều vấn đề cần khắc phục. Dựa trên tình hình thực tế, 4 dự án Pintos được đưa ra để khắc phục phần nào những vấn đề nêu trên. Các dự án này chủ yếu xoay quanh một số nội dung như thread (luồng), user program (chương trình người dùng), virtual memory (bộ nhớ ảo) và filesystem (hệ thống file). Sau khi triển khai được các nội dung này, hệ điều hành sẽ hoạt động hiệu quả, nâng cao hiệu suất của hệ thống cũng như tiết kiệm được các tài nguyên vốn dĩ có hạn như thời gian, năng lượng, bộ nhớ. Các dự án của Pintos sẽ được chạy và kiểm tra bằng một hệ thống mô phỏng. Bản chất, nó cũng chính là một chương trình với chức năng mô phỏng lại một hệ vi xử lý kiến trúc 80x86 cũng như các ngoại vi của nó sao cho vừa đủ để các chương trình của Pintos có thể chạy được trên nó. Hai chương trình mô phỏng phổ biến nhất là Boshs và QEMU. Trong báo cáo cũng như dự án này sẽ sử dụng trình mô phỏng QEMU. 2.1 Hệ thống thư mục của hệ điều hành Pintos Bên trong mã nguồn Pintos, chúng ta có thể nhận ra một số thư mục, các dự án Pintos sẽ được triển khai trên các thư mục này. Chúng ta có thể tìm thấy các thư mục theo đường dẫn sau “…/pintos/src”. Thư mục “luồngs/” Đây là nơi chứa mã nguồn của kernel gốc. Nó cũng là nơi mà chúng ta sẽ triển khai dự án 1 “Luồng”. Thư mục “userpro/” 2

PHẠM QUỐC TRUNG

20172875

Thư mục chứa mã nguồn cho trình tải nạp ứng dụng người dùng. Đây sẽ là nơi chúng ta triển khai dự án 2 “User Program”. Thư mục “vm/” Đây gần như là một thư mục rỗng. Nó sẽ là nơi chúng ta triển khai nội dung liên quan đến dự án số 3 “Virtual Memory” Thư mục “filesys/” Thư mục chứa mã nguồn cho hệ thống file cơ bản. Thư mục này sẽ được sử dụng trong cả 2 dự án là dự án về “User Program” và dự án về “File System”. Thư mục “devices/” Đây là thư mục chứa mã nguồn cho sự giao tiếp của hệ thống với các thiết bị vào ra như: bàn phím, ổ đĩa, màn hình,… Chúng ta sẽ cần thay đổi mã nguồn cho bộ định thời timer trong dự án số 1. Thư mục “lib/” Đây là thư mục tập hợp các thư viện chuẩn trong C phục vụ cho các dự án. Gần như không cần thay đổi mã nguồn trong thư mục này. Khi cần sử dụng một thư viện cụ thể nào ta chỉ cần sử dụng kí hiệu #include. Mã nguồn trong thư viện này được biên dịch dưới 2 dạng là “kernel” và “user”. Thư mục “lib/kernel/” Đây là một phần của thư viện C mà được sử dụng trong nhân của hệ điều hành. Nó bao gồm cả một số kiểu dữ liệu tự định nghĩa như: bitmaps, linked list hay hash table. Thư mục “lib/user/” Phần thư viện C được sử dụng trong các chương trình người dùng của Pintos, Thư mục “tests/”

3

PHẠM QUỐC TRUNG

20172875

Đây là thư mục chứa các kết quả chạy thử của các dự án. Ta có thể thay đổi mã nguồn nếu nó có ích trong quá trình kiểm tra các dự án. Thư mục “examples/” Đây là các ví dụ cho các chương trình người dùng được sử dụng trong dự án số 2.

4

PHẠM QUỐC TRUNG

20172875

CHƯƠNG 2: DỰ ÁN LUỒNG – VẤN ĐỀ “PRIORITY SCHEDULING” 2.1 Cấu trúc dữ liệu và các hàm quan trọng Bên cạnh cấu trúc danh sách (linked list) và cấu trúc luồng đã trình bày trong bài báo cáo trước thì đối với vấn đề này, chúng ta cần quan tâm đến một số cấu trúc khác như lock, semaphore, condition variable và các hàm liên quan. 2.1.1 Cấu trúc semaphore Một biến semaphore được định nghĩa dưới dạng biến cấu trúc thông qua từ khóa “struct”. Cấu trúc này gồm 2 trường như sau. • unsigned value: Giá trị hiện tại của semaphore. • struct list waiters: Danh sách các luồng đang đợi để chiếm semaphore. Một số hàm chức năng quen thuộc khi ta lập trình với semaphore: • sema_init (): Hàm khởi tạo cho biến semaphore • sema_down(): Đây là một phép toán thực hiện trên semaphore (P), nó sẽ tiến hành giảm giá trị của semaphore xuống ngay khi giá trị này lớn hơn 0. • sema_try_down(): Nó sẽ thử kiểm tra giá trị của semaphore, nếu lớn hơn 0 thì sẽ tiến hành giảm nó xuống 1 đơn vị và trả về giá trị TRUE, ngược lại thì sẽ trả về FALSE. • sema_up(): Cùng với P thì đây cũng là một phép toán thực hiện trên semaphore (V), nó sẽ tăng giá trị của semaphore lên một đơn vị đồng thời đánh thức một trong các luồng đang đợi semaphore. 2.1.2 Cấu trúc lock Một biến lock được định nghĩa dưới dạng biến cấu trúc thông qua từ khóa “struct”, gồm 2 trường như sau • struct thread*holder: Trỏ đến luồng đang nắm giữ khóa. • struct semaphore semphore: Giá trị nhị phân semaphore phụ vụ quá trình kiểm soát quá trình truy nhập khóa. 5

PHẠM QUỐC TRUNG

20172875

Một số hàm quen thuộc khi ta lập trình với khóa: • lock_init (struct lock*lock): hàm dùng để khởi tạo cho khóa • lock_acquire (struct lock*lock): hàm này sử dụng khi một luồng muốn chiếm lấy một khóa nào đó. • lock_try_acquire(struct lock*lock): hàm giúp một luồng cố chiếm lấy khóa mà nó mong muốn, trả về giá trị TRUE nếu chiếm khóa thành công và ngược lại trả về giá trị FALSE nếu chiếm khóa thất bại. • lock_release (struct lock*lock): Khi một luồng hoàn thành công việc và không cần khóa nữa thì nó sẽ thực hiện giải phóng khóa để các luồng khác chiếm. 2.1.3 Cấu trúc condition variable Một biến condition được định nghĩa dưới dạng một cấu trúc và bao gồm một trường duy nhất (struct list waiters) là danh sách các luồng đang đợi. Đối với loại cấu trúc này, ta cần có một vài lưu ý. Một biến điều kiện (condition variable) sẽ chỉ liên kết với một khóa, nhưng một khóa thì sẽ liên kết với nhiều biến điều kiện, đây chính là quan hệ một nhiều. Một số hàm chúng ta cần quan tâm khi làm việc với biến condition, có thể kể đến như sau: • cond_init (struct condition *cond): Hàm thực hiện quá trình khởi tạo cho biến condition. • cond_wait (struct condition *cond, struct lock *lock): Các luồng đợi biến điều kiện và được đẩy vào hàng đợi. • cond_signal (struct condition *cond, struct lock *lock UNUSED): Nếu một luồng nào đó đang đợi biến điều kiện, hàm này sẽ thực hiện việc đánh thức một luồng trong danh sách đợi và luồng được đánh thức bắt buộc phải đang giữ khóa liên kết với biến điều kiện (khóa duy nhất). • cond_broadcast (struct condition *cond, struct lock *lock): Đánh thức tất cả các luồng trong danh sách đợi. Lưu ý rằng khóa liên kết bởi biến điều kiện bắt buộc phải được chiếm bởi luồng nào đó trước khi ta gọi hàm này. 6

PHẠM QUỐC TRUNG

20172875

2.2 Vấn đề đặt ra Như chúng ta đã biết, mỗi hệ điều hành sẽ có một thành phần đảm nhiệm vai trò lập lịch cho các luồng và tiến trình. Hiểu đơn giản, nó sẽ chọn luồng tiếp theo chiếm giữ CPU từ các luồng trong hàng đợi ready queue. Đối với hệ điêu hành Pintos, cơ chế lập lịch mặc định của nó là Round – Robin, có nghĩa là cơ chế lập lịch tuần tự. Cơ chế này hoạt động rất đơn giản, khi mỗi luồng kết thúc time slice của mình và nhường CPU cho luồng khác, nó sẽ trở về cuối hàng đơi ready queue, khi bộ lập lịch chọn luồng tiếp theo được chiếm CPU, nó sẽ luôn luôn chọn luồng ở đầu hàng đợi. Ta có thể thấy, với cơ chế này bộ lập lịch gần như không quan tâm đến mức ưu tiên của các luồng mặc dù trong cấu trúc của luồng đã bao gồm thuộc tính priority nghĩa là độ ưu tiên.

Hình 2. 1 Cơ chế Round - Robin Trong thực tế, cơ chế lập lịch này thường ít khi được sử dụng. Do trong quá trình hoạt động, một số luồng hoặc một số tiến trình sẽ có vai trò quan trọng, thường được ưu tiên hơn ví dụ các tiến trình tương tác với người dùng hay các tiến trình ảnh hưởng đến hoạt động của hệ thống. Vì vậy, hệ điều hành thông thường sẽ phải quan tâm đến mức ưu tiên của các tiến trình để lập lịch sao cho phù hợp. Bên cạnh vấn đề lập lịch, thì còn một vấn đề khác liên quan đến việc lựa chọn luồng chiếm giữ các biến phục vụ cho quá trình đồng bộ khi các luồng truy cập tới các vùng nhớ critical section. Giả sử, chúng ta có một danh sách các luồng đang đợi một biến lock hoặc

7

PHẠM QUỐC TRUNG

20172875

một biến điều kiện. Khi biến lock đó được giải phóng thì luồng có mức ưu tiên cao nhất cần được đánh thức đầu tiên. Mặc dù bộ lập lịch ưu tiên đã cơ bản khắc phục được nhược điểm của bộ lập lịch Round – Robin, tuy vậy nó cũng có một số nhược điểm cố hữu: • Hiện tượng “starvation”: Khi mà các luồng có mức ưu tiên cao luôn chiếm được CPU còn các luồng có ưu tiên thấp thì gần như không bao giờ chiếm được CPU. • Khi các luồng có ưu tiên cao thực hiện việc chờ đợi ở các cổng IO quá lâu nó sẽ làm mất sự công bằng giữa các luồng. Các nhược điểm này sẽ được khắc phục trong vấn đề “Advanced Scheduler” của dự án này. 2.3 Mục tiêu của đề tài Mục tiêu cơ bản cần hoàn thiện của đề tài là thay thế cơ chế lập lịch của hệ điều hành từ Round – Robin sang lập lịch theo mức ưu tiên “Priority Scheduler” cùng với đó là giải quyết vấn đề liên quan đến việc tranh chấp các biến khóa và biến điều kiện giữa các luồng. 2.4 Phương án giải quyết Với mã nguồn nguyên bản của Pintos, mỗi luồng sẽ có một trường thông tin chứa mức ưu tiên của nó (priority), và chúng ta sẽ có tổng cộng 64 mức ưu tiên trong khoảng từ 0 đến 63. Khi một luồng mới được tạo ra nếu ta không gán cho nó một mức ưu tiên cụ thể thì mức ưu tiên mặc định là 31 và trong quá trình các luồng chiếm CPU cũng như ra vào hàng đợi ready queue thì mức ưu tiên của nó. Dựa trên cơ sở này, việc tìm ra giải pháp cho vấn đề đã nêu sẽ trở nên đơn giản rất nhiều. Trước hết đối với bộ lập lịch ưu tiên, chúng ta có thể có hai cách để triển khai bộ lập lịch ưu tiên.

8

PHẠM QUỐC TRUNG

20172875

• Cách 1: Chúng ta tổ chức hàng đợi ready queue một cách có trật tự, các luồng được sắp xếp theo thứ tự tăng dần (giảm dần) dựa theo mức độ ưu tiên của nó. Khi lựa chọn luồng tiếp theo chiếm CPU, bộ lập lịch sẽ chọn luồng nằm ở đầu hoặc ở cuối của hàng đợi tùy theo các sắp xếp. • Cách 2: Không cần tổ chức hàng đợi ready queue một cách có trật tự. Khi lập lịch bộ lập lịch sẽ tìm ra luồng có mức ưu tiên lớ n nhất trong hàng đợi và đẩy luồng đó vào chiếm CPU.

Hình 2. 2 Cơ chế Priority Scheduling Với mỗi cách trên thì đều sẽ có ưu nhược điểm riêng, xét về bản chất thì 2 cách nêu trên thực ra không khác nhau, nó đều nhằm mục đích chọn ra luồng có mức ưu tiên cao nhất để thực hiện lập lịch. Trong dự án này em sẽ chọn cách số 2 để tiến hành triển khai bộ lập lịch ưu tiên cho hệ điêu hành Pintos. Bên cạnh đó, khi một luồng có mức ưu tiên cao hơn luồng đang chiếm CPU được thêm vào hàng đợi ready queue thì luồng đang chiếm CPU cần phải nhường CPU cho luồng có mức ưu tiên cao hơn ngay lập tức.

9

PHẠM QUỐC TRUNG

20172875

Đối với vấn đề chọn luồng được chiếm khóa hay biến điều kiện thì ý tưởng triển khai cũng hoàn toàn tương tự. 2.4 Triển khai cụ thể Trước hết, đối với bộ lập lịch ưu tiên, ta cần quan tâm đến hàm quyết định luồng nào sẽ được chọn để chiếm CPU. Khi đọc mã nguồn của Pintos, ta có thể dễ dàng phát hiện ra đó chính là hàm next_thread_to_run(). Như vậy ta sẽ tiến hành thay đổi hàm đó để lựa chọn ra luồng có mức ưu tiên cao nhất trong hàng đợi ready queue. Để đảm bảo khi một luồng có mức độ ưu tiên cao hơn luồng đang chiếm CPU được thêm vào hàng đợi ready queue thì luồng đang chiếm CPU phải nhường CPU ngay lập tức, ta sẽ tiến hành thay đổi hàm thread_create(). Còn đối với việc đảm bảo luồng có mức ưu tiên cao nhất sẽ là luồng được đánh thức trước để chiếm lấy khóa hoặc biến điều kiện. Chúng ta sẽ tiến hành thay đổi 4 hàm trong file synch.c đó là các hàm sema_up (), sema_down(), cond_wait() và cond_signal(). Để phục vụ cho quá trình thay đổi 4 hàm này em có viết thêm 2 hàm khác là compare_sema_priority() và compare_priority(). Cụ thể sự thay đổi của mã nguồn được trình bày trong bảng sau: Bảng 2. 1 Bảng tổng kết các hàm được thêm m ới và các hàm được sửa đổi trong vấn đề “Priority Scheduling”

Hàm

thread.h

thread.c

synch.h

synch.c

Không có

thread_create(),

Không có

sema_up(),

bị

next_thread_to_run(

sema_down()

thay

)

cond_wait()

đổi

thread_set_priority()

cond_signal()

Hàm

compare_thread_p

compare_thread_pri

compare_sema_pr compare_sem

được

riority()

ority()

iority()

a_priority()

thêm mới 10

PHẠM QUỐC TRUNG

20172875

CHƯƠNG 3: DỰ ÁN LUỒNG – VẤN ĐỀ “PRIORITY DONATION” 3.1 Các cấu trúc dữ liệu quan trọng Các cấu trúc cần sử dụng trong vấn đề này đều đã được nêu ở chương 2 như cấu trúc lock, condition và semaphore. 3.2 Vấn đề đặt ra Sau khi triển khai bộ lập lịch, chúng ta sẽ thấy một vấn đề bất cập là đôi khi luồng có mức ưu tiên cao lại không được chiếm CPU mà thay vào đó là luồng có mức ưu tiên thấp hơn. Hiện tượng này được gọi là “Priority Inversion”. Hiện tượng này sẽ xảy ra khi mà một luồng có mức ưu tiên cao đang đợi một biến khóa hoặc biến điều kiện nhưng biến này lại đang do một luồng có mức ưu tiên nắm giữ và chưa được giải phóng. Để cụ thể hơn cho điều này ta đi xét ví dụ sau. Xét 3 luồng lần lượt như sau: luồng H có mức ưu tiên là 35, luồng M có mức ưu tiên là 33 và cuối cùng là luồng L có mức ưu tiên là 31. Luồng H đang chờ một khóa do luồng L chiếm và hiện tượng có thể được mô tả bằng hình vẽ sau.

Hình 3. 1 Vấn đề “Priority Inversion” Ta có thể dễ dàng phát hiện ra vấn đề ở đây, mặc dù luồng M có mức ưu tiên thấp hơn luồng H, nhưng nó lại chiếm được CPU do luồng H phải đợi khóa từ luồng L. Rõ ràng tình huống này đã đi trái với thiết kế ban đầu của chúng ta.

11

PHẠM QUỐC TRUNG

20172875

3.3 Mục tiêu của đề tài Như vậy với vấn đề chúng ta đã nêu ở trên, mục tiêu của đề tài này là khắc phục hiện tượng “Priority Inversion” đã nêu ở trên bằng cách đưa ra phương án giải quyết và triển khai cụ thể đó bằng việc lập trình và sửa đổi mã nguồn. 3.4 Phương án giải quyết Để giải quyết vấn đề đã nêu dựa trên sự gợi ý của tài liệu chính thông thì chúng ta có thể đưa ra một phương án giải quyết sau. Phương án này chủ yếu sẽ xoay quanh biến khóa. Rõ ràng khi một luồng (luồng H) có mức ưu tiên cao đang đợi một khóa để có thể truy nhập vào “critical section” mà khóa này lại đang được nắm giữ bởi một luồng khác có mức ưu tiên thấp hơn (luồng L) thì luồng H nên chuyển mức ưu tiên của nó cho luồng L để luồng L được chiếm CPU và thực hiện xong công việc của mình sau đó giải phóng khóa. Khi đó, luồng H sẽ chiếm được khóa và luồng L sẽ cập nhật lại mức ưu tiên của mình trở lại giá trị ban đầu. Phương án này có thể được mô tả bằng hình vẽ bên dưới

Hình 3. 2 Ý tưởng thực hiện “Priority Donation” Tuy vậy khi thực hiện quá trình chuyển giao và cập nhật mức ưu tiên cần phải rất cẩn thận. Khi thiết kế phương án, chúng ta sẽ thấy có hai trường hợp cần lưu tâm đó là “Multiple Donations” và “Nested Donations” Multiple Donation: Đây là tình huống mà một luồng có mức ưu tiên thấp giữ nhiều hơn một khóa và các khóa này đang được đợi bởi các luồng có mức ưu tiên cao hơn. Khi đó

12

PHẠM QUỐC TRUNG

20172875

các lu...