st(state-threads)coroutine 스케줄링

10336 단어
st(state-threads) https://github.com/winlinvip/state-threads
st 기반 RTMP/HLS 서버:https://github.com/winlinvip/simple-rtmp-server
st는 coroutine의 메커니즘, 즉 사용자 상태 스레드 또는 협동 스레드를 실현했다.epoll(async,nonblocking socket)의 비저지를 협동 방식으로 바꾸어 모든 상태 공간을 stack에 넣고 비동기적인 대순환과 상태 공간의 판단을 피한다.
st에 대한 자세한 내용은 번역을 참조하십시오.http://blog.csdn.net/win_lin/article/details/8242653
나는 st를 간소화하여 다른 시스템을 없애고 linux 시스템만 고려하며 i386/x86_64/arm/mips 네 가지 cpu 시리즈, 참고:https://github.com/winlinvip/simple-rtmp-server/tree/master/trunk/research/st본고는 coroutine의 스케줄링을 소개했는데 주로 epoll과timeout 시간 초과 대기열과 관련된다.

EPOLL 및 TIMEOUT


일반적인 EPOLL의 사용은 읽을 때 다 읽지 못할 수도 있고, 다 썼는지, 얼마나 읽을 수 있는지, 얼마나 쓸 수 있는지도 모르기 때문에 fd가 쓸 수 있을 때 계속 쓰고 fd가 읽을 수 있을 때 계속 읽어야 한다.이게 큰 epoll_wait 순환, 모든 깨어난 fd, 어떤 것이 읽어야 하고, 어떤 것이 써야 하는지를 처리합니다.
타임아웃은 fd의 시간 초과, sleep 일정 시간 설정 등 광범위한 업무 수요를 응용하는 것이다.epoll_wait에서도 타임아웃을 제공했는데 마지막은 시간 초과입니다.
이전에 논의한 코루틴의 창설과 점프 방법을 결합하면 st가 epoll을 어떻게 사용하는지 알 수 있다.디버그 프로그램, 인터럽트 설정은_st_epoll_dispatch:
(gdb) bt
#0  _st_epoll_dispatch () at event.c:304
#1  0x000000000040171c in _st_idle_thread_start (arg=0x0) at sched.c:222
#2  0x0000000000401b26 in _st_thread_main () at sched.c:327
#3  0x00000000004022c0 in st_thread_create (start=0x635ed0, arg=0x186a0, joinable=0, stk_size=4199587) at sched.c:600

