Round-robin (RR) is one of the simplest scheduling algorithms for processes in an operating system, which assigns time slices to each process in equal portions and in order, handling all processes without priority. Round-robin scheduling is both simple and easy to implement, and starvation-free. Round-robin scheduling can also be applied to other scheduling problems, such as data packet scheduling in computer networks.
The name of the algorithm comes from the round-robin principle known from other fields, where each person takes an equal share of something in turn.Round-robin (RR) is one of the simplest scheduling algorithms for processes in an operating system, which assigns time slices to each process in equal portions and in order, handling all processes without priority. Round-robin scheduling is both simple and easy to implement, and starvation-free. Round-robin scheduling can also be applied to other scheduling problems, such as data packet scheduling in computer networks.
The name of the algorithm comes from the round-robin principle known from other fields, where each person takes an equal share of something in turn.
Monday, August 4, 2008
context switch
A context switch (also sometimes referred to as a process switch or a task switch) is the switching of the CPU (central processing unit) from one process or thread to another. A context is the contents of a CPU's registers and program counter at any point in time. A register is a small amount of very fast memory inside of a CPU (as opposed to the slower RAM main memory outside of the CPU) that is used to speed the execution of computer programs by providing quick access to commonly used values, generally those in the midst of a calculation. A program counter is a specialized register that indicates the position of the CPU in its instruction sequence and which holds either the address of the instruction being executed or the address of the next instruction to be executed, depending on the specific system. Context switching can be described in slightly more detail as the kernel (i.e., the core of the operating system) performing the following activities with regard to processes (including threads) on the CPU: (1) suspending the progression of one process and storing the CPU's state (i.e., the context) for that process somewhere in memory, (2) retrieving the context of the next process from memory and restoring it in the CPU's registers and (3) returning to the location indicated by the program counter (i.e., returning to the line of code at which the process was interrupted) in order to resume the process.
Dispatcher
Dispatchers are communications personnel responsible for receiving and transmitting pure and reliable messages, tracking vehicles and equipment, and recording other important information.[1] A number of organizations, including police and fire departments, emergency medical services, taxicab providers, trucking companies, train stations, and public utility companies, use dispatchers to relay information and coordinate their operations. Essentially, the dispatcher is the "conductor" of the force, and is responsible for the direction of all units within it.
Thread
A thread in computer science is short for a thread of execution. Threads are a way for a program to fork (or split) itself into two or more simultaneously (or pseudo-simultaneously) running tasks. Threads and processes differ from one operating system to another but, in general, a thread is contained inside a process and different threads in the same process share some resources while different processes do not.
On a single processor, Multithreading generally occurs by time-division multiplexing ("time slicing") in very much the same way as the parallel execution of multiple tasks (computer multitasking): the processor switches between different threads. This context switching can happen so fast as to give the illusion of simultaneity to an end user. On a multiprocessor or multi-core system, threading can be achieved via multiprocessing, wherein different threads and processes can run literally simultaneously on different processors or cores.
On a single processor, Multithreading generally occurs by time-division multiplexing ("time slicing") in very much the same way as the parallel execution of multiple tasks (computer multitasking): the processor switches between different threads. This context switching can happen so fast as to give the illusion of simultaneity to an end user. On a multiprocessor or multi-core system, threading can be achieved via multiprocessing, wherein different threads and processes can run literally simultaneously on different processors or cores.
process
In computing, a process is an instance of a computer program that is being sequentially executed[1] by a computer system that has the ability to run several computer programs concurrently.
A single computer processor executes one or more (multiple) instructions at a time (per clock cycle), one after the other (this is a simplification; for the full story, see superscalar CPU architecture). To allow users to run several programs at once (e.g., so that processor time is not wasted waiting for input from a resource), single-processor computer systems can perform time-sharing. Time-sharing allows processes to switch between being executed and waiting (to continue) to be executed. In most cases this is done very rapidly, providing the illusion that several processes are executing 'at once'. (This is known as concurrency or multiprogramming.) Using more than one physical processor on a computer, permits true simultaneous execution of more than one stream of instructions from different processes, but time-sharing is still typically used to allow more than one process to run at a time. (Concurrency is the term generally used to refer to several independent processes sharing a single processor; simultaneity is used to refer to several processes, each with their own processor.) Different processes may share the same set of instructions in memory (to save storage), but this is not known to any one process. Each execution of the same set of instructions is known as an instance— a completely separate instantiation of the program.
A single computer processor executes one or more (multiple) instructions at a time (per clock cycle), one after the other (this is a simplification; for the full story, see superscalar CPU architecture). To allow users to run several programs at once (e.g., so that processor time is not wasted waiting for input from a resource), single-processor computer systems can perform time-sharing. Time-sharing allows processes to switch between being executed and waiting (to continue) to be executed. In most cases this is done very rapidly, providing the illusion that several processes are executing 'at once'. (This is known as concurrency or multiprogramming.) Using more than one physical processor on a computer, permits true simultaneous execution of more than one stream of instructions from different processes, but time-sharing is still typically used to allow more than one process to run at a time. (Concurrency is the term generally used to refer to several independent processes sharing a single processor; simultaneity is used to refer to several processes, each with their own processor.) Different processes may share the same set of instructions in memory (to save storage), but this is not known to any one process. Each execution of the same set of instructions is known as an instance— a completely separate instantiation of the program.
TIME SLICE:
1. With a multi-user system, a time-slice is the set amount of processing time each user gets.
2.With a single-user system, a time-slice is the set amount of processing time each program gets.
2.With a single-user system, a time-slice is the set amount of processing time each program gets.
CPU Scheduler
We had much experience for waiting. Recently, in bank, we get a unique number entering the bank. There several line processing at the same time. Once the number flip, somebody will be served. A small version of same thing happens on our operating system. Lots of process standby for being served. The main difference was we have just one cpu at most time. For simplicity, we also consider the situation with one cpu which mean there is always one process being served at one time.
Short-term scheduler , a intermediator for dispatching a process to use the cpu resource. One choose a process from free-memory and one from secondary storage device to memory is the difference between short-term scheduler and long-term scheduler(also called job scheduler).
Activity of process of the operatiing system exist all the time. However, there is only one cpu can be used. Therefore a process can be run at one time.The way directly perceived through the senses and simplist is first in first serve which means one process one by one served by cpu a time until no one is waiting.Forgeting bank number will cause a seriel wait when he need call for his family for help. Part of service of next people can proceed to shorten total waiting time.
A lot of scheduling method be brought up like Round-Rubin , FCFS(First come first serve), SJF(Shortest Job First) , Multilevel feedback queue scheduling.I implemented four of them in Java with fully architecture include virtual cpu, virtual timing.
Short-term scheduler , a intermediator for dispatching a process to use the cpu resource. One choose a process from free-memory and one from secondary storage device to memory is the difference between short-term scheduler and long-term scheduler(also called job scheduler).
Activity of process of the operatiing system exist all the time. However, there is only one cpu can be used. Therefore a process can be run at one time.The way directly perceived through the senses and simplist is first in first serve which means one process one by one served by cpu a time until no one is waiting.Forgeting bank number will cause a seriel wait when he need call for his family for help. Part of service of next people can proceed to shorten total waiting time.
A lot of scheduling method be brought up like Round-Rubin , FCFS(First come first serve), SJF(Shortest Job First) , Multilevel feedback queue scheduling.I implemented four of them in Java with fully architecture include virtual cpu, virtual timing.
CONTEXT SWITCH-SOME POINTS
A context switch (also sometimes referred to as a process switch or a task switch) is the switching of the CPU (central processing unit) from one process or thread to another.Context switching is an essential feature of multitasking operating systems. A multitasking operating system is one in which multiple processes execute on a single CPU seemingly simultaneously and without interfering with each other.
ACTIVITES OF CONTEXT SWITCH:
Context switching performing the following activities with regard to processes (including threads) on the CPU
(1) suspending the progression of one process and storing the CPU's state (i.e., the context) for that process somewhere in memory.
(2) retrieving the context of the next process from memory and restoring it in the CPU's .
(3) returning to the location indicated by the program counter (i.e., returning to the line of code at which the process was interrupted) in order to resume the process.
(4)A context switch can also occur as a result of a hardware interrupt.
ACTIVITES OF CONTEXT SWITCH:
Context switching performing the following activities with regard to processes (including threads) on the CPU
(1) suspending the progression of one process and storing the CPU's state (i.e., the context) for that process somewhere in memory.
(2) retrieving the context of the next process from memory and restoring it in the CPU's .
(3) returning to the location indicated by the program counter (i.e., returning to the line of code at which the process was interrupted) in order to resume the process.
(4)A context switch can also occur as a result of a hardware interrupt.
Saturday, August 2, 2008
Multilevel Queue Scheduling
A multilevel queue scheduling algorithm partitions the ready queue in several separate queues, for instance
In a multilevel queue scheduling processes are permanently assigned to one queues.
The processes are permanently assigned to one another, based on some property of the process, such as
Memory size
Process priority
Process type
Algorithm choose the process from the occupied queue that has the highest priority, and run that process either
Preemptive or
Non-preemptively
Each queue has its own scheduling algorithm or policy.
Possibility I If each queue has absolute priority over lower-priority queues then no process in the queue could run unless the queue for the highest-priority processes were all empty.
For example, in the above figure no process in the batch queue could run unless the queues for system processes, interactive processes, and interactive editing processes will all empty.
Possibility II If there is a time slice between the queues then each queue gets a certain amount of CPU times, which it can then schedule among the processes in its queue. For instance;
80% of the CPU time to foreground queue using RR.
20% of the CPU time to background queue using FCFS.
Since processes do not move between queue so, this policy has the advantage of low scheduling overhead, but it is inflexible.
In a multilevel queue scheduling processes are permanently assigned to one queues.
The processes are permanently assigned to one another, based on some property of the process, such as
Memory size
Process priority
Process type
Algorithm choose the process from the occupied queue that has the highest priority, and run that process either
Preemptive or
Non-preemptively
Each queue has its own scheduling algorithm or policy.
Possibility I If each queue has absolute priority over lower-priority queues then no process in the queue could run unless the queue for the highest-priority processes were all empty.
For example, in the above figure no process in the batch queue could run unless the queues for system processes, interactive processes, and interactive editing processes will all empty.
Possibility II If there is a time slice between the queues then each queue gets a certain amount of CPU times, which it can then schedule among the processes in its queue. For instance;
80% of the CPU time to foreground queue using RR.
20% of the CPU time to background queue using FCFS.
Since processes do not move between queue so, this policy has the advantage of low scheduling overhead, but it is inflexible.
DIFFERENCES BETWEEN PREEMPTIVE AND NON-PREEMPTIVE
Non-Preemptive: Non-preemptive algorithms are designed so that once a process enters the running state(is allowed a process), it is not removed from the processor until it has completed its service time ( or it explicitly yields the processor). context_switch() is called only when the process terminates or blocks.
Preemptive: Preemptive algorithms are driven by the notion of prioritized computation. The process with the highest priority should always be the one currently using the processor. If a process is currently using the processor and a new process with a higher priority enters, the ready list, the process on the processor should be removed and returned to the ready list until it is once again the highest-priority process in the system
Non-Preemptive: Non-preemptive algorithms are designed so that once a process enters the running state(is allowed a process), it is not removed from the processor until it has completed its service time ( or it explicitly yields the processor). context_switch() is called only when the process terminates or blocks.
Preemptive: Preemptive algorithms are driven by the notion of prioritized computation. The process with the highest priority should always be the one currently using the processor. If a process is currently using the processor and a new process with a higher priority enters, the ready list, the process on the processor should be removed and returned to the ready list until it is once again the highest-priority process in the system.
Subscribe to:
Posts (Atom)