힙 메모리(malloc/new)를 사용하면 비결정론적 프로그램이 생성되는가?

힙 메모리(malloc/new)를 사용하면 비결정론적 프로그램이 생성되는가?

나는 몇 달 전부터 C에서 우주 애플리케이션용 실시간 시스템용 소프트웨어와 C++를 탑재한 마이크로컨트롤러용 소프트웨어를 개발하기 시작했다.이러한 시스템에는 프로그램을 결정적이지 않게 만들기 때문에 힙 오브젝트(그래서 malloc/new가 없음)를 절대 생성해서는 안 되는 경험칙이 있다.나는 사람들이 나에게 그것을 말할 때 이 진술의 정확성을 확인할 수 없었다.그렇다면, 이것은 올바른 진술인가?

나에게 혼란은 내가 아는 한, 결정론은 프로그램을 두 번 실행하면 정확하고 동일한 실행 경로로 이어진다는 것을 의미한다.내가 이해한 바로는 이것은 다중 스레드 시스템의 문제인데, 동일한 프로그램을 여러 번 실행하면 매번 다른 순서로 실행되는 스레드가 있을 수 있기 때문이다.

실시간 시스템의 맥락에서, 반복 가능한 "실행 경로"보다 결정론에 더 많은 것이 있다.또 다른 필수 속성은 주요 이벤트의 타이밍이 제한되어 있다는 것이다.하드 실시간 시스템에서 허용된 시간 간격(이 간격 시작 전 또는 종료 후) 밖에서 발생하는 이벤트는 시스템 장애를 나타낸다.

이러한 맥락에서 동적 메모리 할당을 사용하면 특히 프로그램의 할당, 할당 해제 및 재할당 패턴이 다른 경우 비결정성을 야기할 수 있다.할당, 할당 해제 및 재할당의 타이밍은 시간이 지남에 따라 달라질 수 있으며, 따라서 시스템의 타이밍을 전체적으로 예측할 수 없게 만든다.

언급된 바와 같이 그 논평은 부정확하다.

비결정적 동작이 있는 힙 관리자를 사용하면 비결정적 동작이 있는 프로그램이 생성된다.그러나 그것은 명백하다.

결정론적 행동을 하는 힙 매니저의 존재는 조금 덜 명백하다.아마도 가장 잘 알려진 예는 풀 할당자일 것이다.N*M 바이트의 배열과available[]N비트의 마스크할당하기 위해 첫 번째 사용 가능한 항목(비트 테스트, O(N), 결정론적 상한)을 확인한다.할당을 해제하려면 사용 가능한 비트(O(1))를 설정하십시오. malloc(X)X를 M의 다음으로 큰 값으로 반올림하여 적절한 풀을 선택한다.

특히 N과 M의 선택이 너무 높은 경우 이는 매우 효율적이지 않을 수 있다.그리고 너무 낮게 선택하면 프로그램이 실패할 수 있다.그러나 N과 M의 한계는 동적 메모리 할당 없이 동등한 프로그램에 비해 낮을 수 있다.

C11 표준이나 n1570에 다음과 같은 것은 없다.malloc결정론적(또는 그렇지 않음)이며, Linux의 malloc(3)와 같은 일부 다른 문서도 아니다.BTW, 많은malloc구현은 무료 소프트웨어 입니다.

그렇지만malloc실패할 수 있으며(그리고 실패한다), 그 성능을 알 수 없다(일반적으로 에 대한 호출).malloc내 데스크톱에서는 실제로 1마이크로초도 걸리지 않을 것이지만, 나는 매우 부하가 많은 컴퓨터에서 몇 밀리초 정도 더 걸릴지도 모르는 이상한 상황을 상상할 수 있었다; 스레싱에 대해 읽는다).그리고 내 리눅스 데스크탑에는 ASLR(주소 공간 레이아웃 랜덤화)이 있어서 같은 프로그램을 두 번 실행하면 다른 점이 있음malloc-ed 주소(프로세스의 가상 주소 공간).BTW는 결정론적(자세한 설명이 필요한 구체적인 가정 하에서)이지만 사실상 쓸모없다.malloc실행

결정론은 프로그램을 두 번 실행하면 정확하고 동일한 실행 경로가 된다는 것을 의미한다.

이것은 대부분의 임베디드 시스템에서는 사실상 잘못된 것이다. 예를 들어, 로켓 엔진을 구동하는 소프트웨어는 추력, 드래그, 풍속 등을 기대할 수 없기 때문이다.한 번의 발사에서 다음 발사까지 정확히 똑같다.

