golang 비동기. synchronization primitive(3). select문의 동작 원리

July 26, 2024 11 minute read

해당 아티클은 다음 수준의 지식을 요구합니다.

고루틴을 사용해본 경험
golang 채널 사용 방법

다음은 다루지 않습니다.

select 문을 활용하는 방법

다음 실행환경에서 동작합니다.

wsl2 Ubuntu-22.04
go1.22.2 linux/amd64

이번에는 golang에서 channel만큼 중요한 select문의 동작 원리에 대해 탐구해보겠습니다. select문 내부 동작에서도 흥미로운 부분이 많기 때문에 이를 학습하면 동시성을 이해하는 데 도움이 될 것이라 생각합니다.

select문 소개

golang의 select문은 거의 모든 경우에 채널과 함께 사용됩니다. 여러 채널로 이루어진 케이스에 대하여 먼저 처리된 케이스에 대한 컨텍스트를 실행하고 싶은 경우 사용합니다. 예를 들어서 다음과 같습니다.

func doSomething(ctx context.Context) error {
	resultChan := make(chan someType)
	errChan := make(chan error)
	go func() {
		result, err := sendHook()
		if err != nil {
			errChan <- err
		}
		resultChan <- result
	}()

	select {
	case result := <-resultChan:
		// ...
	case err := <-errChan:
		return err
	case <-ctx.Done():
		return ctx.Err()
	}
}

어떤 작업을 하는 doSomething 이라는 함수가 있고 해당 함수는 외부 훅을 호출합니다. 이때 doSomething 함수 외부에서 전달되는 취소 신호를 위의 예시처럼 context 패키지를 이용하여 감지할 수 있습니다. 여기는 context에 대해서 자세히 다루지 않고 이런 예시로 사용할 수 있다는 정도로 알아둡시다. 해당 패키지도 동시성 처리에 굉장히 유용하기에 나중에 다루도록 하겠습니다. 여기서 중요한 점은 select문도 채널만큼 golang 비동기 처리에서 핵심적인 역할을 한다는 것입니다. 그러나 select문으로 채널을 이용하다 보면 아래와 같은 궁금점이 생깁니다.

select문은 케이스 순서대로 동작하나?
select문에서 데드락이 발생하진 않는가?

두 케이스의 결과를 살펴보고 select문의 내부를 살펴봅시다.

select문은 케이스 순서대로 동작하나?

select문을 사용하다 보면 종종 select문이 switch문처럼 위부터 아래로 내려오면서 case에 대한 우선순위를 갖지 않을까 생각하게 됩니다. 바로 테스트해봅시다. 아래 코드를 작성합니다.

package main

import "fmt"

func main() {
	for range 100 {
		c1 := make(chan bool, 1)
		c2 := make(chan bool, 1)
		c1 <- true

		select {
		case <-c1:
			fmt.Println("1")
		case c2 <- true:
			fmt.Println("2")
		}
	}
}

순서대로 동작한다면 위의 예시 케이스에 대하여 1만 출력해야 합니다. 그러나 실행해보면 다음 결과를 얻을 수 있습니다.

$ go run .
1
2
2
1
1
1
1
2
2
1

따라서 순서대로 동작하지 않고 랜덤하게 동작합니다.

select문에서 데드락이 발생하진 않는가?

아래 코드에서 첫 번째 고루틴에서 select문은 채널 c1, c2순으로 케이스를 소유하고 두 번째 고루틴에서 select문은 채널 c2, c1 순으로 케이스를 소유합니다.

package main

import (
	"fmt"
	"sync"
)

func main() {
	for range 100 {
		c1 := make(chan bool)
		c2 := make(chan bool)

		wg := sync.WaitGroup{}
		wg.Add(2)
		
		go func() {
			defer wg.Done()
			select {
			case <-c1:
				fmt.Println("g1 c1")
			case c2 <- true:
				fmt.Println("g1 c2")
			}
		}()
		
		go func() {
			defer wg.Done()
			select {
			case <-c2:
				fmt.Println("g2 c1")
			case c1 <- true:
				fmt.Println("g2 c2")
			}
		}()

		wg.Wait()
	}
}

한편, 데드락의 조건은 다음과 같습니다.

