III. CÀI ĐẶT ĐỒNG HỒ
III.2 Phần mềm đồng hồ
Tất cả mọi việc mà phần cứng đồng hồ thực hiện tạo ra các ngắt theo từng khoảng thời gian đều đặn. Mọi điều khác đều được thực hiện bởi phần mềm đồng hồ, là driver đồng hồ. Công việc của driver đồng hồ trên mỗi hệ điều hành là khác nhau, nhưng thường bao gồm những chức năng chính như sau :
Quản lý thời gian trong ngày.
Không cho phép tiến trình chạy lâu hơn thời gian mà nó được phép.
Kế toán việc sử dụng CPU.
Cung cấp watchdog timer cho một phần của chính hệ thống đó.
Chức năng đầu tiên của đồng hồ, quản lý thời gian trong ngày thì không khó.
Chỉ cần tăng một bộ đếm sau mỗi nhịp của đồng hồ như đề cập ở trên. Vấn đề lưu ý ở đây là số lượng bit cho bộ counter. Vớiđồng hồ ở tần số 60 MHz, một bộ đếm 32 bit sẽ bị tràn sau hai năm. Do đó hệ thống không thể lưu trữ thời gian thực sự dưới dạng số nhịp từ 01/01/1970. Có ba cách giải quyết. Thứ nhất, dùng bộ đếm 64 bit, giải pháp này tốn kém. Thứ hai, lưu trữ dưới dạng giây thay vì nhịp vì 232 giây sẽ là 136 năm. Thứ ba, đếm theo nhịp, nhưng liên hệ với thời gian của hệ thống khi khởi động.
Chức năng thứ hai là không cho phép một tiến trình thực hiện quá lâu. Khi nào một tiến trình bắt đầu, bộ lập lịch sẽ khởi gán giá trị cho bộ đếm, mỗi ngắt đồng hồ sẽ giảm giá trị của bộ đếm, khi nào giá trị bằng 0, bộ điều khiển đồng hồ sẽ yêu cầu bộ lập lịch thiết lập giá trị cho một tiến trình khác.
Chức năng thứ ba là kế toán việc sử dụng CPU. Cách thức chính xác nhất là sử dụng một bộ timer thứ hai, khác với timer hệ thống. Bộ timer thứ hai khởi động khi tiến trình bắt đầu và khi tiến trình kết thúc, timer này sẽ cho biết thời gian tiến trình đã thực hiện.
Phần lớn hệ thống cần thiết thiết lập timer. Gọi là watchdog timer. Ví dụ, để sử dụng đĩa mềm, hệ thống phải khởi động motor và chờ khoảng 500msec đạt được tốc độ. Vì vậy, ý tưởng tốt là phải sử dụng watchdog timer để chờ cho thao tác I/O tiếp theo, vào khoảng 3 giây, không tắt motor.
Câu 1. Process là gì?Process khác chương trình ở điểm gì?Cho biết các công việc chính của bộ phận Process Management.
Tiến trình là một chương trình đang xử lí, sở hữu một tập con trỏ lệnh, tập các thanh ghi, các biến và một tập các tài nguyên cần cho hoạt động của tiến trình.
Chương trình là một thực thể thụ động chứa các chỉ thị điều khiển máy tính để tiến hành một hoạt động nào đó, khi thực hiện tác vụ này thì chương trình chuyển thành tiến trình – một thực thể hoạt động với con trỏ lệnh xác định chỉ thị tiếp theo sẽ thi hành và tập tài nguyên.
Bộ phận Process Management có nhiệm vụ:
- Tạo và hủy tiến trình người dùng và tiến trình hệ thống - Hoãn và khôi phục tiến trình
- Cung cấp cơ chế cho việc đồng bộ hóa tiến trình - Cung cấp cơ chế cho việc giao tiếp tiến trình - Cung cấp cơ chế quản lý deadlock
Câu 2. Cho biết các công việc chính của bộ phận Memory Management, file management, secondary storage management?
• Memory Management
o Theo dõi thành phần nào của của bộ nhớ đang được sử dụng và tiến trình nào đang sử dụng
o Quyết định tiến trình nào hoặc dữ liệu nào sẽ được di chuyển ra khỏi hoặc đưa vào bộ nhớ
o Cấp phát và hủy không gian bộ nhớ nếu cần.
• File Management
o Tạo và xóa tập tin
o Tạo và xóa thư mục
o Hỗ trợ các thao tác cơ bản trên tập tin và thư mục
o Ánh xạ tập tin vào trong bộ lưu trữ thứ cấp
o Sao lưu trên các thiết bị ổn định
• Storage Management
o Quản lí không gian trống
o Cấp phát cho việc lưu trữ dữ liệu
o Định thời yêu cầu truy cập bộ nhớ
Câu 3. Cho biết các công việc chính của bộ phận I/O system management và của Hệ thống bảo vệ?
1. I/O Management: Che dấu sự khác biệt của các thiết bị đối với người dùng
1. i. Cung cấp giao diện chung đến các trình điều khiển thiết bị (device
2. ii. Bộ điều khiển thiết bị phần cứng
3. iii. Các cơ chế buffering, caching, spooling
4. b. Hệ thống bảo vệ:
1. i. Cung cấp cơ chế kiểm soát đăng nhập và đăng xuất
2. ii. Phân định sự truy cập tài nguyên hợp pháp, bất hợp pháp
3. iii. Phương tiện thi hành các chính sách (cần bảo vệ dữ liệu của ai đối với ai)
Câu 4. System call là gì? hãy đưa ra một số ví dụ về system call. System program là gì và nó khác application program như thế nào?liệt kê các system program cơ bản.
- System Call là một cơ chế mà các chương trình ứng dụng sử dụng để yêu cầu các dịch vụ có sẵn của hệ điều hành. Hay nói cách khác System Call cung cấp một giao diện cho các dịch vụ mà hệ điều hành cung cấp.
- Ví dụ về system call: Lệnh fork() trong Unix dùng để tạo ra một tiến trình mới.
- System Program là các chương trình cung cấp một môi trường thuận tiện để phát triển và thực thi chương trình. Application là chương trình được viết ra để giúp người sử dụng giải quyết một vấn đề nào đó hoặc thao tác trong công việc. Ví dụ như Web Browser, Microsoft Office Word
- Vài ví dụ về các System Program là: Compiler, Linker, Loader, Debugger Câu 5. Kernel mode là gì ? User mode là gì ? Cho biết sự khác nhau giữa chúng ? Các trạng thái của một quá trình? vẽ sơ đồ và giải thích sự chuyển đổi giữa các trạng thái?
- Kernel mode: tác vụ được thực thi thay mặt cho hệ diều hành - User mode: tác vụ được thực thi thay mặt cho người dùng
- Khác biệt: Khi CPU ở Kernel mode, nó có thể thực thi bất cứ chỉ thị nào và tham chiếu đến bất kì địa chỉ nhớ nào. Khi Cpu ở user mode, nó không thể truy nhập đến phần cứng hoặc tham chiếu đến bộ nhớ một cách trực tiếp. Các đoạn mã trong user mode phải được chuyển đổi thành các hàm API của hệ thống để có thể truy nhập tới bộ nhớ và phần cứng.
- Các trạng thái của quá trình (process states):
• new: quá trình vừa được tạo
• ready: quá trình đã có đủ tài nguyên, chỉ còn cần CPU
• running: các lệnh của quá trình đang được thực thi
• waiting: hay là blocked, quá trình đợi I/O hoàn tất, tín hiệu.
• terminated: quá trình đã kết thúc.
Câu 6. Tại sao các hệ điều hành hiện đại hỗ trợ môi trường đa nhiệm ? Phân biệt multitask, multiprogramming và multiprocessing.
- Các hệ điều hành hiện đại hỗ trợ môi trường đa nhiệm vì: tăng hiệu suất sử dụng CPU và tăng tốc độ xử lý
- Multitasking (đa nhiệm): thực hiện nhiều nhiệm vụ cùng một lúc, CPU sẽ luân phiên xử lý các tiến trình trong một khoảng thời gian rồi chuyển sang cho tiến trình khác. VD: nghe nhạc và duyệt web đồng thời
- Multiprogramming (đa chương): có nhiều hơn một chương trình đang nằm trong bộ nhớ để được lựa chọn chuyển giao cho CPU thực thi. Ví dụ: mở Word, Excel, Powerpoint cùng lúc, trong khi chúng ta sử dụng Word thì Excel và
Powerpoint vẫn thường trực trong bộ nhớ mặc dù chúng không thực hiện việc gì cả - Multiprocessing (đa tiến trình): sử dụng nhiều hơn 1 CPU để có thể xử lý song song cùng lúc nhiều tiến trình.
Câu 7. Khái niệm tiến trình được xây dựng nhằm mục đích gì ? Sự khác biệt, mối quan hệ giữa tiến trình và tiểu trình ?
- Để hỗ trợ sự đa chương, máy tính phải có khả năng thực hiện nhiều tác vụ đồng thời. Nhưng việc điều khiển nhiều hoạt động song song ở cấp độ phần cứng là rất khó khăn. Vì thế các nhà thiết kế hệ điều hành đề xuất một mô hình song song gỉa lặp bằng cách chuyển đổi bộ xử lý qua lại giữa các chương trình để duy trì hoạt động của nhiều chương trình cùng lúc, điều này tạo cảm giác có nhiều hoạt động được thực hiện đồng thời. Trong mô hình này, tất cả các phần mềm trong hệ thống được tổ chức thành một số những tiến trình (process).
- Tiến trình có không gian địa chỉ và chỉ có một dòng xử lý. Các tiểu trình thì chia sẻ một không gian địa chỉ, và các dòng xử lý này hoạt động song song tương tự như các tiến trình phân biệt.
- Một tiến trình có thể có nhiều tiểu trình chạy đồng thời
Câu 8. Thông tin lưu trữ trong PCB và TCB ? Tổ chức điều phối tiến trình ? Phân tích ưu, khuyết của các chiến lược điều phối
- PCB là một trong các cấu trúc dữ liệu quan tọng nhất của hệ điều hành và gồm:
• Trạng thái quá trình: new, ready, running,…
• Bộ đếm chương trình
• Các thanh ghi
• Thông tin lập thời biểu CPU: độ ưu tiên, …
• Thông tin quản lý bộ nhớ
• Thông tin tài khoản: lượng CPU, thời gian sử dụng,
• Thông tin trạng thái I/O
Tổ chức điều phối: Long-term scheduling,Medium-term scheduling,Short term scheduling.
- Hỗ trợ sự thực thi luân phiên giữa nhiều quá trình + Hiệu suất sử dụng CPU
+ Thời gian đáp ứng
- Phân phối tài nguyên hệ thống hợp lý + tránh deadlock, trì hoãn vô hạn định,…
- Cung cấp cơ chế giao tiếp và đồng bộ hoạt động các quá trình - Cung cấp cơ chế hỗ trợ user tạo/kết thúc quá trình
Câu 9. Các cơ chế trao đổi thông tin : tình huống sử dụng, ưu, khuyết ?Các yêu cầu đồng bộ hoá ?
Các cơ chế trao đổi thông tin:
- Signal : Không truyền được dữ liệu - Pipe: Truyền dữ liệu không cấu trúc
- Shared Memory: Mâu thuẫn truy xuất => nhu cầu đồng bộ hoá - Message: Liên lạc trên môi trường phân tán
+ Liên kết tiềm ẩn
• Send(message) : gởi một thông điệp
• Receive(message) : nhận một thông điệp
+ Liên kết tường minh
• Send(destination, message) : gởi một thông điệp đến destination
• Receive(source,message) : nhận một thông điệp từsource - Socket: là một thiết bị truyền thông hai chiều như tập tin
+ Mỗi Socket là một thành phần trong một mối nối giữa các máy trong mạng + Các thuộc tính của socket:domaine, type.
Các yêu cầu đồng bộ hóa:
• Độc quyền truy xuất (Mutual exclusion):Khi một process P đang thực thi trong vùng tranh chấp (CS) của nó thì không có process Q nào khác đang thực thi trong CS của Q.
• Progress:Một tiến trình tạm dừng bên ngoài miền găng không được ngăn cản các tiến trình khác vào miền găng và việc lựa chọn P nào vào CS phải có hạn định
• Chờ đợi giới hạn (Bounded waiting): Mỗi process chỉ phải chờ để được vào vùng tranh chấp trong một khoảng thời gian có hạn định nào đó. Không xảy ra tình trạng đói tài nguyên (starvation).
• 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
Câu 10. Phân biệt nhóm giải pháp busy waiting và Sleep&Wakeup.Phân biệt cách sử dụng semaphore, monitor.
Busy Wating
While(Chưa có quyền) Do nothing;
CS;
Từ bỏ quyền;
• TiếptụctiêuthụCPUtrongkhichờđợivàomiềngăng
• KhôngđòihỏisựtrợgiúpcủaHệđiềuhành Sleep Wake up
if (chưa có quyền) Sleep() ; cs;
wake up (by someone);
• TừbỏCPUkhichưađượcvàomiềngăng
• CầnđượcHệđiềuhànhhỗtrợ
Câu 11. Giải thích sự khác biệt giữa địa chỉ logic và địa chỉ physic?Giải thích sự khác biệt giữa hiện tượng phân mảnh nội vi và ngoại vi?
Địa chỉ Logic: là địa chỉ không chỉ đến một địa chỉ tồn tại thực trong bộ nhớ, nó là một vị trí nhớ được diễn tả bởi một chương trình nào đó. Địa chỉ logic được phát
sinh bởi CPU, và được chuyển sang địa chỉ vật lí (physic) bởi một chương trình quản lí bộ nhớ – memory Management Unit (MMU).
Địa chỉ vật lí là địa chỉ bộ nhớ phát sinh bởi MMU( Memory management Unit), nó chỉ đến một vị trí nhớ có thực nằm trong bộ nhớ vật lí.
Phân mảng ngoại: (External Fragmentation)
Kích thước không gian bộ nhớ còn trống đủ để thỏa mãn một yêu cầu cấp phát, tuy nhiên không gian nhớ này không liên tục.
Phân mảnh nội (internal fragmentation)
Kích thước vùng nhớ được cấp phát có thể hơi lớn hơn so với yêu cầu.Ví dụ cấp một khoảng 18,464 bytes cho một yêu cầu 18,462 bytes.
Hiện tượng phân mảng nội thường xảy ra khi bộ nhớ thực (physical memory) được chia thành các khối kích thước ố định (fixed sized block) và các process được cấp phát theo đơn vị khối. ví dụ cơ chế phân trabg (paging).
Câu 12. Khi nào thì xảy ra lỗi trang ?Mô tả xử lý của hệ điều hành khi có lỗi trang.Giả sử có một chuỗi truy xuất bộ nhớ có chiều dài p với n số hiệu trang khác nhau xuất hiện trong chuỗi. Giả sử hệ thống sử dụng m khung trang ( khởi động trống). Với một thuật toán thay thế trang bất kỳ :Cho biết số lượng tối thiểu các lỗi trang xảy ra ?Cho biết số lượng tối đa các lỗi trang xảy ra ?
Lỗi trang xảy ra khi người dùng truy cập tới một trang không hợp lệ (nghĩa là trang không ở trong không gian địa chỉ của quá trình – không đang ở trong bộ nhớ chính) hoặc ta đang truy cập bởi một trang hợp lệ nhưng đang ở bộ nhớ phục (swap space).
Xử lí của hệ điều hành: Việc truy xuất một trang không hợp lệ gây ra một trap lỗi trang (Page – fault trap). Phần cứng phần trang, dịch địa chỉ thông qua bảng trang, sẽ thông báo rằng bit không hợp lệ đã được đặt vào, gây ra một trap tới hệ điều hành. Trap này kích khởi dịch vụ page – fault service routine (PFSR) của hệ điều hành.
Các bước xử lí của PFSR:
- B1: chuyển process phát ra tham chiếu về trạng thái blocked.
- B2:phát ra một yêu cầu đọc đĩa để nạp trang được tham chiếu vào một frame trống; trong khi đợi I/O. một process khác được cấp CPU để thực thi
- B3: Sau khi I/O hoàn tất, đĩa gây ra một ngắt đến hệ điều hành, PFSR cập nhật page table và chuyển process về trạng thái ready.
* Tại bước 2 của PFSR, giả sử phải thay trang vì không tìm được frame trống, PFSR được bổ sung như sau:
+ xác định vị trí trên đĩa của trang đang cần + tìm một frame trống
• nếu có frame trống thì dùng nó
• nếu không có frame trống thì dùng một giải thuật thay trang để chọn một trang hy sinh (victim page)
• ghi victim page lên đĩa, cập nhật page table và frame table tương ứng + đọc trang đang cần vào frame trống, cập nhật page table và frame table tường ứng.
1.Điều phối FIFO
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.
*Thời gian xử lý : P1=24,P2=3,P3=3
* Thời gian xử lý trung bình : (24+3+3)/3=10
*Thời gian đợi : P1=0; P2=24-1 =23 ; P3 = 24+3-2 = 25
*Thời gian đợi trung bình: (0+23+25)/3 = 16
* Thời gian lưu lại trong hệ thống : P1=24 ; P2=3; P3=3
* Thời gian lưu lại trung bình : (24+3+3)/3 =10
2.Chiến lược điều phối xoay vòng :
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.
*Thời gian xử lý : P1=24,P2=3,P3=3
* Thời gian xử lý trung bình : (24+3+3)/3=10
*Thời gian đợi : P1=0
P2=4-1=3 P3=4+3-2=5 P1'=4+3+3-3=6
đến lúc này p1 sẽ được xử lý liên tục nên không phải tính thời gian chờ của p1'' p1'''...
*Thời gian đợi trung bình: (0+3+5+6)/3=4.66
* Thời gian lưu lại trong hệ thống :
P1: vòng 1 =4 vòng 2=20 khoảng cách 2 vòng là 6 => thời gian lưu lại của P1
=4+20+6 =30 P2=3
P3=3
* Thời gian lưu lại trung bình : (30+3+3)/3=12 3.Điều phối với độ ưu tiên
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. Khi một tiến trình được đưa vào danh sách các tiến trình sẵn sàng, độ ưu tiên của nó được so sánh với độ ưu tiên của tiến trình hiện hành đang xử lý. Giải thuật điều phốivới độ ưu tiên và không độc quyền sẽ thu hồi CPU từ tiến trình hiện hành để cấp phát cho tiến trình mới nếu độ ưu tiên của tiến trình này cao hơn tiến trình hiện hành. Một giải thuật độc quyền sẽ chỉ đơn giản chèn tiến trình mới vào danh sách sẵn sàng, và tiến trình hiện hành vẫn tiếp tục xử lý hết thời gian dành cho nó.