+>Hệ điều hành: là một chương trình hay một hệ chương trình hoạt động giữa người sử dụng (user) 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 để người sử dụng có thể thi hành các chương trình. Nó làm cho máy tính dể sử dụng hơn, thuận lợi hơn và hiệu quả hơn.

+> Địa chỉ Logic: là địa chỉ ảo, là tất cả các địa chỉ do bộ xử lý tạo ra.

+> Địa chỉ vật lý: là địa chỉ thực tế mà quá trình quản lý bộ nhớ nhìn thấy và thao tác.

+> Địa chỉ ảo và địa chỉ vật lý là như nhau trong phương thức kết buộc địa chỉ vào thời điểm biên dịch cũng như thời điểm nạp. Tuy nhiên có sự khác biệt giữa địa chỉ ảo và địa chỉ vật lý trong phương thức kết buộc vào xử lý.

+>Không gian địa chỉ: là tập hợp tất cả các địa chỉ ảo phát sinh bởi một chương trình.

+>Không gian vật lý: là tập hợp tất cả các địa chỉ vật lý tương ứng với các địa chỉ ảo.

+> Phân mảnh nội vi( internal fragmentation): là hiện tượng kích thước của tiến trình không vừa đúng bằng kích thước phân vùng chứa nó, phần bộ nhớ không sử dụng đến trong phân vùng sẽ bị lãng phí

+> Phân mảnh ngoại vi( external fragmentation ): là hiện tượng các tiến trình lần lượt vào và ra khỏi hệ thống, dần dần xuất hiện các khe hở giữa các tiến trình. Đây là các khe hở được tạo ra kích thước của tiến trình mới được nạp nhỏ hơn kích thước vùng nhớ mới được giải phóng bởi một tiến trình kết thúc và ra khỏi hệ thống.

+> Phân vùng cố định: Bộ nhớ được chia thành n phân vùng có kích thước cố định( các phân vùng khác nhau có thể có kích thước khác hay bằng nhau ) . Các tiến trình có nhu cầu bộ nhớ sẽ được lưu trữ trong hàng đợi.

+> Phân vùng động: Khi một tiến trình được đưa vào hệ thống, cấp phát cho tiến trình một vùng nhớ có kích thước vừa đúng với kích thước của tiến trình. Khi một tiến trình kết thúc, vùng nhớ đã cấp cho nó sẽ được giải phóng và có thể được cấp phát cho một tiến trình khác.

I. Điều phối

+> Tiến trình(Process): là một chương trình đang xử lý, sở hữu một con trỏ lệnh, tập các thanh ghi và các biến.

- Đồng bộ hóa các tiến trình: là bắt các tiến trình phải thực hiện theo một trình tự nào đó

(Mục tiêu điều phối)

Bộ điều phối không cung cấp cơ chế, mà đưa ra các quyết định. Các hệ điều hành xây dựng nhiều chiến lược khác nhau để thực hiện việc điều phối, nhưng tựu chung cần đạt được các mục tiêu sau :

a) Sự công bằng ( Fairness) : Các tiến trình chia sẻ CPU một cách công bằng, không có tiến trình nào phải chờ đợi vô hạn để được cấp phát CPU

b) Tính hiệu qủa (Efficiency) : Hệ thống phải tận dụng được CPU 100% thời gian.

c) Thời gian đáp ứng hợp lý (Response time) : Cực tiểu hoá thời gian hồi đáp cho các tương tác của người sử dụng

d) Thời gian lưu lại trong hệ thống ( Turnaround Time) : Cực tiểu hóa thời gian hoàn tất các tác vụ xử lý theo lô.

e) Thông lượng tối đa (Throughput ) : Cực đại hóa số công việc được xử lý trong một đơn vị thời gian.

Tuy nhiên thường không thể thỏa mãn tất cả các mục tiêu kể trên vì bản thân chúng có sự mâu thuẫn với nhau mà chỉ có thể dung hòa chúng ở mức độ nào đó.

- Đặc điểm của tiến trình:

a) Tính hướng xuất / nhập của tiến trình

b) Tính hướng xử lý của tiến trình

c) Tiến trình tương tác hay xử lý theo lô

d) Độ ưu tiên của tiến trình

e) Thời gian đã sử dụng CPU của tiến trình

f) Thời gian còn lại tiến trình cần để hoàn tất

