현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

Round Robin 알고리즘에 대해 질문드려요~

ystory의 이미지
글쓴이: ystory / 작성시간: 월, 2009/10/19 - 3:28오후

부전공 필수 때문에 뒤늦게 운영체제 과목을 듣고 있는데

책이 이상한 건지 제가 이상한 건지 난관에 맞닥뜨렸습니다.

Round Robin에 사용되는 대기큐 = 원형큐 아닌가요?

burst time이 CPU time quantum보다 크면 타이머가 끝난뒤에 원형큐 꼬리로 붙는 걸로 생각하고

아무리 풀어봐도 책하고 자꾸만 틀리네요. ㅠㅠ

그리고 한가지 더 궁금한 점은 실제로는 이런 일이 있을런지 모르겠지만

문제를 풀어야 해서 궁금증이 생겼는데 문맥교환과 프로세스 도착시간이 겹칠때

특별히 처리하는 방법이 있나요?

물론 Round Robin 알고리즘에 포함된 내용중에 방법이 있는지 알고 싶어요.

그럼 답변 부탁드리겠습니다. 신나는 월요일~ 좋은 한주 되세요. ㅎ

-사진 첨부 합니다.
밑에 써놓은건 책에 답나오는데로 대기큐에 들어가는 과정 풀어본건데 제가 푼거하고 달라요. ㅠㅠ
1번 물음표는 문맥교환과 프로세스 도착시간이 겹칠때인데 책에서는 그냥 프로세스 도착을 먼저 처리했네요.
2번 물음표는 4번 프로세스가 나중에 도착했음에도 이미 문맥교환으로 꼬리에 붙어있던 1번보다 위에 가있네요.

Forums: 
프로그래밍 QnA
ckebabo의 이미지

글쓴이: ckebabo / 작성시간: 월, 2009/10/19 - 5:00오후

1. 일단 겹칠때라는건 일어나지 않습니다. 물론 예로 드는 경우 시간에 대해 unit time으로 표현해서 겹치는 경우가 발생하는 경우가 있겠지만, 실제로는 문맥교환중에 프로세스가 도착하거나, 다른 프로세스가 실행중에 새로운 프로세스가 도착하거나 하는거죠.

2. 프로세스들을 단순히 리스트로 관리하고 순차적으로 time quantum만큼 실행시킨다고 보시는 것이 편할것 같네요. 마지막이 되면 처음꺼로 오고요...

ystory의 이미지

글쓴이: ystory / 작성시간: 월, 2009/10/19 - 5:10오후

그렇다면..
1번의 경우 어느것이 우선이다. 라고 명시하지 않으면 문제가 잘못된건가요?
2번의 경우 2 - 3 - 1 의 상태에서 새로운 프로세스 4가 들어왔는데 2 - 3 - 1 - 4 가 아닌 2 - 3 - 4 - 1 형태가 되었습니다.

--------------------------------------
으휴
mail@ystory.kr

--------------------------------------
으휴

freestyle의 이미지

글쓴이: freestyle / 작성시간: 월, 2009/10/19 - 7:43오후

Quote:
1번 물음표는 문맥교환과 프로세스 도착시간이 겹칠때인데 책에서는 그냥 프로세스 도착을 먼저 처리했네요.

-> P3가 1번째 ?가 존재하는 시점에 들어왔지만,
이미 그 시점 대기열(P1->P2)의 순서에서 P2가 P1 다음 실행할 프로세스이기에
P3가 새로 들어왔든 이전부터 들어와 있었든 상관 없이 P2부터 실행됩니다. 우선순위를 적용한 방식이라면 모를까.
단, 스케쥴링 시점에 이미 대기열(P1->P2->P3)에 P3이 추가됩니다.

만약 P3가 진입한 '시간4'지점이 P2의 Time Slice가 만료된 뒤 다음 스케쥴링 대상을 찾는 것이었다면,
제가 이해하고 있는 운영체제는 P2 다음으로 P3을 선택할 것입니다.

이전 프로세스가 Time Slice를 빼앗긴 '현재' 시점까지 도착한 프로세스 대기열에서
다음에 실행할 프로세스를 도착 순서에 의해(마지막 실행된 프로세스의 도착시간 이후에 도착한 프로세스를 선택, n이 증가하는 방향)
찾는 방법이 RR입니다.

Quote:
2번 물음표는 4번 프로세스가 나중에 도착했음에도 이미 문맥교환으로 꼬리에 붙어있던 1번보다 위에 가있네요.

-> 라운드 로빈은 우선순위가 없고, 무조건 현재 대기열에 있는 프로세스 중 n의 값이 증가하는 순서로 실행됩니다.
따라서 ?가 위치한 시점에 도착한 P4는 P3 다음에 실행되고, P4 다음에 P1이 실행되는 것입니다.

저 그림이 장황한 설명을 간단히 설명하고 있네요.
OS 책의 스케쥴링의 특징에 대해서는 저 그림을 분석해서 세밀히 규칙을 다듬는 게 중요합니다.

----------------------------------------------------------------------------------------
Don't Feed the Trolls!
----------------------------------------------------------------------------------------

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.