강의 계획 레슨 148개 중 48번째 · 빌려 온 기계
빌려 온 기계

분류를 빌려 오기: 작업 큐 순서 정하기

왜 중요한가 "우선순위 큐를 써라"는 우선순위가 있는 어떤 큐에든 반사 작용이에요. 진짜 질문이 흔히 "누가 가장 덜 기다릴 수 있나?"일 때 "누가 가장 중요한가?"에 답해요. 다른 분야들이 오랫동안 그 질문에 답해 왔어요.

창구 셋

병원 응급실. 분류 간호사가 도착한 사람마다 범주를 매기고, 범주마다 진료받을 목표 시간이 있어요: 널리 쓰이는 Manchester 체계에서는 즉시, 10분 안, 60, 120, 240분. 의사가 비면 다음 환자는 그냥 방에서 가장 아픈 사람이 아니에요: 목표를 막 넘기려는 표준 환자가 1분 전에 도착해 아직 시간이 있는 긴급 환자보다 먼저 갈 수 있어요.

공항 체크인. 프리미엄과 이코노미 줄이 따로 있어요. 한 줄 안에서는 도착 순서대로 처리돼요. 하지만 비행기가 막 마감되려 하면, 직원이 이코노미 줄을 걸으며 그 비행기 승객을 앞으로 불러내요. 비행기가 더 늦게 떠나는 프리미엄 승객보다 먼저요.

도서관 반납 창구. 줄 하나, 엄격히 순서대로 처리. 아무도 추월당하지 않고, 아무의 급함도 고려되지 않아요.

코딩 전에 비교하기

  1. 각 창구에서 다음에 누가 처리될지 무엇이 정하나?
  2. 어떤 창구가 누군가를 영원히 기다리게 할 수 있나? 어떤 창구가 긴급한 경우를 너무 오래 기다리게 할 수 있나?
  3. 병원과 공항은 전혀 닮지 않았어요. 무엇을 공유하나? 병원도 비행기도 언급하지 않는 한 문장으로 쓰세요.
  4. 공항에서 왜 각 줄의 맨 앞만 봐도 충분할까?

목표

백그라운드 작업 시스템이 작업마다 정확히 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개예요.

이 레슨에서 문제를 발견했나요? 알려 주세요 · 이 레슨에 대해 묻기

이 연습은 곧 열려요

앞의 레슨을 마치면 이 레슨이 열려요. 강좌 전체가 무료이고 계정도 필요 없으며, 이 레슨은 지금 바로 읽을 수 있어요.