LÝ THUYẾT HỆ ĐIỀU HÀNH – ĐỀ CƯƠng bài giảNG

HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH

Bộ môn : Khoa học Máy tính
Giáo viên : 1 ) TRỊNH Minh Châu

2)

1. 
   Bài (chương, mục): Chương II: QUẢN LÝ TIẾN TRÌNH
   

II.1. Tiến trình

2. 
   Thời lượng: (GV giảng, thảo luận, thực hành, tự học) 3 tiết, tự học 3 tiết
   
3. 
   Mục đích, yêu cầu: Hiểu rõ khái niệm Tiến trình, phân biệt được chương trình, tiến trình; Nắm được các trạng thái của tiến trình, các mô hình tiên trìnhvà nguyên tắc quản lý tiến trình.
   

Học xong phần này có thể giải thích được việc hệ thống chuyển từ việc thực hiện tiến trìnhn này sang tiến trình khác như thế nào và tại sao

4. 
   Nội dung:
   

1. 
   Nội dung chi tiết: (công thức, định lý, hình vẽ)
   

II. 1.1. Khái niệm, định nghĩa tiến trình ( Process ) .
Tiến trình là một chương trình hoặc một phần của chương trình đã được nạp vào bộ nhớ chính, đang trong quy trình thực thi ( nhưng không nhất thiết là luôn luôn được cấp CPU ) .
Chương trình là thực thể thụ động, tiến trình là thực thể dữ thế chủ động của chương trình và có thời hạn sống nhất định ( life cycle ) .
Trong 1 số ít tài liệu tiếng Anh có sử dụng khái niệm job hay task : việc làm hay công dụng, hoàn toàn có thể hiểu là tiến trình giống như process, và 1 số ít tài liệu tiếng Việt dịch process là quy trình .

II. 1.2. Các trạng thái của tiến trình

• 
  Mới (new): tiến trình mới vừa được khởi tạo
  
• 
  Sẵn sàng (ready): Tiến trình đang đợi trong hàng đợi (ready queue) sãn sàng chiếm dụng CPU để tiếp tục thi hành
  
• 
  Thực thi (running): Tiến trình đang được CPU thực thi các câu lệnh (tiến trình đang chiếm dụng CPU)
  
• 
  Bị chặn-chờ (blocked – waiting): Tiến trình đang đợi một sự kiện nào đó trước khi tiếp tục thi hành. Sự kiện đó có thể là việc xuất/nhập dữ liệu hoặc tín hiệu đồng bộ từ một tiến trình khác.
  
• 
  Kết thúc (terminated-exited): tiến trình kết thúc.
  

Một tiến trình có thể chuyển từ trạng thái này sang trạng thái khác chủ động hoặc bị động

II. 1.3. Khối điều khiển và tinh chỉnh tiến trinh PCB ( Process Control Block )
Mỗi một tiến trình được quản trị trong HĐH bởi một PCB .
Khối điều khiển và tinh chỉnh tiến trình là một cấu trúc tài liệu gồm những thông tin quan trọng sau :
1. Danh định cho tiến trình ( PID )
2. Trạng thái của tiến trình
3. Bộ đếm chương trình – chứa địa chỉ của lệnh tiếp theo
4. Vùng lưu giá trị thanh ghi CPU
5. Độ ưu tiên của tiến trình
6. Thông tin xác định bộ nhớ tiến trình
7. Thông tin bảo mật thông tin
8. Con trỏ đến những tiến trình cha, con
9. Bộ vi giải quyết và xử lý mà tiến trình đang sử dụng ( trong những hệ đa bộ giải quyết và xử lý )

10. Danh sách các tài nguyên mà tiến trình đang sử dụng

II.1.4. Mô hình tiến trình, các loại tiến trình (Process Models)

Các mạng lưới hệ thống khác nhau hoàn toàn có thể tổ chức triển khai để những tiến trình hoàn toàn có thể thực thi tuần tự hoặc song hành .

Ở hệ thống các tiến trình song hành có thể chia làm nhiều dạng (mô hình) khác nhau:

• 
  Tiến trình song hành đồng mức
  
• 
  Tiến trình song hành độc lập
  
• 
  Tiến trình song hành có quan hệ thông tin
  
• 
  Tiến trình song hành phân cấp
  

Như vậy ở góc nhìn nào đó như liên quan tới lịch sử phát triển HĐH, có thể hình dung có các mô hình tiến trình như sau:

• 
  Mô hình theo dõi giản đơn (Simple Monitor System Models)
  
