LinuxQuestions.org
Visit Jeremy's Blog.
Go Back   LinuxQuestions.org > Forums > Linux Forums > Linux - General
User Name
Password
Linux - General This Linux forum is for general Linux questions and discussion.
If it is Linux Related and doesn't seem to fit in any other forum then this is the place.

Notices


Reply
  Search this Thread
Old 08-29-2005, 11:42 PM   #1
asurya
LQ Newbie
 
Registered: Apr 2005
Posts: 10

Rep: Reputation: 0
Scheduling in Linux


Hi All,

I have a query regarding the scheduling in Linux.

After executing an ISR(Interrupt Service Routine), will the scheduler be invoked again to select a new kernel process to run or the process which is running when the interrupt has occurred is run again for the remaining time slice.

When a kernel process is interrupted by an interrupt, what will be the state of the kernel process when the interrupt service routine is being executed. Will it be in ready state or running state?

Is there any difference between the way scheduler is invoked after ISR in Linux 2.4 and 2.6.

Regards
Surya Santosh
 
Old 08-30-2005, 01:30 AM   #2
foo_bar_foo
Senior Member
 
Registered: Jun 2004
Posts: 2,553

Rep: Reputation: 53
it's easiest to talk in terms of one processor only not SMP so i will do that
first ~ i don't know that much about this stuff so don't take what i say as even remotely true !
and i will most likely ramble and not answer your question.
first thing to remember is that the interupt and the ISR are the last things that happen in the scenario where a device requests attention so the kernle tries to go imediately and handle the request.
in 2.4 after the ISR if the kernel determines a thread from a driver has been woken up and can run
the kernel sets the need_resched flag on the current process(this would be in the intuerupt handler or top half i think) then switches to kernel space
when the kernel gets to a point where scheduling is allowed it calls schedule()
latency here has to do with some blocks of kernel code that just don't offer oportunity for scheduling.
timeslice gets interupted i think when the context switches to kernel space.
the timeslice recalculation algorithm requires that all processes exhaust their timeslice before their new timeslices can be recomputed but i think that only effects what hapens in schedule() -- not sure..
the kernel is not real time or preemptive and scheduling occurs when scheduling occurs within the kernel code after context switch.

this is changed HUGELY in 2.6 -- 2.6 is a preemptive kernel on the way to a realtime OS.
many of the changes involve vastly improved SMP and new run ques per cpu instead of one master run que but the big change for what you are talking about is kernel preemption.
Now code in kernel space can be preempted by other processes. (some kernel code is of course locked from preemption but not much)(schedule() itself is locked from preemption) for scheduling i looked at 2.6.8.1 the version i am running
First the new schedular is very small and fast and cues are held outside of the schedular as priority arrays and runques. every 1ms a timer interupt calls schedular_tick() and anything in the inactive array (that is its slice has run out) will get picked right back up into the active array with it's new timeslice. I think when a process goes in the que like from a driver and signals a pending interupt all uninteruptible tasks are taken off the cue then the kernel just picks up the next task and when the interupt happens ISR sets TIF_NEED_RESCHED on the current process
the kernel once it determines a thread has woken up imediately runs schedule() and the woken up thread becomes next and TIF_NEED_RESCHED is cleared. this is if the new task isn't RT.
if it is RT i'm not sure how it works but it might not even go through schedule(). something for me to check out i guess

Last edited by foo_bar_foo; 08-30-2005 at 01:41 AM.
 
Old 08-30-2005, 10:07 AM   #3
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 9,352
Blog Entries: 4

Rep: Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334
As others have said, the 2.6 kernel scheduler is completely different and much simpler. The kernel is also partly interruptible.

But generally speaking it is the same: after the interrupt service routine(s) complete, control will return (however briefly) to the scheduler, which will then have the decision of whether to resume the previous task or to pre-empt it.

Most processes, that are now running and therefore are runnable, do not cease to be runnable as a result of an interrupt... but the scheduler may decide that they should no longer be running! If the interrupt just-received signaled the completion of a disk I/O operation that was requested by a higher priority process, the scheduler might well choose to switch control to that process. Or, it may not. "It depends." If pre-emption occurs, the current process will be placed back onto the run-queue since it is still runnable.

