Mar 26
Managing Time with CPU Real-Time Scheduling Algorithm
“If only I had more time, I am sure that I can spend it with you,” said Luke to his girlfriend, Sarah. “No, we all have the same amount of time. It is just you who did not make your time for me!” Sarah replied. Luke froze and no words came out of his mouth. His empty eyes watching Sarah went away, drowning him in regrets.
Don’t we all have the same problem as Luke? No, not the girlfriend or boyfriend thing, but the time management one. I believe we all have experienced difficulties in managing time. This may or may not leave us with consequences and regrets later on. But, do you know that computers also need to effectively manage their time?
Before going on, let me explain some of the terms and basic concepts in operating systems. In utilizing resources, computer scientists have an objective called multiprogramming. The multiprogramming means that the CPU needs to have some process to execute most of the time (it should not be chilling!).
The idea of multiprogramming is simple. If a process needs to wait for some external requests (e.g I/O request), the CPU will suspend the process, and put it in the waiting queue until it is ready again. But, while waiting, the CPU will execute another process in the ready queue. Hence, the CPU will not be sitting idle, waiting indefinitely for I/O from another party.
The concept is basically the same for us. We will take this analogy: CPU as us, the person, and processes are our tasks. When we want to finish all of our assignments, we utilize our energy, skills, and time as much as we can. We can try to maximize this by using a CPU scheduling algorithm.
There are a lot of CPU scheduling algorithms, but this algorithm is the one that is working for me lately. It is intuitive, though. The algorithm is taken from real-time CPU scheduling called Earliest-Deadline-First (EDF). From its name, you can guess how it works, don’t you?
EDF scheduling assigns priorities dynamically according to the deadline and time to finish the process. The earlier the deadline, the faster you should execute it. However, when two or more processes have the same deadlines, do which one with the shortest time to finish. Furthermore, if both the deadlines and time to finish are the same, pick using FCFS (first come, first served) algorithm. In the real-world case, you can add your own priority criteria to your processes.
Note that the EDF algorithm is preemptive. When a new process comes with higher priority, you should stop whatever you are doing right now and start executing the new process.
Theoretically, the EDF scheduling algorithm is very efficient, compared to other real-time scheduling algorithms. That being said, we do not have energy all the time, don’t we? Therefore, we may need to stop processing one task, take a break, and start another one (in CPU, it can be called context switching). Hence, 100% efficiency in the EDF algorithm is hard to achieve in practice since it is less predictable — we never plan to run out of energy, right?
However, afraid not, since we still can achieve relatively high efficiency in utilizing our resources. My advice is to add some modifications to your algorithm. For instance, when a task is impossible to finish before the deadline, leave it alone and move on to another one. This will avoid the unwanted domino effect (when all processes miss their deadlines).
Let us go back to Luke’s problem. From my explanation, it seems that he can try to fix his time management by implementing the EDF algorithm in his scheduling. Even so, he needs to add his own priority criteria, though! Luke can give higher priority to the things he finds important. I am sure he will be able to make time for his future wife. ;)
Good luck to Luke and us! May we find a way to spend our time wisely. It is not about doing a lot of (unnecessary) jobs. But, it is about doing whatever is important to us, whether it is family, girlfriend/boyfriend, or yourself.
References: Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts 10th edition. Hoboken, NJ: Wiley.