• 
  Mô hình xử lý theo bó giản đơn (Batch System Models)
  
• 
  Mô hình xử lý theo bó thông minh (Batch System ưith Block Models)
  
• 
  Mô hình phân chia thời gian (Time Sharing Interactive Models)
  

II. 1.5. Chuyển CPU giữa những tiến trình ( Context Switch )
Giả sử có 2 tiến trình P0, P1. P0 đang chạy thì Open ngắt và P0 dừng lại, khi đó hàng loạt thông tin về P0 từ những thanh ghi được ghi ra thực thể PCB0 trong bộ nhớ chính. Sau đó những thông tin của P1 từ PCB1 trong bộ nhớ chính được nạp vào những thanh ghi và thực thi P1 … .

II. 1.6. Lập thời biểu tiến trình ( Process Scheduling )
Trong mạng lưới hệ thống có nhiều tiến trình song hành, những tiến trình chuyển từ trạng thái này sang trạng thái khác và CPU chuyển từ việc cấp cho tiến trình này sang tiến trình khác. CPU tại một thời gian đơn cử chỉ hoàn toàn có thể triển khai một chỉ lệnh của một tiến trình, thế cho nên những tiến trình khác sẽ phải chờ trong những hang đợi khác nhau .

1. 
   Hàng đợi lập thời biểu (Scheduling Queues)
   

Các tiến trình đang chờ được cấp CPU để được thực hiện được xếp vào hang đợi sẵn sang. Các tiến trình khác có thể đang trong quá trình chờ kết thúc hoặc ngoại vi sẵn sang sẽ nằm trong các hàng đợi tương ứng.

2. 
   Bộ định thời biểu (Schedulers)
   

Việc xếp các tiến trình vào vị trí thích hợp trong các hàng đợi khác nhau sẽ do các bộ định thời thực hiện. Các bộ định thời bao gồm:

• 
  Bộ định thời dài (Long-term Scheduler)
  
• 
  Bộ định thời ngắn (Short-term Scheduler)
  
• 
  Bộ định thời trung kỳ (Midle-term Scheduler)
  

Bộ định thời ngắn quyết định chọn tiến trình nào trong hàng đợi sẵn sang để thực thi tức là cấp CPU cho nó, và vì vậy cũng được gọi là bộ định thời CPU hay lập lịch cho CPU (CPU Scheduling) sẽ được nghiên cứu kỹ trong bài sau.

2. 
   Nội dung thảo luận
   
3. 
   Nội dung tự học
   

4. 
   Bài tập (bắt buộc, mở rộng)
   

5. 
   Tài liệu tham khảo (sách, báo – chi tiết đến chương, mục, trang)
   

• 
  Tài liệu 1: Chương 4 từ trang 95 đến trang 107
  
• 
  Tài liệu 2: Chương 2 mục 2.1 từ trang 48 đến trang 52
  

6. 
   Câu hỏi ôn tập
   

HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH

Bộ môn : Khoa học Máy tính

Giáo viên: 1) TRỊNH Minh Châu

2)

1. 
   Bài (chương, mục): Chương II QUẢN LÝ TIẾN TRÌNH
   

II.2. Luồng (Thread)

2. 
   Thời lượng: (GV giảng, thảo luận, thực hành, tự học) 1 tiết, tự học 1 tiết
   

Mục đích, yêu cầu: Học xong phần này nắm được khái niệm về luồng, phân biệt được chương trình, tiến trình và luồng. Có thể giải thích được việc hệ thống chuyển từ việc thực hiện tiến trìnhn này sang tiến trình khác như thế nào và tại sao.

3. 
   Nội dung:
   

1. 
   Nội dung chi tiết: (công thức, định lý, hình vẽ)
   

II.2.1 Khái niệm
Luồng hay còn được sử dụng với khái niệm tiểu trình hay thiết trình .
Luồng được xem như một phiên bản đơn thuần của tiến trình mà đã được bỏ đi nhiều đặc tính. Truyền thống, một tiến trình sẽ có một luồng thực thi việc làm. Nhưng một tiến trình hoàn toàn có thể tiềm ẩn nhiều luồng .
Một tiến trình gồm có : thread id, program counter, tập thanh ghi register, và một ngăn xếp stack. Luồng sẽ san sẻ với những luồng trong cùng một tiến trình phần mã ( code ssection ), phần dữ liệu ( data section ), và những tài nguyên của HĐH mà được dùng bởi tiến trình .

II. 2.2. Lợi ích của việc sử dụng luồng