In the case of SMP, things can get very funky. CPU #1 might take the interrupt and schedule the high-priority task, but it may so-happen that the task currently has affinity to CPU #2, so the hipri task starts running on CPU #2 while CPU #1 resumes doing what it was doing. Meanwhile CPU #146...

Last edited by sundialsvcs; 08-30-2005 at 10:09 AM.
 
Old 08-30-2005, 11:28 PM   #4
foo_bar_foo
Senior Member
 
Registered: Jun 2004
Posts: 2,553

Rep: Reputation: 53
yea it all has to do with what is giong on
really this is a very hard thing because for different types of implementations you might want very different behaviour.
for desktop you really need to handle those interupts imediately mouse movement/clicks keyboard typing cd burning or video recording and stuff desktop users really expect this stuff to happen instantly or sooner not wait a minute i'm doing something else now.
the new priority arrays are very complex but new woken up threads get a little bonus in the decision
and drivers have to set interupt flags i think so the kernel just ignores funky somethings wrong with my hardware interupts
 
Old 08-30-2005, 11:33 PM   #5
asurya
LQ Newbie
 
Registered: Apr 2005
Posts: 10

Original Poster
Rep: Reputation: 0
From the explanation from the mails, it can be inferred that the scheduler will be invoked after executing an ISR. So, the process which is interrupted may or may not run immediately after ISR.

But in case of 2.4, interrupts use the same stack of the process, i.e as interrupts do not have a separate stack of their own, they use the stack of the process that got interrupted. So when the ISR is completed, the control should return back to the process that got interrupted as the same stack is being used by the interrupt.
As per my understanding, when an interrupt occurs, the registers which need to be saved and program counter of the kernel process that is interrupted are pushed on to the stack and the interrupt service routine is executed. So after the exection of ISR, the values pushed on to the stack need to be popped off into the Program counter and registers. After popping off, the Program counter contains the address of the instruction in Kernel process's code. Which means that kernel process will be run.

Please let me know if my understanding is wrong.

If this is not the scenario and scheduler is invoked, how the entire process is handled.

In case of 2.6, interrupts have a separate stack per processor and interrupts do not use the same stack as the kernel process that got interrupted. So when an interrupt has occurred, the registers and Program counter of the current kernel process are pushed on to the process's stack and the ISR is run which uses it's own stack. When the ISR execution is completed, scheduler can select a new process to be run based on the priority and the state of the process as kernel preemption is enabled.
 
Old 08-31-2005, 08:34 AM   #6
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 9,352
Blog Entries: 4

Rep: Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334Reputation: 3334
Have a look at e.g. arch/i386/kernel/irq.c & i8259.c. When an interrupt occurs, control is not transferred directly to the registered interrupt-handling routine nor directly back. Instead, look at handle_irq_event().

The kernel has to consider, not only the fact that there are different interrupts and different types of interrupts, but there may be multiple CPUs and etc. It's really quite complicated in its details ...

As described in e.g. DocBook/kernel-hacking.tmpl (for 2.4):
Quote:
Timer ticks, network cards and keyboards are examples of real hardware which produce interrupts at any time. The kernel runs interrupt handlers, which services the hardware. The kernel guarantees that this handler is never re-entered: if another interrupt arrives, it is queued (or dropped). Because it disables interrupts, this handler has to be fast: frequently it simply acknowledges the interrupt, marks a `software interrupt' for execution and exits.
Then:
Quote:
Whenever a system call is about to return to userspace, or a hardware interrupt handler exits, any `software interrupts' which are marked pending (usually by hardware interrupts) are run (kernel/softirq.c). Much of the real interrupt handling work is done here.
"Use the source, Luke!"
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
editing the linux cpu scheduling algo cathiejcm Linux - Software 1 11-11-2005 07:25 AM
linux scheduling problem lordofring Programming 2 08-30-2005 09:08 AM
switching Linux kernel I/O scheduling algorithms irfanhab Slackware 1 03-17-2005 11:53 AM
Process Scheduling in Linux Newbiegal Programming 6 10-04-2004 12:08 PM
Linux Scheduling Kumar Programming 3 06-14-2004 04:24 AM

LinuxQuestions.org > Forums > Linux Forums > Linux - General

All times are GMT -5. The time now is 09:45 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration