[완료] CPU scheduling 자세한 경우를 설명 좀 해주세요.
글쓴이: APRIL1024 / 작성시간: 토, 2007/04/21 - 8:54오후
CPU-scheduling decisions may take place under the following four circumstances:
1. running -> waiting
2. running -> ready
3. waiting -> ready
4. terminates
위 경우 중 2,3 일 때, CPU-scheduling이 일어날 때 preemptive scheduling이라고 책에 설명되어 있습니다.
2,3 자세한 예제 좀 들어 주세요. 특히, 3번에서 왜 스케쥴링이 일어나야 하는지 모르겠어요. 그냥 레디큐에 들어가면 되는데..
설명 부탁드립니다.
Forums:
프로세스가 어떤
프로세스가 어떤 이벤트가 일어날때까지 할일이 없을 때는 CPU time을 낭비할 필요가 없으니 sleep 상태로 들어갑니다. 그러다 원하던 이벤트가 발생해서 커널이 자던 프로세스를 깨우면 그제서야 벌떡 일어나서 다시 일하러 레디큐에 들어가는 것이죠. 자세한 사례는 다음 분에게 양보..;
대충
대충 예를들어드리면, 어떤 프로세스가 100M의 데이터를 전송받으려고 한다고 가정해봅시다.
100M가 모두 전송되기 전에는 다음 단계로 갈수 없습니다.
그럼, 먼저 100M가 필요한 부분에서 프로세스는 waiting 큐에 들어가게 되고, OS가 어딘가에다가 100M를 저장할 것입니다. 전송이 완료되면 OS측에서 당신은 ready 큐에 들어갈 수 있다고 알려주어야 ready 큐에 들어가게 되는겁니다.
그럼, waiting 큐를 사용하지 않고, 모든 프로세스가 ready 큐에 들어간다고 가정해 봅시다.
이 경우, 위 예에서 전송이 완료되지 않았음에도 불구하고 프로세스가 실행권한을 획득할 수 있을 것입니다.
그러나, 프로세스는 힘들게 실행권한을 얻었지만 다음으로 진행할 수 없기때문에 더 기다려야 하고, 불필요한 context change가 일어나겠지요.
결론을 말씀드리면, ready 큐에는 필요한 모든 자원을 할당받고, 당장 수행될 수 있는 프로세스만이 들어갑니다.
이해 됐습니다.
감사드립니다.
어떤 프로세스가 CPU
2의 경우)
어떤 프로세스가 CPU 위에서 돌다가 ready 상태로 가는 예로는 배정 받은 time slice 를 모두 사용해서, 스케줄러에 의해 내려지는 경우입니다. 그래서 preemtive scheduling 인 것이죠. 스스로 CPU 를 놓지 않았음에도 강제적으로 ready 상태가 된 것이니까요. 만약 스케줄러가 선점형이 아니라면, 2 와 같은 스케줄링은 일어나지 않습니다.
3의 경우)
어떤 프로세스가 여러 원인으로 인해 wait queue 에 들어갔다가, 더 이상 wait 할 필요가 없어서 ready queue 에 들어가는 경우입니다. 수 많은 예가 있겠지만, 입출력을 끝나기를 기다리다가 깨어나는 경우가 대표적이겠네요.
이 경우 왜 스케줄링이 일어나냐고 하셨는데, 스케줄링이 일어나지 않아도 상관 없습니다. 다만 새로운 ready 상태의 프로세스가 생겼는데 스케줄러가 불리지 않는다면, 이 스케줄러는 실시간 성이 떨어진다고 볼 수 있습니다. 만약 현재 running 중인 프로세스의 우선순위가 지금 막 ready 상태로 바뀐 프로세스의 우선순위보다 더 낮다고 가정해 봅시다. 이런 상황에서 wait->ready 로 바꼈을 때 스케줄러가 불리지 않는다면, 현재 running 중인 프로세스의 우선순위가 더 낮음에도 그대로 계속 실행되게 됩니다. 따라서 실시간 성이 떨어지죠.
3의 경우가 preemtive 한 이유는 wait 상태의 프로세스가 ready 상태로 전환할 때 레디큐에 들어가고 끝이라면 현재 running 상태의 프로세스는 CPU 를 내놓지 않습니다. 반면 스케줄러가 불리게 되면 running 상태의 프로세스는 스스로 CPU 를 내놓지 않더라도, CPU 를 내주게 되죠.
ps: 답글 쓰는 도중에 답글이 달렸군요 ㅜㅜ
* 한번 수정했습니다.
처음에 제가 질문을
처음에 제가 질문을 잘못 이해했군요. 아직 원하시는 답변이 나오지 않은 것 같은데 [완료]라고 달려서 당황스럽기도 합니다;;
3번 경우를 이해를 못하시는 이유는 'CPU-scheduling decisions may take place...'라는 부분을 잘못 이해하셨기 때문입니다. 위의 4가지 경우는 실제 scheduling이 일어나는 경우를 얘기한게 아니라 scheduling decision이 일어나는 경우를 말합니다. 즉 scheduling이 필요한지 아닌지 결정이 나는 상황을 말합니다. 1,2,4번의 경우는 곧 scheduling이 필요하다는 것을 한눈에 알 수 있을 겁니다. 3번의 경우가 좀 색다른데, sleep 상태에서 깨어난 process는 sleep 상태에 들어가게된 이유에 따라 현재 process보다 우선 순위가 낮을 수도 높을 수도 있습니다. 실제 scheduling이 필요한 경우는 현재 process보다 우선 순위가 높을 경우일 뿐이겠죠. 그래서 wakeup 과정에서 현재 돌아가는 process와 우선 순위 비교후 scheduling이 필요한 경우에만 scheduler flag에 표시를 해서 다음 scheduling이 가능할 때 schedule 알고리즘이 실행되도록 합니다. 즉, wakeup 과정에서 즉시 scheduling이 일어나는 것이 아닙니다. 만일 매번 scheduler가 돌아가게 만든다면 resource 낭비겠죠.
preemptive scheduling이라는 것은 CPU time slice를 받을 process의 우선 순위를 process가 아닌 kernel이 전적으로 관리한다는 의미입니다. 2번의 경우는 이해 되실테고, 3번의 경우는 sleep 상태에 들어가면서 sleep 하게된 이유에 따라 우선순위가 정해진다고 말씀드렸는데 이 우선순위를 결정하는 주체가 kernel이기 때문에 preemptive scheduling이 되는 것입니다.
음 제 생각이랑 좀
음 제 생각이랑 좀 차이가 나는 것 같아서 질문 드리겠습니다.
이 문제는 커널의 구현에 따라서 다르지 않을까요? 언급하신 대로 커널을 구현되어도 상관은 없지만, wakeup 과정에서 스케줄러를 부르는 것에 비해서 실시간 성이 떨어질 것 같습니다만. "다음 스케줄링이 가능할 때"가 스케줄러가 어떤 방식이냐에 따라서 달라지기 때문입니다. 예를 들어 언급하신 대로의 커널이고 비선점형 커널이면 "다음 스케줄링이 가능할 때"는 현재 실행중인 프로세스 스스로가 CPU 를 놓을 때 입니다. time-slice 에 의해서 선점가능한 스케줄러라고 해도 현재 실행 중인 프로세스가 time-slice 를 다 쓰기 전까 지는 무조건 기다려야 되죠. 리소스 낭비이긴 하지만 커널에 따라서 리소스 낭비를 부담하고서라도 실시간 성이 보장되어야 하는 경우가 있지 않나요?
선점형 스케줄링을 이렇게 정의하면, 비선점형 스케줄링은 CPU time slice 를 받을 process 의 우선 순위를 process 가 관리한다는 것인데 무슨 의미인지가 저로서는 애매하네요. 그리고 비선점형 스케줄링의 경우도 우선 순위를 커널이 관리하는 경우가 있지 않나요? 리눅스도 비선점형 커널이던 때가 있었는데, 그렇다고 그 시절의 리눅스가 CPU time slice 를 받을 process 의 우선 순위를 커널이 결정하지 않았다고 보기는 힘들지 않을까요? 선점형 스케줄링의 일반적인 의미가 (일반적으로 커널 모드에서) 실행중인 프로세스가 스스로 CPU 를 내놓지 않더라도, 다른 프로세스가 CPU 를 가로챌수(선점할 수) 있다는 것으로 지금까지 알고 있어서 질문드립니다.
* 한 번 내용상의 수정이 있었습니다.
그렇게 구현되어도
그렇게 구현되어도 상관없는게 아니라 UNIX 커널은 실제로 그렇게 설계되고 구현되어 있습니다. '다음 scheduling이 가능한 때'를 잘못 이해하신 거 같군요. scheduling이 가능한 때는 kernel mode에서 user mode로 들어갈 때를 말합니다. 3번의 경우 scheduling이 필요하다고 결정이 되면 time slice를 다 사용하지 않았더라도 현재 프로세스가 kernel mode에서 user mode로 전환될때 scheduling이 일어나고 context switch가 됩니다. 실시간성이 뭘 의미하는 지는 모르겠지만, scheduling이 필요할 때에 scheduling이 일어납니다. 다시 한번 강조하지만 이 경우 scheduling decision과 실제 scheduling이 일어나는 시점은 다르다는 것이죠.
preemptive scheduling에 관한 글은 '우선순위'라는 말 때문에 확실히 부정확하게 되버렸군요. 다시 적자면, 'preemptive scheduling이라는 것은 CPU time slice를 받을 process를 process가 아닌 kernel이 전적으로 관리한다는 의미입니다'. 이러기 위해서는 필요한 경우에 kernel이 돌아가던 process를 preempt 할수 있어야 하고 그 우선 순위를 kernel이 관리해야 하는 것이죠.
정확하게 얘기하자면, process는 항상 kernel mode에서 user mode로 넘어가는 도중에 preempt 됩니다. preempt되었던 process가 다시 실행될때는 항상 user mode에서 시작하게 되죠.
음.. 제가 알고 있는
먼저, 그리고 preemtive schduling 에 대한 이야기는, 제가 preemtive kernel 이야기랑 헷갈렸습니다. 죄송합니다. 이놈의 선점형은 몇년이 지나도록 헷갈리네요.
전통적인 비선점형 유닉스의 구현이 보통 님께서 언급한 대로 아니던가요? Bach 책에 잘 나오는 방식으로요. 요즘 대부분의 유닉스는 선점형 커널이므로 바로 스케줄링 해버리는 경우도 많습니다. 스케줄링이 커널 모드에서 유저 모드로 넘어갈 때 일어나게 만드는 이유가, 커널 모드에서 실행중인 프로세스를 중간에 다른 프로세스가 선점하지 못하게 비선점형으로 커널을 디자인 하면 훨씬 간단해지므로 전통적인 유닉스들이 이런 방식을 채택했었던 것으로 알고 있습니다. 드리고 싶은 말씀은 어디까지나 구현에 따라서 다르다는 것입니다.
예를 들어 어떤 프로세스 A가 커널 모드에서 CPU 를 잡고 실행 중일 때, 인터럽트가 걸려서 어떤 프로세스 B가 ready 상태가 되었다고 합시다. 그리고 A의 우선 순위가 B의 우선 순위보다 낮다고 하구요. 이럴 경우 님께서 언급하신 대로 스케줄러한테 알려주기만 하고, 현재 실행중인 프로세스A가 커널 모드에서 유저 모드로 전환되는 과정에서 B로 스케줄링이 일어나면, 이는 전형적인 비선점형 커널입니다. 만약 선점형 커널이라면 커널 모드에서 실행중인 프로세스 A 한테서 CPU 를 바로 뺐어서 B가 실행 될 수 있어야 합니다. 실시간성이 떨어지는 이유는 B의 우선순위가 높음에도 A가 커널 모드에 있다는 이유만으로 A가 계속 실행되기 때문이죠. 따라서 구현에 따라서 달라지지 않을까 하는게 제 생각입니다.
* 내용 여섯 번 수정했습니다.;;;
아하, 이제 무슨
아하, 이제 무슨 얘기를 하고 싶어 하는지 알겠습니다. user level preemption, kernel level preemption model 얘기를 하고 싶었던 거군요. 선점형 커널, 비선점형 커널이란 용어는 불필요한 오해를 불러오니 user level preemption, kernel level preemption(이하 ULP, KLP)란 용어를 쓰겠습니다.
일반적으로 사용하는 전형적인 kernel은 ULP model 입니다. KLP가 등장하게된 이유는 정해진 시간안에 반드시 응답이 와야하는 realtime 환경의 필요성 때문입니다. ULP model에서는 SYSCALL의 실행이 완료되고 다시 user mode로 넘어 갈때 process가 preempt되는데, 이때 실행되는 SYSCALL이 반드시 realtime 환경이 원하는 만큼 짧은 시간안에 끝난다는 보장이 없습니다. 이 문제를 해결하기 위해서 KLP model에서는 SYSCALL 사이 사이 preemption point를 삽입해서 SYSCALL 중간 중간 scheduling이 필요한 상황이 발생했는지 확인하고, 필요할 때에는 scheduling을 하는 것이죠. 이해에 유의할 점은 KLP model 역시 필요하다고 해서 scheduling이 바로바로 일어나는 게 아니라 정해진 preemption point에서만 일어난다는 점입니다. 정확한 표현은 아니지만 이해를 돕기위해 얘기하자면, ULP model은 preemption point가 SYSCALL이 끝나는 지점에 있는데 반해 KLP model은 빠른 응답을 위해서 SYSCALL 중간 중간에도 존재하고 있는 것이죠.
요즘 대부분의 유닉스가 KLP model이라니 믿기 힘든데 참고 문헌 있으면 좀 알려 주시겠습니까? 리눅스도 Realtime 환경에서의 요구가 많아지자 그런 환경에서도 쓸 수 있도록 패치되서 KLP mode로 컴파일 가능하게 된것이지 기본 컴파일 옵션은 ULP mode로 알고 있거든요. SYSCALL이 잘리기 때문이 KLP model로 커널 만드려면 제한 사항도 많을 뿐 아니라 SYSCALL 디자인이나 여러가지 면에서 복잡하고 유지 보수도 까다로운 걸로 압니다. (RTOS는 전공분야도 아니고 관심분야도 아니니 구체적인 내용은 묻지 마세요;) 이런 단점에도 불구하고 일반 데스크탑이나 서버용 OS를 별 이득없는 KLP model로 만들리는 없을 거 같군요.
뭐 어쨌거나 ULP model이건 KLP model이건 간에 scheduling decision이 일어나는 지점과 실제 scheduling이 일어나는 지점이 다르다는 건 이해하셨을 거라 봅니다. 오프토픽에다 서로 잘 모르는 얘기는 그만 하는게 좋을 거 같군요.
확실히 ULP, KLP 라는
확실히 ULP, KLP 라는 표현이 더 나아 보이는군요. :) 그런데 요즘 운영체제 중에 ULP 가 안되는 경우는 거의 없다는 것을 말씀드리고 싶습니다. 그래서 제가 선점형 스케줄링이라는 단어를 썼을 때는 KLP 를 염두에 뒀었구요.
리눅스는 말씀하신대로 KLP 가 정식 커널 트리에 들어간 지는 오래되었습니다. FreeBSD 는 http://www.freebsd.org/features.html 대문에 kernel preemtion 된다고 써있구요. Solaris 2.x 경우에는 Unix Internals pp131. 에 "The solaris 2.x kernel is fully preemptive,..." 라고 되어 있습니다. 그리고 일반 데스크탑이나 서버용 OS 인 Windows 는 NT 시절부터 KLP 가 된 것으로 알고 있습니다. 참고 문헌으로 Tannenbaum, Modern Operating System pp804 에 "... Windows 2000 is fully preemtive..." 라고 되어 있네요.
이 정도면 적어도 대부분의 운영체제는 KLP 가 불가능하다고 보기는 힘들지 않을까요?
요즘 환경이 멀티 프로세서 하드웨어가 일반적으로 보급되고, 멀티미디어가 일반화가 되어서 일반적인 운영체제도 KLP 가 필요한 경우가 많다고 알고 있습니다.
그리고 KLP 이 필요한 또 다른 이유 중의 하나가 커널 쓰레드(=커널 모드에서만 돌아가고, 커널 주소 영역만을 가지는 쓰레드) 때문입니다. ULP 만 가능하다면 커널 쓰레드들은 전부 스스로 scheduler 를 불러야만 합니다.
ULP와 KLP 공히 preemtion 여부를 결정하는 곳은 일반적으로 타이머를 포함한 ISR 이 됩니다. 심지어 modern operating system 에서 preemtive scheduling 에 대해서 설명할 때 scheduling decision 이 타이머 ISR 에서 일어나느냐의 여부에 달려 있다고 까지 쓰고 있습니다. ULP 와 KLP 의 차이는 여기서 스케줄링을 커널 모드 수행이 끝날 때까지 미루느냐 아니면 바로 preemt 하느냐의 차이라고 할 수 있지 않을까요? 물론 바로라는 말 자체가 일반적으로 ISR 에서 커널 모드로 돌아오는 순간에 스케줄링이 일어난다는 뜻이지만요.
제가 처음에 질문을 드린 이유 중 하나가 3)은 "scheduling decision 이 일어나는 지점과 실제 scheduling이 일어나는 지점이 다르기 때문에 3)의 경우 scheduling decision 만 일어난다가" 아니라, "3)의 경우에 스케줄링이 일어나야 preemtive scheduling 인 것이다" 같아서 질문을 드린 것입니다. 3)의 경우 스케줄링이 안 일어나면 그냥 스케줄러가 비선점형인 것 뿐이지 않을까요?
질문자께서 인용하신 부분에도 "...may take place..." 라고 하였고, 그 뒤의 문장에도 "When scheduling takes place only under circumstances 1 and 4, we say that the scheduling scheme is nonpreemtive or cooperative; otherwise it is preemtive" 라고 되어 있습니다. 즉 3)의 경우에 구현에 따라서 schd. decision 이 일어나지 않아도 된다는 말씀을 그래서 드렸던 것입니다. 게다가 3)의 경우 스케줄링이 일어나지 않고 2)의 경우만 일어나도 선점형 스케줄링이라고 볼 수 있지 않을까요? (그리고 scheduling decision 이 아닌 scheduling 이라고 되어 있기도 하구요.)
대부분의 구현에서 스케줄링 자체와 schd. decision 이 따로 일어나는 것은 맞습니다만, 제가 드리고 싶은 질문은 구현하기에 따라서 달라질 수 있지 않을까 입니다. 예를 들어 스케줄링 자체와 schd. decision 이 동시에 일어나는 구현도 불가능해 보이지는 않아서요.
* 내용 상 수정이 한번 있었습니다 ;;
wish 씀: 리눅스는
KLP mode가 기본으로 돌아가는 건지 아니면 지원을 한다는 건지는 확인해 봐야겠지만 KLP가 지원되는 건 확실해 보이는군요. 멀티미디어 얘기는 일리가 있습니다. 멀티미디어 재생이 특정시간안에 응답이 와야하는 realtime 요소가 있으니까요. OS 공부한지도 제법 되고, 그때 공부한 책도 오래된 책들이라 그 당시랑 환경이 많이 차이가 나네요.
아닙니다.
제가 했던 얘기가 완전 무용지물이 됬군요. KLP라고 해서 바로 scheduling이 일어나는게 아니라 preemption point에서 일어난다고 위에 써 놓았지 않습니까? 이 말이 이해가 안가거나 틀리다고 생각되거든 계속 같은말 하지말고 책이나 자료 찾아서 확인하고 근거를 대주세요.
3의 경우 scheduling이 필요하면 ULP의 경우 현재 process가 kernel mode를 벗어날때, KLP의 경우 다음 preemption point에 일어난다고 적어놨는데 제가 쓴 글이 그렇게 이해가 안되시나요? 정말 답답하네요.
뭐 scheduling 필요하다고 굳이 표시하지 않아도 ready queue에 들어가 있으니 다음 time interrupt에 2번 경우가 되서 scheduler 돌아가겠죠. 그런데 그거 참 궁금하네요. 그렇게 하지 않을 이유가 도대체 어디있나요? 현재 process하고 우선 순위 비교해서 필요하면 scheduling 필요하다고 flag 표시만 하면 되는 간단한 작업인데 말이죠. 물론 3번 경우 방금 얘기한 대로 건너뛰게 만들 수는 있습니다. 그런데 시중에 그런 식으로 만들어 놓은 kernel이 있던가요? 아니 지름길 놔두고 왜 둘러 갑니까? 이거 상식선에서 이해되는 이야기 아닌가요?
위에서는 "3)의 경우 스케줄링이 안 일어나면 그냥 스케줄러가 비선점형인 것 뿐이지 않을까요?"라고 써 놓으시고는 이제 선점형이라고 하시니, 도대체 어느걸 주장하고 싶으신 겁니까? 글 쓰는게 시간낭비라는 생각이 자꾸 드는군요.
복잡하게 얘기할 것 없습니다. 그 scheduling decision이 나자마자 scheduling이 된다는 실제 구현 사례 한가지만 들어주시면 됩니다. 그러면 제가 인정할 필요도 없이 저절로 증명이 될테니까요. 그게 왜 불가능한지 일일이 설명하기엔 제가 시간도 능력도 안됩니다. 게다가 이 내용은 오프 토픽이니 정 궁금하시다면 포럼에 새로 글을 쓰는게 좋을 듯하군요. 전 APRIL1024님이 질문하신 내용과 관련해선 할 수 있는 설명은 다 한듯 싶습니다.
댓글 달기