^{(그래서 나는 당신이 실시간 시스템이 결정론적이라고 믿거나 원한다는 것에 놀랐다; 그것들은 절대 그렇지 않다!아마도 당신은 캐쉬 때문에 예측하기가 점점 더 어려워지는 WCET에 신경을 쓰고 있을 것이다.)}

BTW 일부 "실시간" 또는 "임베디드" 시스템이 자체 구현 중임malloc(또는 그것의 일부 변형)C++ 프로그램은 표준 컨테이너에서 사용할 수 있는 할당자를 가질 수 있다.이것 저것 등을 참조하라...

그리고 임베디드 소프트웨어의 높은 계층(자율 자동차와 그것의 계획 소프트웨어를 생각함)은 확실히 힙 할당과 어쩌면 쓰레기 수거 기술(일부는 "실시간")을 사용하고 있지만 일반적으로 안전에 중요한 것으로 간주되지는 않는다.

tl;dr: 동적 메모리 할당이 본질적으로 (동일한 실행 경로 측면에서 정의한 대로) 결정적이지 않다는 것은 아니다; 그것은 일반적으로 당신의 프로그램을 예측할 수 없게 만든다.구체적으로 임의의 입력 순서에 직면하여 할당자가 실패할 수 있는지 여부를 예측할 수 없다.

결정적이지 않은 할당자가 있을 수 있다.이는 운영 체제가 주소 레이아웃 랜덤화와 같은 것을 사용하는 실시간 세계 밖에서 실제로 흔하다.물론, 그렇게 되면 당신의 프로그램은 결정적이지 않을 것이다.

그러나 그것은 흥미로운 경우가 아니므로, 완벽하게 결정론적인 할당자를 가정해 봅시다: 동일한 배열과 할당 해제 순서는 항상 동일한 위치에서 동일한 블록을 생성하며 이러한 할당과 할당 해제에는 항상 한정된 실행 시간이 있을 것이다.

이제 당신의 프로그램은 결정론적이 될 수 있다: 동일한 입력 세트가 정확히 동일한 실행 경로로 이어질 것이다.

문제는 입력에 대응하여 메모리를 할당하고 해제하는 경우 할당에 실패할지 여부를 예측할 수 없다는 것이다(실패는 옵션이 아니다).

첫째, 당신의 프로그램은 기억을 잃을 수 있다.따라서 무한정 실행해야 할 경우 결국 할당에 실패하게 된다.

그러나 누수가 없다는 것을 증명할 수 있다 하더라도, 사용 가능한 것보다 더 많은 메모리를 요구할 수 있는 입력 순서는 결코 없다는 것을 알아야 할 것이다.

그러나 프로그램이 사용 가능한 것보다 더 많은 메모리를 결코 필요로 하지 않는다는 것을 증명할 수 있다고 하더라도, 할당자는 할당 순서와 자유도에 따라 메모리를 분할하고 따라서 전체적으로 충분한 여유 메모리가 있음에도 불구하고 할당을 만족시킬 연속적인 블록을 찾을 수 없을 수도 있다.

병리학적 단편화를 초래할 일련의 입력들이 없다는 것을 증명하는 것은 매우 어렵다.

분할이 없을 것이라고 보장하도록 할당자를 설계할 수 있지만(예: 한 가지 크기의 블록만 할당함) 이는 발신자에게 상당한 제약을 주며 폐기물로 인해 필요한 메모리 양을 증가시킬 수 있다.그리고 발신자는 여전히 누수가 없고 입력의 순서와 상관없이 필요한 총 메모리에 만족스러운 상한선이 있다는 것을 증명해야 한다.이 부담은 너무 커서 실제로 동적 메모리 할당을 사용하지 않도록 시스템을 설계하는 것이 더 간단하다.

실시간 시스템과의 거래는 프로그램이 (입력에 따라 여전히 상당히 달라질 수 있는) 실행 경로에 관계 없이 특정 계산 및 메모리 제한을 엄격히 충족해야 한다는 것이다.그렇다면 이러한 맥락에서 일반적인 동적 메모리 할당(예: malloc/new)의 사용은 무엇을 의미할까?이것은 개발자가 어느 시점에서 정확한 메모리 소비량을 결정할 수 없으며, 결과 프로그램이 메모리와 계산 전력에 대한 요구 사항을 충족할 수 있을지는 알 수 없다는 것을 의미한다.

그래, 맞아.당신이 언급하는 어플리케이션의 종류에 대해서는 발생할 수 있는 모든 것을 구체적으로 명시해야 한다.프로그램은 사양에 따라 최악의 상황을 처리하고 더 이상, 더 이상, 더 이상, 더 이상, 더 이상, 더 이상, 더 이상, 더 이상, 더 이상, 더 이상, 더 이상, 더 이상, 더 이상, 더 이상,"입력을 몇 개나 받는지 알 수 없다"는 상황은 존재하지 않는다.최악의 시나리오는 고정 숫자로 지정된다.

