FIFO(컴퓨팅 및 전자제품)

FIFO (computing and electronics)

컴퓨팅 및 시스템 이론에서 FIFO는 first in, first out(first in은 first out)의 약자로, 큐의 가장 오래된 엔트리 또는 "헤드"가 먼저 처리되는 데이터 구조(종종 데이터 버퍼)의 조작을 조직하는 방법입니다.

이러한 처리는 큐 영역의 사람들에게 선착순(FCFS) 기준으로 서비스를 제공하는 것과 유사합니다.즉, 큐의 후미에 도착하는 순서와 동일합니다.

FCFS는 [1]FIFO 운영체제스케줄링 알고리즘의 전문 용어이기도 합니다.이 알고리즘은 모든 프로세스의 중앙처리장치(CPU)에 필요한 순서대로 시간을 부여합니다.FIFO의 반대는 LIFO(Last-in-First-out)로, 가장 어린 엔트리 또는 "스택의 상위"가 먼저 [2]처리됩니다.priority 큐는 FIFO도 LIFO도 아니지만 일시적으로 또는 기본적으로 유사한 동작을 채택할 수 있습니다.큐잉 이론에는 데이터 구조를 처리하는 방법뿐만 아니라 엄밀한 FIFO 큐 간의 상호 작용도 포함됩니다.

컴퓨터 공학

enqueue 및 dequeue 연산이 있는 FIFO 큐를 나타냅니다.

애플리케이션에 따라 FIFO는 하드웨어 시프트 레지스터로 구현되거나 다른 메모리 구조(일반적으로 순환 버퍼 또는 목록)를 사용하여 구현될 수 있습니다.추상 데이터 구조에 대한 자세한 내용은 대기열(데이터 구조)을 참조하십시오.FIFO 큐의 대부분의 소프트웨어 실장은 스레드 세이프가 아니기 때문에 데이터 구조 체인이 한 번에1개의 스레드에 의해서만 조작되고 있는 것을 확인하기 위한 잠금 메커니즘이 필요합니다.

다음 코드는 링크 리스트 FIFO C++ 언어 구현을 나타내고 있습니다.실제로는 일반적인 Unix 시스템C sys/queue.h 매크로 또는 C++ 표준 라이브러리 std::list 템플릿 등 다수의 리스트 실장이 존재하기 때문에 데이터 구조를 처음부터 구현할 필요가 없습니다.70 .

#실패하다 <메모리> #실패하다 <stdexcept>  사용. 네임스페이스 표준;  템플릿 < >타이프네임 T> 학급 선입선출 {     구조 노드 {         T 가치;         shared_ptr< >노드> 다음 분. = 특수;          노드(T _값): 가치(_값) {}     };      shared_ptr< >노드> 전선. = 특수;     shared_ptr< >노드> 뒤로  = 특수;  일반의:     무효 큐잉(T _값) {         한다면 (전선. == 특수) {             전선. = make_shared(공유)< >노드>(_값);             뒤로 = 전선.;         } 또 다른 {             뒤로->다음 분. = make_shared(공유)< >노드>(_값);             뒤로 = 뒤로->다음 분.;         }     }      T 큐잉을 해제하다() {         한다면 (전선. == 특수)             던지다 언더플로우_에러("큐를 해제할 수 없음");          T 가치 = 전선.->가치;         전선. = 움직이다(전선.->다음 분.);                  돌아가다 가치;     } };

프로세스 간 통신을 위한 파이프 앤 필터 모델을 지원하는 컴퓨팅 환경에서 FIFO는 명명된 파이프의 다른 이름입니다.

디스크 컨트롤러는 FIFO를 디스크 스케줄링 알고리즘으로 사용하여 디스크 I/O 요청을 처리하는 순서를 결정할 수 있습니다.이 순서는 [1]앞에서 설명한 CPU 스케줄링과 동일한 FCFS 이니셜리즘으로도 알려져 있습니다.

컴퓨터 네트워크에서 사용되는 통신 네트워크 브리지, 스위치 및 라우터는 FIFO를 사용하여 다음 수신처로 전송되는 데이터 패킷을 유지합니다.통상, 네트워크 접속 마다 적어도1개의 FIFO 구조가 사용됩니다.일부 디바이스는 여러 FIFO를 갖추고 있어 서로 다른 유형의 [3]정보를 동시에 독립적으로 큐잉할 수 있습니다.

