intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Đồ án: Viết chương trình mô phỏng các giải thuật định thời

Chia sẻ: Kun | Ngày: | Loại File: DOC | Số trang:38

Thêm vào BST
Báo xấu
856
lượt xem 142
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Với đề tài viết chương trình mô phỏng các giải thuật định thời FIFO, RR, SJF, HRRN, MLFQ. Trình bày quá trình hoạt động của các tiến trình trong CPU, các trạng thái của hệ thống và việc chuyển từ trạng thái này sang trạng thái khác được thực hiện theo một quá trình nào đó.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đồ án: Viết chương trình mô phỏng các giải thuật định thời

  1. Chƣơng trình mô phỏng các giải thuật định thời  LỜI CẢM ƠN Đồ Án Em xin tỏ lòng cảm ơn tới các thầy cô giáo là cán bộ giảng dạy của khoa Công nghệ Thông tin- Trƣờng Đại học Bách khoa. Đặc biệt, em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo Nguyễn Võ Quang Đông, là ngƣời trực tiếp hƣớng dẫn em hoàn thành đề tài này. Do thời gian có hạn nên không tránh khỏi thiếu sót, kính mong đƣợc sự góp ý của các thầy cô để đề tài trở nên hoàn thiện hơn. Em xin chân thành cảm ơn! Viết chƣơng trình mô Đà Nẵng, 12/2007 SVTH: Trần Văn Trung Lớp : 03T3 phỏng các giải thuật định thời Trần Văn Trung, Lớp: 03T3 Trang :1
  2. Chƣơng trình mô phỏng các giải thuật định thời MỤC LỤC LỜI CẢM ƠN ................................................................................................................................. 1 LỜI NÓI ĐẦU ................................................................................................................................ 3 Chƣơng I : Tổng quan về đề tài ...................................................................................... 4 1. Giới thiệu sơ lƣợc về đề tài ................................................................................................. 4 2. Mục tiêu đề tài ..................................................................................................................... 4 2. Hƣớng giải quyết ................................................................................................................. 4 Chƣơng II. Cơ sở lý thuyết .................................................................................................. 5 1. Định nghĩa hệ điều hành...................................................................................................... 5 2. Các chức năng chính của hệ điều hành ............................................................................... 5 a.Quản lý, chia sẻ tài nguyên............................................................................................... 6 b. Giả lập một máy tính ...................................................................................................... 6 3. Các chiến lƣợc điều phối ..................................................................................................... 6 a. Chiến lƣợc FIFO .............................................................................................................. 6 b.Chiến lƣợc xoay vòng ( Round Robin ) ........................................................................... 6 c. Chiến lƣợc công việc ngắn nhất ( Shotrtest job first-SJF ) ............................................ 6 1. Định nghĩa tiến trình ........................................................................................................... 7 b. Khối điều khiển tiến trình( Process Control Block) ........................................................ 8 c. Thực hiện tuần tự ............................................................................................................. 8 + Thực hiện song song ........................................................................................................ 8 III. Phân loại tiến trình song song ......................................................................................... 10 1.Độc lập ............................................................................................................................... 10 2.Quan hệ thông tin ............................................................................................................... 10 3.Loại song song phân cấp .................................................................................................... 11 4.Tiến trình đồng mức song song .......................................................................................... 12 Chƣơng III: Phân tích và thiết kế hệ thống ............................................................................. 14 1.Tài nguyên găng và đoạn găng ........................................................................................... 14 2.Phƣơng pháp khoá trong .................................................................................................... 15 3. Phƣơng pháp Kiểm tra và Xác lập (Test and Set) ............................................................. 19 4. Kỹ thuật đèn báo ............................................................................................................... 20 5. Cài đặt -Triển khai chƣơng trình ....................................................................................... 22 a. Sơ đồ thuật toán ............................................................................................................. 22 b. Kết quả chƣơng trình ..................................................................................................... 23 Chƣơng IV KẾT LUẬN .................................................................................. 26 1.Ƣu điểm: ............................................................................................................................. 26 2.Khuyết điểm ....................................................................................................................... 26 PHỤ LỤC ...................................................................................................................................... 27 1. Giớ thiệu ............................................................................................................................ 27 2. Chiến lƣợc SJF .................................................................................................................. 29 3. Chiến lƣợc RR ................................................................................................................... 29 TÀI LIỆU THAM KHẢO ............................................................................................................. 35 NHẬN XÉT CỦA GIÁO VIÊN.................................................................................................... 36 Trần Văn Trung, Lớp: 03T3 Trang :2
  3. Chƣơng trình mô phỏng các giải thuật định thời LỜI NÓI ĐẦU Trong cuộc sống ngày nay và trong tƣơng lai, tin học trở thành một phần không thể thiếu. Với sự bùng nổ của công nghệ thông tin đóng góp một phần không nhỏ vào việc nâng cao năng suất, hiệu quả cho sự phát triển cho các ngành khác nhau của xã hội. Tại nƣớc ta, một đất nƣớc mà tin học mới bắt đầu phát triển, cũng đã đạt đƣợc nhiều thành tựu trong lĩnh vực ứng dụng tại các ngành giáo dục và đào tạo, quân sự, địa chính,… Trong vòng bốn thập kỷ lại đây, hệ điều hành dã có những bƣớc phát triển đáng kể bởi do hai lý do sau: + Đó là hệ điều khiển các hoạt động bên trong các máy tính điện tử xuất phát từ yêu cầu của các nhà tin học và cũng do các chuyên gia cao cấp của ngành tin học lập trình nên. + Đó là hệ thống đầu tiên kể từ khi phần cứng đƣợc hình thành tạo điề u kiện thuận lợi cho ngƣời sử dụng trong việc phát triển và thực hiện các chƣơng trình máy tính của mình. Hệ điều hành có hai chức năng chính là: Quản lý và chia sẻ tài nguyên 1. Giả lập một máy tính mở rộng. 2. Và 7 thành phần của hệ điều hành là: Quản lý tiến trình 1. Quản lý bộ nhớ chính 2. Quản lý nhập xuất 3. Quản lý tập tin 4. Hệ thống bảo vệ 5. Quản lý mạng 6. Hệ thống dịch lệnh 7. Đồ án này em xin trình bày Viết chƣơng trình mô phỏng các giải thuật định thời FIFO, SJF, RR,… nói về cách hoạt động của các tiến trình trong hệ điều hành. Trần Văn Trung, Lớp: 03T3 Trang :3
  4. Chƣơng trình mô phỏng các giải thuật định thời Chƣơng I : Tổng quan về đề tài 1. Giới thiệu sơ lƣợc về đề tài Với đề tài viết chƣơng trình mô phỏng các giải thuật định thời FIFO, RR, SJF, HRRN, MLFQ. Trình bày quá trình hoạt động của các tiến trình trong CPU, các trạng thái của hệ thống và việc chuyển từ trạng thái này sang trạng thái khác đƣợc thực hiện theo một quá trình nào đó. 2. Mục tiêu đề tài Mục tiêu của đề tài là tìm hiểu và nghiên cứu sự giao tiếp giữa các tiến trình, làm thế nào để phân chia công việc cho các tiến trình chạy trong hệ điều hành. Viết chƣơng trình mô phỏng giải thuật FIFO, RR, SJF, HRRN, MLFQ nói lên nguyên tắc hoạt động của giải thuật này và nêu lên sự khác nhau giửa các gải thuật. Giới thiệu hệ điều hành nêu lên định nghĩa, chức năng của hệ điều hành. 2. Hƣớng giải quyết Vì giới hạn về kiến thức cũng nhƣ kinh nghiệm trong việc tìm hiểu hệ điều hành và thời gian hạn chế, nên em chỉ đi sâu tìm hiểu đƣợc một số giải thuật. Trong đề tài này em sử dụng ngôn ngữ C để cài đặt chƣơng trình minh hoạ. Trần Văn Trung, Lớp: 03T3 Trang :4
  5. Chƣơng trình mô phỏng các giải thuật định thời Chƣơng II. Cơ sở lý thuyết I. Hệ điều hành Xét về phƣơng diện chức năng, các chƣơng trình máy tính có thể chia thành hai nhóm chính, đó là: - Các chƣơng trình cơ sở trợ giúp việc điều hành các máy tính. - Các chƣơng trình ứng dụng giải quyết các bài toán trong thực tiễn. 1. Định nghĩa hệ điều hành Hệ điều hành (HĐH) là một phần quan trọng của mõi hệ thống thông tin. Mõi hệ thống thông tin gồm 4 thành phần quan trọng: Phần cứng, hệ điều hành, chƣơng trình ứng dụng và ngƣời sử dụng. Phần cứng: Gồm CPU, bộ nhớ, thiết bị vào ra cung cấp các tài nguyên thông tin cơ sở. Các chƣơng trình ứng dụng: Gồm chƣơng trình dịch, hệ thống cơ sở dữ liệu, trình soạn thảo văn bản,… quy định cách sử dụng các tài nguyên đó để giả quyết những vấn đề của ngƣời sử dụng. Hệ điều hành: Điều khiển và đồng bộ việc sử dụng phần cứng của các chƣơng trình ứng dụng phục vụ các ngƣời sử dụng khác nhau với các mục đích phong phú đa dạng. Ngƣời sử dụng: Hiểu theo nghĩa rộng bao gồm những ngƣời sử dụng thuần tuý và các cán bộ vận hành đặc biệt đối với các máy trung và các máy lớn. Ta có thể hiểu hệ điều hành là hệ thống các chƣơng trình đảm bảo các chức năng giao tiếp ngƣời máy và và quản lý tài nguyên hệ thống tính toán. Tuy nhiên có nhiều ngƣời quan sát HĐH dƣới các góc độ khác nhau vì thế tồn tại nhiều định nghĩa về HĐH. Đối với ngƣời sử dụng : HĐH là tập hợp các chƣơng trình, phục vụ khai thác hệ thống tính toán một cách dễ dàng, thuận tiện. Ngƣời sử dụng khi thực hiện một chƣơng trình nào đó trên máy tính thì chỉ quan tâm đến việc hệ thống có đáp ứng đƣợc nhu cầu của hộ hay không? Họ không quan tâm đến việc hệ điều hành làm nhƣ thế nào, nhằm mục đích gì, có cấu trúc nhƣ thế nào? Đối với ngƣời làm công tác quản lý: HĐH là một tập các chƣơng trình phục vụ quản lý chặt chẽ và sử dụng tối ƣu các tài nguyên của hệ thống. Đối với cán bộ kỹ thuật: HĐH là hệ thống chƣơng trình bao trùm lên một máy tính vật lý cụ thể để tạo ra một máy logic với những tài nguyên mới và khả năng mới. 2. Các chức năng chính của hệ điều hành Hệ điều hành là một chƣơng trình đóng vai trò trung gian trong việc giao tiếp giữa ngƣời sử dụng và phần cứng của máy tính. Mục tiêu của hệ điều hành là cung cấp một môi trƣờng cho phép ngƣời sử dụng phát triển và thực hiện các ứng dụng của họ một cách dễ dàng và hiệu quả. Theo nguyên tắc, một hệ điều hành cần thoả mãn hai chức năng sau: Trần Văn Trung, Lớp: 03T3 Trang :5
  6. Chƣơng trình mô phỏng các giải thuật định thời a .Quản lý, chia sẻ tài nguyên. Tài nguyên hệ thống, đặc biệt các tài nguyên phầ cứng nhƣ CPU, bộ nhớ, thiết bị ngoại vi,.. hệ điều hành cần có các cơ chế và chiến lƣợc thích hợp để quản lý việc phân phối tài nguyên. b. Giả lập một máy tính Chức năng thứ hai của hệ điều hành là che dấu các chi tiết phần cứng của máy tính và giới thiệu với ngƣời dùng một máy tính mở rộng có đầy đủ các chức năng của máy tính. Với đề tài Viết chƣơng trình mô phỏng các giải thuật định thời trình bày về quá trình hoạt động của các tiến trình trong CPU, các trạng thái của hệ thống tính toán và việc chuyển từ trạng thái này sang trạng thái khác đƣợc thực hiện theo một chƣơng trình nào đó. Đã có nhiều chƣơng trình nghiên cứu đề tài này và ứng dụng trong cuộc sống và nó có những ƣu và khuyết điểm cố định + Ƣu điểm : Đã đƣa ra đƣợc cách xử lý của các tiến trình Chƣơng trình đơn giản, + Khuyết điểm : Chƣa nêu rõ việc tập hợp điều phối giữa các tiến trình Hƣớng nghiên cứu giới thiệu 3. Các chiến lƣợc điều phối a. Chiến lược FIFO Nguyên tắc: CPU đƣợc cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng có yêu cầu, là tiến trình đƣợc đƣa vào hệ thống sớm nhất. Đây là một thuật toán điều phối theo nguyên tắc độc quyền. Một khi CPU đƣợc cấp phát cho tiến trình, CPU chỉ đƣợc tiến trình tự nguyện giải phóng khi kết thúc xử lí hay khi có một yêu cầu xuất/ nhập. Chiến lƣợc này thì thời gian chờ trung bình không đạt cực tiểu và biến đổi đáng kể đối với các giá trị về thời gian yêu cầu xử lí và thứ tự khác nhau của cácd tiến trình trong danh sách sẵn sàng. Cá thể xảy ra hiện tƣợng tích luỹ thời gian chờ, khi tất cả các tiến trình phảI chờ đợi một tiến trình có yêu cầc thời gian dài kết thúc xử lí . Giải thuật này đặc biệt không phù hợp với các hệ phân chia thời gian, trong các hệ này, cần cho phếp mỗi tiến trình đƣợc cấp phát CPU đều đặn trong từng khoảng thời gian. b.Chiến lược xoay vòng ( Round Robin ) Nguyên tắc: Danh sách sẵn sàng đƣợc xử lí nhƣ một danh sách vòng, bộ điều phối lần lƣợt cấp phát cho từng tiến trình trong danh sách một khoảng thời gian sử dụng CPU đến hết thời gian quantum dành cho nó, hệ điều hành thu hồi và cấp phát cho quá trình kế tiếp trong danh sách. Nếu tiến trình bị khoá hay kết thúc trƣớc khi sử dụng hết thời gian quantum, hệ điều hành cũng lập tức cấp phát CPU cho tiến trình khác. Khi tiến tình tiêu thụ hết thời gian CPU cấp phát dành cho nó mà chƣa hoàn tất, tiến trình đƣợc đƣa trở lại vào cuối danh sách sẵn sàng để đƣợc cấp CPU trong lƣợt kế tiếp. Vấn đề quan tâm đối với giả thuật RR là độ dài quantum quá bé sẽ phát sinh quá nhiều sự chuyển đổi giữa các tiến trình và khiến cho việc sử dụng quantum quá lớn sẽ làm tăng thời gian hỏi đáp và giảm khả năng tƣơng tác của hệ thống. c. Chiến lược công việc ngắn nhất ( Shotrtest job first-SJF ) Nguyên tắc: Đây là một trƣờng hợp đặp biệt của giải thuật điều phối với độ ƣu tiên p đƣợc gán cho mỗi tiến trình là mỗi tiến trình là nghịch đảo của thời gian xử lí mà tiến Trần Văn Trung, Lớp: 03T3 Trang :6
  7. Chƣơng trình mô phỏng các giải thuật định thời trình yêu cầu: p=1/t. Khi CPU đƣợc tự do thì nó sẽ đƣợc cấp phát cho tiến trình yêu cầu ít thời gian nhất để kết thúc tiến trình ngắn nhất. Giải thuật này cũng có khả năng độc quyền hay không độc quyền. Sự lựa chọn xảy ra khi có một tiến trình mới đƣa vào danh sách sẵn sàng trong khi một tiến trình khác đang xử lí. Tiến trình mới có thể sở hữu một yêu cầu thời gian sử dụng CPU cho lần tiếp theo ngắn hơn thời gian còn lại mà tiến trình hiện hành cần xử lí. GiảI thuật SJF không độc quyền sẽ dừng họat động của tiến trình hiện hành, trong khi giải thuật độc quyền sẽ cho phép tiến trình hiện hành tiếp tục xử lí. Giải thụât này cho phép đạt đƣợc thời gian chờ trung bình cực tiểu. Khó khăn thực sự của giải thuật SJF là không thể biết đƣợc thời gian xử lí lần thứ n, t n+1 là giá trị dự đoán cho lần xử lí tiếp theo. Với hy vọng gia trị dữ đoán sẽ giống với các giá trị trƣớc đó, có thể sử dụng công thức: Tn+1 = α tn+1(1-α)tn Trong đó tn+1 chứa đựng thông tin gần nhất, tn chứa đựng các thông tin quá khứ đƣợc tích luỹ, tham số ỏ kiểm soát trọng số hiện tại gần hay quá khứ ảnh hƣởng đến công thức dữ toán. II. Định nghĩa tiến trình 1. Định nghĩa tiến trình Tất cả các máy tính hiện đại đều có thể thực hiện nhiều việc cùng một lúc. Trong khi thực hiện chƣơng trình của ngƣời sử dụng, máy tính có thể đọc dữ liệu từ đĩa và đƣa ra màn hình hoặc máy in. Trong môi trƣờng đa chƣơng trình ( multiprogramming system ), một CPU có thể chuyển từ chƣơng trình này sang chƣơng trình khác, thực hiện mỗi chƣơng trình trong khoảng 1% hoặc 1/10 mili giây. Nếu nói chính xác, thì tại một thời điểm, CPU chỉ thực hiện đƣợc một chƣơng trình. Nhƣng nếu xét trong khoảng thời gian phần trăm giây thì CPU có thể thực hiện nhiều công việc. Định nghĩa Tiến trình là một dãy các trạng thái của hệ thống tính toán và việc chuyển từ trạng thái này sang trạng thái khác đƣợc thực hiện theo 1 chƣơng trình nào đó. … sn-1 … s0 s1 s2 s3 s4 s5 s6 s7 sn sn+1 Các trạng thái này không nhất thiết phải liên tiếp nhau. + Nếu chƣơng trình của hệ thống thì cho ta tiến trình hệ thống + Nếu chƣơng trình của ngƣời sử dụng thì cho ta tiến trình là chƣơng trình đang đƣợc thực hiện Hiểu một cách thông thƣờng ta có thể coi tiến trình là một chƣơng trình đang đƣợc thực hiện. Ví dụ Trần Văn Trung, Lớp: 03T3 Trang :7
  8. Chƣơng trình mô phỏng các giải thuật định thời Khëi t¹o KÕt thóc ng¾t ®-îc chÊp nhËn tho¸t S½n sµng Thùc hiÖn ®iÒu phèi kÕt thóc mét sù kiÖn hoÆc mét chê ®îi mét sù kiÖn hoÆc mét tÝn hiÖu vµo/ra tÝn hiÖu vµo/ra Chê ®îi + Khởi tạo: Tiến trình đang đƣợc tạo ra + Sẵn sang: Tiến trình chờ để kết nối vào Processor. + Thực hiện: Các lệnh đang đƣợc thực hiện. + Chờ đợi: Tiến trình chờ một sự kiện vào/ra hoặc chờ nhận một tín hiệu nào đó + Kết thúc: Tiến trình kết thúc thực hiện. b. Khối điều khiển tiến trình( Process Control Block) Mỗi tiến trình đƣợc biểu diễn trong hệ điều hành bởi một khối điều khiển tiến trình gồm có + Trạng thái tiến trình. + Lệnh máy: máy tính chỉ ra địa chỉ lệnh máy đầu tiên trong tiến trình. Bộ thanh ghi. + Thông tin về lịch trong bộ điều khiểu CPU: bao gồm thứ tự ƣu tiên của tiến trình, các tham số để lập lịch. + Thông tin về bộ nhớ. + Thông tin tính toán: gồm thời gian chiếm giữ processor, thời gian thực tế, giới hạn về thời gian, số lƣợng công việc. Thông tin trạng thái các cổng vào/ra. c. Thực hiện tuần tự Khi hệ thống kết thúc một tiến trình thì hệ thống mới chuyển sang tiến trình khác. Thực hiện tuần tự không phải là đối tƣợng nghiên cứu của chúng ta. + Thực hiện song song Hai tiến trình đƣợc gọi là song song nếu thời điểm bắt đầu của một tiến trình nằm giữa thời điểm bắt đầu và kết thúc của tiến trình kia. Tiến trình 1 Bắt đầu Kết thúc Tiến trình 2 Trần Văn Trung, Lớp: 03T3 Trang :8
  9. Chƣơng trình mô phỏng các giải thuật định thời Bắt đầu Thực hiện song song vật lý: cùng một thời điểm 2 tiến trình cùng đƣợc thực hiện. Các điểm cần chú ý: + Loại này chỉ có thể thực hiện ở trong chế độ nhiều processor. + Hai tiến trình song song vật lý có thể sử dụng song song thiết bị ngoại vi và processor do đó cách làm việc của hệ thống hoàn toàn khác so với chế độ đơn processor. Thực hiện song song đan xen Để nâng cao hiệu quả của processor, các tiến trình lần lƣợt đƣợc phục vụ đan xen lẫn nhau. B A C C B A TiÕn tr×nh Thêi gian A HÖ ®iÒu hµnh B Ngắt hoặc lời gọi hệ thống Cất giữ trạng thái trong PCBA NghØ Khôi phục trạng thái từ PCBB Hoạt động NghØ Ngắt hoặc lời gọi hệ thống đ ộ ng Cất giữ trạng thái trong PCBB NghØ Khôi phục trạng thái từ PCBA Ho¹t ®éng Sự thay đổi thực hiện tiến trình Trần Văn Trung, Lớp: 03T3 Trang :9
  10. Chƣơng trình mô phỏng các giải thuật định thời III. Phân loại tiến trình song song 1.Độc lập Hai tiến trình song song đƣợc thực hiện riêng rẽ không có quan hệ với nhau. A1 B1 A2 B2 … … An Bm Hệ thống phải có cơ chế bảo vệ để tiến trình này không làm ảnh hƣởng đến tiến trình khác. 2.Quan hệ thông tin Hai tiến trình A và B đƣợc gọi là có quan hệ thông tin với nhau nếu tiến trình này có gửi thông báo cho tiến trình kia. Tiến trình gửi thông báo có thể không cần biết tiến trình nhận có tồn tại hay không? ở đâu? và đang ở giai đoạn nào? A1 B1 Information A2 B2 Information … … An Bm Trần Văn Trung, Lớp: 03T3 Trang :10
  11. Chƣơng trình mô phỏng các giải thuật định thời Các phƣơng pháp tổ chức lƣu trữ các thông báo: Sử dụng bộ nhớ Hệ thống sẽ sử dụng một phần bộ nhớ để lƣu trữ các thông báo. Mỗi tiến trình cần nhận thông báo chỉ việc rà soát trong “ hòm thƣ ” của hệ thống.  Ƣu điểm: lƣu trữ đƣợc lƣợng thông tin lớn với thời gian lƣu trữ lâu.  Nhƣợc điểm: tính thụ động cao. Gửi thông báo qua cổng vào/ra +Ƣu điểm: các tiến trình có thể dễ dàng lấy thông tin từ cổng mà không bị hàng rào bộ nhớ ngăn cản. + Nhƣợc điểm: dung lƣợng thông tin chứa ở các cổng không lớn, thời gian lƣu trữ thông báo bị hạn chế. Sử dụng chƣơng trình thƣ ký (Monitor) Chƣơng trình thƣ ký (Monitor) là chƣơng trình của hệ thống, nó đƣợc cung cấp mọi thông tin nhƣng không có khả năng điều khiển hệ thống. Thông qua chƣơng trình này, tiến trình có thể dễ dàng xác định đƣợc tiến trình kia ở đâu. + Ƣu điểm: Tính chủ động cao. 3.Loại song song phân cấp Là loại tiến trình mà trong quá trình hoạt động nó sản sinh ra một tiến trình nữa hoạt động song song với chính nó. A1 A2 B1 … B2 An … Bm Trần Văn Trung, Lớp: 03T3 Trang :11
  12. Chƣơng trình mô phỏng các giải thuật định thời Khi tiến trình con đã hoạt động thì hai tiến trình này không biết gì về nhau Tài nguyên của tiến trình con có thể lấy từ vốn tài nguyên của hệ thống hoặc lấy từ vốn tài nguyên của tiến trình chính. + Nếu lấy tài nguyên từ vốn tài nguyên của hệ thống thì hệ thống có thể quản lý tài nguyên tập chung. Nhƣ vậy sẽ tối ƣu hoá đƣợc việc sử dụng tài nguyên, nhƣng việc quản lý này rất phức tạp. + Nếu tiến trình con lấy từ vốn tài nguyên của tiến trình chính thì ta có hệ quản lý tài nguyên phân tán. Loại tài nguyên này đơn giản, nhƣng không có khả năng khai thác tối ƣu tài nguyên hệ thống. Trong mọi trƣờng hợp nếu tài nguyên lấy ở đâu thì phải trả về đó, vì vậy tiến trình chính thƣờng sử dụng các lệnh chờ POS hoặc WAIT để các tiến trình con kịp trả lại tài nguyên. 4.Tiến trình đồng mức song song Hai tiến trình đƣợc gọi là đồng mức nếu có thể sử dụng chung tài nguyên theo nguyên tắc lần lƣợt. A1 B1 Tài A2 B2 Nguyên … … An Bm Hai tiến trình này không phân biệt tiến trình chính và tiến trình con, mà là hai tiến trình độc lập. Mỗi tiến trình sau khi sử dụng tài nguyên thì phải trả lại cho hệ thống và tiếp tục hoạt động độc lập. Ví dụ: chƣơng trình chơi cờ: Tài nguyên chung là bàn cờ. Giả sử đến lƣợt tiến trình thứ nhất, tiến trình thứ nhất chiếm tài nguyên để chơi, khi ra quyết định xong thì trả lại bàn cờ cho hệ thống. Tiến trình thứ hai phải kiểm tra xem tiến trình thứ nhất đã đi chƣa? nếu xong rồi thì mới đến lƣợt nó (thực hiện nhƣ tiến trình thứ nhất). Mô tả tiến trình song song Ta dùng ký pháp nhân tạo Trần Văn Trung, Lớp: 03T3 Trang :12
  13. Chƣơng trình mô phỏng các giải thuật định thời Giả sử cần thực hiện một tập các khối lệnh song song s1, s2, … , sn Ta đƣa vào trong một khối lệnh đƣợc bắt đầu bởi từ khoá ParBegin (Parallel Begin) và kết thúc bởi từ khoá ParEnd (Parallel End). ParBegin S1; S2; ... Sn; ParEnd; … S1 S2 Sn Trần Văn Trung, Lớp: 03T3 Trang :13
  14. Chƣơng trình mô phỏng các giải thuật định thời Chƣơng III: Phân tích và thiết kế hệ thống 1.Tài nguyên găng và đoạn găng Tài nguyên găng là tài nguyên mà trong một khoảng thời gian nhất định thì chỉ phục vụ hợp lý cho một số hữu hạn các tiến trình. Đoạn chƣơng trình sử dụng tài nguyên găng gọi là đoạn găng hay chỗ hẹp trong tiến trình. Hệ điều hành phải tổ chức cho mọi tiến trình đi qua chỗ hẹp một cách hợp lý, công việc này gọi là điều độ tiến trình qua đoạn găng. Sự cần thiết phải điều độ Ta xem xét ví dụ khi 2 tiến trình cùng muốn in ra máy in. + Khi một tiến trình cần in một tệp ra máy in, nó đƣa tên tệp vào thƣ mục spool. Một tiến trình điều khiển in khác kiểm tra định kỳ nếu có tệp nào cần in, nếu tìm thấy thì in tệp nó và loại tên tệp khỏi thƣ mục spool. Giả sử thƣ mục spool có số lƣợng phần tử rất lớn (mỗi phần tử chứa một tên tệp). Ta có hai biến dùng dung là OUT để chỉ tệp tiếp theo cần in và IN để chỉ vị trí rỗng tiếp theo dùng để chứa tên tệp cần in. + Ta giả sử vị trí 0 – 3 rỗng (các tệp đã đƣợc in), vị trí 4 – 6 đang bận (chứa tên tệp cần in). Nhƣ vậy biến OUT = 4 và IN = 7 Tiến trình A OUT = 4 4 Abc.txt 5 Prog.doc 6 Prog.pas IN = 7 7 Tiến trình B + Giả sử tiến trình A cần in một tệp a.txt, khi đó tiến trình A sẽ đọc biến IN và đƣa vào biến cục bộ INA, nhƣ vậy INA = 7. Lúc đó có tín hiệu ngắt đồng hồ và CPU quyết định tiến trình A đã chạy đủ thời gian và chuyển sang thực hiện tiến trình B. Đến lƣợt mình, tiến trình B cũng muốn in tệp b.txt. Tiến trình B đọc biến IN và đƣa vào biến cục bộ INB, nhƣ vậy INB = 7. Tiến trình B đƣa tên tệp b.txt vào vị trí thứ 7 trong thƣ mục spool và cập nhật biến IN = INB + 1 = 8, sau đó làm các việc khác. Trần Văn Trung, Lớp: 03T3 Trang :14
  15. Chƣơng trình mô phỏng các giải thuật định thời + Khi CPU chuyển sang thực hiện tiến trình A, không may tiến trình A vẫn giữ nguyên biến INA=7. Tiến trình A đƣa tên tệp a.txt vào vị trí thứ 7 và cập nhật biến IN = INA + 1 = 8. + Tiến trình điều khiển in không đƣợc thông báo là có sự cố và tiếp tục thực hiện nhiệm vụ. + Nhƣ vậy tệp b.txt đã bị đổi thành tệp a.txt và sẽ không đƣợc in ra máy in. Các công cụ điều độ phải thoả mãn các yêu cầu sau: + Phải đảm bảo sao cho tiến trình không chiếm giữ tài nguyên găng vô hạn + Nếu có một tiến trình xếp hàng chờ tài nguyên găng thì sớm hay muộn nó phải vào đƣợc đoạn găng của mình (đƣợc phục vụ tài nguyên găng). + Nếu có tiến trình xếp hàng chờ đợi tài nguyên găng và nếu tài nguyên găng đó đƣợc giải phóng thì nó phải đƣợc phục vụ trong các tiến trình đang chờ đợi. Các công cụ điều độ: Chia làm ba lớp chính + Phƣơng pháp khoá trong: là loại giải thuật không yêu cầu gì về thiết bị hoặc hệ thống. Phƣơng pháp này có tính chất vạn năng ứng với mọi ngôn ngữ, mọi loại máy. + Kiểm tra và xác lập Xác lập dựa vào thiết bị, thiết bị có những lệnh đặc biệt phục vụ cho riêng công tác điều độ. +Kỹ thuật đèn báo: dựa vào công cụ đặc biệt của từng hệ điều hành. 2.Phƣơng pháp khoá trong Nguyên lý: Dùng thêm các biến với tƣ cách là tài nguyên chung để chứa các cờ cho biết tiến trình vào đoạn găng hay ra khỏi đoạn găng. Giả thiết:  Có hai tiến trình song song cùng sử dụng 1 tài nguyên găng chung và khả năng phục vụ của tài nguyên găng là 1.  Mỗi tiến trình chỉ có một đoạn găng nằm ở đầu tiến trình.  Các tiến trình này lặp vô hạn, nếu có kết thúc thì ở đâu đó ngoài đoạn găng. Sử dụng một biến IS_USED có giá trị bằng 1 để chỉ ra tài nguyên găng đang bị một tiến trình nào đó chiếm giữ và ngƣợc lại, khi IS_USED = 0 chỉ ra tài nguyên găng đang sẵn sàng phục vụ. Khi một tiến trình thấy biến IS_USED = 0, nó phải đặt biến IS_USED = 1 trƣớc khi sử dụng tài nguyên găng. Tuy nhiên ta dễ dàng tiến biến IS_USED lại trở thành tài nguyên găng. Giả sử tiến trình 1 kiểm tra thấy biến IS_USED = 0, trƣớc lúc nó đặt biến này lên 1 thì tiến trình 2 lại kiểm tra biến này và tất nhiên khi đó biến IS_USED = 0. Nhƣ vậy cả hai tiến trình đều vào đoạn găng và đều sử dụng tài nguyên găng. Nói cách khác vấn đề điều độ chƣa đƣợc giải quyết Sử dụng biến TURN để chỉ đến lƣợt tiến trình nào đƣợc sử dụng tài nguyên găng.  Sơ đồ nguyên lý Trần Văn Trung, Lớp: 03T3 Trang :15
  16. Chƣơng trình mô phỏng các giải thuật định thời Var turn : integer; Begin turn := 1; ParBegin { Hai khối lệnh trong từ khoá ParBegin và ParEnd được thực hiện song song với nhau } TT1: REPEAT while (turn 1) do ; vao_doan_gang_1; { đoạn găng của tiến trình 1 } turn := 2; { chuyển tài nguyên găng cho tt2) thuc_hien_viec_khac_1; { phần còn lại của tiến trình 1 } UNTIL FALSE; TT2: REPEAT while (turn 2) do ; vao_doan_gang_2; { đoạn găng của tiến trình 2 } turn := 1; { chuyển tài nguyên găng cho tt1) thuc_hien_viec_khac_2; { phần còn lại của tiến trình 2 } UNTIL FALSE; ParEnd; End.  Giải thích: Ban đầu TURN = 1, tức là tiến trình 1 đƣợc phép sử dụng tài nguyên găng. Khi tiến trình 1 dùng tài nguyên găng xong thì đặt TURN = 2, để cho phép tiến trình 2 sử dụng tài nguyên găng. Khi tiến trình 2 sử dụng xong tài nguyên găng thì lại đặt TURN = 1, để chỉ đến lƣợt tiến trình 1 sử dụng.  Tuy nhiên ta giả sử tiến trình 1 dùng xong tài nguyên găng, sau khi đặt TURN = 2 sang thực hiện thủ tục thuc_hien_viec_khac_1, thủ tục này khá ngắt, tiến trình 1 quay lại đoạn găng. Nhƣng lúc này tiến trình 2 đang bận thực hiện các công việc khác trong thủ tục thuc_hien_viec_khac_2. Tiến trình 2 vẫn chƣa vào đoạn găng vì vậy biến TURN vẫn có giá trị bằng 2. Vì vậy mặc dù tài nguyên găng không đƣợc sử dụng nhƣng do TURN = 2 mà tiến trình 1 không thể sử dụng đƣợc tài nguyên găng. Để khắc phục nhƣợc điểm này ngƣời ta đƣa ra cách thức dùng hai biến c1 và c2 cho hai tiến trình nhƣ sau:  Sơ đồ nguyên lý Var c1,c2 : integer; Trần Văn Trung, Lớp: 03T3 Trang :16
  17. Chƣơng trình mô phỏng các giải thuật định thời Begin c1 := 0; c2 := 0; ParBegin { Hai khối lệnh trong từ khoá ParBegin và ParEnd được thực hiện song song với nhau } TT1: REPEAT while (c2 > 0) do ; c1 := 1; vao_doan_gang_1; { đoạn găng của tiến trình 1 } c1 := 0; thuc_hien_viec_khac_1; { phần còn lại của tiến trình 1 } UNTIL FALSE; TT2: REPEAT while (c1 > 0) do ; c2 := 1; vao_doan_gang_2; { đoạn găng của tiến trình 2 } c2 := 0; thuc_hien_viec_khac_2; { phần còn lại của tiến trình 2 } UNTIL FALSE; ParEnd; End. Giải thích C1 và C2 đại diện cho việc sử dụng tài nguyên găng thứ nhất và tài nguyên găng thứ hai.  Ban đầu cả hai biến đều có giá trị bằng 0 thể hiện tài nguyên găng đang ở trạng thái sẵn sàng phục vụ.  Giả sử tiến trình 1 đƣợc phục vụ trƣớc, tiến trình 1 bỏ qua việc chờ đợi while (c2 > 0) do ; và chiếm lấy tài nguyên găng đồng thời đặt C1 = 1;  C1 = 1 có nghĩa là tiến trình 1 đang sử dụng tài nguyên găn g. Trong lúc tài nguyên găng đang bị tiến trình 1 chiếm giữ thì tiến trình 2 phải chờ đợi while (c1 > 0) do ; Khi tiến trình 1 dùng xong tài nguyên găng thì đặt lại biến C1 = 0.  Khi C1 = 0 và tiến trình 2 kết thúc việc chờ đợi Trần Văn Trung, Lớp: 03T3 Trang :17
  18. Chƣơng trình mô phỏng các giải thuật định thời while (c1 > 0) do ; { đƣợc kết thúc do c1 = 0 } lúc này tiến trình 2 chiếm giữ tài nguyên găng và đặt C2 = 1; Khi tiến trình 2 dùng xong tài nguyên găng thì đặt lại C2 = 0;  Quá trình nhƣ vậy đƣợc lặp đi lặp lại, cho đến khi kết thúc cả hai tiến trình (lệnh kết thúc ở trong đoạn chƣơng trình không phải là đoạn găng). Trong trƣờng hợp tồi nhất, cả hai tiến trình đều vào đoạn găng và đặt biến C1 và C2 bằng 1, và cả hai tiến trình đều không vào đƣợc đoạn găng và gây ra hiện tƣợng chờ đợi vòng tròn. Lý đo là việc xác lập vào đoạn găng và khả năng xem xét có đƣợc vào đoạn găng của hai đoạn trên không có quan hệ với nhau. Vì vậy ngƣời ta đƣa ra một phƣơng pháp khác phối hợp hai phƣơng pháp trên, phƣơng pháp này phối hợp Xác lập – Kiểm tra – Xác lập, do Delker công bố năm 1968 nhƣ sau: Var c1, c2, tt: integer; Begin c1:=0; c2:=0; tt:=1; ParBegin TT1: REPEAT c1:=1; while(c2=1) do Begin if(tt = 2) then Begin c1:=0; while(tt =2) do; c1:=1; End; End; vao_doan_gang_1; c1:=0; tt:=2; thuc_hien_viec_khac_1; UNTIL FALSE; TT2: REPEAT c2:=1; while(c1=1) do Begin if(tt = 1) then Begin c2:=0; while(tt =1) do; c2:=1; End; End; Trần Văn Trung, Lớp: 03T3 Trang :18
  19. Chƣơng trình mô phỏng các giải thuật định thời vao_doan_gang_2; c2:=0; tt:=1; thuc_hien_viec_khac_2; UNTIL FALSE; ParEnd; End. Ƣu điểm:  Giải thuật này có tính chất vạn năng áp dụng cho mọi công cụ và mọi hệ thống.  Tận dụng, phát huy khả năng tối đa tài nguyên găng. Nhƣợc điểm  Độ phức tạp tỷ lệ với số lƣợng tiến trình và số tài nguyên găng.  Tồn tại hiện tƣợng chờ đợi tích cực. Mặc dù không làm gì cả nhƣng vẫn chiếm thời gian processor. Nguyên nhân là do mỗi tiến trình phải làm việc với nhiều biến, trong đó có nhiều biến không phải của mình (ví dụ: muốn xác lập biến c1 phải kiểm tra biến c2 và biến tt). 3. Phƣơng pháp Kiểm tra và Xác lập (Test and Set) Trong hệ lệnh của máy tính tồn tại lệnh cho thực hiện nhiều công việc liên tục. Các công việc này tạo thành một hệ lệnh nguyên tố, không thể chỉ thực hiện một công việc. Thủ tục Test_And_Set có thể đƣợc định nghĩa nhƣ sau: Procedure TS(var local: integer); Begin local:=global; global:=1; End;  Chú ý: hai lệnh trên phải đƣợc thực hiện liên tục không bị chia rẽ.  Mỗi tiến trình sẽ sử dụng hai biến là biến local của mình và biến global của toàn chƣơng trình. Sơ đồ điều độ Var lc1, lc2: integer; global: integer; Procedure TS(var local: integer); Begin local:=global; global:=1; End; Trần Văn Trung, Lớp: 03T3 Trang :19
  20. Chƣơng trình mô phỏng các giải thuật định thời Begin gl:=0; ParBegin TT1: REPEAT lc1:=1; while lc1=1 do TS(lc1); vao_doan_gang_1; gl:=0; thuc_hien_viec_khac_1; UNTIL FALSE; TT2: REPEAT lc2:=1; while lc2=1 do TS(lc2); vao_doan_gang_2; gl:=0; thuc_hien_viec_khac_2; UNTIL FALSE; ParEnd; End. Global Lc1 Lc2 0 1 1 0 1 (chờ đợi) 1 ... 0 1 0 1 (chờ đợi) ... ... ... Ưu điểm: Khắc phục đƣợc độ phức tạp của thuật toán, độ phức tạp thuật toán không phụ thuộc vào số lƣợng tiến trình. Nhƣợc điểm: Vẫn còn hiện tƣợng chờ đợi tích cực. 4. Kỹ thuật đèn báo Đây là công cụ phụ thuộc vào hệ thống do Dijkstra đề xuất, với tƣ tƣởng nhƣ sau: Trần Văn Trung, Lớp: 03T3 Trang :20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.01: Bộ Luận Văn Thạc Sĩ Quản Trị Kinh Doanh MBA
165 tài liệu
2069 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

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

 

Đồng bộ tài khoản
2=>2