idle 라인이 epoll을 호출한 epoll_를 보실 수 있습니다.wait 방법,timeout과 각종 활성화된 fd를 계산한 다음 대응하는 coroutine를 활동 대기열에 놓고 한 라인씩 전환합니다.
ST_HIDDEN void _st_epoll_dispatch(void)
{
    if (_ST_SLEEPQ == NULL) {
        timeout = -1;
    } else {
        min_timeout = (_ST_SLEEPQ->due <= _ST_LAST_CLOCK) ? 0 : (_ST_SLEEPQ->due - _ST_LAST_CLOCK);
        timeout = (int) (min_timeout / 1000);
    }

    if (_st_epoll_data->pid != getpid()) {
        // WINLIN: remove it for bug introduced.
        // @see: https://github.com/winlinvip/simple-rtmp-server/issues/193
        exit(-1);
    }

    /* Check for I/O operations */
    nfd = epoll_wait(_st_epoll_data->epfd, _st_epoll_data->evtlist, _st_epoll_data->evtlist_size, timeout);

라인 스케줄링의 핵심은 io나timeout에 따라 스케줄링합니다.
스케줄링은 사실 idle 라인으로 이루어진 것이다. 코드는 다음과 같다.
void *_st_idle_thread_start(void *arg)
{
    _st_thread_t *me = _ST_CURRENT_THREAD();
    
    while (_st_active_count > 0) {
        /* Idle vp till I/O is ready or the smallest timeout expired */
        _ST_VP_IDLE();
        
        /* Check sleep queue for expired threads */
        _st_vp_check_clock();
        
        me->state = _ST_ST_RUNNABLE;
        _ST_SWITCH_CONTEXT(me);
    }
    
    /* No more threads */
    exit(0);
    
    /* NOTREACHED */
    return NULL;
}

보아하니 선_ST_VP_IDLE 호출 epoll_wait에서 활성 io의 스레드를 활성화한 다음_st_vp_check_clock에서 시간 초과 라인을 검사합니다.

TIME


시간을 초과할 때, 상대적인 시간을 사용한다면, 예를 들어 st_usleep(100*1000), 100ms 휴면, 마지막으로 epoll_wait 시간은 100ms, 즉 st 사용 상대 시간:
(gdb) f
#0  _st_epoll_dispatch () at event.c:308
308	        timeout = (int) (min_timeout / 1000);
(gdb) p min_timeout
$2 = 100000

상대적인 시간을 사용하면 지연되는 문제가 있다. 예를 들어 다음과 같다.
st_usleep(100ms)
for (int i = 0; i < xxxx; i++) {
        // st , 200ms
}
// st 

위의 코드는 실제 st_usleep는 200밀리초입니다. 물론 코드가 100밀리초를 실행하는 것은 매우 복잡한 작업이고 성능 병목입니다.이것은 사실 무시해도 된다.따라서 st의 reference에서는 다음과 같이 설명합니다.
Timeouts

The timeout parameter to st_cond_timedwait() and the I/O functions, and the arguments to st_sleep() and st_usleep() specify a maximum time to wait since the last context switch not since the beginning of the function call.

시간 초과는 함수 호출이 아니라 스레드 전환에서 계산한다.그러니까 st의 시간 초과는 항상 시간 지연이 있다는 거야.
st_ 보기utime라는 함수의 실현은 기본적으로 gettime ofday를 사용합니다. 이 함수가 빈번하게 호출되면 성능 병목이 있습니다.실제로 몇 군데만 이 함수를 호출했다.
sched.c:163:    _st_this_vp.last_clock = st_utime(); // st_init()
sched.c:478:    now = st_utime(); // _st_vp_check_clock()
stk.c:165:        srandom((unsigned int) st_utime()); // st_randomize_stacks()
sync.c:93:        _st_last_tset = st_utime(); // st_timecache_set()

실제 호출이 많은 것은_st_vp_check_clock, 이것은 실제로idle에서 호출됩니다.
void *_st_idle_thread_start(void *arg)
{
    _st_thread_t *me = _ST_CURRENT_THREAD();
    
    while (_st_active_count > 0) {
        /* Idle vp till I/O is ready or the smallest timeout expired */
        _ST_VP_IDLE();
        
        /* Check sleep queue for expired threads */
        _st_vp_check_clock();
        
        me->state = _ST_ST_RUNNABLE;
        _ST_SWITCH_CONTEXT(me);
    }

즉, 이것은 사실상 매번 스케줄링할 때만 호출되고 실제로는 받아들일 수 있다는 것이다.
라인의 시간 초과는due 필드를 통해 설정됩니다. 이것은 sleep이든 io든 이 필드를 설정합니다.
sched.c:461:    trd->due = _ST_LAST_CLOCK + timeout;

실제로 이_ST_LAST_CLOCK는 스케줄링할 때마다 업데이트되는 시계입니다.이를 통해 알 수 있듯이 st는 매번 스케줄링할 때 시계를 한 번만 업데이트하고 다른 때는 상대적인 시간을 사용합니다.
SLEEP의 매개 변수는 상대 시간입니다. 작업을 추가할 때 절대 시간을 사용하고 시간을 초과할 때 두 갈래 트리의 균형을 맞춥니다. 한 마디로 시간을 초과하면 성능에 문제가 있습니다.다음은 상세하게 분석한다.

TIMEOUT


st 모든timeout은 같은 메커니즘으로 이루어진다.sleep,io의 시간 초과,cond 시간 초과 등을 포함합니다.
모든 시간 초과 객체는 시간 초과 대기열, 즉_ST_SLEEPQ.idle 스레드, 즉_st_idle_thread_start가 먼저 epoll_wait 이벤트 스케줄링, 즉_st_epoll_dispatch.에폴에서_wait시 마지막 매개 변수는 시간 초과 ms입니다. 시간 초과 대기열은 절대 시간을 사용하기 때문에 시간 초과 대기열의 첫 번째 요소와 현재의 차이를 비교하면 알 수 있습니다.
epoll_wait 이벤트는 io가 있는 라인을 활성화하고 idle 라인 호출로 돌아갑니다_st_vp_check_clock, 이것이 바로 절대 시간을 업데이트하고 시간을 초과하는 라인을 찾아내는 것이다._ST_DEL_SLEEPQ는 시간을 초과하는 라인을 활성화하는 데 사용되며, 이 함수는 _st_del_sleep_q, 그리고 heap_ 호출delete.
static void heap_delete(_st_thread_t *trd) 
{
    _st_thread_t *t, **p;
    int bits = 0;
    int s, bit;
    
    /* First find and unlink the last heap element */
    p = &_ST_SLEEPQ;
    s = _ST_SLEEPQ_SIZE;
    while (s) {
        s >>= 1;
        bits++;
    }
    
    for (bit = bits - 2; bit >= 0; bit--) {
        if (_ST_SLEEPQ_SIZE & (1 << bit)) {
            p = &((*p)->right);
        } else {
            p = &((*p)->left);
        }
    }
    
    t = *p;
    *p = NULL;
    --_ST_SLEEPQ_SIZE;
    if (t != trd) {
        /*
        * Insert the unlinked last element in place of the element we are deleting
        */
        t->heap_index = trd->heap_index;
        p = heap_insert(t);
        t = *p;
        t->left = trd->left;
        t->right = trd->right;
        
        /*
        * Reestablish the heap invariant.
        */
        for (;;) {
            _st_thread_t *y; /* The younger child */
            int index_tmp;
            
            if (t->left == NULL) {
                break;
            } else if (t->right == NULL) {
                y = t->left;
            } else if (t->left->due < t->right->due) {
                y = t->left;
            } else {
                y = t->right;
            }
            
            if (t->due > y->due) {
                _st_thread_t *tl = y->left;
                _st_thread_t *tr = y->right;
                *p = y;
                if (y == t->left) {
                    y->left = t;
                    y->right = t->right;
                    p = &y->left;
                } else {
                    y->left = t->left;
                    y->right = t;
                    p = &y->right;
                }
                t->left = tl;
                t->right = tr;
                index_tmp = t->heap_index;
                t->heap_index = y->heap_index;
                y->heap_index = index_tmp;
            } else {
                break;
            }
        }
    }
    
    trd->left = trd->right = NULL;
}

이 함수는 비교적 복잡하다는 것을 알 수 있다. 이것은 st에 의하면 O(log N)의 복잡도 (timeout_heap.txt 참조) 라고 하지만, 빈번하게 호출되면 문제가 될 수 있다.주로 자주 호출할 때 epoll_wait와 epoll_ctl는 빈번하게 호출되기 때문에 (타임아웃이 많기 때문에) 실제로는 타임아웃을 너무 많이 사용해서 st에서 꺼린다.
st 최고 성능은 타임아웃이 없고 모두 epoll_wait는 io 스케줄링을 하는데 이때는 완전히 linux의 성능입니다. 매우 높습니다.

Deviation


st의 오차는 도대체 얼마나 됩니까?측정 결과(물론 복잡도가 높을수록 오차가 크다):
    srs_trace("1. sleep...");
    st_utime_t start = st_utime();
    st_usleep(sleep_ms * 1000);
    st_utime_t end = st_utime();
    
    srs_trace("2. sleep ok, sleep=%dus, deviation=%dus", 
        (int)(sleep_ms * 1000), (int)(end - start - sleep_ms * 1000));

결과:
1. sleep...
2. sleep ok, sleep=100000us, deviation=147us

즉, 시스템이 비어 있을 때 오차가 천분의 1로 완전히 무시할 수 있다는 것이다.
시스템이 바쁠 때는요?30억 번의 공중 순환 연산 후 라인 전환 테스트를 합니다.
st_mutex_t sleep_work_cond = NULL;
void* sleep_deviation_func(void* arg)
{
    st_mutex_lock(sleep_work_cond);
    srs_trace("2. work thread start.");

    int64_t i;
    for (i = 0; i < 3000000000ULL; i++) {
    }
    
    st_mutex_unlock(sleep_work_cond);
    srs_trace("3. work thread end.");
    
    return NULL;
}

int sleep_deviation_test()
{
    srs_trace("===================================================");
    srs_trace("sleep deviation test: start");
    
    sleep_work_cond = st_mutex_new();
    
    st_thread_create(sleep_deviation_func, NULL, 0, 0);
    st_mutex_lock(sleep_work_cond);
    
    srs_trace("1. sleep...");
    st_utime_t start = st_utime();
    
    // other thread to do some complex work.
    st_mutex_unlock(sleep_work_cond);
    st_usleep(1000 * 1000);
    
    st_utime_t end = st_utime();
    
    srs_trace("4. sleep ok, sleep=%dus, deviation=%dus", 
        (int)(sleep_ms * 1000), (int)(end - start - sleep_ms * 1000));

    st_mutex_lock(sleep_work_cond);
    srs_trace("sleep deviation test: end");
    
    st_mutex_destroy(sleep_work_cond);
    
    return 0;
}

이때 st의 오차는 다음과 같다.
sleep deviation test: start
1. sleep...
2. work thread start.
3. work thread end.
4. sleep ok, sleep=100000us, deviation=6560003us
sleep deviation test: end

io의 다른 모든 타임아웃의 실현을 보십시오. 모두 같습니다.그래서 st는 오차가 있습니다. 일부 성능에 문제가 있는 프로그램에서 심각한 스케줄링 문제를 초래할 수 있습니다. (물론 성능에 문제가 있으면 성능 문제를 해결해야 합니다.)
st의timeout 메커니즘은 전체적으로 보면 문제가 없다. 이것이 바로 결론이다.

좋은 웹페이지 즐겨찾기