일렉트로닉스

FIFO 스케줄

FIFO는 하드웨어와 소프트웨어 간의 버퍼링 및 흐름 제어에 일반적으로 사용됩니다.하드웨어 형태에서 FIFO는 주로 일련의 읽기 및 쓰기 포인터, 스토리지 및 제어 로직으로 구성됩니다.스토리지는 정적 랜덤 액세스 메모리(SRAM), 플립 플랍, 래치 또는 기타 적합한 스토리지 형태일 수 있습니다.크기가 중요하지 않은 FIFO의 경우 보통 듀얼 포트 SRAM이 사용되며, 한쪽 포트는 쓰기 전용이고 다른 한쪽 포트는 읽기 전용입니다.

1969년 Fairchild Semiconductor에서 [4]Peter Alfke에 의해 전자제품에 구현된 것으로 알려진 FIFO가 처음 소개되었습니다.Alfke는 후에 Xilinx의 이사였다.

동기성

동기 FIFO는 읽기 및 쓰기 모두에 동일한 클럭이 사용되는 FIFO입니다.비동기 FIFO는 읽기 및 쓰기에 서로 다른 클럭을 사용하기 때문에 준거성 문제가 발생할 수 있습니다.비동기 FIFO의 일반적인 실장에서는 읽기 및 쓰기 포인터에 그레이 코드(또는 임의의 단위 거리 코드)를 사용하여 신뢰할 수 있는 플래그 생성을 보장합니다.플래그 생성에 관한 또 하나의 주의사항은 비동기 FIFO 구현용 플래그를 생성하기 위해 포인터 연산을 사용해야 한다는 것입니다.반대로 리크 버킷접근법 또는 포인터 계산을 사용하여 동기 FIFO 구현으로 플래그를 생성할 수 있습니다.

하드웨어 FIFO는 동기용으로 사용됩니다.이것은 순환 큐로 구현되는 경우가 많기 때문에 다음 두 가지 포인터가 있습니다.

  • 포인터 읽기/주소 레지스터 읽기
  • 포인터 쓰기/주소 쓰기 레지스터

상태 플래그

FIFO 상태 플래그의 예로는 full, empty, empty, empty 등이 있습니다.읽기 주소 레지스터가 쓰기 주소 레지스터에 도달하면 FIFO는 비어 있습니다.쓰기 주소 레지스터가 읽기 주소 레지스터에 도달하면 FIFO가 가득 찬다.읽기 주소와 쓰기 주소는 처음에는 모두 첫 번째 메모리 위치에 있으며 FIFO 큐는 비어 있습니다.

어느 경우든 읽기 주소와 쓰기 주소는 동일합니다.두 상황을 구별하기 위해 읽기 및 쓰기 주소별로 1비트를 추가하는 것이 간단하고 견고한 방법입니다.이 비트는 주소가 랩될 때마다 반전됩니다.이 설정에서는, 명확화 조건은 다음과 같습니다.

  • 읽기 주소 레지스터가 쓰기 주소 레지스터와 같을 경우 FIFO는 비어 있습니다.
  • 읽기 주소 레지스터와 쓰기 주소 레지스터가 최상위 비트에서만 달라지고 나머지 비트가 같을 경우 FIFO는 가득 찬 것입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Andrew S. Tanenbaum; Herbert Bos (2015). Modern Operating Systems. Pearson. ISBN 978-0-13-359162-0.
  2. ^ Kruse, Robert L. (1987) [1984]. Data Structures & Program Design (second edition). Joan L. Stone, Kenny Beck, Ed O'Dougherty (production process staff workers) (second (hc) textbook ed.). Englewood Cliffs, New Jersey 07632: Prentice-Hall, Inc. div. of Simon & Schuster. p. 150. ISBN 0-13-195884-4.{{cite book}}: CS1 유지보수: 위치(링크)
  3. ^ James F. Kurose; Keith W. Ross (July 2006). Computer Networking: A Top-Down Approach. Addison-Wesley. ISBN 978-0-321-41849-4.
  4. ^ "Peter Alfke's post at comp.arch.fpga on 19 Jun 1998".

외부 링크

  • Removi