+> Tiểu trình(Thred): là một cơ chế xử lý cho phép có nhiều dòng xử lý trong cùng một tiến trình.

+>Điều phối độc quyền: Cho phép một tiến trình khi nhận được CPU sẽ có quyền độc chiếm CPU đến khi hoàn tất xử lý hoặc tự nguyện giải phóng CPU.

+>Điều phối không độc quyền: Cho phép tạm dừng hoạt động của một tiến trình đang sẵn sàng xử lý. Khi một tiến trình nhận được CPU, nó vẫn được sử dụng CPU đến khi hoàn tất hoặc tự nguyện giải phóng CPU, nhưng một tiến trình khác có độ ưu tiên có thể dành quyền sử dụng CPU của tiến trình ban đầu. Như vậy, tiến trình có thể bị tạm dừng hoạt động bất cứ lúc nào mà không được báo trước, để tiến trình khác xử lý.

+> Độ ưu tiên:

- Độ ưu tiên tĩnh: là độ ưu tiên được gán sẵn cho tiến trình, và không thay đổi bất kể sự biến động của môi trường.

- Độ ưu tiên động: là độ ưu tiên thay đổi theo thời gian và môi trường xử lýcủa tiến trình.

+> Cấp độ điều phối:

- Điều phối tác vụ: Quyết định lựa chọn tác vụ nào được đưa vào hệ thống, và nạp những tiến trình của tác vụ đó vào bộ nhớ chính để thực hiện. Chức năng điều phối tác vụ quyết định mức độ đa chương của hệ thống( số lượng tiến trình trong bộ nhớ chính.)

- Điều phối tiến trình: Chọn một tiến trình ở trạng thái sẵn sàng( đã được nạp vào bộ nhớ chính và có đủ tài nguyên để hoạt động) và cấp phát CPU cho tiến trình đó thực hiện.

+> Ưu, khuyết của chiến lược điều phối

- 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à 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 nhập/xuất.

Nhận xét : 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ác tiến trình trong danh sách sẵn sàng. Có thể xảy ra hiện tượng tích lũy thời gian chờ, khi các tất cả các tiến trình (có thể có yêu cầu thời gian ngắn) phải chờ đợi một tiến trình có yêu cầu 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.

- Chiến lược Phân phối 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 gọi là quantum. Đây là một giải thuật điều phối không độc quyền : khi một tiến trình sử dụng CPU đến hết thời gian quantum dành cho nó, hệ điều hành thu hồi CPU và cấp cho tiến trình kế tiếp trong danh sách. Nếu tiến trình bị khóa 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 trình tiêu thụ hết thời gian CPU 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 để đợi được cấp CPU trong lượt kế tiếp.

Nhận xét : Vấn đề đáng quan tâm đối với giải thuật RR là độ dài của quantum. Nếu thời lượng 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 CPU kém hiệu qủa. Nhưng nếu 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.

- Điều phối với Độ ưu tiên:

Nguyên tắc : Mỗi tiến trình được gán cho một độ ưu tiên tương ứng, tiến trình có độ ưu tiên cao nhất sẽ được chọn để cấp phát CPU đầu tiên. Độ ưu tiên có thể được định nghĩa nội tại hay nhờ vào các yếu tố bên ngoài. Độ ưu tiên nội tại sử dụng các đại lượng có thể đo lường để tính toán độ ưu tiên của tiến trình,

Nhận xét: Tình trạng 'đói CPU' (starvation) là một vấn đề chính yếu của các giải thuật sử dụng độ ưu tiên. Các giải thuật này có thể để các tiến trình có độ ưu tiên thấp chờ đọi CPU vô hạn ! Để ngăn cản các tiến trình có độ ưu tiên cao chiếm dụng CPU vô thời hạn, bộ điều phối sẽ giảm dần độ ưu tiên của các tiến trình này sau mỗi ngắt đồng hồ. Nếu độ ưu tiên của tiến trình này giảm xuống thấp hơn tiến trình có độ ưu tiên cao thứ nhì, sẽ xảy ra sự chuyển đổi quyền sử dụng CPU.Quá trình này gọi là sự 'lão hóa' (aging) tiến trình.

- Chiến lược Công việc ngắn nhất:

