Computer Science / Engineering

컴퓨터 과학 / 공학

코스 전체목록

닫기
본 토픽은 현재 준비중입니다. 공동공부에 참여하시면 완성 되었을 때 알려드립니다.

(1) FIFO, Round Robin Scheduling

@ FIFO (First come First Serves)

    // 먼저 오는 것을 먼저 처리하는 기법입니다.

        > Process일 경우 단위는

            .. CPU Burst단위로 움직이게 됩니다.

    // 장점은 직관적이라는 것입니다.

    // 단점은 Monopolize하는 경우입니다.

        > CPU Burst가 무한루프를 가진 경우가 예시가 됩니다.

        > 이 때에는 Timer를 사용하는 방법입니다.

    // 그리고 Waiting Time을 고려했을 때

        > CPU Burst Time이 적은 것부터 하는 편이 효율적입니다.

            .. Shortist job First를 따라야 합니다. 

    // 그렇기에 FIFO는 이 관점에서 Optimal 하지 않습니다.

    

@ 하지만 Shortist job First OS는 태스크의 CPU Burst를 예측해야 하는데

    // 이는 불가능하게 됩니다.        

        > 그래서 이와 비슷한 효과를 내기 위해서 어떻게 하는지를 알아보겠습니다.

        

@ Shortist job First는 두개로 나눌 수 있습니다.

    // Pre-emptive job first

        > 현재는 가장 짧은 Burst를 수행하다가

            .. 나중에 들어온 것이 더 짧으면 그것을 수행합니다.

            .. 새로운 Process가 도착하면 re-Scheduling합니다.

        > STCF(Shortist Job Complite First)

        

    // non Pre-emptive job first

        > 현재 수행하던 것이 끝났을 때

            .. 새로 들어온 Process를 확인해서

            .. re-Scheduling합니다.

        > SJF

        

    

@ 그렇다면 Burst size는 어떻게 예측할 까요?

    // Exponential Average라는 기법을 예측합니다.

        > 바로 직전 실제측정한 Burt size에 

            .. Alpha를 곱하고 

            .. 1-Alpha를 그전에 예측했던 값에 곱합니다.

            .. (사진)

    // Alpha = 0

        > 과거 예측 값만 고려하고

        > 최근 history는 고려하지 않습니다.

    // Alpha = 1

        > 바로 전 history만 고려한다는 의미입니다.

    // 이 사이의 trade-off를 찾아야 합니다.

    // 식 자체는 과거는 희미해지고, 현재의 history를 강하게 보는 형태가 됩니다.

 

@ Alpha 값을 찾는 것은 불가능했고

    // 실제로 적용하기에는 어려운 측면이 있습니다.

    

@ 그렇다면 어떤 방식을 사용했을까요? (Round Robin Scheduling)

    // 일단 가장 손쉬운 방법은 FIFO Order를 따라 Scheduling 합니다.

        > 단, 굉장히 자주 Shortist값을 잡기 위해서 Scheduling을 들여다 봅니다.

            .. Timeout값을 둬서

            .. job을 수행하다가 Timeout interrupt가 발생하면

            .. 그 job은 CPU burst가 Timeout보다 긴 것이기 때문에

            .. Pre-emptive하게 수행을 뒤로 미룹니다. (강제 종료 - Ready queue)

            .. 그리고 다음 Process가 Timeout보다 작기를 기대하며 불러옵니다.

                .. 이 때 만약 Timeout보다 작으면 성공이고

                .. 또 긴 Process가 들어오면 뒤로 미룹니다.

    // 이런 형태의 Scheduling을 Round Robin Scheduling이라고 합니다. 

        > 이 기법을 사용하면 효과적으로 기존의 문제를 어느정도 해결할 수 있습니다.

            .. 이 기법은 기본적으로 FIFO입니다.

    // 여기서 문제는 Timeout값을 어떻게 할 것이냐는 문제가 발생합니다.

        > 여기서는 Time slice(Time Quentum)이 적절해야 합니다.

            .. 이 문제를 어떻게 해결할 수 있을까요?

댓글

댓글 본문
버전 관리
박천명
현재 버전
선택 버전
graphittie 자세히 보기