Consider and operating system with a non-preemptive SJF schedule. If it is given a workload of say 10 processes, and each process performs a CPU burst which ranges from 10ms to 20ms followed by a 500ms I/O burst, will any of the processes experience starvation?
Working through this I know that the shortest process is scheduled first and whichever process is running will run to completion but I don't understand how to determine if any processes will be postponed due to a resource never being allocated given this information, I would like to know before continuing with it and I was wondering how I can tell given the workload and type of scheduler?
Consider and operating system with a non-preemptive SJF schedule. If it is given a workload of say 10 processes, and each process performs a CPU burst which ranges from 10ms to 20ms followed by a 500ms I/O burst, will any of the processes experience starvation?
If you define "starvation" as "perpetually not getting any CPU time"; then, with a "shortest job first" algorithm:
a) longer jobs will get starvation when shorter jobs are created faster than they complete (regardless of how many CPUs there are they literally can't keep up because new shorter jobs are being created too often).
b1) if the number of tasks that take an infinite amount of time exceeds the number of CPUs and none of the tasks block (e.g. wait for IO), or more processes will be starved of CPU time (unless you augment SJF with some some form of time sharing to avoid starvation among "always equal length" jobs).
b2) if the number of tasks that take an infinite amount of time exceeds the number of CPUs and some of the tasks do block (e.g. wait for IO), then whether starvation happens or not depends on "sum of time each process is not blocked".
If a SJF scheduler is given a workload of 10 processes and none of them are "infinite length", and no additional new processes are ever created; then all 10 tasks must complete sooner or later and none of the tasks will be perpetually waiting for a CPU.
Of course this doesn't mean some tasks won't have to wait (temporarily, briefly) for a CPU.
Note: for real systems, typically there are lots of infinite length tasks that do block (e.g. for both Windows and Linux, often there's over 100 processes running as services/daemons and for GUI); nobody knows how long any task will take (and not just because the speed of each CPU keeps changing due to power management - e.g. how long will the web browser you're using run for?); often nobody can know if a process will take an infinite amount of time or not (halting problem); and sometimes a process will accidentally loop forever due to a bug. In other words; "shortest job first" is almost always impossible to implement.