분류를 빌려 오기: 작업 큐 순서 정하기
왜 중요한가 "우선순위 큐를 써라"는 우선순위가 있는 어떤 큐에든 반사 작용이에요. 진짜 질문이 흔히 "누가 가장 덜 기다릴 수 있나?"일 때 "누가 가장 중요한가?"에 답해요. 다른 분야들이 오랫동안 그 질문에 답해 왔어요.
창구 셋
병원 응급실. 분류 간호사가 도착한 사람마다 범주를 매기고, 범주마다 진료받을 목표 시간이 있어요: 널리 쓰이는 Manchester 체계에서는 즉시, 10분 안, 60, 120, 240분. 의사가 비면 다음 환자는 그냥 방에서 가장 아픈 사람이 아니에요: 목표를 막 넘기려는 표준 환자가 1분 전에 도착해 아직 시간이 있는 긴급 환자보다 먼저 갈 수 있어요.
공항 체크인. 프리미엄과 이코노미 줄이 따로 있어요. 한 줄 안에서는 도착 순서대로 처리돼요. 하지만 비행기가 막 마감되려 하면, 직원이 이코노미 줄을 걸으며 그 비행기 승객을 앞으로 불러내요. 비행기가 더 늦게 떠나는 프리미엄 승객보다 먼저요.
도서관 반납 창구. 줄 하나, 엄격히 순서대로 처리. 아무도 추월당하지 않고, 아무의 급함도 고려되지 않아요.
코딩 전에 비교하기
- 각 창구에서 다음에 누가 처리될지 무엇이 정하나?
- 어떤 창구가 누군가를 영원히 기다리게 할 수 있나? 어떤 창구가 긴급한 경우를 너무 오래 기다리게 할 수 있나?
- 병원과 공항은 전혀 닮지 않았어요. 무엇을 공유하나? 병원도 비행기도 언급하지 않는 한 문장으로 쓰세요.
- 공항에서 왜 각 줄의 맨 앞만 봐도 충분할까?
목표
백그라운드 작업 시스템이 작업마다 정확히 1분이 걸리는 작업자 하나에서 돌아요. 작업은 대화형(우선순위 1), 표준(2), 일괄(3)이고, 우선순위마다 서비스 약속이 있어요: 그 우선순위의 작업이 시작 전에 기다릴 수 있는 가장 긴 시간. 지금 스케줄러는 언제나 가장 높은 우선순위의 대기 작업을 돌리고, 일괄 작업은 매일 오후 약속을 놓쳐요.
order(jobs, max_wait)를 쓰세요. jobs는 arrive(정수 분)로 정렬된 {"id", "arrive", "priority"}의 리스트이고, max_wait는 우선순위를 작업이 기다릴 수 있는 최대 분에 매핑해요. 작업자가 돌리는 순서대로 작업 id를 반환하세요. 작업자는 1분에 작업 하나를 돌려요: 작업은 도착과 앞 작업의 끝 중 늦은 때 시작하고, 대기는 시작 빼기 도착이에요. 규칙: 어떤 작업도 max_wait[priority]보다 오래 기다리면 안 돼요. 테스트 날들은 모두 늦는 작업 없이 처리할 수 있어요. {1: 3, 2: 20, 3: 60}에서 하루에 작업이 약 1,000개예요.
이 연습은 곧 열려요
앞의 레슨을 마치면 이 레슨이 열려요. 강좌 전체가 무료이고 계정도 필요 없으며, 이 레슨은 지금 바로 읽을 수 있어요.
이 브라우저가 learn.floati.life의 쿠키를 막고 있어서, 여기서 마친 레슨들이 순서대로 열리지 않아요. 이 사이트의 쿠키를 허용하고 새로고침하세요.