당신의 프로그램은 최악의 시나리오까지 모든 것을 다룰 수 있다는 점에서 결정론적이어야 한다.

힙의 목적은 실행 중인 프로그램/프로세스/스레드의 양이 결정론적이지 않은 PC와 같이 RAM 메모리를 공유하기 위한 것이다.이 시나리오는 실시간 시스템에 존재하지 않는다.

또한 시간이 지남에 따라 세그먼트가 추가되거나 제거되기 때문에 힙은 그 성격상 결정적이지 않다.

자세한 내용은 https://electronics.stackexchange.com/a/171581/6102를 참조하십시오.

힙 할당자가 반복 가능한 동작(할당 순서와 무료 통화 순서가 동일한 블록 순서를 생성하므로 (희망적으로) 동일한 내부 힙 상태를 제공함)을 가지고 있더라도, 호출 순서가 변경되면 힙 상태가 급격히 변화하여 잠재적으로 메모리 할당 실패를 야기할 수 있다.예측할 수 없는 방법

항공기나 우주선 유도나 생명 유지 시스템과 같은 임무 핵심적 시스템이나 생명 유지 시스템과 같은 임베디드 시스템에서 완전히 금지된 것에 대해 힙 할당이 눈살을 찌푸리게 하는 이유는 본질적으로 비동기적인 이벤트에 대응하여 발생할 수 있는 만록/프리 통화 순서의 모든 가능한 변동을 시험할 방법이 없기 때문이다.

해결책은 각 처리기가 자신의 목적에 맞게 하나의 메모리를 따로 보관하는 것이다. 그리고 이러한 처리기가 어떤 순서로 호출되는지는 더 이상 중요하지 않다(적어도 메모리 사용에 관한 한).

하드 실시간 소프트웨어에서 힙을 사용할 때의 문제는 힙 할당이 실패할 수 있다는 것이다.더미가 떨어지면 무엇을 하십니까?

너는 우주 응용에 대해 말하고 있다.넌 꽤 어려운 실패 요건이 있어.메모리 누수의 가능성이 없어야 안전모드 코드가 실행될 수 있는 정도는 아니다.넘어져서는 안 된다.캐치 블록이 없는 예외는 던져서는 안 된다.메모리 보호 기능이 있는 OS가 없어서 애플리케이션 하나가 이론적으로 모든 것을 제거할 수 있을 겁니다.

당신은 아마 힙을 전혀 사용하고 싶지 않을 것이다.이익은 전체 프로그램 비용보다 크지 않다.

결정론적이지 않은 것은 보통 다른 것을 의미하지만, 이 경우에 가장 좋은 것은 그들은 전체 프로그램 행동을 완전히 예측할 수 있기를 원한다는 것이다.

GHS의 무결성 RTOS 소개:

https://www.ghs.com/products/rtos/integrity.html

및 LynxOS:

http://www.lynx.com/products/real-time-operating-systems/lynxos-178-rtos-for-do-178b-software-certification/

LynxOS와 Integrity RTOS는 당국이 승인하거나 인증하지 않은 다른 많은 소프트웨어들(예: FAA)이 우주 응용 프로그램, 미사일, 항공기 등에 사용되는 소프트웨어 중 하나이다.

https://www.ghs.com/news/230210r.html

공간 애플리케이션의 엄격한 기준을 충족하기 위해, Integrity RTOS는 실제로 소프트웨어가 규격에 따라 동작한다는 공식 검증, 즉 수학적으로 입증된 논리를 제공한다.

다음 기준 중에서 여기서 인용하십시오.

https://en.wikipedia.org/wiki/Integrity_(operating_system)

다음 항목:

Green Hills Integrity 동적 메모리 할당

다음 사항:

나는 공식적인 방법의 전문가는 아니지만, 아마도 이 검증의 요구사항 중 하나는 메모리 할당에 필요한 타이밍의 불확실성을 제거하는 것이다.RTOS에서 모든 이벤트는 서로로부터 밀리초 떨어진 곳에서 정확하게 계획된다.그리고 동적 메모리 할당은 항상 필요한 타이밍에 문제가 있다.

수학적으로 당신은 모든 것이 기억의 양과 타이밍에 대한 가장 근본적인 가정으로부터 작동했다는 것을 증명할 필요가 있다.

메모리를 더 많이 저장할 수 있는 대안을 생각한다면, 정적 메모리 입니다.주소가 고정되어 있고, 할당된 크기가 고정되어 있다.기억 속의 위치는 고정되어 있다.그래서 메모리 용량, 신뢰성, 가용성 등에 대해 추론하기가 매우 쉽다.

