Một Số Bài Tập Hệ điều Hành Cần Chú ý

Trang chủ Tìm kiếm Trang chủ Tìm kiếm Một số bài tập hệ điều hành cần chú ý doc 22 719 KB 61 833 4 ( 13 lượt) Xem tài liệu Nhấn vào bên dưới để tải tài liệu Tải về Đang chuẩn bị: 60 Bắt đầu tải xuống Để tải xuống xem đầy đủ hãy nhấn vào bên trên Chủ đề liên quan Bài tập hệ điều hành thuật giải nhà băng Round-Robin bài tập phân đoạn tính địa chỉ vật lý địa chỉ logic

Nội dung

MOT SO BAI TAP CAN CHU Y !!! Round-Robin, SJFS, Bộ nhớ ảo, Bảng FAT, Thuật giải Nhà băng, Sản xuất-Tiêu thụ (semFull-semEmpty), Dining-Philosopers (deadlock, không deadlock). Thuật giải Nhà băng.............................................................................................................1 Round-Robin, SJFS,............................................................................................................3 bài tập phân đoạn, tính địa chỉ vật lý cho địa chỉ logic.......................................................7 bài tập phân đoạn, tính địa chỉ vật lý cho địa chỉ logic có trường hợp không hợp lệ......9 Bảng FAT,.........................................................................................................................11 RAG...................................................................................................................................13 Bộ nhớ ảo...........................................................................................................................14 Sản xuất-Tiêu thụ (semFull-semEmpty),...........................................................................18 Dining-Philosopers (deadlock, không deadlock)...............................................................21 BÀI TẬP HỆ ĐIỀU HÀNH Thuật giải Nhà băng Câu 1: Một hệ thống có 3 ổ băng từ và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên ở thời điểm Ti thể hiện bằng véc-tơ Allocation = (1, 0, 1) và Max = (1, 2, 2): Dùng thuật giải nhà băng để: a. Chứng minh trạng thái này an toàn. (1 điểm) b. Xác định có nên đáp ứng hay không yêu cầu xin thêm 1 ổ nữa của của P3 ? (1 điểm) Giải: a. Xét tại thời điểm Ti mà 3 tiến trình được cấp phát như đề bài ta có: Với: Need[i] = Max[i] – Allocation[i] và Available = 3 – (1 + 0 + 1) = 1 Tìm chuỗi an toàn: Vậy tại thời điểm T0 tồn tại chuỗi an toàn {P1, P2, P3}. Suy ra, hệ thống tại thời điểm Ti ở trạng thái an toàn. b. Ta thấy, yêu cầu thêm 1 ổ nữa của P3 thoả các điều kiện: o Request3 địa chỉ vật lý của segment 0 là từ 300 -> 1000 Với segment 1: + Địa chỉ vật lý cơ sở (basic) là 1200, nên ta sẽ vẽ bắt đầu từ 1200, như vậy từ 1000>1200 là trống, không có segment nào + Limit là 500 ==> địa chỉ vật lý của segment 1là từ 1200 -> 1700 và segment 2 các bạn tính tương tự 2. Cách tính địa chỉ logic 7 Tính địa chỉ vật lý + Với dữ liệu đề bài cho là (1,200), ta xác định: tính địa chỉ vật lý của segment 1, địa chỉ logic là 200 (lưu ý: giá trị X tính được này nằm trong segment 1 hay ko (1200 không hợp lệ vì 800 > 700 (limit của segment 0) + (2,650) --> không hợp lệ vì 650 > 600 (limit của segment 2) + (1,501) --> không hợp lệ vì 501 > 500 (limit của segment 1) Tóm lại nếu nhìn thấy địa chỉ logic mà đề bài cho > limit của segment đó thì kết luận ngay là không hợp lệ bài tập phân đoạn, tính địa chỉ vật lý cho địa chỉ logic có trường hợp không hợp lệ Giả sử có Bảng đoạn sau: Hãy tính địa chỉ vật lý cho mỗi địa chỉ lô-gic sau: a. 0430 b. 1010 8 c. 2500 d. 3400 e. 4112 giải Tính địa chỉ vật lý + Với dữ liệu đề bài cho là (0,430) = 219 +430 = 649 ( hợp lệ) Vì nó nằm trong đoạn Segment 0. + (1,010) = 2300+ 10 = 2310 (hợp lệ) + (2,500) = 90 + 500 = 1400 (không hợp lệ) + (3,400) = 1327+ 400 = 1727 (hợp lệ) + (4,112) = 1952 + 112 = 2064 (không hợp lệ) =>Với các địa chỉ logic (0,430); (1,010); (1,500); (3,400); (4,112) ta có các địa chỉ vật lý tương ứng là 649; 2310; không hợp lệ;1727; không hợp lệ. 9 Bảng FAT, Trên một hệ tập tin FAT32, tập tin Lớp HC08TH2.jpg có nội dung trải trên các liên cung 5, 6, 9, 10; trong khi Icon1.ico chỉ cần liên cung 8. Hãy thể hiện bằng hình vẽ cấu trúc bảng FAT và các Directory Entry. Giải: File Lớp HC08TH2.jpg jpg Cần đến 2 Directory Entry cho Lớp HC08TH2.jpg 2 . j p g 1 Lớp L opHC0~1 C K C K A 0 A 0 A N Creation Last Last S Upp Low T time acc write Bytes 0 H C 0 8 T 0 H 2 Size Ghi chú: Lớp gồm 5 ký tự Lowps. H C 0 8 T có 5 ký tự + 1 ký tự khoảng trắng ( _ ) phía trước là 6. Bytes 8 3 1 1 1 4 2 2 4 2 4 10 Icon1.ico Ext N T Creation date/time Last acces Last write date/time File Size Câu 7 (1 điểm) Trên một hệ tập tin FAT32, tập tin DeThi1.pdf có nội dung tại liên cung 5, trong khi DapAn1.pdf cần các liên cung 8, 6, 7. Hãy thể hiện bằng hình vẽ cấu trúc bảng FAT và các Directory Entry. Giải: 11 RAG Một hệ thống có 1 máy in laser và 1 ổ băng từ. Hai tiến trình P1 và P2 đang vận hành với trạng thái cấp phát tài nguyên như sau: Hãy: a. Thể hiện bằng RAG b. Xác định và giải thích trạng thái này. Giải: a. Đồ thị cấp phát tài nguyên RAG: b. Trạng thái này là trạng thái Deadlock .vì mỗi tài nguyên chỉ có một phiên bản và tồn tại chu trình hay vòng tròn khép kín các yêu cầu tài nguyên. 12 Bộ nhớ ảo 13 Với đề bài và cách giải trên thì mình xin làm và giải thích theo cách hiểu của mình Bạn nào có cách giải thích rõ hơn, chính xác hơn thì bổ sung nhé + Hình 1: Logical Memory + Hình 2: Page table + Hình 3: Physical memory 14 + Hình 4: Backstore 15 Một hệ thống có Bộ nhớ trong chia thành 8 khung trang với Khung 0 dành cho Hệ điều hành và các khung còn lại dành cho 2 tiến trình đang vận hành là P0 (gồm các trang C, D, E, F) và P1 (gồm các trang O, P, Q, R). Bằng hình vẽ, với kỹ thuật tổ chức bộ nhớ ảo dạng phân trang, hãy tìm cách: a. Phân bổ ngẫu nhiên các trang của P0 và P1 vào Bộ nhớ trong kể trên b. Tổ chức lại các bảng trang sao cho trang chưa nạp (do hết chỗ) bây giờ được nạp 16 Sản xuất-Tiêu thụ (semFull-semEmpty), Phát biểu bài toán Sản xuất-Tiêu thụ với thuật giải đồng bộ hoá bằng 2 đèn hiệu semFull và semEmpty. Giải: Bài toán người sản xuất-người tiêu thụ (Producer-Consumer) thường được dùng để hiển thị sức mạnh của các hàm cơ sở đồng bộ hoá. Hai quá trình cùng chia sẻ một vùng đệm có kích thước giới hạn n. Biến semaphore mutex cung cấp sự loại trừ hỗ tương để truy xuất vùng đệm và được khởi tạo với giá trị 1. Các biến semaphore empty và full đếm số khe trống và đầy tương ứng. Biến semaphore empty được khởi tạo tới giá trị n; biến semaphore full được khởi tạo tới giá trị 0. – Dữ liệu chia sẻ: SEMAPHORE full, empty, mutex; – Khởi tạo: full = 0; empty = BUFFER_SIZE; 17 mutex = 1; Buffer xoay vòng i n out PRODUCER while (1) { … nextP = new_item(); … wait(empty); wait(mutex); … insert_to_buffer(nextP); … signal(mutex); signal(full); } CONSUMER while (1) { wait(full) wait(mutex); … nextC = get_buffer_item(out); … signal(mutex); signal(empty); … consume_item (nextC); … } Câu 2 (1 điểm) Phát biểu bài toán Sản xuất-Tiêu thụ với thuật giải đồng bộ hoá bằng 3 đèn hiệu semFull, semEmpty và Mutex. Trả lời: - Tiến trình sản xuất (Producer) tạo ra dòng thông tin để tiến trình tiêu thụ (Consumer) sử dụng. - Ví dụ: Compiler và Assembler vừa là nhà sản xuất vừa là nhà tiêu thụ. Compiler tạo ra mã dùng cho Assembler, tiếp theo Assembler sản sinh mã máy làm đầu vào cho Loader hoặc Linkage Editor. - Phát biểu bài toán: Bộ nhớ đệm Buffer bao gồm một số hữu hạn các khoang chứa (Items). Producer lần lượt đưa các sản phẩm S1, S2,…vào các khoang của Buffer. Consumer lấy sản phẩm ra theo đúng thứ tự. Công việc của các tiến trình phải đồng bộ với nhau: không đưa ra sản phẩm khi hết chỗ trống, không lấy được sản phẩm khi chưa có. - Thuật giải đồng bộ hoá bằng 3 đèn hiệu: semFull (quản lý số sản phẩm có trong bộ đệm, 18 giá trị ban đầu bằng 0), semEmpty (quản lý số khoang còn trống, giá trị ban đầu bằng số khoang của bộ đệm) và Mutex (đảm bảo tính loại trừ tương hỗ, nghĩa là mỗi thời điểm chỉ có 1 tiến trình sản xuất hay tiêu thụ được truy cập/cập nhật tài nguyên dùng chung, giá trị ban đầu bằng 1). o Thuật giải cho Producer: wait(semEmpty); wait(Mutex); // Đưa sản phẩm vào Buffer .......................... signal(semFull); signal(Mutex); o Thuật giải cho Consumer: wait(semFull); wait(Mutex); // Lấy sản phẩm từ Buffer .......................... signal(semEmpty); signal(Mutex); 4.1. Phát biểu bài toán Sản xuất-Tiêu thụ và trình bày Thuật giải với Bộ đệm thực thi bằng mảng xoay vòng. Giải: Phát biểu bài toán:  Giả sử có Bộ nhớ đệm (Buffer) bao gồm nhiều khoang (Items) được tiến trình Producer lần lượt đưa các sản phẩm S1, S2,... vào.  Tiến trình Consumer lần lượt lấy sản phẩm ra theo đúng thứ tự.  Công việc của Producer phải đồng bộ với Consumer: Không được đưa sản phẩm vào khi Buffer đầy, Không được lấy ra khi chưa có. Trình bày giải thuật: 19 Buffer xoay vòng i n out PRODUCER item nextProduced; while (1) { while(((in+1)%BUFFER_SIZE)==out); / /quẩn tại đây khi buffer đầy. buffer[in] = nextProduced; in = (in+1)%BUFFER_SIZE; } CONSUMER item nextConsumed; while (1) { while(in==out); //quẩn khi buffer rỗng nextConsumed = buffer[out]; out = (out+1)%BUFFER_SIZE; } Dining-Philosopers (deadlock, không deadlock). 7.1. Phân tích thuật giải sai bài toán Dining-Philosophers (dẫn đến Deadlock). Giải: Dữ liệu chia sẻ: semaphore chopstick[5]; Khởi đầu các biến đều là: 1. while (1) { wait(chopstick[i]) wait(chopstick[(i+1) % 5 ] ) … eat … signal(chopstick[i]); signal(chopstick[(i+1) % 5] ); … think … } Giải pháp trên có thể gây ra deadlock Khi tất cả triết gia đói bụng cùng lúc và đồng thời cầm một chiếc đũa bên tay trái  deadlock Có thể xảy ra trường hợp ách vô hạn định (starvation). 7.2. Phân tích thuật giải đúng bài toán Dining-Philosophers (dùng đèn hiệu). 20 Giải: Dữ liệu chia sẻ: semaphore chopstick[5]; Khởi đầu các biến đều là: 1. HANDLE cs[2] while (1) { cs[0] = chopstick[i]; cs[0] = chopstick[(i+1) % 5 ] WaitForMultipleObjects(2, cs, TRUE, INFINITE); … eat … ReleaseMutex(chopstick[i]; ReleaseMutex(chopstick[(i+1) % 5 ]) … think … } 21 This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

Tìm kiếm

Chủ đề

Mẫu sơ yếu lý lịch Đề thi mẫu TOEIC Trắc nghiệm Sinh 12 Đơn xin việc Đồ án tốt nghiệp Hóa học 11 Giải phẫu sinh lý Bài tiểu luận mẫu Lý thuyết Dow Atlat Địa lí Việt Nam Tài chính hành vi Thực hành Excel adblock ​ Bạn đang sử dụng trình chặn quảng cáo?

Nếu không có thu nhập từ quảng cáo, chúng tôi không thể tiếp tục tài trợ cho việc tạo nội dung cho bạn.

Tôi hiểu và đã tắt chặn quảng cáo cho trang web này