힙 메모리 (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내 바탕 화면은 것에 실질적으로 마이크로 초보다 적은 가지고,하지만 난 아주로드에 훨씬 더 걸릴 수 있습니다 이상한 상황, 아마도 많은 밀리 초를 상상할 수 컴퓨터; 스 래싱 에 대해 읽어보십시오 ). 그리고 내 Linux 데스크톱에는 ASLR (주소 공간 레이아웃 무작위 화)이 있으므로 동일한 프로그램을 두 번 실행 malloc하면 프로세스의 가상 주소 공간에서 다른 -ed 주소가 제공 됩니다. 여기서 BTW 는 결정적이지만 (정교화해야하는 특정 가정하에) 실질적으로 쓸모없는 malloc구현입니다.

결정론은 프로그램을 두 번 실행하면 정확히 동일한 실행 경로로 이어진다는 것을 의미합니다.

이것은 물리적 환경이 변화하고 있기 때문에 대부분의 임베디드 시스템에서 사실상 잘못된 것입니다. 예를 들어, 로켓 엔진을 구동하는 소프트웨어는 추력, 항력, 풍속 등이 한 번의 발사에서 다음 발사까지 정확히 동일 하다고 기대할 수 없습니다 .

^{(따라서 실시간 시스템이 결정적이라고 믿거 나 바라는 것에 놀랐습니다. 결코 그렇지 않습니다! 아마도 캐시 때문에 예측하기가 점점 더 어려워지는 WCET에 관심이있을 것 입니다 )}

BTW 일부 "실시간"또는 "내장형"시스템은 자체 malloc(또는 일부 변형)를 구현합니다 . C ++ 프로그램은 표준 컨테이너 에서 사용할 수있는 할당 자 -s를 가질 수 있습니다 . 참조 이 와 그 등 등 .....

그리고 높은 수준의 임베디드 소프트웨어 계층 (자율 주행 자동차 및 계획 소프트웨어)은 확실히 힙 할당과 가비지 수집 기술 (일부는 "실시간")을 사용하고 있지만 일반적으로 안전에 중요한 것으로 간주되지 않습니다.

---

tl; dr : 동적 메모리 할당이 본질적으로 비 결정적 이라는 것은 아닙니다 (동일한 실행 경로에 대해 정의한대로). 그것은 일반적으로 프로그램을 예측할 수 없게 만듭니다 . 특히, 임의의 입력 시퀀스에 직면하여 할당자가 실패할지 여부를 예측할 수 없습니다.

비 결정적 할당자를 가질 수 있습니다. 이것은 실제로 운영 체제가 주소 레이아웃 무작위 화와 같은 것을 사용하는 실시간 세계 밖에서 일반적입니다. 물론 그것은 당신의 프로그램을 비 결정적으로 만들 것입니다.

그러나 이것은 흥미로운 경우가 아니므로 완벽하게 결정적인 할당자를 가정 해 보겠습니다. 동일한 할당 및 할당 해제 시퀀스는 항상 동일한 위치에서 동일한 블록을 생성하며 이러한 할당 및 할당 해제는 항상 제한된 실행 시간을 갖습니다.

이제 프로그램이 결정적 일 수 있습니다. 동일한 입력 세트가 정확히 동일한 실행 경로로 이어질 것입니다.

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

첫째, 프로그램에서 메모리 누수가 발생할 수 있습니다. 따라서 무기한으로 실행해야하는 경우 결국 할당이 실패합니다.

그러나 누수가 없다는 것을 증명할 수 있더라도 사용 가능한 것보다 더 많은 메모리를 요구할 수있는 입력 시퀀스가 ​​없다는 것을 알아야합니다.

그러나 프로그램이 사용 가능한 것보다 더 많은 메모리를 필요로하지 않는다는 것을 증명할 수 있더라도 할당자는 할당 및 해제 순서에 따라 메모리를 조각화하여 결국 할당을 만족시킬 연속 블록을 찾지 못할 수 있습니다. 전체적으로 충분한 여유 메모리가 있습니다.

병리학 적 단편화로 이어지는 일련의 입력이 없다는 것을 증명하는 것은 매우 어렵습니다.

조각화가 발생하지 않도록 할당자를 설계 할 수 있지만 (예 : 한 크기의 블록 만 할당하여) 호출자에게 상당한 제약을 가하고 낭비로 인해 필요한 메모리 양을 늘릴 수 있습니다. 그리고 호출자는 여전히 누수가 없으며 입력 순서에 관계없이 필요한 총 메모리에 만족할만한 상한선이 있음을 증명해야합니다. 이 부담이 너무 커서 동적 메모리 할당을 사용하지 않도록 시스템을 설계하는 것이 실제로 더 간단합니다.

---

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

---

네, 맞습니다. 언급 한 응용 프로그램의 종류에 따라 발생할 수있는 모든 사항을 자세히 지정해야합니다. 프로그램은 사양에 따라 최악의 시나리오를 처리해야하며 그 이상도 그 이하도 아닌 정확히 그만큼의 메모리를 따로 확보해야합니다. "우리가 얼마나 많은 입력을 받는지 모른다"는 상황은 존재하지 않습니다. 최악의 시나리오는 고정 된 숫자로 지정됩니다.

프로그램은 최악의 시나리오까지 모든 것을 처리 할 수 ​​있다는 점에서 결정적이어야합니다.

힙의 목적은 실행중인 프로그램 / 프로세스 / 스레드의 양이 결정적이지 않은 PC에서와 같이 관련없는 여러 응용 프로그램이 RAM 메모리를 공유 할 수 있도록하는 것입니다. 이 시나리오는 실시간 시스템에 존재하지 않습니다.

또한 시간이 지남에 따라 세그먼트가 추가되거나 제거되므로 힙은 본질적으로 비 결정적입니다.

