I want to know if longest remaining time first (LRTF) CPU scheduling has starvation or not. Also give reason how it starve/does not starve a process.
I know longest job first (LJF) may starve a process if all other incoming processes have longer CPU burst.
TLDR: Starvation is possible under some assumptions.
Without loss of generality let's assume that in tie situation of longest remaining time first (LRTF) algorithm we give CPU time to process with lowest ID.
Let's also assume that incoming processes IDs are always increasing.
Now let's consider two cases.
1) At some time there will be no new processess.
This is obvious because once new processess will stop arriving then eventually all processess will be executed, so no starvation.
2) New processess will never stop arriving.
Let's say that at time 0 all max time of process is $d$. In other words: $d=\max_{p\in\mathcal{P}}(t_p)$. Where $\mathcal{P}$ is set of processess and $t_i$ it remaining time of $i$'th process.
So now let's consider following scenario:
Adversary knows $d$ and that at time 0 there are $n$ processess, at each time unit adversary inserts new process with time $d+1$.
At time $1$ one of processess numbered $1...n$ (the one with time $d$) will consume one time unit. Then new process will arrive with time $d+1$ it will gain one time unit from scheduler. From now no of processess $1...n$ will gain CPU time, because all adversary processess will remain $d$ time units and newly arrived process will have prority over another.
There is on problem with this analysis. It assumes that there can be infinite number of processess in the system. In real operating systems this cannot be achieved.
Now let's assume that adversary doesn't know $d$. He might choose some constant $k>2$ and insert it's processess with that time. At some point in time which is equal to $\sum^{n}_{i=1}{\max(0, k-t_i)}$ adversary processess will starve all other procesess.
