hệ điều hành
CHÚ TRỌNG ÔN THI
1. Phân tích các hình thái giao tiếp của hệđiều hành
a) Hình tháidòng lệnh
Người sử dụng giao tiếp với HĐH qua các dòng lệnh, mỗi lệnh có các tham số tương ứng.
ưu điểm
Dễ xây dựng và giảm công sức cho người xây dựng hệ thống.
Người sử dụng có thể đưa tham số của lệnh một các chính xác theo mong muốn.
1.1.1.1.1.1.1.1 Nhược điểm
1.1.1.1.1.1.1.1.1Tốc độđưa lệnh vào chậm, người sử dụng phải nhớ các tham số.
1.1.1.1.1.1.1.1.2Đối với các thao tác viên không có kinh nghiệm, thì hình thái giao tiếp. này gây cản trởđến hiệu quả làm việc.
Hình thái giao tiếp này bị cản trở bởi hàng rào ngôn ngữ.
b) Hình thái thực đơn
Người sử dụng giao tiếp với HĐH thông các các thực đơn, các thực đơn thường có dạng trải xuống (Popup). Mỗi một thực đơn con tương ứng với một chức năng. Các tham số có thểđược đưa vào thông qua giao tiếp với người sử dụng.
1.1.1.1.1.1.1.2 ưu điểm
1.1.1.1.1.1.1.2.1 Hình thái này không yêu cầu nhớ lệnh
1.1.1.1.1.1.1.2.2 Người sử dụng có thể truy nhập vào thực đơn qua bàn phím hoặc qua chuột.
1.1.1.1.1.1.1.3 Nhược điểm
1.1.1.1.1.1.1.3.1 Hình thái giao tiếp này bị cản trở bởi hàng rào ngôn ngữ.
Đôi khi các từ trên thực đơn không nêu bật được chức năng của nó
c) Hình thái cửa sổ – biểu tượng
Người sử dụng giao tiếp với HĐH thông các các thanh công cụ và các biểu tượng. Mỗi một biểu tượng tương ứng với một chức năng. Các tham số có thểđược đưa vào thông qua giao tiếp với người sử dụng.
1.1.1.1.1.1.1.4 ưu điểm
1.1.1.1.1.1.1.4.1 Hình thái này không yêu cầu nhớ lệnh
1.1.1.1.1.1.1.4.2 Người sử dụng không bị hàng rào ngôn ngữ gây cản trở.
1.1.1.1.1.1.1.5 Nhược điểm
1.1.1.1.1.1.1.5.1 Có thể có rất nhiều biểu tượng do đó gây sự nhập nhằng về chức năng.
1.1.1.1.1.1.1.5.2 Không thuận lợi khi thao tác bằng bàn phím
d) Hình thái kết hợp
Hệđiều hành thường kết hợp nhiều hình thái giao tiếp để tạo ra tính thân thiện với người sử dụng. Ví dụ: việc kết hợp thực đơn với các biểu tượng, hoặc kết hợp giữa các biểu tượng và các từ gợi ý (tooltip).
Hình thái giao tiếp kết hợp này khắc phục được các nhược điểm của các hình thái giao tiếp đơn lẻ.
Trình bày mục tiêu của việc điều phối sự hoạt động của các tiến trình và các đặc điểm quan trọng của tiến trình để điều phối
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 nhiều nhất (100% là tối ưu) 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ô.
1.1.1.1.1.1.1.5.3 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.
* Một số đặc điểm của tiến trình cần được quan tâm như những tiêu chuẩn điều phối :
a) Tính hướng xuất / nhập của tiến trình ( I/O-boundedness):
Khi một tiến trình nhận được CPU, chủ yếu nó chỉ sử dụng CPU đến khi phát sinh một yêu cầu nhập xuất ? Hoạt động của các tiến trình như thế thường bao gồm nhiều lượt sử dụng CPU, mỗi lượt trong một thời gian khá ngắn.
b) Tính hướng xử lý của tiến trình ( CPU-boundedness):
Khi một tiến trình nhận được CPU, nó có khuynh hướng sử dụng CPU đến khi hết thời gian dành cho nó ? Hoạt động của các tiến trình như thế thường bao gồm một số ít lượt sử dụng CPU , nhưng mỗi lượt trong một thời gian đủ dài.
c) Tiến trình tương tác hay xử lý theo lô
d) Độ ưu tiên của tiến trình :
Các tiến trình có thể được phân cấp theo một số tiêu chuẩn đánh giá nào đó, một cách hợp lý, các tiến trình quan trọng hơn (có độ ưu tiên cao hơn) cần được ưu tiên hơn.
e) Thời gian còn lại tiến trình cần để hoàn tất
f) Thời gian đã sử dụng CPU của tiến trình :
Một số quan điểm ưu tiên chọn những tiến trình đã sử dụng CPU nhiều thời gian nhất vì hy vọng chúng sẽ cần ít thời gian nhất để hoàn tất và rời khỏi hệ thống . Tuy nhiên cũng có quan điểm cho rằng các tiến trình nhận được CPU trong ít thời gian là những tiến trình đã phải chờ lâu nhất, do vậy ưu tiên chọn chúng.
Trình bày nguyên tắc, lấy ví dụ minh họa về các chiến lược điều phối FIFO, xoay vòng (Round Robin), độ ưu tiên.
1. 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.
Ví dụ :
Tiến trình Thời điểm vào RL Thời gian xử lý
P1 0 24
P2 1 3
P3 2 3
Thứ tự cấp phát CPU cho các tiến trình là :
P1 P2 P3
0 ‘24 27 30
thời gian chờ đợi được xử lý là 0 đối với P1, (24 -1) với P2 và (24+3-2) với P3. Thời gian chờ trung bình là ( 0+23+25)/3 = 16 milisecondes.
2. 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.
Hình 2.13 Điều phối Round Robin
Ví dụ :
Tiến trình Thời điểm vào RL Thời gian xử lý
P1 0 24
P2 1 3
P3 2 3
Nếu sử dụng quantum là 4 milisecondes, thứ tự cấp phát CPU sẽ là :
P1 P2 P3 P1 P1 P1 P1 P1
0 ‘4 7 10 14 18 22 26 30
Thời gian chờ đợi trung bình sẽ là (0+6+3+5)/3 = 4.66 milisecondes.
Nếu có n tiến trìh trong danh sách sẵn sàng và sử dụng quantum q, thì mỗi tiến trình sẽ được cấp phát CPU 1/n trong từng khoảng thời gian q. Mỗi tiến trình sẽ không phải đợi quá (n-1)q đơn vị thời gian trước khi nhận được CPU cho lượt kế tiếp.
3. Đ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, ví dụ các giới hạn thời gian, nhu cầu bộ nhớ…Độ ưu tiên cũng có thể được gán từ bên ngoài dựa vào các tiêu chuẩn do hệ điều hành như tầm quan trọng của tiến trình, loại người sử dụng sỡ hữu tiến trình…
Giải thuật điều phối với độ ưu tiên có thể theo nguyên tắc độc quyền hay không độc quyền.
Ví dụ : (độ ưu tiên 1 > độ ưu tiên 2> độ ưu tiên 3)
Tiến trình Thời điểm vào RL Độ ưu tiên Thời gian xử lý
P1 0 3 24
P2 1 1 3
P3 2 2 3
Sử dụng thuật giải độc quyền, thứ tự cấp phát CPU như sau :
P1 P2 P3
0 ‘24 27 30
Sử dụng thuật giải không độc quyền, thứ tự cấp phát CPU như sau :
P1 P2 P3 P1
0 ‘1 4 7 30
4. Trình bày các thành phần trong cấu trúc của khối điều khiển tiến trình
Hệ điều hành quản lý các tiến trình trong hệ thống thông qua khối quản lý tiến trình (Process Control Block -PCB). PCB là một vùng nhớ lưu trữ các thông tin mô tả cho tiến trình, với các thành phần chủ yếu bao gồm :
Định danh của tiến trình(1) : giúp phân biệt các tiến trình
Trạng thái tiến trình (2): xác định hoạt động hiện hành của tiến trình.
Ngữ cảnh của tiến trình (3): mô tả các tài nguyên tiến trình đang trong quá trình, hoặc để phục vụ cho hoạt động hiện tại, hoặc để làm cơ sở phục hồi hoạt động cho tiến trình, bao gồm các thông tin về:
1.1.1.1.1.1.1.6 Trạng thái CPU: bao gồm nội dung các thanh ghi, quan trọng nhất là con trỏ lệnh IP lưu trữ địa chỉ câu lệnh kế tiếp tiến trình sẽ xử lý. Các thông tin này cần được lưu trữ khi xảy ra một ngắt, nhằm có thể cho phép phục hồi hoạt động của tiến trình đúng như trước khi bị ngắt.
Số hiệu bộ xử lý: dùng cho máy có cấu hình nhiều CPU, xác định số hiệu CPU mà tiến trình đang sử dụng.
Bộ nhớ chính: danh sách các khối nhớ được cấp cho tiến trình.
Tài nguyên sử dụng: danh sách các tài nguyên hệ thống mà tiến trình đang sử dụng.
Tài nguyên tạo lập: danh sách các tài nguyên được tiến trình tạo lập.
Thông tin giao tiếp: phản ánh các thông tin về quan hệ của tiến trình với các tiến trình khác trong hệ thống :
+ Tiến trình cha: tiến trình tạo lập tiến trình này .
+ Tiến trình con: các tiến trình do tiến trình này tạo lập .
Độ ưu tiên : giúp bộ điều phối có thông tin để lựa chọn tiến trình được cấp CPU.
Thông tin thống kê (4): đây là những thông tin thống kê về hoạt động của tiến trình, như thời gian đã sử dụng CPU,thời gian chờ. Các thông tin này có thể có ích cho công việc đánh giá tình hình hệ thống và dự đoán các tình huống tương lai.
5. Phân tích các nguyên lý xây dựng hệđiều hành
a) Module
1.1.1.1.1.1.1.7 HĐH phải được xây dựng từ các module độc lập nhưng có khả năng liên kết thành một hệ thống có thể thu gọn hoặc mở rộng tuỳý.
1.1.1.1.1.1.1.8 Các module đồng cấp quan hệ với nhau thông qua dữ liệu vào và ra.
1.1.1.1.1.1.1.9 Tồn tại quan hệ phân cấp khi các liên kết các module tạo thành những module có khả năng giải quyết các vấn đề phức tạp hơn.
b) Phủ chức năng
1.1.1.1.1.1.1.10 Một công việc có thể thực hiện bằng nhiều cách khác nhau.
1.1.1.1.1.1.1.11 Ví dụ Muốn in tệp f1.txt ta có thể làm bằng nhiều cách
1.1.1.1.1.1.1.11.1 C:\> copy f1.txt prn
1.1.1.1.1.1.1.11.2 C:\> print f1.txt
c) Marco-processor
1.1.1.1.1.1.1.12 Khi có một công việc cụ thể, hệ thống sẽ xây dựng các yêu cầu, liệt kê các bước phải thực hiện từđó xây dựng chương trình tương ứng, sau đó thực hiện chương trình nói trên.
Ví dụ: Trong MSDOS ta có các tệp config.sys và autoexec.bat
d) Nguyên lý bảng tham sốđiều khiển
1.1.1.1.1.1.1.13 Hệ thống không tham chiếu trực tiếp đến thiết bị, đối tượng vật lý mà chỉ làm việc với bảng tham số xác định đặc trưng của thiết bịđó.
1.1.1.1.1.1.1.14 Bảng tham sốđược hệ thống xây dựng ngay trong quá trình làm việc
1.1.1.1.1.1.1.15 Ví dụ
Bảng tham số của một máy tính PC được lưu trong CMOS 64byte
1.1.1.1.1.1.1.16 Lợi ích của việc sử dụng bảng tham số
1.1.1.1.1.1.1.16.1 Truy nhập thực hiện công việc nhanh với CPU
Không phụ thuộc vào các thiết bị vật lý cụ thể
e) Nguyên lý giá trị chuẩn
HĐH chuẩn bị bảng giá trị của các tham số gọi là bảng giá trị chuẩn. Trong trường hợp một module hoặc một câu lệnh có nhiều tham số và người sử dụng không nêu hết các giá trị tham số thì HĐH phải lấy giá trị trong bảng giá trị chuẩn bổ xung vào các tham số thiếu.
f) Nguyên lý bảo vệ nhiều mức
1.1.1.1.1.1.1.17 Chương trình và dữ liệu phải được bảo vệ nhiều mức bằng nhiều khoá.
1.1.1.1.1.1.1.18 Ví dụ trong Linux
1.1.1.1.1.1.1.18.1 Mức 1: Người sử dụng phải có tài khoản mới được sử dụng máy tính.
Mức 2: Chỉ những người sử dụng thuộc nhóm A mới được truy nhập và tệp chung của nhóm A.
6. Trình bày các loại thông tin trong quan hệ giữa các tiến trình
Tín hiệu (Signal): 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.
Mỗi tiến trình sỡ hữu một bảng biễu diễn các tín hiệu khác nhau. Với mỗi tín hiệu sẽ có tương ứng một trình xử lý tín hiệu (signal handler) qui định các xử lý của tiến trình khi nhận được tín hiệu tương ứng.
Quan hệ bằng tín hiệu mang tính chất không đồng bộ, nghĩa là một tiến trình nhận tín hiệu không thể xác định trước thời điểm nhận tính hiệu. Hơn nữa các tiến trình không thể kiểm tra được sự kiện tương ứng với tín hiệu có thật sự xảy ra ? Cuối cùng, các tiến trình chỉ có thể thông báo cho nhau về một biến cố nào đó, mà không trao đổi dữ liệu theo cơ chế này được.
2. Pipe
Một pipe là một kênh quan hệ 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ự)
Quan hệ bằng pipe là một cơ chế quan hệ một chiều (unidirectional), nghĩa là một tiến trình kết nối với một pipe chỉ có thể thực hiện một trong hai thao tác đọc hoặc ghi, nhưng không thể thực hiện cả hai. Một số hệ điều hành cho phép thiết lập hai pipe giữa một cặp tiến trình để tạo quan hệ hai chiều.
Trong những hệ thống đó, có nguy cơ xảy ra tình trạng tắc nghẽn (deadlock) : một pipe bị giới hạn về kích thước, do vậy nếu cả hai pipe nối kết hai tiến trình đều đầy(hoặc đều trống) và cả hai tiến trình đều muốn ghi (hay đọc) dữ liệu vào pipe(mỗi tiến trình ghi dữ liệu vào một pipe), chúng sẽ cùng bị khóa và chờ lẫn nhau mãi mãi ! Cơ chế này cho phép truyền dữ liệu với cách thức không cấu trúc.
3 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.
4 Trao đổi thông điệp (Message)
Hệ điều hành còn cung cấp một cơ chế quan hệ giữa các tiến trình không thông qua việc chia sẻ một tài nguyên chung , mà thông qua việc gởi thông điệp. Để hỗ trợ cơ chế quan hệ bằng thông điệp, hệ điều hành cung cấp các hàm IPC chuẩn (Interprocess communication), cơ bản là hai hàm:
Send(message) : gởi một thông điệp
Receive(message) : nhận một thông điệp
5 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 quan hệ trong thực tế : quan hệ thư tín (socket đóng vai trò bưu cục) và quan hệ điện thoại (socket đóng vai trò tổng đài) .
7. Nêu thành phần và kiến trúc của hệ điều hành
1.1.1.1.1.1.1.18.2 a) Thành phần của HĐH
1.1.1.1.1.1.1.18.3 - Ngôn ngữ làm việc và giao tiếp
1.1.1.1.1.1.1.18.4 Hệ điều hành phải có ít nhất 3 ngôn ngữ làm việc và giao tiếp phục vụ cho các đối tượng khác nhau.
1.1.1.1.1.1.1.18.5 Ngôn ngữ máy: Là ngôn ngữ thực hiện duy nhất của hệ thống vì vậy còn gọi là ngôn ngữ thực hiện. Mọi ngôn ngữ khác đều phải được ánh xạ sang ngôn ngữ này.
1.1.1.1.1.1.1.18.6 Ngôn ngữ vận hành: Là ngôn ngữ giúp thao tác viên giao tiếp với hệ thống. Ví dụ: ngôn ngữ MSDOS.
1.1.1.1.1.1.1.18.7 Ngôn ngữ thuật toán: Là ngôn ngữ chủ yếu giúp người sử dụng giao tiếp với hệ thống. Ví dụ ngôn ngữ Pascal, C, Visual Basic. Mỗi ngôn ngữ có thể có nhiều chương trình dịch đểánh xạ sang ngôn ngữ máy.
1.1.1.1.1.1.1.19 - Hệ thống quản lý tài nguyên: Supervisor
Đây là hệ thống phục vụ phân phối và quản lý tài nguyên.
b) Kiến trúc HĐH
Nhân là phần chính của HĐH làm các nhiệm vụ như quản lý bộ nhớ, quản lý tiến trình, phân chia tài nguyên…Nhân chỉ đảm nhiệm các chức năng cơ bản nhất, có kích thước nhỏ để giảm đến mức tối thiểu lỗi.
Dịch vụ là phần mở rộng các chức năng của HĐH cho phép khai thác tài nguyên hệ thống và hỗ trợ người dùng như quản lý tệp, quản lý thư mục, thư điện tử, truyền tệp.
Giao tiếp là phần tạo ra môi trường giao tiếp giữa người sử dụng và máy tính.
Các chương trình ứng dụng là các chương trình phục vụ người sử dụng được hệđiều hành hỗ trợ về môi trường để có thể hoạt động.
8. Trình bày kỹ thuật phân trang cơ bản trong các hệ điều hành hiện đại
Ý tưởng:
Phân bộ nhớ vật lý thành các khối (block) có kích thước cố định và bằng nhau, gọi là khung trang (page frame). 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, và được gọi là trang (page). Khi cần nạp một tiến trình để xử lý, các trang của tiến trình sẽ được nạp vào những khung trang còn trống. Một tiến trình kích thước N trang sẽ yêu cầu N khung trang tự do.
Cơ chế MMU(Memory Management Unit) trong kỹ thuật phân trang:
Cơ chế phần cứng hỗ trợ thực hiện chuyển đổi địa chỉ trong cơ chế phân trang là bảng trang (pages table). Mỗi phần tử trong bảng trang cho biết các địa chỉ bắt đầu của vị trí lưu trữ trang tương ứng trong bộ nhớ vật lý ( số hiệu khung trang trong bộ nhớ vật lý đang chứa trang ).
Chuyển đổi địa chỉ:
Mỗi địa chỉ phát sinh bởi CPU được chia thành hai phần:
số hiệu trang (p): sử dụng như chỉ mục đến phần tử tương ứng trong bảng trang.
địa chỉ tương đối trong trang (d): kết hợp với địa chỉ bắt đầu của trang để tạo ra địa chỉ vật lý mà trình quản lý bộ nhớ sử dụng.
Để dễ phân tích địa chỉ ảo thành số hiệu trang và địa chỉ tương đối, kích thước của một trang thông thường là một lũy thừa của 2
Cài đặt bảng trang:
Trong trường hợp đơn giản nhất, bảng trang một tập các thanh ghi được sử dụng để cài đặt bảng trang. Tuy nhiên việc sử dụng thanh ghi chỉ phù hợp với các bảng trang có kích thước nhỏ, nếu bảng trang có kích thước lớn, nó phải được lưu trữ trong bộ nhớ chính, và sử dụng một thanh ghi để lưu địa chỉ bắt đầu lưu trữ bảng trang (PTBR)
Tổ chức bảng trang:
Mỗi hệ điều hành có một phương pháp riêng để tổ chức lưu trữ bảng trang. Đa số các hệ điều hành cấp cho mỗi tiến trình một bảng trang. Tuy nhiên phương pháp này đòi hỏi một vùng nhớ qúa lớn! Để khắc phục vấn đề này các HĐH: Phân trang đa cấp và Bảng trang nghịch đảo
Sử dụng duy nhất một bảng trang nghịch đảo cho tất cả các tiến trình. Mỗi địa chỉ ảo khi đó là một bộ ba <idp, p, d >
Trong đó : idp là định danh của tiến trình, p là số hiệu trang và d là địa chỉ tương đối trong trang. Mỗi phần tử trong bảng trang nghịch đảo sẽ là một cặp <idp, p >.
Bảo vệ: Cơ chế bảo vệ trong hệ thống phân trang được thực hiện với các bit bảo vệ được gắn với mỗi khung trang. Ngoài ra, một bit phụ trội được thêm vào trong cấu trúc một phần tử của bảng trang : bit hợp lệ-bất hợp lệ (valid-invalid).
Hợp lệ : trang tương ứng thuộc về không gian địa chỉ của tiến trình.
Bất hợp lệ : trang tương ứng không nằm trong không gian địa chỉ của tiến trình, điều này có nghĩa tiến trình đã truy xuất đến một địa chỉ không được phép
Chia sẻ bộ nhớ trong cơ chế phân trang:
Một ưu điểm của cơ chế phân trang là cho phép chia sẻ các trang giữa các tiến trình.Trong trường hợp này, sự chia sẻ được thực hiện bằng cách ánh xạ nhiều địa chỉ logic vào một địa chỉ vật lý duy nhất. Có thể áp dụng kỹ thuật này để cho phép có tiến trình chia sẻ một vùng code chung:
9. Thế nào là tắc nghẽn cho ví dụ, điều kiện xuất hiện tắc nghẽn
1. Định nghĩa:
Một tập hợp các tiến trình được định nghĩa ở trong tình trạng tắc nghẽn khi mỗi tiến trình trong tập hợp đều chờ đợi một sự kiện mà chỉ có một tiến trình khác trong tập hợp mới có thể phát sinh được.
Nói cách khác, mỗi tiến trình trong tập hợp đều chờ được cấp phát một tài nguyên hiện đang bị một tiến trình khác cũng ở trạng thái blocked chiếm giữ. Như vậy không có tiến trình nào có thể tiếp tục xử lý , cũng như giải phóng tài nguyên cho tiến trình khác sử dụng, tất cả các tiến trình trong tập hợp đều bị khóa vĩnh viễn !
Vấn đề Bữa ăn tối của các triết gia : 5 nhà triết học cùng ngồi ăn tối với món spaghetti nổi tiếng. Mỗi nhà triết học cần dùng 2 cái nĩa để có thể ăn spaghetti . Nhưng trên bàn chỉ có tổng cộng 5 cái nĩa để xen kẽ với 5 cái đĩa. Mỗi nhà triết học sẽ suy ngẫm các triết lý của mình đến khi cảm thấy đói thì dự định lần lượt cầm 1 cái nĩa bên trái và 1 cái nĩa bên phải để ăn. Nếu cả 5 nhà triết học đều cầm cái nĩa bên trái cùng lúc, thì sẽ không có ai có được cái nĩa bên phải để có thể bắt đầu thưởng thức spaghetti . Đây chính là tình trạng tắc nghẽn.
2. Điều kiện xuất hiện tắc nghẽn
Coffman, Elphick và Shoshani đã đưa ra 4 điều kiện cần có thể làm xuất hiện tắc nghẽn:
Có sử dụng tài nguyên không thể chia sẻ (Mutual exclusion): Mỗi thời điểm, một tài nguyên không thể chia sẻ được hệ thống cấp phát chỉ cho một tiến trình , khi tiến trình sử dụng xong tài nguyên này, hệ thống mới thu hồi và cấp phát tài nguyên cho tiến trình khác.
Sự chiếm giữ và yêu cầu thêm tài nguyên (Wait for): Các tiến trình tiếp tục chiếm giữ các tài nguyên đã cấp phát cho nó trong khi chờ được cấp phát thêm một số tài nguyên mới.
Không thu hồi tài nguyên từ tiến trình đang giữ chúng (No preemption): Tài nguyên không thể được thu hồi từ tiến trình đang chiếm giữ chúng trước khi tiến trình này sủ dụng chúng xong.
Tồn tại một chu kỳ trong đồ thị cấp phát tài nguyên ( Circular wait): có ít nhất hai tiến trình chờ đợi lẫn nhau : tiến trình này chờ được cấp phát tài nguyên đang bị tiến trình kia chiếm giữ và ngược lại.
Khi có đủ 4 điều kiện này, thì tắc nghẽn xảy ra. Nếu thiếu một trong 4 điều kiện trên thì không có tắc nghẽn.
10. Trình bày các dạng định nghĩa của hệđiều hành
Hệđiều hành là một phần quan trọng của mọi hệ thống thông tin. Một hệ thống thông tin gồm 4 thành phần chính: phần cứng, hệđiều hành, chương trình ứng dụng, người sử dụng.
Phần cứng: 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: chương trình dịch, hệ thống cơ sở dữ liệu, trình soạn thảo văn bản…. qui định cách sử dụng các tài nguyên đóđể giải 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 sử dụng phong phúđa dạng.
Ta có thể hiểu HĐH 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à quản lý tài nguyên hệ thống tính toán.
1.1.1.1.1.1.1.20 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.
1. Đố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 MTDT thì chỉ quan tâm đến việc hệ thống cóđáp ứng được nhu cầu của họ hay không? Có chương trình cần thực hiện, cóđủ bộ nhớđể chạy…Họ không quan tâm đến việc hệđiều hành làm gì nhằm mục đích gì, có cấu trúc như thế nào?
2. Đố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 trẽ và sử dụng tối ưu các tài nguyên của hệ thống tính toán.
Đố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.
Các định nghiã trên phản ánh vị trí quan sát của người nêu. Họđứng ở ngoài hệ thống và thể hiện điều họ mong đợi và cũng làđiều họ nhìn thấy.
3. Đối với cán bộ lập trình hệ thống: HĐH là hệ thống mô hình hoá, mô phỏng các hoạt động của máy, của người sử dụng và của thao tác viên hoạt động trong các hệ thống đối thoại nhằm tạo môi trường để quản lý chặt trẽ các tài nguyên và tổ chức khai thác chúng một cách thuận tiện và tối ưu.
Đối với các cán bộ lập trình hệ thống, vị trí của họ làở bên trong hệđiều hành. Họ quan sát các module, các thành phần của hệ thống, quan sát mối quan hệ giữa chúng. Đây là quan điểm của chúng ta trong suốt quá trình khảo sát nghiên cứu hệđiều hành.
11. Trình bày giải pháp đồng bộ bằng kiểm tra luân phiên và giải pháp Peterson
Sử dụng việc kiểm tra luân phiên :
Tiếp cậ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.
(a) Cấu trúc tiến trình A
while (TRUE) {
while (turn != 0); // wait
critical-section ();
turn = 1;
Noncritical-section ();
}
(b) Cấu trúc tiến trình B
while (TRUE) {
while (turn != 1); // wait
critical-section ();
turn = 0;
Noncritical-section ();
}
Hình 3.6 Cấu trúc các tiến trình trong giải pháp kiểm tra luân phiên
Giải pháp của Peterson
Tiếp cận : Petson đưa ra một giải pháp kết hợp ý tưởng của cả hai giải pháp kể trên. Các tiến trình chia sẻ hai biến chung :
int turn; // đến phiên ai
int interesse[2]; // khởi động là FALSE
Nếu interesse[i] = TRUE có nghĩa là tiến trình Pi muốn vào miền găng. Khởi đầu, interesse[0]=interesse[1]=FALSE và giá trị của turn được khởi động là 0 hay 1. Để có thể vào được miền găng, trước tiên tiến trình Pi đặt giá trị interesse[i]=TRUE ( xác định rằng tiến trình muốn vào miền găng), sau đó đặt turn=j (đề nghị thử tiến trình khác vào miền găng).
Nếu tiến trình Pj không quan tâm đến việc vào miền găng (interesse[j]=FALSE), thì Pi có thể vào miền găng, nếu không, Pi phải chờ đến khi interesse[j]=FALSE. Khi tiến trình Pi rời khỏi miền găng, nó đặt lại giá trị cho interesse[i]= FALSE.
while (TRUE) {
int j = 1-i; // j là tiến trình còn lại
interesse[i]= TRUE;
turn = j;
while (turn == j && interesse[j]==TRUE);
critical-section ();
interesse[i] = FALSE;
Noncritical-section ();
}
12. Cho biết các trạng thái, vẽ mô hình chuyển trạng thái của tiến trình
Các trạng thái của tiến trình
Trạng thái của tiến trình tại một thời điểm được xác định bởi hoạt động hiện thời của tiến trình tại thời điểm đó. Trong quá trình sống, một tiến trình thay đổi trạng thái do nhiều nguyên nhân như : phải chờ một sự kiện nào đó xảy ra, hay đợi một thao tác nhập/xuất hoàn tất, buộc phải dừng hoạt động do đã hết thời gian xử lý, …
Tại một thời điểm, một tiến trình có thể nhận trong một các trạng thái sau đây :
Mới tạo : tiến trình đang được tạo lập.
Running : các chỉ thị của tiến trình đang được xử lý.
Blocked : tiến trình chờ được cấp phát một tài nguyên, hay chờ một
sự kiện xảy ra .
Ready : tiến trình chờ được cấp phát CPU để xử lý.
Kết thúc : tiến trình hoàn tất xử lý.
Tại một thời điểm, chỉ có một tiến trình có thể nhận trạng thái running trên một bộ xử lý bất kỳ. Trong khi đó, nhiều tiến trình có thể ở trạng thái blocked hay ready.
Các cung chuyển tiếp trong sơ đồ trạng thái biễu diễn sáu sự chuyển trạng thái có thể xảy ra trong các điều kiện sau :
Tiến trình mới tạo được đưa vào hệ thống
Bộ điều phối cấp phát cho tiến trình một khoảng thời gian sử dụng CPU
Tiến trình kết thúc
Tiến trình yêu cầu một tài nguyên nhưng chưa được đáp ứng vì tài nguyên chưa sẵn sàng để cấp phát tại thời điểm đó ; hoặc tiến trình phải chờ một sự kiện hay thao tác nhập/xuất.
Bộ điều phối chọn một tiến trình khác để cho xử lý .
Tài nguyên mà tiến trình yêu cầu trở nên sẵn sàng để cấp phát ; hay sự kiện hoặc thao tác nhập/xuất tiến trình đang đợi hoàn tất.
Bạn đang đọc truyện trên: Truyen2U.Pro