Trong các hệ thống lập trình đơn như MS DOS, khi một tiến trình chờ bất kỳ hoạt động I / O nào được thực hiện, CPU vẫn là thần tượng. Đây là một khoản phí lớn vì nó lãng phí thời gian và gây ra vấn đề chết đói. Tuy nhiên, trong hệ thống Đa chương trình, CPU không ở trạng thái nghỉ trong thời gian chờ của Quy trình và nó bắt đầu thực hiện các quy trình khác. Hệ điều hành phải xác định quá trình CPU sẽ được cung cấp.
Trong các hệ thống Đa chương trình, Hệ điều hành lập lịch trình cho các quá trình trên CPU để sử dụng nó tối đa và thủ tục này được gọi là lập lịch cho CPU . Hệ điều hành sử dụng các thuật toán lập lịch khác nhau để lập lịch cho các quá trình.
Các bài viết liên quan:
Đây là một nhiệm vụ của bộ lập lịch ngắn hạn để lập lịch cho CPU về số lượng quy trình có trong Nhóm công việc. Bất cứ khi nào quá trình đang chạy yêu cầu một số hoạt động IO thì bộ lập lịch ngắn hạn sẽ lưu bối cảnh hiện tại của quá trình [còn được gọi là PCB] và thay đổi trạng thái của nó từ đang chạy sang chờ. Trong thời gian, tiến trình ở trạng thái chờ đợi; bộ lập lịch ngắn hạn chọn một quá trình khác từ hàng đợi sẵn sàng và chỉ định CPU cho quá trình này. Thủ tục này được gọi là chuyển đổi ngữ cảnh .
Xem thêm Priority Scheduling trong Hệ điều hành
Những gì được lưu trong Khối Kiểm soát Quy trình?
Hệ điều hành duy trì một khối điều khiển quy trình trong suốt thời gian tồn tại của quy trình. Khối điều khiển quá trình bị xóa khi quá trình bị kết thúc hoặc bị giết. Có thông tin sau được lưu trong khối điều khiển quy trình và sẽ thay đổi theo trạng thái của quy trình.
Tại sao chúng ta cần Lập lịch trình?
Trong Đa chương trình, nếu bộ lập lịch dài hạn chọn nhiều quá trình ràng buộc I / O hơn thì phần lớn thời gian, CPU vẫn là thần tượng. Nhiệm vụ của Hệ điều hành là tối ưu hóa việc sử dụng tài nguyên.
Nếu hầu hết các tiến trình đang chạy thay đổi trạng thái của chúng từ đang chạy sang chờ thì có thể luôn có khả năng xảy ra bế tắc trong hệ thống. Do đó, để giảm thiểu chi phí này, HĐH cần lên lịch các công việc để có được việc sử dụng CPU tối ưu và tránh khả năng bị deadlock.
Xem thêm Thuật toán Shortest Remaining Time First [SRTF]
Các thuật toán lập lịch trình
Có nhiều thuật toán khác nhau được Hệ điều hành sử dụng để lập lịch các quá trình trên bộ xử lý một cách hiệu quả.
Mục đích của thuật toán lập lịch trình
- Sử dụng CPU tối đa
- Phân bổ giá vé của CPU
- Thông lượng tối đa
- Thời gian quay vòng tối thiểu
- Thời gian chờ đợi tối thiểu
- Thời gian phản hồi tối thiểu
Có các thuật toán sau đây có thể được sử dụng để lập lịch trình công việc.
Đây là thuật toán đơn giản nhất để thực hiện. Quá trình với thời gian đến tối thiểu sẽ nhận được CPU đầu tiên. Thời gian đến càng ít, quá trình nhận được CPU càng sớm. Đây là kiểu lập kế hoạch không ưu tiên. Xem thêm Lập lịch FCFS trong Operating System
Trong thuật toán lập lịch Round Robin, Hệ điều hành xác định một lượng tử thời gian [lát cắt]. Tất cả các quá trình sẽ được thực thi theo cách tuần hoàn. Mỗi tiến trình sẽ lấy CPU trong một khoảng thời gian nhỏ [gọi là lượng tử thời gian] và sau đó quay trở lại hàng đợi sẵn sàng để chờ đến lượt tiếp theo của nó. Đây là một kiểu lập kế hoạch phủ đầu.
- Công việc ngắn nhất đầu tiên
Công việc có thời gian bùng nổ ngắn nhất sẽ nhận được CPU đầu tiên. Thời gian bùng nổ càng ít, quá trình lấy CPU càng sớm. Đây là kiểu lập kế hoạch không ưu tiên.
- Thời gian còn lại ngắn nhất trước
Đó là hình thức phủ đầu của SJF. Trong thuật toán này, Hệ điều hành lên lịch Công việc theo thời gian thực hiện còn lại.
- Lên lịch dựa trên mức độ ưu tiên
Trong thuật toán này, mức độ ưu tiên sẽ được chỉ định cho mỗi quá trình. Mức độ ưu tiên càng cao thì tiến trình nhận được CPU càng sớm. Nếu mức độ ưu tiên của hai quy trình là như nhau thì chúng sẽ được sắp xếp theo thời gian đến.
- Tỷ lệ phản hồi cao nhất Tiếp theo
Trong Thuật toán lập lịch này, quy trình có tỷ lệ phản hồi cao nhất sẽ được lên lịch tiếp theo. Điều này làm giảm tình trạng đói trong hệ thống.
Xem thêm Lập lịch Highest Response Ratio Next [HRRN] trong hệ điều hành
Lời mở đầu
Có lẽ không cần phải nói quá nhiều về cụm từ hệ điều hành nữa. Dù là bất cứ ai, khi mà đã hoặc đang sử dụng một chiếc máy tính để học tập, làm việc thì đều ít nhiều từng nghe đến cụm từ "Hệ điều hành". Với phần lớn hệ thống máy tính, khi mà người sử dụng bật thiết bị của họ lên, thì ngay sau đoạn logo của của hãng phần cứng xuất hiện sẽ là sự xuất hiện của hệ điều hành. Với đa số người, biểu tượng cửa sổ huyền thoại của hệ điều hành Microsoft Windows không có gì xa lạ nữa. Từ những năm 90 của thế kỉ trước, những phiên bản đầu tiên như Windows 1.0, Windows 3.1 ... cho đến Windows 95, 98, ngày nay là Windows 7, Windows 8.1 hay Windows 10, có đôi chút thay đổi về màu sắc, kiểu dáng nhưng vẫn là cái biểu tượng quen thuộc - biểu tượng của hệ điều hành Windows.Thế giới máy tính ngày nay, ngoài Windows còn có thêm rất nhiều hệ điều hành khác cho phép người dùng trải nghiệm, như macOS dành cho máy tính của hãng Apple, ChromeOS dành riêng cho ChromeBook của Google, hoặc những hệ thống dựa trên nhân Linux và BSD. Nhưng nhìn chung, cho dù là gì đi nữa thì cũng vẫn là hệ điều hành máy tính, đều là một loại phần mềm đặc biệt có thể quản lý bộ nhớ, các tiến trình cũng như cho phép các phần mềm khác hoạt động phía trên nó. Ngoài ra, hệ điều hành còn cho phép kết nối, giao tiếp [làm cầu nối] giữa các máy tính với nhau mà không yêu cầu người sử dụng phải hiểu biết quá nhiều về kỹ thuật hay ngôn ngữ của máy tính [ngôn ngữ nhị phân]. Có thể nhận định rằng:
Không có hệ điều hành, các thiết bị máy tính là vô dụng.
Bạn đang xem: 2. lập lịch là gì? ứng dụng lập lịch trong hệ thống thời gian thực như thế nào?
Tại sao phải nghiên cứu về các hoạt động của hệ điều hành?Hệ điều hành được tạo ra nhằm mục đích giúp con người có thể sử dụng máy tính và làm việc trên nó, đôi khi là giải trí hoặc tương tác với các máy tính khác. Khi nó ra đời, bản thân nó đã bao gồm cả việc khiến cho mọi người đều có thể sử dụng máy tính, mặc dù việc này là không đảm bảo được chắc chắn nếu như hệ điều hành đó không đi kèm một số tài liệu hướng dẫn sử dụng cần thiết. Và khi hệ điều hành được sử dụng rộng rãi cũng không có nghĩa là nó hoàn hảo. Đâu đó bên trong hệ thống phức tạp này vẫn còn tồn tại vài lỗi, hoặc thậm chí vài lỗ hổng bảo mật có thể khiến toàn bộ thiết bị cũng như các phần mềm khác bị trục trặc. Chính vì vậy, cần có những đội hoặc nhóm chuyên biệt, có trình độ kỹ thuật cao được lập ra để nghiên cứu về các vấn đề xoay quanh hoạt động của hệ điều hành, hiểu rõ về bản chất của nó và giúp cho việc khắc phục các vấn đề liên quan đến nó dễ dàng hơn.Bài viết này của mình được nhằm mục đích tìm hiểu, cũng như giới thiệu cho mọi người những hoạt động cơ bản nhất của hệ điều hành, qua đó có thể giúp mọi người nắm được cơ bản các vấn đề xử lý ở mức thấp hơn của hệ thống mà chúng ta vẫn đang sử dụng. Mặc dù các hệ điều hành có thể khác nhau nhưng nhìn chung hoạt động về cơ bản là giống nhau.
Hệ điều hành là gì?Trước khi nói về hoạt động, mình sẽ giải thích cơ bản một chút về hệ điều hành. Nhìn chung, hệ điều hành là một phần mềm máy tính, nhưng không giống như các phần mềm quen thuộc chúng ta hay dùng hàng ngày như trình duyệt, trình soạn thảo văn bản hay trình biên tập file. Hệ điều hành là tập hợp của các chương trình có chức năng quản lý phần cứng cũng như cung cấp các dịch vụ cần thiết cho các phần mềm khác hoạt động. Ngoài ra, hệ điều hành hầu hết sẽ che giấu đi những xử lý tính toán phức tạp, tính toán việc sử dụng tài nguyên cũng như cung cấp các chức năng về cách ly [để tránh tối đa xung đột giữa phần cứng với phần mềm] và tạo một vài lớp bảo vệ tránh tấn công từ bên ngoài [điển hình nhất là Firewall].Hệ điều hành bao gồm 3 thành phần, 3 yếu tố cấu thành và 2 nguyên tắc thiết kế
3 thành phần chính là File system [các tập tin hệ thống ], Scheduler[bộ lập lịch] và Device driver[trình điều khiển thiết bị ].2 nguyên tắc thiết kế bao gồm: Separation of mechanism and policy [đảm bảo thiết kế các cơ chế dễ đáp ứng việc bổ sung chính sách] và Optimization for common case [Tối ưu cho các trường hợp phổ biến]Ngay sau đây, mình sẽ trình bày một số hoạt động chính của hệ điều hành mà mình tìm hiểu được, do số lượng nội dung khá nhiều nên mình sẽ chia bài viết làm 3 phần. Trong phần 1 này, mình sẽ nói về 3 vấn đề: [1] Quản lý tiến trình, [2] Luồng và xử lý đồng bộ và [3] Cơ chế lập lịch.
Một tiến trình về cơ bản là một chương trình đang ở trong trạng thái thực thi. Việc thực thi của các tiến trình buộc phải diễn ra theo kiểu tuần tự. Đơn giản là, danh sách các chương trình muốn thực thi sẽ được điền vào một tệp văn bản và khi máy tính hoạt động, nội dung của tệp trở thành thứ tự thực thi các tiến trình tương ứng, nội dung của tệp sẽ được thay đổi theo thời gian. Mặc dù đã từng có nhiều nhận định cho rằng máy tính có thể xử lý song song, tuy nhiên đó là với các vi xử lý hiện đại ngày nay có chứa nhiều nhân [core] hoạt động độc lập, còn thực tế các tiến trình được quản lý bởi một nhân xử lý sẽ luôn hoạt động tuần tự, chẳng qua việc xử lý diễn ra nhanh đến mức mắt người không thể thấy được. Các chương trình sẽ luân phiên hoạt động để đánh lừa mắt người rằng chúng đang hoạt động song song ^^.Khi một chương trình được nạp vào bộ nhớ và trở thành một tiến trình, nó có thể được chia thành bốn phần - Stack, Heap, Data và Text. Hình ảnh sau đây cho thấy bố cục đơn giản của một tiến trình bên trong bộ nhớ chính:
Trong đó,
Stack: Chứa dữ liệu tạm thời, thường chỉ chứa dữ liệu dùng trong thời gian rất ngắn hoặc dùng một lần.Heap: Đây là vùng bộ nhớ được cấp phát động cho một tiến trình trong thời gian thực thi.Data: Chứa các biến global [biến dùng chung ở cấp toàn bộ chương trình] và static [loại biến dùng chung ở cấp struct].Text: Bao gồm hoạt động hiện tại được biểu thị bằng giá trị của Program Counter và nội dung của các thanh ghi trên vi xử lý.Khi một tiến trình thực thi, nó có thể đi qua các trạng thái khác nhau. Các giai đoạn này có thể khác nhau đối với các hệ điều hành khác nhau và tên của các trạng thái này cũng không được chuẩn hóa cụ thể. Nhưng nhìn chung, một tiến trình có thể có một trong năm trạng thái sau đây tại một thời điểm:
Xem thêm: What Is The Meaning Of "Amore Mio Là Gì Trong Tiếng Ý? What Is The Meaning Of Amore Mio
Để lưu dữ liệu hoạt động của các tiến trình, hệ điều hành sẽ sử dụng một cấu trúc dữ liệu gọi là Process Control Block [PCB]. Mỗi PCB được xác định bởi một số nguyên dương [bắt đầu từ 1], gọi là Process ID [PID]. PCB thường sẽ bao gồm các thông tin như sau:
Scheduling [lập lịch] là nhiệm vụ của bộ xử lý, nó sẽ tiến hành loại bỏ các tiến trình đang chạy khỏi CPU và lựa chọn một danh sách tiến trình khác trên cơ sở một chiến lược cụ thể. [Có thể danh sách mới sẽ bao gồm một số tiến trình trong danh sách cũ].Lập lịch là một trong các tiêu chí của việc thiết kế hệ điều hành đa nhiệm [multi-task]. Các hệ điều hành này cho phép nhiều hơn một tiến trình được nạp vào bộ nhớ để thực thi tại một thời điểm và tiến trình được nạp sẽ chia sẻ thời gian CPU bằng cách sử dụng ghép kênh thời gian [multiplexing].Hệ điều hành duy trì tất cả các PCB [đã nhắc đến ở cuối phần 1] trong Process Scheduling Queues [hàng đợi lập lịch tiến trình]. Đồng thời, mỗi trạng thái của tiến trình sẽ có một hàng đợi riêng được duy trì [1 hàng đợi riêng cho ready, 1 hàng đợi riêng cho running, ...] và PCB của tất cả các tiến trình trong cùng trạng thái thực thi được đặt trong cùng một hàng đợi. Khi trạng thái của một tiến trình được thay đổi, PCB của nó sẽ bị xóa liên kết khỏi hàng đợi hiện tại và được chuyển sang hàng đợi trạng thái mới [áp dụng thuật toán danh sách liên kết cơ bản và cơ chế truy xuất theo địa chỉ].Ngoài các hàng đợi theo trạng thái, hệ điều hành còn duy trì một số hàng đợi như:
Job queue: Hàng đợi lưu trữ mọi tiến trình đang ở trong hệ thốngReady queue: Chứa các tiến trình mới được khởi tạo.Device queue: Nếu một tiến trình cần chờ để có thể sử dụng thiết bị I/O thì được đưa vào đây. Dưới đây là hình ảnh mô ta một tiến trình từ khi bắt đầu cho đến khi rời khỏi CPU:Một số chính sách thường sẽ được sử dụng để lập lịch bao gồm FIFO, Round Robin hoặc Priority ...Theo như trên hình, khi một tiến trình rời khỏi Ready queue để bắt đầu thực thi, nó có thể có 4 khả năng:
Request I/O: tiến trình cần xử lý liên quan đến đọc - ghi => Sẽ được chuyển vào Device queue.Timeout: tiến trình đã dùng hết thời gian được cấp phép bởi CPU, sẽ được đưa trở lại vào Ready queue để đợi đến lượt tiếp theo.Fork child: tiến trình tạo ra tiến trình con để tiếp tục xử lý, thường là các tiến trình phức tạp hoặc cần xử lý đồng thời nhiều công việc.Interrupt: tiến trình bị gián đoạn do một vấn đề nào đó đột ngột phát sinh.Một khái niệm khác có thể được nhắc tới là Context switch [kỹ thuật chuyển ngữ cảnh]. Đây là cơ chế lưu trữ và khôi phục trạng thái hoặc ngữ cảnh của CPU trong PCB. Nó cho phép thực hiện tiến trình được bắt đầu lại từ cùng một trạng thái kết thúc trước đó. Giống như khi ta ghi dữ liệu lên một file, sau đó khi sửa file này ta sẽ tiếp tục với nội dung được lưu trước đó thay vì bắt đầu lại từ đầu. Kỹ thuật này cho phép nhiều tiến trình cùng chia sẻ một CPU. Context switch là một tính năng thiết yếu của hệ điều hành đa nhiệm.Khi bộ lập lịch chuyển CPU từ việc thực thi một tiến trình này sang một tiến trình khác, trạng thái từ tiến trình đang chạy hiện tại được lưu trữ vào PCB. Với lần thực thi tiếp theo, trạng thái cho tiến trình đó được tải từ PCB của chính nó và được sử dụng để thiết lập bộ đếm chương trình, các thanh ghi, v.v. Tại thời điểm đó, tiến trình thứ hai có thể bắt đầu thực thi.Việc tính toán Context switch rất chuyên sâu, vì thanh ghi và trạng thái bộ nhớ phải được lưu và khôi phục lại đúng như giai đoạn thực thi trước đó. Để tránh thời gian chuyển đổi quá lâu, một số hệ thống phần cứng sử dụng hai hoặc nhiều thanh ghi của bộ xử lý để tính toán.Khi tiến trình được chuyển đổi bởi Context switch, các thông tin sau sẽ được lưu trữ để sử dụng: bộ đếm chương trình, thông tin lập lịch, giá trị thanh ghi cơ sở và giới hạn, thanh ghi hiện được sử dụng, trạng thái thay đổi, thông tin I/O và thông tin kế toán.
3. Luồng và xử lý đồng bộLuồng [hay Thread] là một quy trình thực hiện thông qua mã tiến trình, một tiến trình có thể có nhiều luồng thực hiện song song. Nó có bộ đếm chương trình [Program Counter] riêng để theo dõi chỉ dẫn nào sẽ thực hiện tiếp theo. Nó cũng có các thanh ghi hệ thống chứa các biến làm việc hiện tại và một ngăn xếp chứa lịch sử thực hiện các chỉ dẫn.Một luồng chia sẻ với các luồng ngang hàng của nó các thông tin khác nhau như code segment, data segment và các file đang mở. Khi một luồng làm thay đổi bất cứ thông tin nào kể trên, tất cả các luồng khác sẽ thấy.Luồng cũng có thể được gọi là một tiểu tiến trình. Luồng cung cấp một cách để cải thiện hiệu suất ứng dụng thông qua việc xử lý song song. Luồng đại diện cho một cách tiếp cận phần mềm để cải thiện hiệu suất của hệ điều hành bằng cách giảm chi phí xử lý. Một luồng tương đương với một tiến trình cổ điển.Mỗi luồng thuộc về chính xác một tiến trình và không có luồng nào có thể tồn tại bên ngoài một tiến trình [nói cách khác, không có tiến trình thì không có luồng]. Luồng thường được áp dụng trong các máy chủ network hoặc máy chủ web, đáp ứng thực thi song song trong một hệ thống dùng chung bộ nhớ.
Hình ảnh trên cho thấy trừ là các thanh ghi và ngăn xếp ra thì mọi dữ liệu khác đều được dùng chung bởi luồng, khác với tiến trình ở việc tất cả đều được dùng riêng.
Các ưu điểm của luồng bao gồm:
Giảm thời gian chuyển ngữ cảnh [**Context switch]Các tài nguyên được cung cấp đồng thời giữa các luồng của cùng một tiến trình.Việc giao tiếp giữa các luồng luôn đạt hiệu quả cao [thay vì là tạo tiến trình con]Tiết kiệm chi phí hơn việc dùng đa tiến trình.Cho phép tận dụng hiệu quả hơn với vi xử lý hiện đại.Kết luậnVậy là mình đã xong phần thứ nhất của bài tìm hiểu cơ bản về hệ điều hành cũng như các hoạt động của nó. Ở phần thứ hai của bài viết, mình sẽ tiếp tục tìm hiểu và trình bày về các vấn đề như: Memory Management [Quản lý bộ nhớ], Input/Output Management [Quản lý vào/ra] và Virtualization [Công nghệ ảo hóa phần cứng]. Cảm ơn mọi người đã đọc bài viết ^^.