단답

1단계 또는 2단계 트리거 섬광기 장치의 데이터 값 또는 통계적 불확실성 분포에 약간의 영향이 있으며, 예를 들어, 사용자가 기다려야 할 수 있는 비생산적 시간에서 도출할 수 있다.malloc/free.

최악의 측면은 하드웨어와 물리적인 현상과 관련이 있는 것이 아니라 어떻게든 기억의 상태(및 그 역사)와 관련이 있다는 점이다.

그 경우에 당신의 목표는 그러한 오류의 영향을 받는 데이터로부터 사건의 원래 순서를 재구성하는 것이다.재구성/구입 순서도 오류의 영향을 받는다.항상 이 반복이 안정적인 솔루션에 수렴되는 것은 아니며, 올바른 솔루션이 될 것이라고는 말할 수 없으며, 데이터가 더 이상 독립적이지 않다.논리적인 단락을 감수하고...

긴 대답

당신은 "사람들이 나에게 그것을 말해줄 때 나는 이 진술의 정확성을 확인할 수 없었다"고 말했다.
나는 당신에게 순전히 가상적인 상황/사례 연구를 제공하도록 노력할 것이다.

자원을 절약해야 하는 시스템에서 CCD 또는 1, 2차 레벨 섬광기 트리거를 처리한다고 가정해 봅시다(우주 공간).
취득률을 설정해 배경을 정리한다.x%의MAXBINCOUNT.

• 폭발이 있고 카운트에 스파이크가 있고 빈 카운터에 오버플로가 있어
  나는 모든 것을 원한다: 당신은 최대 획득률로 전환하고 당신의 완충제를 끝내는 것이다.
  추가 버퍼를 완료하는 동안 메모리를 더 확보/할당하십시오.
  뭐 하실 건가요?

  1. 오버플로를 감수하고 대응력을 유지할 것이다(두 번째 레벨은 데이터 패키지의 타이밍을 적절하게 계산하려고 할 것이다). 그러나 이 경우, 해당 기간의 카운트를 과소평가하게 되는가?
  2. 너는 시계열의 구멍을 소개하는 카운터를 멈출거니?

  참고:

  • 할당을 기다리면 일시적(또는 최소한 시작)이 손실된다.
  • 당신이 무엇을 하든지 그것은 기억의 상태에 달려 있고 그것은 재현할 수 없다.

• 이제 대신 신호는maxbincount하드웨어에서 허용되는 최대 획득 속도 및 이벤트가 평소보다 길다.
  공간을 마무리하고 더 많은 것을 요구하면...한편, 위와 같은 문제에 처하게 된다.
  오버플로우 및 시스템 피크 카운트 과소평가 또는 시계열의 구멍?

두 번째 레벨로 이동합시다(1레벨 트리거에도 있을 수 있음).

당신의 하드웨어로부터 당신은 당신이 비축하거나 전송할 수 있는 것보다 더 많은 데이터를 받는다.
데이터를 시간 또는 공간으로 클러스터링해야 함(2x2, 4x4, ... 16x16 ... 256x256...픽셀 스케일링...)

이전 문제의 불확실성이 오차 분포에 영향을 미칠 수 있다.
테두리의 픽셀에 가까운 카운트가 있는 CCD 설정이 있음maxbincount("어디서"를 더 잘 보고 싶은지"에 따라 달라진다.)
이제 총 카운트 수는 같지만 통계적 불확실성은 다른 CCD 또는 단일 대형 지점에 샤워를 할 수 있다(대기 시간에 의해 도입되는 부분).

예를 들어 로렌츠 프로파일이 기대되는 곳에서 가우스 프로파일의 콘볼루션을 얻을 수 있다(Voigt) 또는 두 번째가 음습한 가우스 프로파일의 콘볼루션을 실제로 지배한다면...

항상 절충이 있다.프로그램의 실행 환경과 그것이 수행하는 태스크가 HIP의 사용 여부를 결정하는 기반이 되어야 한다.

힙 개체는 여러 함수 호출 간에 데이터를 공유하려는 경우에 효율적이다.힙은 전체적으로 액세스할 수 있으므로 포인터를 통과하면 된다.단점도 있다.어떤 기능은 이 기억을 자유롭게 할 수 있지만, 여전히 몇몇 참조는 다른 장소에도 존재할 수 있다.

작업이 완료된 후 힙 메모리가 해제되지 않고 프로그램이 더 많은 메모리를 계속 할당하는 경우, 어떤 시점에서 힙 메모리가 부족하여 프로그램의 결정론적 특성에 영향을 미치게 된다.

참조URL: https://stackoverflow.com/questions/46298257/does-using-heap-memory-malloc-new-create-a-non-deterministic-program