• 
  Khả năng đáp ứng nhanh: Các phần của ứng dụng có thể phúc đáp với user độc lập với nhau. Một luồng của Web browser có thể web, luồng khác có thể download tệp
  
• 
  Chia sẻ tài nguyên: Các luồng có thể chia sẻ không gian bộ nhớ và tài nguyên của tiến trình.
  
• 
  Kinh tế: Việc cấp phát bộ nhớ và tài nguyên cho tiến trình là một việc tốn thời gian, nhưng việc này có thể giảm đi rất nhiều nếu áp dụng luồng.
  
• 
  Tận dụng được ưu thế của các kiến trúc đa bộ vi sử lý.
  

Tiến trình đa luồng ( multithreaded process ) là tiến trình thực thi trong nhiều luồng. Các thread trong cùng một process san sẻ code section, data section và tài nguyên khác ( những file đang mở, … ) của process .

II. 2.3. Các quy mô đa luồng :

• 
  Mô hình nhiều – một (Many to One)
  
• 
  Mô hình một – một (One to One)
  
• 
  Mô hình nhiều – nhiều (Many to Many)
  

2. 
   Nội dung thảo luận
   
3. 
   Nội dung tự học
   

Tự đọc về giao tiếp liên tiến trình (Interprocesses Communication)

4. 
   Bài tập (bắt buộc, mở rộng)
   

4. 
   Tài liệu tham khảo (sách, báo – chi tiết đến chương, mục, trang)
   

• 
  Tài liệu 1, chương 5 trang 129 đến 149
  
• 
  Tài liệu 2: chương 2 mục 2.1.3 trang 53
  

5. 
   Câu hỏi ôn tập
   

HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH

Bộ môn : Khoa học Máy tính
Giáo viên : 1 ) TRỊNH Minh Châu

2)

1. 
   Bài (chương, mục): Chương II QUẢN LÝ TIẾN TRINH
   

II. 3. Lập lich cho CPU ( CPU Scheduling )

2. 
   Thời lượng: (GV giảng, thảo luận, thực hành, tự học) 2 tiết, tự học 3 tiết
   
3. 
   Mục đích, yêu cầu:
   

Nắm được các khái niệm liên quan tới lập lịch bao gồm lập licgh cho CPU, nắm sâu hơn vấn đề song hành của các tiến trình và việc thực hiện chúng.

Hiểu và vận dụng được những thuật toán lập lịch cho CPU, hướng tới viết được những modul chương trình quản trị cấp phép CPU

4. 
   Nội dung:
   

1. 
   Nội dung chi tiết: (công thức, định lý, hình vẽ)
   

Bộ lập lịch cho CPU: Bất cứ khi nào CPU rỗi, HĐH phải chọn một tiến trình đang có trong hàng đợi sẵn sàng để thực hiện, đây là hệ thống đa nhiệm. Việc chọn này được thực hiện bởi một lập lịch gọi là lập lịch ngắn hạn (Short-term Scheduler).

II. 3.1. Các khái niệm cơ bản ( Basic Concepts )

• 
  Chu kỳ CPU-I/O (CPU-I/O Burst Cycle)
  

Thông thường một tiến trình trong quá trình được thực hiện có thời gian làm việc mà thực chủ yếu là chờ I/O (do I/O thường rất chậm so với việc CPU thực thi các chỉ lệnh).

• 
  Bộ lập lịch CPU
  

Bộ định thời hay bộ lập lịch cho CPU là chức năng cơ bản của bất cứ HĐH nào, đảm nhiệm việc chọn tiến trinh để cấp CPU cho nó. Quyết định lập lịch CPU có thể xảy ra dưới điều kiện 1 trong 4 trường hợp sau:

1. 
   Tiến trình chuyển từ Running sang trang thái chờ
   
2. 
   Tiến trình chuyển từ Running sang trạng thái sẵn sang
   
3. 
   Tiến trình chuyển từ trạng thái chờ sang sẵn sang
   
4. 
   Tiến trình kết thúc.
   

Trường hợp 1 và 4 tiến trình đang giữa CPU trả CPU cho hệ thống một cách tự nguyện vì bản than nó không cần CPU lúc đó.

• 
  Định thời không trưng dụng, không bắt buộc tức là tự nguyện (NonePre-emptive)
  

Tiến trình giữa CPU sẽ chỉ trả CPU khi nó kết thúc hoặc chuyển sang trạng thái chớ khi làm việc với I/O chẳng hạn. Cũng có thể sử dụng thuật ngữ không ưu tiên trước như một số tài liệu.