Nguyên tắc : Đây là một trường hợp đặc biệt của giải thuật điều phối với độ ưu tiên. Trong giải thuật này, độ ưu tiên p được gán cho mỗi tiến trình là nghịch đảo của thời gian xử lý t mà tiến trình yêu cầu : p = 1/t. Khi CPU được tự do, 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ó thể độc quyền hay không độc quyền. Sự chọn lựa xảy ra khi có một tiến trình mới được đư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 (CPU-burst) 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 hoạt độ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ý.

Nhận xét: Giải thuậ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 yêu cầu xử lý còn lại của tiến trình ? Chỉ có thể dự đoán giá trị này theo cách tiếp cận sau : gọi tn là độ dài của 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 giá trị dự đoán sẽ gần giống với các giá trị trước đó, có thể sử dụng công thức:

t n+1 = a tn + (1-a )t n

Trong công thức này,tn chứa đựng thông tin gần nhất ; t n chứa đựng các thông tin quá khứ được tích lũy. Tham số a ( 0 £ a £ 1) kiểm soát trọng số của hiện tại gần hay quá khứ ảnh hưởng đến công thức dự đón.

- Chiến lược điều phối Nhiều mức độ ưu tiên:

Nguyên tắc : Ý tưởng chính của giải thuật là phân lớp các tiến trình tùy theo độ ưu tiên của chúng để có cách thức điều phối thích hợp cho từng nhóm. Danh sách sẵn sàng được phân tách thành các danh sách riêng biệt theo cấp độ ưu tiên, mỗi danh sách bao gồm các tiến trình có cùng độ ưu tiên và được áp dụng một giải thuật điều phối thích hợp để điều phối. Ngoài ra, còn có một giải thuật điều phối giữa các nhóm, thường giải thuật này là giải thuật không độc quyền và sử dụng độ ưu tiên cố định.Một tiến trình thuộc về danh sách ở cấp ưu tiên i sẽ chỉ được cấp phát CPU khi các danh sách ở cấp ưu tiên lớn hơn i đã trống.

Nhận xét : Thông thường, một tiến trình sẽ được gán vĩnh viễn với một danh sách ở cấp ưu tiên i khi nó được đưa vào hệ thống. Các tiến trình không di chuyển giữa các danh sách. Cách tổ chức này sẽ làm giảm chi phí điều phối, nhưng lại thiếu linh động và có thể dẫn đến tình trạng 'đói CPU' cho các tiến trình thuộc về những danh sách có độ ưu tiên thấp. Do vậy có thể xây dựng giải thuật điều phối nhiều cấp ưu tiên và xoay vòng. Giải thuật này sẽ chuyển dần một tiến trình từ danh sách có độ ưu tiên cao xuống danh sách có độ ưu tiên thấp hơn sau mỗi lần sử dụng CPU. Cũng vậy, một tiến trình chờ quá lâu trong các danh sách có độ ưu tiên thấp cũng có thể được chuyển dần lên các danh sách có độ ưu tiên cao hơn.

+> Cơ chế trao đôi thông tin, tình huống sử dụng

- Tín hiệu(Signal): Tín hiệu là một cơ chế phần mềm tương tự như các ngắt cứng tác động đến các tiến trình. Một tín hiệu được sử dụng để thông báo cho tiến trình về một sự kiện nào đó xảy ra. Có nhiều tín hiệu được định nghĩa, mỗi một tín hiệu có một ý nghĩa tương ứng với một sự kiện đặc trưng.

- Pipe: Một pipe là một kênh liên lạc trực tiếp giữa hai tiến trình : dữ liệu xuất của tiến trình này được chuyển đến làm dữ liệu nhập cho tiến trình kia dưới dạng một dòng các byte.

Khi một pipe được thiết lập giữa hai tiến trình, một trong chúng sẽ ghi dữ liệu vào pipe và tiến trình kia sẽ đọc dữ liệu từ pipe. Thứ tự dữ liệu truyền qua pipe được bảo toàn theo nguyên tắc FIFO. Một pipe có kích thước giới hạn (thường là 4096 ký tự)

- Vùng nhớ chia sẻ: Cách tiếp cận của cơ chế này là cho nhiều tiến trình cùng truy xuất đến một vùng nhớ chung gọi là vùng nhớ chia sẻ (shared memory).Không có bất kỳ hành vi truyền dữ liệu nào cần phải thực hiện ở đây, dữ liệu chỉ đơn giản được đặt vào một vùng nhớ mà nhiều tiến trình có thể cùng truy cập được.

