Least Slack Time (LST)
Least Slack Time (LST) is a dynamic priority-driven scheduling algorithm used in real-time
systems.
• In LST, all the tasks in the system are assigned some priority according to their slack
time. The task which has the least slack time has the highest priority and vice
versa.
• Priorities to the tasks are assigned dynamically
• Slack time can be calculated using the equation:
• slack_time = ( D - t - e' )
Here D : Deadline of the task t : Real time when the cycle starts. e' : Remaining
Execution Time of the task.
task which has the minimal slack time is dispatched to the CPU for its execution as it has the
highest priority. Hyper Period (HP) is the time period of the Gantt chart which is equal to the
LCM of the periods of all the tasks in the system. At time t, the slack of a task is equivalent to
( d-t ) minus the time required to complete the remaining portion of the task.
Example 1:
Example 2:
• At time t=0: Only task T1, has arrived. T1 is executed till time t=4.
• At time t=4: T2 has arrived. Slack time of T1: 33-4-6=23 Slack time of T2: 28-4-3=21
Hence T2 starts to execute till time t=5 when T3 arrives.
• At time t=5: Slack Time of T1: 33-5-6=22 Slack Time of T2: 28-5-2=21 Slack Time
of T3: 29-5-10=12 Hence T3 starts to execute till time t=13
• At time t=13: Slack Time of T1: 33-13-6=14 Slack Time of T2: 28-13-2=13 Slack
Time of T3: 29-13-2=14 Hence T2 starts to execute till time t=15
• At time t=15: Slack Time of T1: 33-15-6=12 Slack Time of T3: 29-15-2=12 Hence T3
starts to execute till time t=16
• At time t=16: Slack Time of T1: 33-16-6=11 Slack Time of T3:29-16-=12 Hence T1
starts to execute till time t=18 and so on..
POSIX (Portable Operating System Interface)
POSIX (Portable Operating System Interface) is a set of IEEE standards that define
how applications interact with operating systems. It provides a standard programming
interface mainly for UNIX-based systems, allowing programs to run on multiple operating
systems without modification.
POSIX ensures portability, compatibility, and reliability of applications across different
platforms such as Linux, UNIX, and macOS.
POSIX Standards
POSIX includes several important standards.
1. POSIX.1 – Core Services
Defines basic operating system functions such as:
• Process management
• File operations
• Input/Output handling
• Signal handling
These services provide the basic functionality required for application portability.
2. POSIX.1b – Real-Time Extensions
Supports real-time system features, including:
• Real-time scheduling
• Shared memory
• Message queues
• Semaphores
• High-resolution timers
These extensions are useful for embedded and real-time systems.
3. POSIX.1c – Thread Extensions
Introduces multithreading support through POSIX Threads (Pthreads).
Threads allow multiple tasks to execute concurrently within the same process.
POSIX Process Model
In POSIX:
• Each process runs in its own address space.
• Processes cannot directly access other processes' memory.
A new process is created using the fork() system call, which creates a child process
identical to the parent process.
Important POSIX System Calls
Function Purpose
fork() Creates a new process
exec() Executes a new program in a process
wait() Parent waits for child process
exit() Terminates a process
POSIX Real-Time Scheduling
POSIX supports real-time scheduling using functions such as:
sched_setscheduler()
Example scheduling policies:
• SCHED_FIFO – First-In First-Out scheduling
• SCHED_RR – Round Robin scheduling
• SCHED_OTHER – Default scheduling for non-real-time tasks
POSIX Synchronization Mechanisms
POSIX provides several mechanisms for process communication and synchronization.
1. Semaphores
Control access to shared resources.
Functions:
• sem_open()
• sem_wait()
• sem_post()
2. Shared Memory
Allows multiple processes to share memory space.
Functions:
• shm_open()
• mmap()
3. Message Queues
Used for communication between processes.
Functions:
• mq_send()
• mq_receive()
POSIX Program Example (Process and Thread)
The following program demonstrates POSIX process creation using fork() and thread
creation using pthread.
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
void* thread_function(void* arg)
{
printf("Thread running in process ID: %d\n", getpid());
return NULL;
}
int main()
{
pid_t pid;
pthread_t thread;
pid = fork(); // create child process
if(pid == 0)
{
printf("Child process ID: %d\n", getpid());
pthread_create(&thread, NULL, thread_function, NULL);
pthread_join(thread, NULL);
}
else
{
printf("Parent process ID: %d\n", getpid());
pthread_create(&thread, NULL, thread_function, NULL);
pthread_join(thread, NULL);
}
return 0;
}
Program Explanation
1. fork()
o Creates a new process called the child process.
2. pthread_create()
o Creates a new thread within the process.
3. pthread_join()
o Waits for the thread to finish execution.
Thus, both parent and child processes create and execute threads simultaneously.
Advantages of POSIX
1. Provides portable applications across operating systems
2. Supports multithreading
3. Provides real-time scheduling
4. Supports interprocess communication mechanisms
5. Ensures standardized OS interfaces