상호 배제: 채널에 대한 송수신은 동시접근을 허용하지 않으므로 성립합니다.
점유 대기: 각 고루틴은 하나의 케이스를 점유하고 다른 고루틴에 할당된 자원을 점유하기 위해 대기합니다.
비선점: 각 고루틴은 다른 고루틴의 채널사용을 중지할 수 없습니다.
순환 대기: 고루틴 1은 c1 수신 대기, c2 송신 대기를 시도하고 고루틴2는 c2 수신 대기, c1 송신 대기를 시도합니다. 따라서 순환대기로 볼 수 있습니다.

이 경우에는 어떨까요? 첫 번째 경우에서 케이스 문의 순서가 섞일 수 있다는 것을 알았지만, 만약 운이 나쁘게 두 고루틴 모두 앞선 케이스를 체크하거나 뒤의 케이스를 먼저 체크하면 데드락이 생길 수 있어보이지 않나요? 실행 결과는 이렇습니다.

go run .
g1 c1
g2 c2
g1 c2
g2 c1
g1 c2
g2 c1
g1 c2
g2 c1
g1 c1
g2 c2

실행하면 데드락 없이 잘 실행되는 것을 확인할 수 있습니다.

select문에는 어떤 구현이 있기에 이렇게 동작할까요? 내부 코드를 지금부터 살펴봅시다.

select문 내부 동작

select문이 호출되면 runtime/select.go의 selectgo함수부터 시작합니다. 해당 함수는 아래 링크에서 확인할 수 있습니다. 같이 확인해보면서 위의 두 경우가 어디서 출발하는지 찾아봅시다.

https://github.com/golang/go/blob/a10e42f219abb9c5b/src/runtime/select.go#L121

함수가 처음 실행되고 진행하는 로직은 함수 초기화입니다. 초기화 과정에서 주요한 변수가 있습니다. scases는 select문의 case를 담는 배열이고, pollorder는 케이스를 무작위로 접근하기 위한 순서 배열, lockorder는 락 순서를 관리하는 배열입니다. 이 정도만 살펴보고 다음으로 넘어갑시다.