Với phương thức này, các tiến trình chia sẻ một vùng nhớ vật lý thông qua trung gian không gian địa chỉ của chúng. Một vùng nhớ chia sẻ tồn tại độc lập với các tiến trình, và khi một tiến trình muốn truy xuất đến vùng nhớ này, tiến trình phải kết gắn vùng nhớ chung đó vào không gian địa chỉ riêng của từng tiến trình, và thao tác trên đó như một vùng nhớ riêng của mình.

- Trao đổi thông điệp( Message):

- Sockets: Một socket là một thiết bị truyền thông hai chiều tương tự như tập tin, chúng ta có thể đọc hay ghi lên nó, tuy nhiên mỗi socket là một thành phần trong một mối nối nào đó giữa các máy trên mạng máy tính và các thao tác đọc/ghi chính là sự trao đổi dữ liệu giữa các ứng dụng trên nhiều máy khác nhau.

Sử dụng socket có thể mô phỏng hai phương thức liên lạc trong thực tế : liên lạc thư tín (socket đóng vai trò bưu cục) và liên lạc điện thoại (socket đóng vai trò tổng đài) .

+> Đồng bộ hóa tiến trình:

- Miền Găng( Critical Section): là đoạn chương trình trong đó có khả năng xảy ra các mâu thuẫn truy xuất trên tài nguyên chung.

*>Thỏa mãn:

. Không có hai tiến trình cùng ở trong miền găng cùng lúc.

. Không có giả thiết nào đặt ra cho sự liên hệ về tốc độ của các tiến trình, cũng như về số lượng bộ xử lý trong hệ thống.

. Một tiến trình tạm dùng bên ngoài miền Găng không được phép ngăn cản các tiến trình khác vào miền Găng.

. Không có tiến trình nào phải chờ vô hạn để được vào miền Găng.

- Giải pháp:

. Busy Waiting

Các giải pháp phần mềm

1. Sử dụng các biến cờ hiệu: các tiến trình chia sẻ một biến chung đóng vai trò « chốt cửa » (lock) , biến này được khởi động là 0. Một tiến trình muốn vào miền găng trước tiên phải kiểm tra giá trị của biến lock. Nếu lock = 0, tiến trình đặt lại giá trị cho lock = 1 và đi vào miền găng. Nếu lock đang nhận giá trị 1, tiến trình phải chờ bên ngoài miền găng cho đến khi lock có giá trị 0. Như vậy giá trị 0 của lock mang ý nghĩa là không có tiến trình nào đang ở trong miền găng, và lock=1 khi có một tiến trình đang ở trong miền găng.

2. Sử dụng viêc kiểm tra luân phiên: Đây là một giải pháp đề nghị cho hai tiến trình. Hai tiến trình này sử dụng chung biến turn (phản ánh phiên tiến trình nào được vào miền găng), được khởi động với giá trị 0. Nếu turn = 0, tiến trình A được vào miền găng. Nếu turn = 1, tiến trình A đi vào một vòng lặp chờ đến khi turn nhận giá trị 0. Khi tiến trình A rời khỏi miền găng, nó đặt giá trị turn về 1 để cho phép tiến trình B đi vào miền găng.

3. Giải pháp Peterson:

Các giải pháp phần cứng

1. Cấm ngắt: cho phép tiến trình cấm tất cả các ngắt trước khi vào miền găng, và phục hồi ngắt khi ra khỏi miền găng. Khi đó, ngắt đồng hồ cũng không xảy ra, do vậy hệ thống không thể tạm dừng hoạt động của tiến trình đang xử lý để cấp phát CPU cho tiến trình khác, nhờ đó tiến trình hiện hành yên tâm thao tác trên miền găng mà không sợ bị tiến trình nào khác tranh chấp.

2. Chỉ thị TSL( Test and Set): đây là một giải pháp đòi hỏi sự trợ giúp của cơ chế phần cứng. Nhiều máy tính cung cấp một chỉ thị đặc biệt cho phép kiểm tra và cập nhật nội dung một vùng nhớ trong một thao tác không thể phân chia, gọi là chỉ thị Test-and-Set Lock

. Sleep and Wakeup

Semaphore:

. Ưu điểm: Dùng Semaphore để giải quyết các vấn đề đồng bộ khác nhau. Giải quyết vấn đề truy xuất độc quyền hay tổ chức phối hợp giữa các tiến trình, cho phép đảm bảo nhiều tiến trình cùng truy xuất đến miền găng mà không có sự mâu thuẫn truy xuất.