자세한 정보 : https://electronics.stackexchange.com/a/171581/6102

---

힙 할당 자에 반복 가능한 동작이 있더라도 (동일한 할당 및 사용 가능 호출이 동일한 블록 시퀀스를 생성하므로 (희망적으로) 동일한 내부 힙 상태), 호출 시퀀스가 ​​변경되면 힙 상태가 크게 달라질 수 있습니다. , 잠재적으로 조각화로 인해 예측할 수없는 방식으로 메모리 할당 실패가 발생합니다.

힙 할당이 임베디드 시스템에서 완전히 금지되어 눈살을 찌푸리는 이유, 특히. 항공기 또는 우주선 안내 또는 생명 유지 시스템과 같은 미션 크리티컬 시스템은 본질적으로 비동기 이벤트에 대한 응답으로 발생할 수있는 malloc / free 호출 시퀀스의 가능한 모든 변형을 테스트 할 방법이 없습니다.

해결책은 각 핸들러가 목적을 위해 하나의 메모리를 따로 확보하는 것이며, 이러한 핸들러가 호출되는 순서는 더 이상 중요하지 않습니다 (적어도 메모리 사용에 관한 한).

---

하드 실시간 소프트웨어에서 힙을 사용할 때의 문제점은 힙 할당이 실패 할 수 있다는 것입니다. 힙이 부족하면 무엇을합니까?

우주 응용 프로그램에 대해 이야기하고 있습니다. 당신은 매우 어려운 무 실패 요구 사항이 있습니다. 메모리 누수 가능성이 없어야하므로 최소한 안전 모드 코드를 실행하기에 충분하지 않습니다. 넘어져서는 안됩니다. catch 블록이없는 예외를 throw해서는 안됩니다. 보호 된 메모리가있는 OS가 없기 때문에 충돌하는 애플리케이션 하나가 이론상 모든 것을 제거 할 수 있습니다.

힙을 전혀 사용하고 싶지 않을 것입니다. 혜택은 전체 프로그램 비용을 능가하지 않습니다.

비 결정적은 일반적으로 다른 것을 의미하지만이 경우 최상의 읽기는 전체 프로그램 동작을 완전히 예측할 수 있어야한다는 것입니다.

---

GHS의 Integrity 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 Dynamic memory allocation

is this:

I am not a specialist in formal methods, but perhaps one of the requirements for this verification is to remove the uncertainties in the timing required for memory allocation. In RTOS, all event is precisely planned milliseconds away from each other. And dynamic memory allocation always have a problem with timing required.

Mathematically you really need to prove everything worked from most fundamental assumptions about timing and amount of memory.

And if you think of the alternatives to heap memory: static memory. The address is fixed, the size allocated is fixed. The position in memory is fixed. So it is very easy to reason about memory sufficiency, reliability, availability etc.

---

Short answer

There are some effects on the data values or their statistical uncertainty distributions of, e.g, a first or second level trigger scintillator device that can derive from the non-reproducible quantity of time that you may have to wait for malloc/free.

The worst aspect is that they are not related to the physical phenomenon either with the hardware but somehow with the state of the memory (and its history).

Your goal, in that case, is to reconstruct the original sequence of events from the data affected by those errors. The reconstructed/guessed sequence will be affected by errors too. Not always this iteration will convergence on a stable solution; it is not said it will be the correct one; your data is not any more independent... You risk a logical short-circuit...

Longer answer

You stated "I wasn't able to verify the correctness of this statement when people tell me that".
I will try to give you a purely hypothetical situation/ case study.

Let's we imagine you deal with a CCD or with some 1st and 2nd level scintillator triggers on a system that have to economize resources (you're in space).
The acquisition rate will be set so that the background will be at x% of the MAXBINCOUNT.

• There's a burst, you have a spike in the counts and an overflow in the bin counter.
  I want it all: you switch to the max acquisition rate and you finish your buffer.
  You go to free/allocate more memory meanwhile you finish the extra buffer.
  What will you do?

  1. You will keep the counteractive risking the overflow (the second level will try to count properly the timing of the data-packages) but in this case, you will go to underestimate the counts for that period?
  2. you will stop the counter introducing a hole in the time series?

  Note that:

  • Waiting for allocation you will lose the transient (or at least its beginning).
  • Whatever you do it depends on the state of your memory and it is not reproducible.

• Now instead the signal is variable around the maxbincount at the maximum acquisition rate allowed from your hardware, and the event is longer than usual.
  You finish the space and ask for more... meanwhile, you incur in the same problem above.
  Overflow and systematic peaks counts underestimation or holes in the time series?

Let we move a second level (it can be on the 1st level trigger too).

From your hardware, you receive more data than you can stock or transmit.
You have to cluster the data in time or space (2x2, 4x4, ... 16x16 ... 256x256... pixel scaling...).

The uncertainty from the previous problem may affect the error distribution.
There are CCD setting for which you have the pixels of the border with counts close to the maxbincount (it depends from "where" you want to see better).
Now you can have a shower on your CCD or a single big spot with the same total number of counts but with a different statistical uncertainty (the part that is introduced by the waiting time)...

So for example where you are expecting a Lorentzian profile you can obtain its convolution with a Gaussian one (a Voigt), or if the second it's really dominant with a dirty Gaussian...

---

There is a trade-off always. It's the program's running environment and the tasks it performs that should be the basis to decide whether HEAP should be used or not.

Heap object is efficient when you want to share the data between multiple function calls. You just need to pass the pointer since heap is globally accessible. There are disadvantages as well. Some function might free up this memory but still some references may exist at other places as well.

If the heap memory is not freed after it's work is done and the program keeps on allocating more memory, at some point HEAP will run out of memory and affects the deterministic character of the program.

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