• 
  Định thời trưng dụng hay định thời ưu tiên trước: Lập lịch ưu tiên trước (Pre-emptive) ưu tiên cho những tiến trình có CPU burst ngắn hơn
  
• 
  Bộ cấp phát (Dispatcher)
  

II. 3.2. Các tiêu chuẩn lập lịch
Đánh giá bộ lập lích dựa trên những tiêu chuẩn trung dưới đây ; với những mạng lưới hệ thống và nhu yếu khác nhau những tiêu chuẩn hoàn toàn có thể đóng vai trò quan trọng khác nhau :

• 
  Việc sử dụng CPU
  
• 
  Thông lượng
  
• 
  Thời gian hoàn thành
  
• 
  Thời gian chờ
  
• 
  Thời gian đáp ứng/ thời gian phúc đáp
  

II. 2.3. Các thuật toán định thời ( Scheduling Algorythms )
Thuật toán định thời vận dụng để chọn tiến trình đang trongb hàng đợi sẵn sang để cấp CPU

1. 
   Tiến trình đến trước phục vụ trước: Thuật toán FCFS (First Come First Serve)
   

Đây là giải thuật đơn giản nhất khi mà tiến trình nào vào hàng đợi sẵn sang trước sẽ được lựa chọn phục vụ trước tức là được chọn để cấp CPU.
Thuật toán này sẽ cấp CPU cho tiến trình cho đến khi CPU được giải phỏng, như vậy FCFS là định thời không trưng dụng hay định thời tự nguyện .

2. 
   Chọn tiến trinh yêu cầu CPU ngắn nhất: Giải thuật SJF (Shortest Job First)
   

Giải thuật này lựa chọn tiến trình có yêu cầu CPU ít nhất trong số các tiến trình đang xếp ở hàng đợi sẵn sàng. Khi tiến trình đã được cấp CPU nó sẽ chiếm giữ CPU đến khi nó tự nguyện nhường trả CPU nên cũng được gọi là SJF không trưng dụng hay không ưu tiên

3. 
   Thuật toán SJF trưng dụng:
   

Tương tự như SJF nhưng trong khi tiến trình đang giữa CPU có tiến trình mới sẵn sàng nhưng chỉ yêu cầu CPU ngắn hơn thời lượng còn cần CPU của tiến trình hiện tại thì CPU cũng sẽ được HĐH giành lại và cấp cho tiến trình mới. Thuật toán này cũng được gọi là Pre_emptive SJF hay SJF trưng dụng hay SRTF (Shortest Remaining Time First). Cũng có cách gọi khác là SJF ưu tiên.

4. 
   Định thời luân phiên Robin (Round Robin Scheduling) hay còn gọi là phân chia thời gian viết tắt là RR. Các tiến trình sẽ được cấp CPU lần lượt, mỗi tiến trình được cấp một khoảng thời lương CPU tối đa xác định.
   

Trong thực tế các HĐH có thể kết hợp, lồng ghép các thuật toán trên hay các giải thuạt phát triển từ các thuật toán trên như định thời với hàng đợi nhiều cấp, định thời hàng đợi phản hồi đa cấp.
Đánh giá những giải thuật

• 
  FCFS
  
• 
  SJF
  
• 
  SRTF
  
• 
  RR
  

2. 
   Nội dung thảo luận
   
3. 
   Nội dung tự học
   

Tự đọc nâng cao phần định thời đa xử lý (đa lõi và đa chip) và Lập lịch thời gian thực.

4. 
   Bài tập (bắt buộc, mở rộng) 3 tiết trên lớp
   

Câu 1: Có các tiến trình P0, P1, P2, P3, P4 và P5 đã đang sẵn sàng chờ được cấp phát CPU. Đánh giá các thuật toán lựa chọn tiến trình để cấp phát (thuật toán lập lịch cho CPU). Các tiến trình có thời gian cần CPU (CPU burst time) và có thời gian đến (vào hàng đợi Ready) được cho trong bảng dưới đây:

Đối với mô hình Time-sharing, Quantum time hay Time slice = 10ms

Câu 2: Có các tiến trình P0, P1, P2, P3, P4 và P5 đã đang sẵn sàng chờ được cấp phát CPU. Đánh giá các thuật toán lựa chọn tiến trình để cấp phát (thuật toán lập lịch cho CPU). Các tiến trình có thời gian cần CPU (CPU burst time) và có thời gian đến (vào hàng đợi Ready) được cho trong bảng dưới đây:

Đối với mô hình Time-sharing, Quantum time hay Time slice = 10ms

5. 
   Tài liệu tham khảo (sách, báo – chi tiết đến chương, mục, trang)
   

• 
  Tài liệu 1: Chương 6, từ trang 151 đến trang 187
  
• 
  Tài liệu 2: Chương 2, mục 2.4 từ trang 82 đến trang 93
  

6. 
   Câu hỏi ôn tập
   

.

HỌC PHẦN: LÝ THUYẾT HỆ ĐIỀU HÀNH

Bộ môn : Khoa học Máy tính
Giáo viên : 1 ) TRỊNH Minh Châu

2)

1. 
   Bài (chương, mục): Chương II: QUẢN LÝ TIẾN TRÌNH
   

II. 4. Đồng bộ hóa tiến trình ( Process Synchronization )

2. 
   Thời lượng: (GV giảng, thảo luận, thực hành, tự học) 2 tiết
   
3. 
   Mục đích, yêu cầu:
   

Nắm được khái niệm đoạn găng, cơ chế hoạt động của hiệu báo Semaphore và Monitor.

Hiểu được những giải pháp điều độ tiến trình qua đoan găng, đồng nhất hóa những tiến trình .

4. 
   Nội dung:
   

1. 
   Nội dung chi tiết: (công thức, định lý, hình vẽ)
   

II.4.1 Đoạn găng

Mỗi một tiến trình có một đoạn mã, gọi là vùng hạn chế (Critial section), trong đó tiến trình sẽ có thể thay đổi các biến dữ liệu chung. Bài toán đặt ra là khi một tiến trình thực hiện trong đoạn hạn chế này, thì không có tiến trình nào khác thực hiện trong đoạn mã hạn chế của nó.

HĐH phải bảo vệ là tại một thời gian chỉ có một tiến trìnhnằm trong đoạn găng, nếu có nhiều tiến trình cùng muốn vào ( thực hiên ) đoạn găng thì những tiến trình khác phải chờ tiến trình thực tại thoát khỏi đọan găng .
Một giải pháp cho bải toán Critical section phải thoả mãn những điều kiện kèm theo dưới đây :

1. 
   Loại trừ lẫn nhau (Mutual exclusion): Nếu tiến trình Pi đang thực hiện trong đoạn hạn chế, thì không có tiến trình nào có thể thực hiện trong đoạn hạn chế.
   
2. 
   Tiến triển (progress): Nếu không có tiến trình nào đang thực hiện trong đoạn hạn chế và có một số tiến trình đang muốn thực hiện đoạn hạn chế, thì chỉ có những tiến trình nào mà hiện tại không thực hiện phần mã còn lại có thể được xem xét.
   
3. 
   Giới hạn chờ đợi (bounded waiting): tồn tại một giới hạn về thời gian các tiến trình khác được cho phép thực hiện đoạn hạn ché của chúng sau khi một tiến trình yêu cầu được thực hiện đoạn hạn chế và trước khi được chấp nhận.
   

II. 4.2 Các giải pháp điều độ tiến trinh qua đoạn găng

• 
  Giải pháp 2 tiến trình (Two-processes Solution)
  
• 
  Giải pháp phần cứng (Synchronization Hardware)
  
• 
  Giải pháp dùng biến khóa
  
• 
  Giải pháp được hỗ trợ bởi HĐH và ngôn ngữ lập trình bao gồm:
  

1. 
   Giải thuật Bakery
   
2. 
   Giải pháp dùng đèn báo Semaphore
   
3. 
   Giải pháp dùng monitor
   
4. 
   Giải pháp trao đổi thông điệp
   

2. 
   Nội dung thảo luận
   
3. 
   Nội dung tự học
   
4. 
   Bài tập (bắt buộc, mở rộng)
   

5. 
   Tài liệu tham khảo (sách, báo – chi tiết đến chương, mục, trang)
   

• 
  Tài liệu 1, chương 7 từ trang 189 đến trang 241.
  

6. 
   Câu hỏi ôn tập
   

Каталог:
FileMonHoc -> Mẫu Đề cương môn học
FileMonHoc -> Môn họC: XỬ LÝ song song
FileMonHoc -> Học viện kỹ thuật quân sự
FileMonHoc -> Mẫu Đề cương môn học
FileMonHoc -> Khoa công nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam
FileMonHoc -> Khoa: CÔng nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam
FileMonHoc -> Khoa công nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam
files -> FileMonHoc
tải về 0.64 Mb.
Chia sẻ với bạn bè của bạn: