프로그램이 순차적으로 일관성있는 아키텍처에서 실행할 수있는 방법 수

Question

이 문제를 이해하고이 문제를 해결하기 위해 애 쓰고 있습니다. 각각 a, b, c 명령어가 포함 된 3 개의 스레드가 있다고 가정 해 봅시다. 얼마나 많은 프로그램이 순차적으로 일관된 아키텍처에서 실행할 수있는 다양한 방법? H 이 문제는 어떻게 해결해야합니까?

Answer 1

3 개의 스레드가 있습니다. 각 프로세스는 일련의 작업을 처리합니다. a, b 및 c. 스레드에 숫자를 사용할 수 있습니다. 이해해야 할 핵심 사항은 각 스레드 1에서 3까지가 의 순서대로 작업을 처리해야한다는 것입니다. 변형은 여러 가지 조합으로 스레드가 작업을 수행 할 수 있기 때문에 발생할 수 있습니다. 우리 머신이 언제든지 하나의 스레드만을 제공 할 수 있다고 가정 해 봅시다. 스레드 컨텍스트 전환이 발생하기 전에 해당 작업이 완료됩니다.

당신은 할 수 있습니다 :

1a, 1b, 1c, 2a, 2b, 2c, 3a, 3b, 3c 
1a, 2a, 1b, 1c, 2b, 2c, 3a, 3b, 3c 
1a, 2a, 2b, 1b, 1c, 2c, 3a, 3b, 3c 
1a, 2a, 2b, 2c, 1b, 1c, 3a, 3b, 3c 
1a, 2a, 2b, 2c, 3a, 1b, 1c, 3b, 3c 
1a, 2a, 2b, 2c, 3a, 3b, 1b, 1c, 3c 
... 

가 보면, 하나는 모든 조합을 산란 나무를 구축 할 수있는 알고리즘을 생각할 수 있습니다. 당신은 기본적으로 "1a"와 같은 후보자를 선택하고, 다음 단계가 가능한지를 결정합니다 (이 경우 1b, 1c, 2a, ... 3c). 다음 경로를 구축 시작할 수 있습니다 :

1a-1b 
1a-2a 
... 

등등. 각 경로마다 요소를 기억합니다. 그리고 다른 요소를 추가하려면 나머지 요소를 체크 아웃해야합니다. 나머지 각 객체는 또 다른 새 경로를 정의합니다. 반복.

이렇게하면 가능한 모든 경로를 계산하는 알고리즘을 정의 할 수 있어야합니다.

이것은 좋은 코딩 카타 운동을 구성 할 것입니다. 그리고 제 입력은 당신을 잘 가게 해 줄 수 있어야합니다. 바로 가기가 필요하면 here을 보일 수도 있습니다. 또는 there.

그 외에도 분명히 이것은 순수 수학적 문제로도 해결 될 수 있습니다. 모든 요소 1a, ... 3c를 목록에 넣고 해당 목록의 모든 순열을 만들면 9 개를 받게됩니다! 그래서, 362880 가능성. 그러나 문제는 1b, 1a와 같은 순열을 배제해야하므로 물론 작동하지 않습니다. 왜냐하면 a, b, c는 항상 요구 사항에 따라 "순서대로"있기 때문입니다.

그래서 (number threads + number steps)! 유효한 경로의 수에 대한 상위 경계를 제공합니다. 어쩌면 다른 사람이오고 잘못된 경로의 수를 계산할 수있는 좀 더 많은 수학을 추가 할 것입니다.

(BTW : "인쇄"에 대한 또 다른 접근 방식이 될 것이라고 가능한 모든 경로가 - 단순히 9 개 모든 요소 순열을 생성하고, 유효하지 않은 것들 드롭)

면책 조항 : 위의 만 차종의 모든 우리가 기본 기계 기계가 정확히 하나의 "진짜"스레드라고 가정하면 이해할 수 있습니다. 그리고 스레드 실행 및 컨텍스트 전환은 작업이 완료된 후에 발생합니다. 즉

1: aaaabbbbcccc 
2: aaaabbbbcccc 
3:  aaaabbbbccc 

: 당신은 이러한 가정을 삭제할 경우에, 당신은 공간을 만들기 당신이 실제 기계의 잠재적 인 경로를 고려하는 경우, 상황이 훨씬 더 복잡해진다.