. Nhược điểm: Đòi hỏi có sự chờ đợi bận, P có thể bị khoá vĩnh viễn nếu đặt Down và Up sai vị trí

Monitor

. Ưu điểm: Bảo đảm độc quyền truy xuất tự động, sử dụng biến điều kiện để thực hiện hò hẹn

. Nhược điểm: Nguy cơ thực hiện đồng bộ hoá sai giảm rất nhiều.

Message

. Ưu điểm: Mô hình đơn giản

. Nhược điểm: Không hữu hạn trong các hệ thống phân tán, khi mỗi bộ vi xử lý sở hữu 1 bộ nhớ riêng biệt và liên lạc thông tin qua mạng.

II. Tắc nghẽn

+> Deadlock( Tắc nghẽn): là một tình trạng của hệ thống, trong đó các tiền trình chờ đợi nhau vô hạn.

- Các yếu tố dẫn đến Deadlock:

. Các tài nguyên không thể chia sẻ (như bộ nhớ).

. Các tiến trình chiếm giữ tài nguyên và yêu cầu thêm tài nguyên.

. Chỉ đến khi kết thúc, tiến trình mới hoàn trả tài nguyên.

. Yêu cầu tài nguyên của các tiến trình tạo thành một chu trình.

- Các giải pháp:

. Phòng tránh tắc nghẽn: Tuân thủ một vài nghi thức bảo đảm hệ thống không bao giờ lâm vào tình trạng tắc nghẽn.

. Phát hiện tác nghẽn: Khi có tắc nghẽn xẩy ra, phát hiện các tiến trình liên quan và tìm cách phục hồi.

. Bỏ qua tắc nghẽn: Xem như hệ thống không bao giờ lâm vào tình trạng tắc nghẽn.

III. Quản lý bộ nhớ

Cách tổ chức bộ nhớ chính:

+> Cấp phát liên tục: Có thể cấp phát các vùng nhớ liên tục cho các tiến trình trong những phân vùng có kích thước cố định hay biến động. Điểm yếu của cách tiếp cận này là kích thước của chương trình có thể được xử lý bị giới hạn bởi các kích thước của khối nhớ liên tục có thể sử dụng.

+> Cấp phát không liên tục: Có thể cấp phát các vùng nhớ không liên tục cho một tiến trình. Hai kỹ thuật thường đước áp dụng là phân trang và phân đoạn

+>Swapping: Sử dụng thêm bộ nhớ phụ để lưu trữ tạm các tiến trình đang bị khóa, nhờ vậy có thể tăng mức tối đa chương của hệ thống với cấu hình máy có dung lượng bộ nhớ chính thấp.

+> Bộ nhớ ảo: là một kỹ thuật cho phép xử lý một tiến trình không được nạp toàn bộ vào bộ nhớ vật lý. Bộ nhớ ảo mô hình hóa bộ nhớ như một bảng lưu trữ rất lớn và đồng nhất, tách biệt hẳn khái niệm không gian địa chỉ và không gian vật lý.

+> Các phân đoạn: là những phần bộ nhớ kích thước khác nhau và có liên hệ logic với nhau. Mỗi phân đoạn có một tên gọi và một độ dài

+>Trang: Không gian địa chỉ cũng được chia thành các khối có cùng kích thước với khung trang

+> Khung trang: Phân bộ nhớ vật lý thành các khối có kích thước cố định và bằng nhau.

+> Lỗi trang(Page fault)

HĐH xử lý lỗi trang :

B1: Kiểm tra truy xuất đến bộ nhớ là hợp lệ hay bất hợp lệ

B2: Nếu truy xuất bất hợp lệ: kết thúc tiến trình

Ngược lại đến B3

B3: Tìm vị trí chứa trang muốn truy xuất trên đĩa

B4: Tìm một khung trang trống trong bộ nhớ chính:

. Nếu tìm thấy: đến B5.

. Nếu không còn khung trang trống, chọn khung trang "nạn nhân" và chuyển trang "nạn nhân" ra bộ nhớ phụ, cập nhập bảng trang tương ứng rồi đến B5.

B5: Chuyển trang muốn truy xuất từ bộ nhớ phụ vào bộ nhớ chính: nạp trang cần truy xuất vào khung trang trống đã chọn; cập nhập nội dung bảng trang, bảng khung trang tương ứng.

B6: Tái kích hoạt tiến trình người sử dụng.