// https://github.com/golang/go/blob/a10e42f219abb9c5b/src/runtime/select.go#L121
func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, nsends, nrecvs int, block bool) (int, bool) {
	if debugSelect {
		print("select: cas0=", cas0, "\n")
	}

	// NOTE: In order to maintain a lean stack size, the number of scases
	// is capped at 65536.
	cas1 := (*[1 << 16]scase)(unsafe.Pointer(cas0))
	order1 := (*[1 << 17]uint16)(unsafe.Pointer(order0))

	ncases := nsends + nrecvs
	scases := cas1[:ncases:ncases]             // ✅ select case 배열
	pollorder := order1[:ncases:ncases]        // ✅ 케이스 탐색 순서 배열
	lockorder := order1[ncases:][:ncases:ncases] // ✅ 락 획득 순서 배열
	// NOTE: pollorder/lockorder's underlying array was not zero-initialized by compiler.

	// Even when raceenabled is true, there might be select
	// statements in packages compiled without -race (e.g.,
	// ensureSigM in runtime/signal_unix.go).
	var pcs []uintptr
	if raceenabled && pc0 != nil {
		pc1 := (*[1 << 16]uintptr)(unsafe.Pointer(pc0))
		pcs = pc1[:ncases:ncases]
	}
	casePC := func(casi int) uintptr {
		if pcs == nil {
			return 0
		}
		return pcs[casi]
	}

	var t0 int64
	if blockprofilerate > 0 {
		t0 = cputicks()
	}

함수가 시작되기 전에 주석이 있는데 주석을 읽어보면 select문이 동작할 때 케이스가 단순한 경우 컴파일러가 최적화 시킨다는 것을 확인할 수 있습니다.

// https://github.com/golang/go/blob/a10e42f219abb9c5b/src/runtime/select.go#L157
func selectgo(
	// ...
) (int, bool) {
	// ...
	// The compiler rewrites selects that statically have
	// only 0 or 1 cases plus default into simpler constructs.
	// The only way we can end up with such small sel.ncase
	// values here is for a larger select in which most channels
	// have been nilled out. The general code handles those
	// cases correctly, and they are rare enough not to bother
	// optimizing (and needing to test).
	// ✅ 컴파일러가 0 또는 1개의 case & default 상황을 단순화

컴파일러는 그럼 단순한 경우를 어떻게 최적화 할까요? 이 경우에 대한 정답은 다시 채널 내부 코드에서 확인할 수 있습니다.

https://github.com/golang/go/blob/a10e42f219abb9c5b/src/runtime/chan.go#L677

// https://github.com/golang/go/blob/a10e42f219abb9c5b/src/runtime/chan.go#L677
// compiler implements
//
//	select {
//	case c <- v:
//		... foo
//	default:
//		... bar
//	}
//
// as
//
//	if selectnbsend(c, v) {
//		... foo
//	} else {
//		... bar
//	}
func selectnbsend(c *hchan, elem unsafe.Pointer) (selected bool) {
	return chansend(c, elem, false, getcallerpc())
}

// compiler implements
//
//	select {
//	case v, ok = <-c:
//		... foo
//	default:
//		... bar
//	}
//
// as
//
//	if selected, ok = selectnbrecv(&v, c); selected {
//		... foo
//	} else {
//		... bar
//	}
func selectnbrecv(elem unsafe.Pointer, c *hchan) (selected, received bool) {
	return chanrecv(c, elem, false)
}

해당 부분에서 채널에 대한 send, recv를 호출하는 부분에 블로킹을 false로 주어 블로킹되지 않고 채널 상태에 따라 로직을 처리합니다.

다음은 확인할 케이스를 섞는 부분입니다. 섞는 부분을 살펴보면 케이스를 돌면서 채널 존재 유무를 살펴보고 존재하는 경우 pollorder의 인덱스 셔플을 진행합니다. 여기서는 현대적인 방식의 피셔 예이츠 셔플을 이용합니다.

피셔-예이츠 셔플

// https://github.com/golang/go/blob/a10e42f219abb9c5b/src/runtime/select.go#L165
func selectgo(
	// ...
) (int, bool) {
	// ...
	// generate permuted order
	norder := 0
	for i := range scases { // ✅ 각 case 순회
		cas := &scases[i]

		// Omit cases without channels from the poll and lock orders.
		if cas.c == nil { // ✅ 채널 없으면 스킵
			cas.elem = nil // allow GC
			continue
		}

		// Fisher-Yates 셔플
		j := cheaprandn(uint32(norder + 1)) // ✅ 무작위 인덱스 선택
		pollorder[norder] = pollorder[j]    // ✅ norder 자리에 j 값 저장
		pollorder[j] = uint16(i)            // ✅ j 자리에 i 삽입
		norder++
	}
	pollorder = pollorder[:norder]
	lockorder = lockorder[:norder]

여기서 왜 순서를 랜덤으로 섞는 걸까요? 만약 select문이 대기하는 케이스가 여러 채널에 대해서 동작하고 있고 채널이 모두 당장 실행될 수 있는 경우, 먼저 선언된 케이스만 동작하게 됩니다. 따라서 이 경우 뒷 케이스의 채널은 스케줄러를 할당받지 못하는 기아 상태가 발생하게 됩니다. 이런 경우를 방지하기 위해 랜덤으로 케이스 탐색 순서를 섞어 진행합니다.

다음은 락을 잡기 위해 순서를 정렬하는 부분입니다. 순서 정렬은 힙정렬을 이용하여 채널을 시간 복잡도 nlogn으로 정렬하는 모습입니다.

// https://github.com/golang/go/blob/a10e42f219abb9c5b/src/runtime/select.go#L182
func selectgo(
	// ...
) (int, bool) {
	// ...
	// sort the cases by Hchan address to get the locking order.
	// simple heap sort, to guarantee n log n time and constant stack footprint.
	for i := range lockorder { // ✅ 최대힙 구성
		j := i
		// Start with the pollorder to permute cases on the same channel.
		c := scases[pollorder[i]].c
		for j > 0 && scases[lockorder[(j-1)/2]].c.sortkey() < c.sortkey() { // ✅ 채널 포인터 주소 기준 비교
			k := (j - 1) / 2
			lockorder[j] = lockorder[k]
			j = k
		}
		lockorder[j] = pollorder[i]
	}
	// ✅ 힙소트로 lockorder 정렬
	for i := len(lockorder) - 1; i >= 0; i-- {
		o := lockorder[i]
		c := scases[o].c
		lockorder[i] = lockorder[0] // ✅ 루트와 마지막 원소 교환
		j := 0
		for {
			k := j*2 + 1
			if k >= i {
				break
			}
			if k+1 < i && scases[lockorder[k]].c.sortkey() < scases[lockorder[k+1]].c.sortkey() {
				k++
			}
			if c.sortkey() < scases[lockorder[k]].c.sortkey() {
				lockorder[j] = lockorder[k]
				j = k
				continue
			}
			break
		}
		lockorder[j] = o
	}

채널의 sortkey 메서드는 다음과 같이 이루어져 있습니다.

// https://github.com/golang/go/blob/a10e42f219abb9c5b/src/runtime/select.go#L518
func (c *hchan) sortkey() uintptr {
	return uintptr(unsafe.Pointer(c)) // ✅ 채널 포인터 주소 반환
}

그럼 왜 락 순서를 정렬할까요? 다음과 같은 select문 코드가 있다고 가정합니다. 위에서 확인한 예시입니다.

package main

import (
	"fmt"
	"sync"
)

func main() {
	for range 100 {
		c1 := make(chan bool) // c1의 주소가 1000,
		c2 := make(chan bool) // c2의 주소가 1001이면

		wg := sync.WaitGroup{}
		wg.Add(2)
		
		go func() {
			defer wg.Done()
			select { // select문에서 lockorder정렬을 1000, 1001순으로 진행
			case <-c1:
				fmt.Println("g1 c1")
			case c2 <- true:
				fmt.Println("g1 c2")
			}
		}()
		
		go func() {
			defer wg.Done()
			select { // select문에서 lockorder정렬을 1000, 1001순으로 진행
			case <-c2:
				fmt.Println("g2 c1")
			case c1 <- true:
				fmt.Println("g2 c2")
			}
		}()

		wg.Wait()
	}
}

정렬된 lockorder를 이용하므로 채널의 주소에 따라 select문의 case를 정렬합니다. 따라서 해당 순서대로 채널 대기로직을 실행하게 되고 모든 고루틴의 select문의 케이스에서 c1 채널을 먼저 확인하게 됩니다. 이렇듯 select문은 힙 정렬을 활용하여 채널 대기 순서를 채널 포인터 주소 기준으로 정렬한 다음 락을 획득하는 방식으로 데드락 문제를 회피합니다.

다음 로직은 당장 실행 가능한 케이스문을 탐색합니다. 아래 로직에서 실행 가능한 케이스문을 탐색했다면 바로 실행합니다.

// https://github.com/golang/go/blob/a10e42f219abb9c5b/src/runtime/select.go#L243
func selectgo(
	// ...
) (int, bool) {
	// ...
	// pass 1 - look for something already waiting
	var casi int
	var cas *scase
	var caseSuccess bool
	var caseReleaseTime int64 = -1
	var recvOK bool
	for _, casei := range pollorder { // ✅ pollorder 순으로 즉시 처리 가능한 케이스 탐색
		casi = int(casei)
		cas = &scases[casi]
		c = cas.c

		if casi >= nsends {
			sg = c.sendq.dequeue()
			if sg != nil {
				goto recv
			}
			if c.qcount > 0 {
				goto bufrecv
			}
			if c.closed != 0 {
				goto rclose
			}
		} else {
			if raceenabled {
				racereadpc(c.raceaddr(), casePC(casi), chansendpc)
			}
			if c.closed != 0 {
				goto sclose
			}
			sg = c.recvq.dequeue()
			if sg != nil {
				goto send
			}
			if c.qcount < c.dataqsiz {
				goto bufsend
			}
		}
	}

위에서 처리 가능한 케이스가 발견되지 않는 경우 각 케이스를 대기열에 등록하고 select문을 호출한 고루틴의 상태를 대기로 변경합니다. select문 고루틴을 sudog로 변경하고 모든 채널에 대하여 등록하여 채널 알림을 수신할 수 있도록 합니다.

// https://github.com/golang/go/blob/a10e42f219abb9c5b/src/runtime/select.go#L282
func selectgo(
	// ...
) (int, bool) {
	// ...
	if !block {
		selunlock(scases, lockorder)
		casi = -1
		goto retc
	}

	// pass 2 - enqueue on all chans
	gp = getg()
	if gp.waiting != nil {
		throw("gp.waiting != nil")
	}
	nextp = &gp.waiting
	for _, casei := range lockorder {
		casi = int(casei)
		cas = &scases[casi]
		c = cas.c
		sg := acquireSudog() // ✅ sudog 생성 및 sendq/recvq에 등록
		sg.g = gp
		sg.isSelect = true
		// No stack splits between assigning elem and enqueuing
		// sg on gp.waiting where copystack can find it.
		sg.elem = cas.elem
		sg.releasetime = 0
		if t0 != 0 {
			sg.releasetime = -1
		}
		sg.c = c
		// Construct waiting list in lock order.
		*nextp = sg
		nextp = &sg.waitlink

		if casi < nsends {
			c.sendq.enqueue(sg)
		} else {
			c.recvq.enqueue(sg)
		}
	}

	// wait for someone to wake us up
	gp.param = nil
	// Signal to anyone trying to shrink our stack that we're about
	// to park on a channel. The window between when this G's status
	// changes and when we set gp.activeStackChans is not safe for
	// stack shrinking.
	gp.parkingOnChan.Store(true)
	gopark(selparkcommit, nil, waitReasonSelect, traceBlockSelect, 1) // ✅ select 고루틴 일시 중지
	gp.activeStackChans = false

고루틴이 활성화되는 경우 성공한 채널을 제외한 나머지 채널을 정리합니다.

// https://github.com/golang/go/blob/a10e42f219abb9c5b/src/runtime/select.go#L336
func selectgo(
	// ...
) (int, bool) {
	// ...
	// pass 3 - dequeue from unsuccessful chans
	// otherwise they stack up on quiet channels
	// record the successful case, if any.
	// We singly-linked up the SudoGs in lock order.
	casi = -1
	cas = nil
	caseSuccess = false
	sglist = gp.waiting
	// Clear all elem before unlinking from gp.waiting.
	for sg1 := gp.waiting; sg1 != nil; sg1 = sg1.waitlink { // ✅ 성공하지 않은 채널 정리
		sg1.isSelect = false
		sg1.elem = nil
		sg1.c = nil
	}
	gp.waiting = nil

	// ✅ 케이스 확인 및 sudog 해제
	for _, casei := range lockorder {
		k = &scases[casei]
		if sg == sglist {
			// sg has already been dequeued by the G that woke us up.
			casi = int(casei)
			cas = k
			caseSuccess = sglist.success
			if sglist.releasetime > 0 {
				caseReleaseTime = sglist.releasetime
			}
		} else {
			c = k.c
			if int(casei) < nsends {
				c.sendq.dequeueSudoG(sglist)
			} else {
				c.recvq.dequeueSudoG(sglist)
			}
		}
		sgnext = sglist.waitlink
		sglist.waitlink = nil
		releaseSudog(sglist)
		sglist = sgnext
	}

	if cas == nil {
		throw("selectgo: bad wakeup")
	}

	// ✅ 성공 케이스 채널 처리
	c = cas.c

이제 select문의 동작 과정을 정리해봅시다. select문을 정리해보면 다음 과정을 따라 동작함을 알 수 있었습니다.

selectgo 필드 초기화
select문에 대한 케이스 pollorder 셔플
lockorder 힙 정렬
당장 실행 가능한 케이스 탐색: 만약 발견되면 바로 해당 케이스 진행
모든 채널의 select문의 고루틴을 대기 리스트로 등록 후 select 고루틴 대기
성공한 케이스 외 나머지 채널 정리 및 해당 케이스 실행

이때 select문의 특징으로 다음을 확인했습니다.

단순한 select문의 경우, 컴파일러가 단순화하여 논블로킹옵션으로 채널 송수신 처리합니다.
select문에 대하여 순서를 셔플합니다: 이 이유는 성공한 케이스가 여럿인 경우 뒤에 선언된 케이스 문의 기아 상태를 방지하기 위해서입니다.
lockorder를 정렬하여 락 순서를 정렬합니다: 이 이유는 여러 채널이 여러 select문에 걸쳐 동작하는 경우 데드락을 방지하기 위해서입니다.

Share on

X Facebook LinkedIn Bluesky

atgane

golang 비동기. synchronization primitive(3). select문의 동작 원리

select문 소개

select문은 케이스 순서대로 동작하나?

select문에서 데드락이 발생하진 않는가?

select문 내부 동작

Share on

Leave a comment

You may also enjoy

kubernetes data plane: containerd는 언제 결정하는가

kubernetes data plane: containerd CreateContainer & StartContainer

kubernetes data plane: containerd sandbox 생성 과정 추적

kubernetes data plane: containerd 플러그인 시스템과 gRPC 서버 초기화