Tìm hiểu các cách đồng bộ giữa các quá trình trong hệ điều hành UNIX: semaphore, lock file

1. 07-10-2015 12:20 #1

   Bài tập của em như sau: Tìm hiểu cách tạo quá trình trong UNIX: hàm fork( ). Tìm hiểu các cách đồng bộ giữa các quá trình trong UNIX: semaphore, lock file (Lock file): - Viết chương trình giải quyết bài toán reader/writer dạng tổng quát. Chương trình phải tạo ra 5 quá trình đồng thời với hoạt động đọc/ghi file bất kỳ để thử nghiệm giải thuật

   Ai biết giúp em với

Tóm tắt nội dung tài liệu

1. Bài tập lớn hệ điều hành Lớp MT2000 BÀI TẬP LỚN HỆ ĐIỀU HÀNH Quy định : • Ngôn ngữ lập trình sử dụng trong các bài tập là C, C++ hoặc Java. • Các bài tập viết trên UNIX phải viết trên nền Linux. • Sinh viên chia nhóm từ 3-4 người. Mỗi nhóm chọn 2 bài tập thuộc 2 ch ủ đề l ập trình và 1 bài tập phần tìm hiểu hệ thống. • Các nhóm sinh viên có thể đăng ký để trình bày trước lớp v ề đề tài c ủa nhóm mình. Các nhóm đăng ký phải chuẩn bị slide hoặc bài viết để trình bày trước lớp trong các bu ổi h ọc cu ối cùng của môn học. • Sinh viên có tham gia thuyết trình sẽ được cộng thêm điểm vào bài tập lớn • Lớp trưởng đánh máy và in ra danh sách các nhóm (họ tên, mã s ố sinh viên), tên bài t ập và thông tin đăng ký thuyết trình của các sinh viên và gởi cho GVHD qua email. BÀI TẬP LẬP TRÌNH Chủ đề 1: Mô phỏng 1. Tài liệu tham khảo - Bài giảng Hệ điều hành, Vũ Lê Hùng - An Introduction To Operating System, H.M. Deitel 2. Ngôn ngữ lập trình sử dụng: C, C++, Java trên UNIX hoặc Windows Bài 1.1: Viết chương trình mô phỏng giải thuật nhà băng của Dijsktra để tránh deadlock. S ố lượng các nguồn tài nguyên, các yêu cầu của hệ thống được t ạo ngẫu nhiên. Hãy hi ện th ực cách xét trạng thái hiện thời của hệ thống là an toàn hay không an toàn. N ếu tr ạng thái là an toàn, chương trình phải chỉ ra cách để thu hồi tài nguyên h ệ th ống. V ới m ỗi yêu c ầu cung c ấp tài nguyên, hãy hiển thị ra màn hình cách cấp phát, thu hồi tương ứng. Bài 1.2: Viết chương trình mô phỏng các giải thuật định thời đã h ọc: FIFO, SJF, SRT, RR, HRRN, MLFQ. Đầu vào của giải thuật: số quá trình, độ dài các CPU burst, I/O burst… đ ược t ạo ngẫu nhiên. Tính toán các thông số và đánh giá độ hiệu quả của từng giải thuật. Bài 1.3: Viết chương trình mô phỏng các giải thuật thay thế trang đã h ọc: OPT, FIFO, LRU, LFU, NUR, Second Chance. Đầu vào của giải thuật: số khung trang, chu ỗi tham kh ảo trang, yêu cầu thay thế trang…được tạo ngẫu nhiên. Đánh giá độ hiệu quả (so sánh số page fault) của t ừng giải thuật. Chủ đề 2: Đồng bộ giữa các quá trình 1. Tài liệu tham khảo - UNIX network programming. - Tài liệu hướng dẫn thực hành Hệ điều hành, Hồ Quốc Thuần. 2. Tìm hiểu cách tạo quá trình trong UNIX: hàm fork( ). 3. Tìm hiểu các cách đồng bộ giữa các quá trình trong UNIX: semaphore, lock file. 4. Ngôn ngữ lập trình sử dụng: C trên UNIX Bài 2.1 : (Semaphore) Viết chương trình tạo ra một quá trình con. Quá trình cha sẽ nh ận chu ỗi s ố nguyên t ừ bàn phím do người dùng nhập và ghi vào file tên input. Quá trình con s ẽ đ ọc d ữ liệu t ừ file này, s ắp xếp chúng theo thứ tự tăng dần và ghi vào một file khác tên là sorted. Bài 2.2 : (Semaphore) Viết chương trình producer-consumer với bounded buffer. Bài 2.3 : (Semaphore) Trang 1/6
2. Bài tập lớn hệ điều hành Lớp MT2000 Viết chương trình giải quyết bài toán 5 triết gia ăn t ối. Chương trình ph ải t ạo ra 5 quá trình con mô phỏng hoạt động của 5 triết gia. Dùng semaphore để đ ồng b ộ ho ạt đ ộng c ủa 5 tri ết gia này. Bài 2.4 : (Lock file) Viết chương trình giải quyết bài toán reader/writer d ạng t ổng quát. Ch ương trình ph ải t ạo ra 5 quá trình đồng thời với hoạt động đọc/ghi file bất kỳ để thử nghiệm giải thuật. Chủ đề 3: Quản lý bộ nhớ 1. Tài liệu tham khảo - The Design of the UNIX Operating System- Andrew S. Tanenbaum, Chương 7 - Interprocess Communications in UNIX-The Nooks and Crannies. - Tài liệu hướng dẫn thực hành Hệ điều hành, Hồ Quốc Thuần. 2. Tìm hiểu các hàm truy cập bộ nhớ : - Tìm hiểu cách tạo quá trình trong UNIX dùng hàm fork( ). - Tìm hiểu cách cấp phát bộ nhớ cho quá trình trong hệ điều hành UNIX. - Tìm hiểu các hàm cho phép lấy các thông tin về vùng nhớ cấp cho quá trình cũng như cho phép thay đổi các vùng nhớ đó. 3. Ngôn ngữ lập trình sử dụng: C trên UNIX Bài 3.1 : Viết chương trình có khai báo 4 biến như sau: - global là biến nguyên toàn cục không khởi động trị. - local là biến nguyên khai báo cục bộ trong hàm doNoth( ) (hàm này không làm gì cả) - intarray là một con trỏ đến biến kiểu nguyên. Trong hàm main(), hãy gán global=1, sau đó in địa chỉ các segment của quá trình ra màn hình. Cho biết địa chỉ các biến global, local và intarray (1). Tiếp theo, hãy dùng hàm fork() tạo ra một quá trình con. Cho biết giá trị các địa chỉ trên ở trong quá trình con (2). Hãy gán global=2 trong quá trình con và cho biết giá trị mới của biến global trong quá trình con và quá trình cha. Trong quá trình cha, sau khi dùng fork(), hãy gọi hàm doNoth(), sau đó dùng malloc() để xin một vùng nhớ cho một mảng 10 số nguyên và gán địa chỉ đầu mảng vào biến intarray. Trả lời các câu hỏi sau: - Biến global là biến chung hay biến riêng của từng quá trình? - Biến intarray của quá trình cha nằm trên stack hay trên heap? - Biến local của quá trình cha nằm trên stack hay trên heap? Các địa chỉ ở (1) và (2) có khác nhau không? Giải thích? - Bài 3.2 : Viết các hàm mymalloc() và myfree() dựa trên các hàm cung cấp sẵn là brk() và sbrk(). Chủ đề 4: Thread 1. Tài liệu tham khảo - UNIX Internal, phần Thread and Lightweight Processes - Multithread Programming Guide. - Interprocess Communications in UNIX. - MSDN CDROM - Java How to Program, phần Threads 2. Tìm hiểu thread : - Tìm hiểu khái niệm thread. - Phân biệt giứa mô hình xử lý dùng multithread và dùng nhiều process. - Tìm hiểu cách đồng bộ giữa các thread trong Java và trong Linux. 3. Ngôn ngữ lập trình sử dụng có thể là C, C++, Java trên UNIX hoặc Windows. Bài 4.1 : Trang 2/6
3. Bài tập lớn hệ điều hành Lớp MT2000 Ứng dụng multithread trong bài toán nhân ma trận. Đọc vào 2 ma tr ận A & B t ừ file, sau đó dùng nhiều thread để thực hiện việc nhân 2 ma trận này. Ghi ma trận kết quả ra một file khác. Bài 4.2 : Ứng dụng multithread trong bài toán xử lý ảnh. Đọc vào m ột ma tr ận A t ừ file, sau đó dùng nhiều thread để thực hiện xử lý trên ma trận này như sau : m ột phần t ử trên ma trận là trung bình cộng của các phần tử chung quanh nó. Ghi ma trận kết quả ra một file khác. Bài 4.3 : Ứng dụng multithread trong bài toán sau : Đọc vào m ột ma trận A t ừ file và nh ập vào m ột s ố k, sau đó dùng n thread để thực hiện tìm kiếm trên các ma tr ận này xem có bao nhiêu ph ần t ử giống k. Mỗi lần tìm thấy phần tử giống k thì tăng biến chung number (khởi động là 0) lên 1. Bài 4.4 : Ứng dụng multithread trong bài toán sau : Đọc vào m ột dãy A t ừ file, dùng n thread đ ể s ắp xếp dãy theo thứ tự tăng dần như sau:  Mỗi thread lấy một phần dãy a và sắp theo thứ tự tăng dần  Sau đó, 1 thread trộn các dãy do n thread vừa rồi đã sắp xếp thành dãy k ết qu ả. Bài 4.5 : Cho người dùng nhập vào 2 số nguyên dương a và b, sau đó dùng n thread đ ể tìm ki ếm các số nguyên tố nằm trong khoảng 2 số đã nhập. Mỗi lần tìm được m ột số thì s ẽ tăng bi ến chung number (khởi động là 0) lên 1. Bài 4.6 : Cho người dùng nhập vào 2 số nguyên dương a và b, sau đó dùng n thread đ ể tìm ki ếm các số nguyên tố nằm trong khoảng 2 số đã nhập và ghi các số này ra file. Bài 4.7: Đọc vào một ma trận (kích thước N*N) từ file, sau đó dùng n thread đ ể tính t ổng c ủa t ừng hàng trên ma trận (1 thread nếu tính tổng m ột hàng xong có th ể tính t ổng c ủa m ột hàng khác). Dùng một thread để thu thập các kết quả của các thread kia và ghi vào một file k ết qu ả. Bài 4.8: Sử dụng thread và các phương thức đồng bộ trên thread đ ể vi ết ch ương trình producers- consumers với 1 bounded buffer trong trường hợp có nhiều producer và nhiều consumer. Bài 4.9: Sử dụng thread và các phương thức đồng bộ trên thread đ ể giải quyết bài toán N tri ết gia ăn tối. Bài 4.10 : Sử dụng thread và các phương thức đồng b ộ trên thread đ ể vi ết gi ải quy ết bài toán reader/writer dạng tổng quát. Chủ đề 5: Giao tiếp giữa các quá trình 1. Tài liệu tham khảo - UNIX network programming, phần Interprocess Communications - Interprocess Communication in UNIX - Tài liệu hướng dẫn thực hành Hệ điều hành, Hồ Quốc Thuần. 2. Tìm hiểu các cơ chế giao tiếp giữa các quá trình trong UNIX - Tìm hiểu các cơ chế giao tiếp giữa các quá trình trong UNIX dùng pipe, message queue, shared memory. - Ưu nhược điểm của từng phương pháp. 3. Ngôn ngữ lập trình sử dụng: C trên UNIX Bài 5.1 : Tạo ra 2 quá trình. Quá trình thứ nhất đọc từ file nhiều chuỗi liên ti ếp, m ỗi chu ỗi g ồm các phép toán +, -, *, / và hai toán hạng. Ví dụ trong file sẽ lưu các chuỗi dạng như sau : 2+3 1 -2 4 *6 Trang 3/6
4. Bài tập lớn hệ điều hành Lớp MT2000 15 / 3 Sau đó quá trình thứ nhất truyền các chuỗi dữ liệu này cho quá trình th ứ hai. Quá trình th ứ hai thực hiện tính toán và trả chuỗi kết quả về lại cho quá trình đầu tiên để ghi l ại vào file nh ư sau: 2+3 =5 1 - 2 = -1 4 * 6 = 24 15 / 3 =5 Thực hiện bài toán dùng message queue để giao tiếp giứa 2 quá trình. Bài 5.2 : Viết chương trình tương tự bài 5.1 nhưng dùng pipe để giao tiếp. Bài 5.3 : Viết chương trình tương tự bài 5.1 nhưng dùng shared memory để giao tiếp. Bài 5.4 : Viết chương trình gồm có 2 quá trình. Quá trình thứ nh ất cho người dùng nh ập vào t ừ bàn phím một chuỗi biễu diễn một phép tính gồm các phần tử +, -, (, ). Độ ưu tiên c ủa các phép tính trong ngoặc (cặp dấu ( & )) là cao nhất, phép + và – cùng độ ưu tiên. Ví d ụ: 1+2+(2-3-4) –((3+4)-5) (1+(-2)–((3+4)-5)) Sau đó truyền chuỗi dữ liệu này cho quá trình thứ hai. Quá trình th ứ hai th ực hi ện tính toán trên và trả kết quả về cho quá trình thứ nhất để hiển thị cho người sử dụng biết. Thực hiện bài toán dùng message queue để giao tiếp giứa 2 quá trình. Bài 5.5 : Viết chương trình tương tự bài 5.4 nhưng dùng pipe để giao tiếp. Bài 5.6 : Viết chương trình tương tự bài 5.4 nhưng dùng shared memory để giao tiếp. Bài 5.7 : Tạo ra 2 quá trình P0 và P1. Quá trình P0 đọc t ừ file nhiều dãy s ố nguyên liên ti ếp (m ỗi dãy có thể có số phần tử khác nhau). Sau đó quá trình này g ởi l ần l ượt các dãy này cho quá trình P1. P1 thực hiện sắp xếp mỗi dãy theo thứ tự tăng dần, đồng th ời tính t ổng c ủa dãy đó và g ởi dãy kết quả cùng với tổng tính được tương ứng cho mỗi dãy về lại quá trình P0. Khi này, P0 th ực hiện ghi các dãy kết quả vào lại file sao cho: dãy có t ổng nhỏ nh ất sẽ đ ược ghi đ ầu tiên, dãy có tổng lớn hơn sẽ được ghi sau. Thực hiện bài toán dùng message queue để giao ti ếp gi ứa 2 quá trình. Bài 5.8 : Viết chương trình tương tự bài 5.7 nhưng dùng pipe để giao tiếp. Bài 5.9 : Viết chương trình tương tự bài 5.7 nhưng dùng shared memory để giao tiếp. Bài 5.10 : Tạo ra 2 quá trình P0 và P1. Quá trình P0 đọc t ừ file m ột ma trận vuông c ấp N*N, sau đó g ởi ma trận này cho P1. Quá trình P1 sẽ thực hiện nghịch đảo ma trận này và ghi k ết qu ả xu ống m ột file khác. Nếu ma trận không thể nghịch đảo được, P1 ghi vào file k ết quả dòng thông báo t ương ứng. Thực hiện bài toán dùng message queue để giao tiếp giứa 2 quá trình. Bài 5.11 : Viết chương trình tương tự bài 5.10 nhưng dùng pipe để giao tiếp. Bài 5.12 : Viết chương trình tương tự bài 5.10 nhưng dùng shared memory để giao tiếp. Chủ đề 6: Socket 1. Tài liệu tham khảo - UNIX network programming, phần Berkeley Sockets - Interprocess Communication in UNIX - Internetworking with TCP/IP volume III, phần mô hình Client/Server. Trang 4/6
5. Bài tập lớn hệ điều hành Lớp MT2000 - Internetworking with TCP/IP volume II (cho các bài về broadcast và multicast). - MSDN CDROM 2. Tìm hiểu socket và mô hình client/server - Tìm hiểu cơ chế làm việc của socket, - Các bước cần thiết trong việc tạo socket dùng TCP và UDP. - Mô hình client/server. 3. Ngôn ngữ lập trình sử dụng: C trên UNIX, C++ trên Windows Bài 6.1: Tạo hai quá trình server và client ở hai máy khác nhau. Client nh ận m ột dãy s ố t ừ ng ười s ử dụng và gởi cho quá trình server. Server sắp xếp chu ỗi này theo th ứ t ự tăng d ần và g ởi tr ả l ại client để hiển thị cho người dùng biết. Bài 6.2: Tạo hai quá trình server và client ở hai máy khác nhau. Client nh ận m ột s ố nguyên d ương t ừ người sử dụng và gởi cho quá trình server. Server phân tích s ố này thành th ừa s ố nguyên t ố và gởi trả lại client để hiển thị cho người dùng biết. Bài 6.3: Dùng socket để viết chương trình chat giữa hai quá trình trên hai máy khác nhau. Gợi ý : viết 1 chương trình chat client (để người dùng s ử d ụng) và dùng m ột ch ương trình chat server để quản lý các chat client đó. Bài 6.4 : Tạo hai quá trình server và client ở hai máy khác nhau. Client nh ận m ột chu ỗi ký t ự do ng ười sử dụng nhập theo dạng một số lệnh thông dụng và thông s ố, ví d ụ nh ư chu ỗi “mkdir /temp/new” và gởi cho quá trình server. Server thực hiện lệnh này và g ởi thông báo thành công hay không cho client để hiển thị cho người dùng biết. Bài 6.5 : Viết 2 chương trình là server và admin. Cho thực thi chương trình server trên nhi ều máy khác nhau. Sau đó sẽ thực thi chương trình admin để biết được có bao nhiêu ch ương trình server đang chạy trên mạng đó. Dùng cơ chế broadcast. Bài 6.6 : Tương tự bài 5.5 nhưng dùng cơ chế multicast. Bài 6.7 : Viết 2 chương trình listen và send. Chương trình listen dùng để nhận thông tin t ừ các ng ười khác gởi đến và hiển thị lên màn hình.Chương trình send cho phép g ởi thông tin đ ến t ất c ả các người chạy chương trình listen trên mạng. Dùng cơ chế broadcast. Bài 6.8 : Tương tự bài 5.7 nhưng dùng cơ chế multicast. BÀI TẬP VỀ TÌM HIỂU HỆ THỐNG Tài liệu tham khảo - ftp.dit.hcmut.edu.vn/pub/OS/books - Sinh viên tự tìm kiếm trên Internet Bài 1: Tìm hiểu cơ chế boot và cách cài đặt multiboot cho nhiều hệ điều hành trên m ột máy đơn. Bài 2: Tìm hiểu phần mềm VMWare và cách chạy nhiều hệ điều hành trên cùng m ột máy t ại một thời điểm. Bài 3: Tìm hiểu và phân tích kiến trúc tổng quát của hệ điều hành Linux. Bài 4: Tìm hiểu và phân tích kiến trúc tổng quát của hệ điều hành WinNT/2000. Bài 5: Tìm hiểu cơ chế định thời của hệ điều hành Solaris/Linux. Bài 6: Tìm hiểu cơ chế định thời của hệ điều hành WinNT /2000. Trang 5/6
6. Bài tập lớn hệ điều hành Lớp MT2000 Bài 7: Tìm hiểu và so sánh mô hình multi-threading của Solaris và WinNT/2000. Bài 8: Tìm hiểu về hệ thống file của Linux. Bài 9: Tìm hiểu về hệ thống file của WinNT/2000. ---Hết--- Trang 6/6

Page 2

YOMEDIA

Bài 1.1: Viết chương trình mô phỏng giải thuật nhà băng của Dijsktra để tránh deadlock. Số lượng các nguồn tài nguyên, các yêu cầu của hệ thống được tạo ngẫu nhiên. Hãy hiện thực cách xét trạng thái hiện thời của hệ thống là an toàn hay không an toàn. Nếu trạng thái là an toàn, chương trình phải chỉ ra cách để thu hồi tài nguyên hệ thống. Với mỗi yêu cầu cung cấp tài nguyên, hãy hiển thị ra màn hình cách cấp phát, thu hồi tương ứng....

10-06-2011 460 54

Download

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.